1. 概念
哈希表（Hash table），也叫散列表，是根据键（Key）而直接访问节点存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
散列函数，顾名思义，它是一个函数。如果把它定义成 hash(key) ，其中 key 表示元素的键值，则 hash(key) 的值表示经过散列函数计算得到的散列值。
散列函数的特点：
- 确定性：如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。
- 散列碰撞（collision）：散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的，但也可能不同。
- 不可逆性：一个哈希值对应无数个明文，理论上你并不知道哪个是。
- 混淆特性：输入一些数据计算出散列值，然后部分改变输入值，一个具有强混淆特性的散列函数会产生一个完全不同的散列值。
2. 哈希表的实现
有许多方法可以实现哈希表，这里将介绍两种：拉链法（separate chaining）和线性探测法（linear probing）。
拉链法
例：现有整数类型（int）的数组S：7,30,10,9,14,19,15,12,90,94,93,53,70。
此数组的元素的哈希值与元素值相同，即7的哈希值是7；30的哈希值是30。
现创建一个有5个元素的数组A：（红色颜色只是为了与数组S的元素区分开来）
然后按顺序把数组S插入数组A中：
插入元素7：元素7的哈希值为7,7%5=2，因此插入到2号元素中；
插入元素30：元素30的哈希值为30,30%5=0，因此插入到0号元素中；
插入元素10：元素10的哈希值为10,10%5=0，因此插入到0号元素中，但0号元素已经有数值30了，故插到30后面，元素30的指针指向元素10。
以此类推，插入元素9：元素9的哈希值为9,9%5=4，因此插入到4号元素中...
全部元素添加完毕后：
现在，如果我们要查找元素19:
元素19的哈希值为19,19%5=4，因此到4号元素去找；
4号元素的值为9,9！=19，去找9的指针指向的元素14；
14！=19，去找14的指针指向的元素19；
19==19，返回数值，查找完毕。
此过程只经历了3次比较！
从此例子中可以看出思路：
对于一个拥有N项元素的数组S,我们需要建立一个含有M项元素的新数组A。
M的值可以自己来定，但如果M过大，则会出现很多空链，如上述例子中的1号链；
如果M过小，则会出现链太长的情况，如果链太长，则意味着比较次数变多。
一般建议M=N/5。
插入元素：
int j=S[i]的哈希值%5;
然后检查A[j]是否为空，如果空，A[j]=S[i]; 如果不为空，temp=A[j], A[j]=S[i], S[i].next=temp;
删除元素：先找出该元素，然后此元素的上一个元素的指针指向此元素的下一个元素，最后删除此元素。
拉链法有一个缺陷，就是很容易有些链过长，有些链过短，甚至是空链。这样会浪费内存和影响搜索速度。
线性探测法（linear probing）
例：现有整数类型（int）的数组S：7,30,10,9,14,19,15,29,13,27。此数组的元素的哈希值与元素值相同，即7的哈希值是7；30的哈希值是30。
现创建一个含有14个元素的数组A:(上面那排数字是为了方便看哪个元素是第几项元素)
然后按顺序把数组S插入数组A中：
插入元素7：元素7的哈希值为7,7%14=7，因此插入到7号元素中；
插入元素30：元素30的哈希值为30,30%14=2，因此插入到2号元素中；
插入元素10：元素10的哈希值为10,10%14=10，因此插入到10号元素中；
插入元素9：元素9的哈希值为9,9%14=9，因此插入到9号元素中；
插入元素14：元素14的哈希值为14,14%14=0，因此插入到0号元素中；
插入元素19：元素19的哈希值为19,19%14=5，因此插入到5号元素中；
插入元素15：元素15的哈希值为15,15%14=1，因此插入到1号元素中；
插入元素29：元素29的哈希值为29,29%14=1，但1号元素已经有数值15了，然后检查下一个元素（2号元素），但2号元素已经有数值30了，然后检查下一个元素（3号元素）,3号元素为空，插入到3号元素：
插入元素13：元素13的哈希值为13,13%14=13，因此插入到13号元素中：
插入元素27：元素27的哈希值为27,27%14=13，但13号元素已经有数值13了，然后检查下一个元素（0号元素），但0号元素已经有数值14了，如此类推，找到4号元素为空，插入到4号元素：
如果我们要查找元素29，元素29的哈希值为29,29%14=1，检查1号元素，15！=29；然后检查下一个元素（2号元素）,30！=29；然后检查下一个元素（3号元素）,29=29，返回数值，查找完毕。
从此例子中可以看出思路：
对于一个拥有N项元素的数组S,我们需要建立一个含有M项元素的新数组A。
M一定要比N大。如果M过少，则搜索进行的比较次数增加，影响速度；如果过大，则太多空位没利用，造成内存浪费。
一般建议M=2*N。
插入元素i: 先获取i的哈希值%M，根据这个值插入到相应的位置中，如果位置有元素了，则插入到下一个位置，循环进行，直到位置是空的为止。
搜索元素：类似于插入元素，详细见上述例子。
参考文章：
https://mp.weixin.qq.com/s/EJt0wvsVujKy040Juq28Qw
https://www.cnblogs.com/mcomco/p/10255459.html
网友评论