简单易懂数据结构之哈希表

Hash表被称作哈希表，也叫做散列表。哈希表是一种比较特殊的数据结构，它遵循函数映射的思想，以Key: Value的方式存储数据。哈希表最大的特点是可以快速定位到要查找的数据，查询的时间复杂度接近O(1).

哈希表的设计原理

如果我们有一组数据,某位工程师每年的收入情况

2017 -- 1000002018 -- 1300002019 -- 1400002020 -- 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] = 2000003. 查询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] = 2000003. 查询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 ->> 08444 * 444 = 197136 ->> 71取中间两位来作为key值

数字分析法完全通过观察数据规律来确定相应key的方法1125699 1123399 1158299通过观察这组数据，发现开头和结尾都一样，那么可以选择中间三位来确定key值256 233 582还可以将它们再减20056 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的位置，又造成了新的冲突。改良的方法有二次方探测法和随机数探测法

总结

哈希表处理了快速查询的需求，但假如设计不当会造成相当但空间白费，需要根据实际情况进行设计。