2022年研究哈希函数 .pdf
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《2022年研究哈希函数 .pdf》由会员分享,可在线阅读,更多相关《2022年研究哈希函数 .pdf(9页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、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 算法经常使用,不论是聚合分类也好,还是m
2、c 代码研究,或是CAS 实现中,hash 算法都起到了至关重要的作用。如果已经把hash从计算科学上转移到纯粹的数学问题来看待,那么D.E.Knuth 的 TAOCP 第三卷,就是必读教材了.同时,在 Bob Jenkins 的网页上能看到很多hash相关的东西.用数学的言论来理解hash 算法,实际就是为一个集合A 里面的元素,找到一个function f(A),让其全部映射到另一个集合B 中去.而对于从B 逆向回溯到A 是基本不可能的事情,那么该f 便是一种hash 算法.按照这种理解,将会存在如下 两种情况:如果 A 元素个数大于B 元素个数,那么由抽屉原理,必定存在两个或两个以上的A
3、 中元素映射到了B 中同一元素,这时,一个冲突便产生了.那么也就是说,一种将大范围的数据hash 到一个小范围数据的hash 算法,是无法保证其安全性能的.这时,应用的时候无非取决两个方面:o其一,应用于安全加密领域,那么取决于是否有可能取到大范围中超过或接近小范围个数的值,如果不能,算法是否能近似保证近难以产生冲突,这时hash 存在是有意义的.o其二,不需要很高的安全性能,只是应用于查找和检索,恰当选择 primer,将 O(logA)的复杂度,降低至O(A/primer)的复杂度,也是可取的.这时,hash 的另一个特征便出现了,如果对于A 中的元素,均匀的映射到了B 上,那么,在这种情
4、况下,该hash 算法是优秀的.第二,如果A 元素个数小于B 元素个数,这种hash 是没有意义的,原因很简单,将 A 映射到B 的目的就是减少处理A 的复杂度的.综上,hash 应用于两类情况,区分好两类情况能更加有效的设计hash 算法,同时设 计 hash 算法还要考虑到算法的计算复杂度,也即计算机处理时长.应用于安全领域的要考虑产生冲突的概率,是否逼近单向函数;应用于查找领域的需要考虑 hash是 否均匀分布.也即 R.W.Floyed 给出的散列思想:一个好的hash算法的计算应该是非常快的一个好的hash算法应该是冲突极小化如果存在冲突,应该是冲突均匀化其中第一点和机器相关,第二和
5、第三点和数据相关.名师资料总结-精品资料欢迎下载-名师精心整理-第 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 这类型
6、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的代码还可以有如下几种变形:/*v
7、1*/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 berns
8、tein(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;除了乘以一个固定的数,常见的还有乘以一个不断改变的数,比如:sta
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年研究哈希函数 2022 研究 函数
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内