2022年2022年经典哈希算法new .pdf

《2022年2022年经典哈希算法new .pdf》由会员分享，可在线阅读，更多相关《2022年2022年经典哈希算法new .pdf（5页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、被逼的，发个技术文章吧(几种经典的hash 算法 ) 注：最近因为在做和hash 有关的题目，感到很纠结。虽然上学期数据结构学过，但是当时觉得 hash 没什么用，所以没有认真学后悔啊现在恶补一下计算理论中，没有Hash函数的说法，只有单向函数的说法。所谓的单向函数，是一个复杂的定义，大家可以去看计算理论或者密码学方面的数据。用“人类” 的语言描述单向函数就是：如果某个函数在给定输入的时候，很容易计算出其结果来；而当给定结果的时候，很难计算出输入来，这就是单项函数。各种加密函数都可以被认为是单向函数的逼近。Hash 函数（或者成为散列函数）也可以看成是单向函数的一个逼近。即它接近于满足单向函数

2、的定义。Hash函数还有另外的含义。实际中的Hash 函数是指把一个大范围映射到一个小范围。把大范围映射到一个小范围的目的往往是为了节省空间，使得数据容易保存。除此以外，Hash函数往往应用于查找上。所以，在考虑使用Hash 函数之前，需要明白它的几个限制：1. Hash 的主要原理就是把大范围映射到小范围；所以，你输入的实际值的个数必须和小范围相当或者比它更小。不然冲突就会很多。2. 由于 Hash 逼近单向函数；所以，你可以用它来对数据进行加密。3. 不同的应用对Hash 函数有着不同的要求；比如，用于加密的Hash 函数主要考虑它和单项函数的差距，而用于查找的Hash 函数主要考虑它映射

3、到小范围的冲突率。应用于加密的Hash 函数已经探讨过太多了，在作者的博客里面有更详细的介绍。所以，本文只探讨用于查找的Hash 函数。Hash 函数应用的主要对象是数组（比如，字符串），而其目标一般是一个int 类型。以下我们都按照这种方式来说明。一般的说， Hash 函数可以简单的划分为如下几类：1. 加法 Hash；2. 位运算 Hash；3. 乘法 Hash；4. 除法 Hash；5. 查表 Hash；6. 混合 Hash；下面详细的介绍以上各种方式在实际中的运用。一加法 Hash 所谓的加法Hash 就是把输入元素一个一个的加起来构成最后的结果。标准的加法Hash的构造如下：stat

4、icintadditiveHash(String key, int prime) int hash, i; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - for (hash = key.length(), i = 0; ikey.length(); i+) hash += key.charAt(i); return (hash % prime); 这里的 prime 是任意的质数，看得出，结果的值域为0,prime-1 。二位

5、运算 Hash 这类型 Hash 函数通过利用各种位运算（常见的是移位和异或）来充分的混合输入元素。比如，标准的旋转Hash的构造如下：staticintrotatingHash(String key, int prime) int hash, i; for (hash=key.length(), i=0; ikey.length(); +i) hash = (hash28)key.charAt(i); return (hash % prime); 先移位，然后再进行各种位运算是这种类型Hash 函数的主要特点。比如，以上的那段计算hash 的代码还可以有如下几种变形：1. hash = (h

6、ash27)key.charAt(i); 2. hash += key.charAt(i); hash += (hash 6); 3. if(i&1) = 0) hash = (hash3); else hash = (hash5); 4. hash += (hash5) + key.charAt(i); 5. hash = key.charAt(i) + (hash16) hash; 6. hash = (hash2); 三乘法 Hash 这种类型的Hash 函数利用了乘法的不相关性（乘法的这种性质，最有名的莫过于平方取头尾的随机数生成算法，虽然这种算法效果并不好）。比如，staticint

7、bernstein(String key) int hash = 0; inti; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - for (i=0; i M_SHIFT) & M_MASK; 以及改进的FNV 算法：public static int FNVHash1(String data) finalint p = 16777619; int hash = (int)2166136261L; for(inti=0;idat

8、a.length();i+) hash = (hash data.charAt(i) * p; hash += hash 7; hash += hash 17; hash += hash 5; return hash; 除了乘以一个固定的数，常见的还有乘以一个不断改变的数，比如：staticintRSHash(String str) int b = 378551; int a = 63689; int hash = 0; for(inti = 0; i10) (hash20)。五查表 Hash 查表 Hash 最有名的例子莫过于CRC系列算法。虽然CRC系列算法本身并不是查表，但是，查表是它的

9、一种最快的实现方式。查表Hash 中有名的例子有：Universal Hashing 和 Zobrist Hashing。他们的表格都是随机生成的。六混合 Hash 混合 Hash算法利用了以上各种方式。各种常见的Hash算法，比如MD5、Tiger 都属于这个范围。它们一般很少在面向查找的Hash函数里面使用。七对 Hash算法的评价http:/ 这个页面提供了对几种流行Hash 算法的评价。我们对Hash 函数的建议如下：1. 字符串的Hash。最简单可以使用基本的乘法Hash，当乘数为33 时，对于英文单词有很好的散列效果（小于6 个的小写形式可以保证没有冲突）。复杂一点可以使用FNV算

10、法（及其改进形式） ，它对于比较长的字符串，在速度和效果上都不错。2. 长数组的Hash。可以使用http:/ 算法叫做： rolling hash ，因为它必须可以滚动的计算）。设计一个真正好的Hash算法并不是一件容易的事情。做为应用来说，选择一个适合的算法是最重要的。九数组 hash inlineinthashcode(constint *v) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - int s = 0; for(inti=0; ik; i+) s=(s4)(vi10); s = s % M; s = s 0 ? s + M : s; return s; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -