Hash表被称作哈希表，也叫做散列表。哈希表是一种比较特殊的数据结构，它遵循函数映射的思想，以Key: Value的方式存储数据。哈希表最大的特点是可以快速定位到要查找的数据，查询的时间复杂度接近O(1).
哈希表的设计原理
假如我们有一组数据,某位工程师每年的收入情况
2017 -- 100000
2018 -- 130000
2019 -- 140000
2020 -- 200000
如果我们用普通的链表来存储这些数据，当我们查询2019年的收入情况时，需要从链表的初始节点开始对整张链表进行遍历，直到找到2019，然后取出对应的数据。这种查找的时间复制度是O(n)，即使当我们顺序存储使用二分查找时，时间复杂度也是O(logn)。如果我们可以知道年份，也就是key值，可以直接取出对应的收入数据，时间复杂度就是O(1)，而如果将数据存储在哈希表中，我们就可以实现这种查找。
哈希表的原理并不复杂，简而言之就是根据Key来计算出存储位置，然后将数据放入该空间，查询时同样根据Key计算出存储位置后直接将相应的值取出。
哈希函数
根据Key来计算存储位置的计算规则我们称之为哈希函数，还是用这个例子，我们取一个最简单的哈希函数H(x) = x。
1. 新建一个长度为2020的数组array[]
2. 根据H(x) = x 计算存储位置，将数据放入数组中。
array[2017] = 100000
array[2018] = 130000
array[2019] = 140000
array[2020] = 200000
3. 查询2019年收入情况时，通过H(x) = x 计算出存储位置，直接取出数据array[2019]
在上面的这个例子中，虽然我们实现了一个简单的哈希表，但是可以很明显的看出，其中有大量的空间被浪费，长度为2020的数组我们只用到了4个空间，下面我们对这个哈希表进行改良。
通过观察需要存储的数据，我们选择一个新的哈希函数H(x) = x - 2000
1. 新建一个长度为20的数组array[]
2. 根据H(x) = x - 2000 计算存储位置，将数据放入数组中。
array[2017 - 2000] = array[17] = 100000
array[2018 - 2000] = array[18] = 130000
array[2019 - 2000] = array[19] = 140000
array[2020 - 2000] = array[20] = 200000
3. 查询2019年收入情况时，通过H(x) = x - 2000 计算出存储位置，直接取出数据array[19]
在这个例子中，可以看到空间的浪费比优化前大幅减小。从中可以看出，根据数据特点选定合适的表大小和哈希函数是哈希表这种数据结构实现的关键。
下面介绍几种通用的哈希函数
除留取余法
这种方法应该是最常用的哈希定址方法了。
H(x) = x % p
假定哈希表长度为s,则p一般取不超过s的最大质数
直接定址法
比较常用的方法
H(x) = a * x + b
一开始的例子就是该方法 a=1,b=0 以及a=1,b=-2000
折叠法
假设有数据 18560 55632，要求key值为两位数，可以计算地址为
18 + 56 + 0 = 74
55 + 63 + 2 = 120 -->> 20(去掉最高位)
折叠法有多种实现方法，此处仅提供一种参考，具体的还要根据实际问题选择
平方取中法
计算数据的平方，然后从平方数中选出中间几位来作为存储的地址。
333 * 333 = 110889 ->> 08
444 * 444 = 197136 ->> 71
取中间两位来作为key值
数字分析法
完全通过观察数据规律来确定相应key的方法
1125699 1123399 1158299
通过观察这组数据，发现开头和结尾都一样，那么可以选择中间三位来确定key值
256 233 582
还可以将它们再减200
56 33 382
冲突
哈希表还要解决的一个问题就是冲突，当选择了一个哈希函数之后，有可能不同的数据会计算出相同的key,比如H(x) = x % 5 这种算法，6 和 11 都会计算出1,此时就会产生冲突。如果不解决冲突，哈希表就无法构建出来。解决冲突的办法有以下几种：
链接地址法
将有冲突的数据放在一个链表里，当查询时会根据key查到链表的第一个节点，然后遍历整个链表，找到相应的值。
开放定址法
最具代表性的一种是线性探测法
H(x) = x % 5
数据样本: {5, 6, 8, 12, 11}
计算Key: { 0, 1, 3, 2, 1}
存储数组 [0, 1, 2, 3, 4, 5, 6, 7 .....]
[5, 6, 12, 8, 11] 当存储11的时候，发现下标是1的位置以及被占据了，此时根据线性探测法的规则依次往后遍历，直到找到空的位置，所以在下标为4的位置填入11
线性探测法最大的问题是冲突累计，解决一个冲突的同时会占据别的key的位置，又造成了新的冲突。
改良的方法有二次方探测法和随机数探测法
总结
哈希表解决了快速查询的需求，但如果设计不当会造成相当但空间浪费，需要根据实际情况进行设计。
网友评论