学步园

今天根据自己的理解重新整理了一下几个字符串hash函数，使用了模板，使其支持宽字符串，代码如下：

/// @brief BKDR Hash Function<br /> /// @detail 本<span class='wp_keywordlink'><a href="http://www.xuebuyuan.com/category/%E7%AE%97%E6%B3%95" title="算法" target="_blank">算法</a></span>由于在Brian Kernighan与Dennis Ritchie的《The C Programming Language》一书被展示而得名，是一种简单快捷的hash算法，也是Java目前采用的字符串的Hash算法（累乘因子为31）。<br /> template<class T><br /> size_t BKDRHash(const T *str)<br /> {<br /> register size_t hash = 0;<br /> while (size_t ch = (size_t)*str++)<br /> {<br /> hash = hash * 131 + ch; // 也可以乘以31、131、1313、13131、131313..<br /> // 有人说将乘法分解为位运算及加减法可以提高效率，如将上式表达为：hash = hash << 7 + hash << 1 + hash + ch;<br /> // 但其实在Intel平台上，CPU内部对二者的处理效率都是差不多的，<br /> // 我分别进行了100亿次的上述两种运算，发现二者时间差距基本为0（如果是Debug版，分解成位运算后的耗时还要高1/3）；<br /> // 在ARM这类RISC系统上没有测试过，由于ARM内部使用Booth's Algorithm来模拟32位整数乘法运算，它的效率与乘数有关：<br /> // 当乘数8-31位都为1或0时，需要1个时钟周期<br /> // 当乘数16-31位都为1或0时，需要2个时钟周期<br /> // 当乘数24-31位都为1或0时，需要3个时钟周期<br /> // 否则，需要4个时钟周期<br /> // 因此，虽然我没有实际测试，但是我依然认为二者效率上差别不大<br /> }<br /> return hash;<br /> }<br /> /// @brief SDBM Hash Function<br /> /// @detail 本算法是由于在开源项目SDBM（一种简单的数据库引擎）中被应用而得名，它与BKDRHash思想一致，只是种子不同而已。<br /> template<class T><br /> size_t SDBMHash(const T *str)<br /> {<br /> register size_t hash = 0;<br /> while (size_t ch = (size_t)*str++)<br /> {<br /> hash = 65599 * hash + ch;<br /> //hash = (size_t)ch + (hash << 6) + (hash << 16) - hash;<br /> }<br /> return hash;<br /> }<br /> /// @brief RS Hash Function<br /> /// @detail 因Robert Sedgwicks在其《Algorithms in C》一书中展示而得名。<br /> template<class T><br /> size_t RSHash(const T *str)<br /> {<br /> register size_t hash = 0;<br /> size_t magic = 63689;<br /> while (size_t ch = (size_t)*str++)<br /> {<br /> hash = hash * magic + ch;<br /> magic *= 378551;<br /> }<br /> return hash;<br /> }<br /> /// @brief AP Hash Function<br /> /// @detail 由Arash Partow发明的一种hash算法。<br /> template<class T><br /> size_t APHash(const T *str)<br /> {<br /> register size_t hash = 0;<br /> size_t ch;<br /> for (long i = 0; ch = (size_t)*str++; i++)<br /> {<br /> if ((i & 1) == 0)<br /> {<br /> hash ^= ((hash << 7) ^ ch ^ (hash >> 3));<br /> }<br /> else<br /> {<br /> hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));<br /> }<br /> }<br /> return hash;<br /> }<br /> /// @brief JS Hash Function<br /> /// 由Justin Sobel发明的一种hash算法。<br /> template<class T><br /> size_t JSHash(const T *str)<br /> {<br /> if(!*str) // 这是由本人添加，以保证空字符串返回哈希值0<br /> return 0;<br /> register size_t hash = 1315423911;<br /> while (size_t ch = (size_t)*str++)<br /> {<br /> hash ^= ((hash << 5) + ch + (hash >> 2));<br /> }<br /> return hash;<br /> }<br /> /// @brief DEK Function<br /> /// @detail 本算法是由于Donald E. Knuth在《Art Of Computer Programming Volume 3》中展示而得名。<br /> template<class T><br /> size_t DEKHash(const T* str)<br /> {<br /> if(!*str) // 这是由本人添加，以保证空字符串返回哈希值0<br /> return 0;<br /> register size_t hash = 1315423911;<br /> while (size_t ch = (size_t)*str++)<br /> {<br /> hash = ((hash << 5) ^ (hash >> 27)) ^ ch;<br /> }<br /> return hash;<br /> }<br /> /// @brief FNV Hash Function<br /> /// @detail Unix system系统中使用的一种著名hash算法，后来微软也在其hash_map中实现。<br /> template<class T><br /> size_t FNVHash(const T* str)<br /> {<br /> if(!*str) // 这是由本人添加，以保证空字符串返回哈希值0<br /> return 0;<br /> register size_t hash = 2166136261;<br /> while (size_t ch = (size_t)*str++)<br /> {<br /> hash *= 16777619;<br /> hash ^= ch;<br /> }<br /> return hash;<br /> }<br /> /// @brief DJB Hash Function<br /> /// @detail 由Daniel J. Bernstein教授发明的一种hash算法。<br /> template<class T><br /> size_t DJBHash(const T *str)<br /> {<br /> if(!*str) // 这是由本人添加，以保证空字符串返回哈希值0<br /> return 0;<br /> register size_t hash = 5381;<br /> while (size_t ch = (size_t)*str++)<br /> {<br /> hash += (hash << 5) + ch;<br /> }<br /> return hash;<br /> }<br /> /// @brief DJB Hash Function 2<br /> /// @detail 由Daniel J. Bernstein 发明的另一种hash算法。<br /> template<class T><br /> size_t DJB2Hash(const T *str)<br /> {<br /> if(!*str) // 这是由本人添加，以保证空字符串返回哈希值0<br /> return 0;<br /> register size_t hash = 5381;<br /> while (size_t ch = (size_t)*str++)<br /> {<br /> hash = hash * 33 ^ ch;<br /> }<br /> return hash;<br /> }<br /> /// @brief PJW Hash Function<br /> /// @detail 本算法是基于AT&T贝尔实验室的Peter J. Weinberger的论文而发明的一种hash算法。<br /> template<class T><br /> size_t PJWHash(const T *str)<br /> {<br /> static const size_t TotalBits = sizeof(size_t) * 8;<br /> static const size_t ThreeQuarters = (TotalBits * 3) / 4;<br /> static const size_t OneEighth = TotalBits / 8;<br /> static const size_t HighBits = ((size_t)-1) << (TotalBits - OneEighth); </p> <p> register size_t hash = 0;<br /> size_t magic = 0;<br /> while (size_t ch = (size_t)*str++)<br /> {<br /> hash = (hash << OneEighth) + ch;<br /> if ((magic = hash & HighBits) != 0)<br /> {<br /> hash = ((hash ^ (magic >> ThreeQuarters)) & (~HighBits));<br /> }<br /> }<br /> return hash;<br /> }<br /> /// @brief ELF Hash Function<br /> /// @detail 由于在Unix的Extended Library Function被附带而得名的一种hash算法，它其实就是PJW Hash的变形。<br /> template<class T><br /> size_t ELFHash(const T *str)<br /> {<br /> static const size_t TotalBits = sizeof(size_t) * 8;<br /> static const size_t ThreeQuarters = (TotalBits * 3) / 4;<br /> static const size_t OneEighth = TotalBits / 8;<br /> static const size_t HighBits = ((size_t)-1) << (TotalBits - OneEighth);<br /> register size_t hash = 0;<br /> size_t magic = 0;<br /> while (size_t ch = (size_t)*str++)<br /> {<br /> hash = (hash << OneEighth) + ch;<br /> if ((magic = hash & HighBits) != 0)<br /> {<br /> hash ^= (magic >> ThreeQuarters);<br /> hash &= ~magic;<br /> }<br /> }<br /> return hash;<br /> } 

我对这些hash的散列质量及效率作了一个简单测试，测试结果如下：

测试1：对100000个由大小写字母与数字随机的ANSI字符串（无重复，每个字符串最大长度不超过64字符）进行散列：

测试2：对100000个由任意UNICODE组成随机字符串（无重复，每个字符串最大长度不超过64字符）进行散列：

测试3：对1000000个随机ANSI字符串（无重复，每个字符串最大长度不超过64字符）进行散列：

结论：也许是我的样本存在一些特殊性，在对ASCII码字符串进行散列时，PJW与ELF Hash（它们其实是同一种算法）无论是质量还是效率，都相当糟糕；例如："b5"与“aE"，这两个字符串按照PJW散列出来的hash值就是一样的。另外，其它几种依靠异或来散列的哈希函数，如：JS/DEK/DJB Hash，在对字母与数字组成的字符串的散列效果也不怎么好。相对而言，还是BKDR与SDBM这类简单的Hash效率与效果更好。

其他：

作者：icefireelf

出处：http://blog.csdn.net/icefireelf/article/details/5796529