浅谈哈希表

1.哈希表的定义

哈希表是一种根据哈希键去寻找哈希值的数据映射结构。通过该结构找到哈希键映射的位置，再根据映射的位置去寻找存放哈希值的地方。

最典型的例子就是字典，假设我们根据拼音索引来查找“阿”这个字的详细信息。我们肯定会去根据它的拼音“a”去查找拼音索引。结果如下：

这个过程就是键值映射。我们先看一下哈希函数的公式：

哈希值=哈希函数（哈希键）

字典的例子中，“阿-a”是哈希键，拼音索引就是哈希函数，页码就是哈希值。

2.哈希冲突

但是问题来了，如果我们要查“啊-a”或者“阿-a”两个不同的哈希键，却得到了一样的哈希值1。这就是哈希冲突。

在公式上表达就是key1≠key2，但f(key1)=f(key2)。冲突会给查找带来麻烦，你想想，你本来查找的是“阿”，但是却找到“啊”字，你又得向后翻一两页，在计算机里面也是一样道理的。

如果你要完全避开这种情况，只能每个发音都在不同的页上，然后每个字在索引里面都有对应的页码，这就可以避免冲突。但是会导致空间增大。所以一般我们认为哈希冲突是正常现象。

3.哈希冲突解决办法

如果遇到冲突，哈希表一般是怎么解决的呢？

最常用的就是开发定址法和链地址法。

我们主要讨论地址法，我感觉业界上用的最多的就是链地址法。

链地址法的原理是如果遇到冲突，就会在原地址新建一个空间，然后以链表结点的形式插入到该空间。

下面从百度上截取来一张图片，可以很清晰明了反应下面的结构。比如说我有一堆数据{1,12,26,337,353...}，而我的哈希算法是H(key)=key mod 16，第一个数据1的哈希值f(1)=1，插入到1结点的后面，第二个数据12的哈希值f(12)=12，插入到12结点，第三个数据26的哈希值f(26)=10，插入到10结点后面，第4个数据337，计算得到哈希值是1，遇到冲突，但是依然只需要找到该1结点的最后链结点插入即可，同理353。

4.哈希函数如何选择

哈希函数应该尽量减少哈希冲突的出现，哈希键对应的哈希值均匀分配在哈希表里面。

1.尽量使哈希键对应的哈希值均匀分配在哈希表里面（比如说某厂商卖30栋房子，均匀划分ABC3个区域，如果你划分A区域1个房子，B区域1个房子，C区域28个房子，有人来查找C区域的某个房子最坏的情况就是要找28次）。

2.哈希键极小的变化可以引起哈希值极大的变化。

5.关于哈希表的性能

由于哈希表高效的特性，查找或者插入的情况在大多数情况下可以达到O(1)，时间主要花在计算hash上，当然也有最坏的情况就是hash值全都映射到同一个地址上，这样哈希表就会退化成链表，查找的时间复杂度变成O(n)，但是这种情况比较少，只要不要把hash计算的公式外漏出去并且有人故意攻击，一般也不会出现这种情况。

如果不需要有序遍历数据，井且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。

6.回顾全文

1. 哈希键

2. 哈希值

3. 哈希表

4. 哈希值=哈希表（哈希键）

5. 哈希冲突：key1≠key2，但f(key1)=f(key2)

6. 哈希冲突解决办法：链地址法

7. 哈希函数如何选择

8. 哈希表的性能：善于查找或者插入，不善于排序

-纸上得来终觉浅，绝知此事要躬行-