快速理解哈希（Hash）表的运作原理
哈希表是什么
哈希表（hash table）又叫散列表。
和二叉树、链表这一类一样。它是一种数据结构，设计出来用于存放数据。
需要哪些基础知识
指针和数组
链表
模运算
哈希表的构建方法：
1.创建一个固定大小的数组
2.对需要进行存储的数据应用哈希函数，将数据转换为数组的索引位置
3.将数据存储在该索引位置处
如下：
| 数组 | 指针 | 指针 | 指针 | 指针 | 指针 | |||||
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ... |
关键字：x -> f(x)（哈希函数）->下标
哈希函数是根据关键字设计的，有很多种函数，主要的原理就是根据数组的大小求模运算。
(关键字) % (数组大小)
例如：20048157 % 17 (结果在0-16)
数组的大小一般设计为质数，因为需要均匀的散布。
遇到冲突怎么办
1、链表式解决(Separate Chaining)
写结构体的时候加入next指针(和链表一样)
数据 Next->数据 Next
遇到冲突的时候，把数据写到next的位置.
例如：
| 数据关键字 | 15 22 24 16 |
| 数组大小 | 7 |
| 哈希函数 | 下标 = 关键字 mod 7 |
| 下标 | 数据 | ||
| 0 | |||
| 1 | 15 | -> | 22 |
| 2 | 16 | ||
| 3 | 24 | ||
| 4 | |||
| 5 | |||
| 6 |
产生冲突时，往后面放指针（15->22->...）
2、开放地址(Open Addressing)
不用next指针，把其他下标的位置都对外开放。
开放地址的方法：
a. 线性探测法
如果遇到冲突，就往下一个地址寻找空位。
如果遇到冲突，新位置=原始位置+ i（i是冲突的次数）
例如：
| 数据关键字 | 28 4 12 |
| 数组大小 | 13 |
| 哈希函数 | 下标=关键字 mod 13 |
| 数组 | 12 | 15 | 2 | 28 | 4 | 38 | |||||||
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
（说明：28%13=2，由于下标2占位，往后寻找空位放入即最终找到下标4这个空位；4、12同理）
b. 平方探测法(二次方探测)
如果遇到冲突，就往(原始位置 + i2 )的位置
寻找空位(i 代表冲突的次数)
如果遇到冲突，新位置=原始位置+ i2
例如：
| 数据关键字 | 2 28 19 10 |
| 数组大小 | 13 |
| 哈希函数 | 下标=关键字 mod 13 |
| 数组 | 15 | 2 | 28 | ||||||||||
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
（说明：28%13=2，由于下标2被占用，下标换为2+12；28%13=2，下标换为2+22，...同理 ）
c.双哈希
要设置第二个哈希的函数，例如: hash2(key)=R-(key mod R)
R要取比数组尺寸小的质数。
例如R=7: hash2(关键字)= 7- (关键字% 7 )
也就是说，二次哈希的结果在1-7之间，不会等于0;
如果遇到冲突，新位置=原始位置+ i . hash 2(关键字)
例如：
| 数据关键字 | 15 2 18 28 |
| 数组大小 | 13 |
| 哈希函数 | 下标=关键字 mod 13 |
| 哈希函数2 | 7-(关键字 mod 7) |
如果遇到冲突，新位置=原始位置+i.hash 2（关键字）
| 数组 | 15 | 18 | 2 | 28 | |||||||||
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
哈希表满了怎办?
再次哈希(Rehashing)
当哈希表数据存储量超过70%，那么就自动新建一个新的哈希表
新表的尺寸是旧表的2倍以上，选择-一个质数
把之前的数据再次通过哈希计算搬到新表里
如果往旧表里再插入-一个数据，那么旧表的存储量将会超过70%
旧表:下标=关键字mod 7
新表:下标=关键字mod 17
旧表：
| 6 | 15 | 2 | 24 | 13 | ||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
新表：
| 2 | 24 | 6 | 13 | 15 | ||||||||||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
为什么设计哈希表
因为哈希表查找的性能快，它比搜索叉树的速度还快。
搜索二叉树的查找速度是0(log2 N),而哈希表发挥稳定的话
可以达到0(1)。
哈希表的缺点
表越满，性能越差