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. 哈希表的性能:善于查找或者插入,不善于排序
-纸上得来终觉浅,绝知此事要躬行-