[转载]Hash

矫情吗；* 2021-11-17 15:08 281阅读 0赞

**【什么是Hash】**

Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不 同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的[消息摘要][Link 1]的函数。

HASH主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做HASH值. 也可以说，hash就是找到一种数据内容和数据存放地址之间的映射关系。

数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。那么我们能不能综合两者的特性，做出一种寻址容易，插入删除 也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表，哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法——拉链法，我们可以理解为 “链表的数组”，如图：

[![2012082318232034.png][]][2012082318232034.png 1]

左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。

元素特征转变为数组下标的方法就是散列法。散列法当然不止一种，下面列出三种比较常用的。

**1，除法散列法**  
最直观的一种，上图使用的就是这种散列法，公式：  
index = value % 16  
学过汇编的都知道，求模数其实是通过一个除法运算得到的，所以叫“除法散列法”。

**2，平方散列法**  
求index是非常频繁的操作，而乘法的运算要比除法来得省时（对现在的CPU来说，估计我们感觉不出来），所以我们考虑把除法换成乘法和一个位移操作。公式：  
index = (value \* value) >> 28  
如 果数值分配比较均匀的话这种方法能得到不错的结果，但我上面画的那个图的各个元素的值算出来的index都是0——非常失败。也许你还有个问 题，value如果很大，value \* value不会溢出吗？答案是会的，但我们这个乘法不关心溢出，因为我们根本不是为了获取相乘结果，而是为了获取index。

**3，斐波那契（Fibonacci）散列法**

平方散列法的缺点是显而易见的，所以我们能不能找出一个理想的乘数，而不是拿value本身当作乘数呢？答案是肯定的。

1，对于16位整数而言，这个乘数是40503  
2，对于32位整数而言，这个乘数是2654435769  
3，对于64位整数而言，这个乘数是11400714819323198485

这几个“理想乘数”是如何得出来的呢？这跟一个法则有关，叫黄金分割法则，而描述黄金分割法则的最经典表达式无疑就是著名的斐波那契数列，如果你还 有兴趣，就到网上查找一下“斐波那契数列”等关键字，我数学水平有限，不知道怎么描述清楚为什么，另外斐波那契数列的值居然和太阳系八大行星的轨道半径的 比例出奇吻合，很神奇，对么？

对我们常见的32位整数而言，公式：  
i ndex = (value \* 2654435769) >> 28

如果用这种斐波那契散列法的话，那我上面的图就变成这样了：

[![2012082318235294.png][]][2012082318232034.png 1]

很明显，用斐波那契散列法调整之后要比原来的取摸散列法好很多。

**【适用范围】**

快速查找，删除的基本数据结构，通常需要总数据量可以放入内存。

**【基本原理及要点】**  
hash函数选择，针对字符串，整数，排列，具体相应的hash方法。  
碰撞处理，一种是open hashing，也称为拉链法；另一种就是closed hashing，也称开地址法，opened addressing。

**【扩展】**  
d-left hashing中的d是多个的意思，我们先简化这个问题，看一看2-left hashing。2-left hashing指的是将一个哈希表分成长度相等的两半，分别叫做T1和T2，给T1和T2分别配备一个哈希函数，h1和h2。在存储一个新的key时，同 时用两个哈希函数进行计算，得出两个地址h1\[key\]和h2\[key\]。这时需要检查T1中的h1\[key\]位置和T2中的h2\[key\]位置，哪一个 位置已经存储的（有碰撞的）key比较多，然后将新key存储在负载少的位置。如果两边一样多，比如两个位置都为空或者都存储了一个key，就把新key 存储在左边的T1子表中，2-left也由此而来。在查找一个key时，必须进行两次hash，同时查找两个位置。

**【问题实例】**  
1).海量日志数据，提取出某日访问百度次数最多的那个IP。

查看答案：[http://diducoder.com/mass-data-topic-3-hash.html][2012082318232034.png 1]

转载于:https://www.cnblogs.com/studynote/articles/4920688.html

[Link 1]: http://baike.baidu.com/view/2396437.htm
[2012082318232034.png]: /images/20211116/3f3d1b4762f040c38ec7327cb84168bb.png
[2012082318232034.png 1]: http://diducoder.com/mass-data-topic-3-hash.html
[2012082318235294.png]: /images/20211116/d1e9dd7ca43041f59fe36e7be9429c1d.png