2022年研究哈希函数 .pdf

Few people think more than two or three times a year.Ive made an international reputation for myself by thinking once or twice a week.If we knew what it was we were doing,it would not be called research,would it?Website sections HomeArticlesProjectsBlogGuoxueAbout me研究哈希函数简介hash 算法经常使用,不论是聚合分类也好,还是mc 代码研究,或是CAS 实现中,hash 算法都起到了至关重要的作用。如果已经把hash从计算科学上转移到纯粹的数学问题来看待,那么D.E.Knuth 的 TAOCP 第三卷,就是必读教材了.同时,在 Bob Jenkins 的网页上能看到很多hash相关的东西.用数学的言论来理解hash 算法,实际就是为一个集合A 里面的元素,找到一个function f(A),让其全部映射到另一个集合B 中去.而对于从B 逆向回溯到A 是基本不可能的事情,那么该f 便是一种hash 算法.按照这种理解,将会存在如下 两种情况:如果 A 元素个数大于B 元素个数,那么由抽屉原理,必定存在两个或两个以上的A 中元素映射到了B 中同一元素,这时,一个冲突便产生了.那么也就是说,一种将大范围的数据hash 到一个小范围数据的hash 算法,是无法保证其安全性能的.这时,应用的时候无非取决两个方面:o其一，应用于安全加密领域,那么取决于是否有可能取到大范围中超过或接近小范围个数的值,如果不能,算法是否能近似保证近难以产生冲突,这时hash 存在是有意义的.o其二,不需要很高的安全性能,只是应用于查找和检索,恰当选择 primer,将 O(logA)的复杂度,降低至O(A/primer)的复杂度,也是可取的.这时,hash 的另一个特征便出现了,如果对于A 中的元素,均匀的映射到了B 上,那么,在这种情况下,该hash 算法是优秀的.第二，如果A 元素个数小于B 元素个数,这种hash 是没有意义的,原因很简单,将 A 映射到B 的目的就是减少处理A 的复杂度的.综上,hash 应用于两类情况,区分好两类情况能更加有效的设计hash 算法,同时设 计 hash 算法还要考虑到算法的计算复杂度,也即计算机处理时长.应用于安全领域的要考虑产生冲突的概率,是否逼近单向函数;应用于查找领域的需要考虑 hash是 否均匀分布.也即 R.W.Floyed 给出的散列思想:一个好的hash算法的计算应该是非常快的一个好的hash算法应该是冲突极小化如果存在冲突,应该是冲突均匀化其中第一点和机器相关,第二和第三点和数据相关.名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 9 页 -哈希函数的几种常见设计方法hash算法的实现,目前主流设计可以从下面几种方面考虑:加法 hash 位运算 hash 乘法 hash 除法 hash 查表 hash 混合 hash 加法 hash 所谓的加法Hash就是把输入元素一个一个的加起来构成最后的结果。标准的加法 Hash 的构造如下：static int additiveHash(String key,int prime)int hash,i;for(hash=key.length(),i=0;i 10)(hash20)位运算 hash 这类型 Hash函数通过利用各种位运算（常见的是移位和异或）来充分的混合输入元素。比如，标准的旋转Hash 的构造如下：static int rotatingHash(String key,int prime)int hash,i;for(hash=key.length(),i=0;ikey.length();+i)hash=(hash28)key.charAt(i);return(hash%prime);名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 9 页 -先移位，然后再进行各种位运算是这种类型Hash 函数的主要特点。比如，以上的那段计算hash的代码还可以有如下几种变形：/*v1*/hash=(hash27)key.charAt(i);/*v2*/hash+=key.charAt(i);hash+=(hash 6);/*v3*/if(i&1)=0)hash=(hash3);else hash=(hash5);/*v4*/hash+=(hash5)+key.charAt(i);/*v5*/hash=key.charAt(i)+(hash16)hash;/*v6*/hash=(hash2);乘法 hash 这种类型的Hash函数利用了乘法的不相关性（乘法的这种性质，最有名的莫过于平方取头尾的随机数生成算法，虽然这种算法效果并不好）。比如，static int bernstein(String key)int hash=0;int i;for(i=0;i M_SHIFT)&M_MASK;以及改进的FNV 算法：public static int FNVHash1(String data)final int p=16777619;int hash=(int)2166136261L;for(int i=0;idata.length();i+)hash=(hash data.charAt(i)*p;hash+=hash 7;hash+=hash 17;hash+=hash 5;return hash;除了乘以一个固定的数，常见的还有乘以一个不断改变的数，比如：static int RSHash(String str)int b=378551;int a=63689;int hash=0;for(int i=0;i str.length();i+)名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 9 页 -hash=hash*a+str.charAt(i);a=a*b;return(hash&0 x7FFFFFFF);除法 hash 除法和乘法一样，同样具有表面上看起来的不相关性。不过，因为除法太慢，这种方式几乎找不到真正的应用。查表 hash 查表 Hash 最有名的例子莫过于CRC 系列算法。虽然CRC 系列算法本身并不是查表，但是，查表是它的一种最快的实现方式。static int crctab256=.;int crc32(String key,int hash)int i;for(hash=key.length(),i=0;i 8)crctab(hash&0 xff)k.charAt(i);return hash;查表 Hash 中有名的例子有：Universal Hashing 和 Zobrist Hashing。他们的表格都是随机生成的。混合 hash 混合 Hash 算法利用了以上各种方式。各种常见的Hash 算法，比如 MD5、Tiger都属于这个范围。它们一般很少在面向查找的Hash 函数里面使用。对哈希算法的评价字符串的Hash。最简单可以使用基本的乘法Hash，当乘数为 33时，对于英文单词有很好的散列效果（小于6个的小写形式可以保证没有冲突）。复杂一点可以使用FNV 算法（及其改进形式），它对于比较长的字符串，在速度和效果上都不错。长数组的Hash。可以使用http:/ 5 页，共 9 页 -一个字符串哈希函数的设计及其优化该哈希函数的设计来源一个项目，要做一个类似ispell 的软件，其中会产生大量的对单词的查找操作。下面各个小节介绍了哈希函数的设计过程，从最初的一个很简单但效果很差的哈希函数，经过不断优化，最后得到一个很强的哈希函数简单求和unsigned int hash_func(char*str,int len)register unsigned int sum=0;register char*p=str;while(p-str len)sum+=*(p+);return sum%MAX_PRIME_LESS_THAN_HASH_LEN;MAX_PRIME_LESS_THAN_HASH_LEN 是比 hash 表长度小的最大的质数，比如说 hash 表是 n 的话，MAX_PRIME_LESS_THAN_HASH_LEN就是不大于 n 的最大的质数，这个数可以通过首先建立一张质数表，然后通过查表查出来。非常简单，但是这是绝对不可取。首先想到可能产生的冲突的是这种情况：abcd和 acbd，对于这两种单词来说，如果用上面的HASH 函数，就一定会发生碰撞，因为每个字符少了关于它自己的位置信息，于是第一次改进版本的HASH函数就给每个字符加上了它的位置信息增加位置信息unsigned int hash_func(char*str,int len)register unsigned int sum=0;register char*p=str;while(p-str len)sum+=*(p+)*(p str);return sum%MAX_PRIME_LESS_THAN_HASH_LEN;经测试比不带位置信息的哈希函数好多了，但是仍然非常的不均匀，因为是用名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 9 页 -的乘法，所以仍然太过于依赖字母产生的结果了。于是改用XOR 操作XOR 操作unsigned int hash_func(char*str,int len)register unsigned int sum=0;register char*p=str;while(p-str len)sum+=(*(p+)*(p str)sum;return sum%MAX_PRIME_LESS_THAN_HASH_LEN;经测验，比上两个哈希函数好多了，但是结果仍然非常不好，原因还是因为数据分布得不够均匀，于是思考单独的用加法来算是不是不太好，根据其他查表类 HASH 算法的过程，发现其大多都用了高低位来组合成最后的结果高低位组合 register unsigned int sum=0;register unsigned int h=0;register char*p=str;while(p-s len)register unsigned short a=*(p+);sum=a*(p-str);h=a/(p-str);return(sum 16)|h)%MAX_PRIME_LESS_THAN_HASH_LEN;不用查表的方法，而通过字符串本身的位置对字符本身进行修正的方法也能得到结果相当满意的HASH 函数。一个点评：从一个大的集合向一个较小的集合映射，碰撞是无可避免的。实际上无论你如何 改进 hash 算法，只要是把任意长字符串hash 为一个有限范围内的整数，总能够构造出输入让你的hash 表操作时空性能严重恶化。hash函数还是要根据特定的需要和输入的预期来构造。如果对输入字符串没有特别的预期，还是不要花费太多时间来改进 hash 算法，有可能得不偿失。名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 9 页 -常用 hash 算法与大质数相乘方法：与一个大质数相乘然后取中间几位(如8位)。该方法多用在以数值为hash 的场合。下面是Linux 中的hash_long 算法,该算法就采用了与大质数相乘去某些位的 方法。static inline unsigned long hash_long(unsigned long val,unsigned int bits)unsigned long hash=val;#if BITS_PER_LONG=64/*Sigh,gcc cant optimise this alone like it does for 32 bits.*/unsigned long n=hash;n=18;hash-=n;n=33;hash-=n;n=3;hash+=n;n=3;hash-=n;n=4;hash+=n;n (BITS_PER_LONG-bits);代码中定义的GOLDEN_RA TIO_PRIME 是大质数0 9e370001，这个数字实际上是最接近 232的黄金分割的质数，Knuth 推荐使用这个数做为乘数来生成哈希数，这 样可以获较好的结果。Chuck Lever 随后证明了这个技术的有效性。See Also 名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 9 页 -简单哈希算法的探讨hash 函数the hash若干经典的哈希字符串函数基于英文单词的快速HASH 索引算法hash functionCopyright?2008 Peng LIU名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 9 页 -