数据结构-hash表

什么是哈希表

哈希表（散列表）是根据关键码值(Key value)而直接进行访问的数据结构。

也就是说，它通过把关键码值映射到表中一个位置来访问记录， 以加快查找的速度。这个映射函数叫做哈希函数，存放记录的数组叫做哈希表。

给定表M，存在函数f(key)，对任意给定的关键字值key，
代入函数后，
若能得到包含该关键字的记录在表中的下标地址，
则称表M为哈希(Hash）表，
函数f(key)为哈希(Hash) 函数。

根据给定的关键字key，运用hash算法得到下标，但是根据算法得到的数据可能会发生下标重复。需要处理hash碰撞冲突，主要有拉链法和线性探测法

优势

上面一堆废话，那hash为啥要这么搞呢（好处是啥）？

举个例子，假如我们现在要插入3个元素:12,15,22

假定数组默认大小是4(size)

给定一个hash算法【算法很多，这里给出一个简单的】h(key) = key%size

index = h(12) = 12%4 = 0

index = h(15) = 15%4 = 3

index = h(22) = 22%4 = 2

index则为元素插入后在数组中的下标

当要查询元素11是否存在的时候怎么查？

for循环遍历查询，如果数组容量很大的时候，根本行不通 如果套入同样的hash算法，是不是很快能得出一个下标，是不是马上可以精准的定位到元素应该被存在的位置

以下内容转载自哈希表原理详解【样式复制问题，个人博客中有原文地址】

还有哪些类似的取下标的算法

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

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

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

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

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

这几个“理想乘数”是如何得出来的呢？这跟一个法则有关，叫黄金分割法则，而描述黄金分割法则的最经典表达式无疑就是著名的斐波那契数列，即如此形式的序列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377, 610， 987, 1597, 2584, 4181, 6765, 10946，…。另外，斐波那契数列的值和太阳系八大行星的轨道半径的比例出奇吻合。

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

注：用斐波那契散列法调整之后会比原来的取模散列法好很多。

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

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

散列冲突的解决方案

1.建立一个缓冲区，把凡是拼音重复的人放到缓冲区中。当我通过名字查找人时，发现找的不对，就在缓冲区里找。

2.进行再探测。就是在其他地方查找。探测的方法也可以有很多种。

（1）在找到查找位置的index的index-1，index+1位置查找，index-2，index+2查找，依次类推。这种方法称为线性再探测。

（2）在查找位置index周围随机的查找。称为随机在探测。

（3）再哈希。就是当冲突时，采用另外一种映射方式来查找。