哈希表详解

• 哈希表的概念
• 哈希冲突
• • 开放地址法
  • 链地址法

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

在理想的情况下，每一个 关键字，通过哈希函数计算出来的地址都是不一样的。但是在实际情况中，我们常常会碰到两个关键字key1≠key2,但是f(key1) = f(key2), 这种现象称为冲突，并把key1和key2称为这个散列函数的同义词。冲突的出现会造成查找上的错误，具体解决方法有两种，

这个方法的基本思想是：当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。这个过程可用下式描述：

H_i(key) = (H(key) + d_i) mod m ( i = 1,2,…… ， k ( k ≤ m – 1))

其中： H ( key ) 为关键字 key 的直接哈希地址， m 为哈希表的长度， d_i 为每次再探测时的地址增量。

采用这种方法时，首先计算出元素的直接哈希地址 H ( key ) ，如果该存储单元已被其他元素占用，则继续查看地址为 H ( key ) + d₁ 的存储单元，如此重复直至找到某个存储单元为空时，将关键字为 key 的数据元素存放到该单元。

增量 d 可以有不同的取法，并根据其取法有不同的称呼：

1. d_i ＝ 1,2,3, …… 线性探测再散列；
2. d_i ＝ 1²,-1²,2²,-2²,k²,-k²…… 二次探测再散列；
3. d_i ＝ 伪随机序列 伪随机再散列；

下面是一个开放地址法的例子：

设有哈希函数 H ( key ) = key mod 7 ，哈希表的地址空间为 0 ～ 6 ，对关键字序列（ 32 ， 13 ， 49 ， 55 ， 22 ， 38 ， 21 ）按线性探测再散列和二次探测再散列的方法分别构造哈希表。

（ 1 ）线性探测再散列
32 ％ 7 = 4 ； 13 ％ 7 = 6 ； 49 ％ 7 = 0 ；55 ％ 7 = 6 发生冲突，下一个存储地址（ 6 ＋ 1 ）％ 7 ＝ 0 ，仍然发生冲突，再下一个存储地址：（ 6 ＋ 2 ）％ 7 ＝ 1 未发生冲突，可以存入。
22 ％ 7 ＝ 1 发生冲突，下一个存储地址是：（ 1 ＋ 1 ）％ 7 ＝ 2 未发生冲突；
38 ％ 7 ＝ 3 ；
21 ％ 7 ＝ 0 发生冲突，按照上面方法继续探测直至空间 5 ，不发生冲突，所得到的哈希表对应存储位置：

49 55 22 38 32 21 13

当然还有其他的方法比如再哈希法，Coalesced Hashing法（综合了Seperate Chainging 和 Open Addressiing）等。

这个方法的思想是：将散列表同一位置处的所有key存储在一个单链表中，散列表中存储同义词子表的头指针。

如关键字集合为{19，14，23，01，68，20，84，27，55，11，10，79}，按哈希函数H（key） = key mod 13，采用链地址法的散列表如下：

链地址法解决了冲突，提供了永远都能找到地址的保证。但是，也带来了查找时需要遍历单链表的性能损耗。

这里我们可以采用链表的方式，当然我们已可以存红黑树，或者TreeMap，如下图所示：