Hash Table 算法数据结构基础——哈希表( 二 ) _哈希表

理想状态下，我们的哈希函数是完美的一对一映射，即一个关键字（key）对应一个值（value），不需要处理冲突。但是一般情况下，不同的关键字 key 可能对应了同一个值 value，这就发生了哈希冲突。
设计再好的哈希函数也无法完全避免哈希冲突。所以就需要通过一定的方法来解决哈希冲突问题。常用的哈希冲突解决方法主要是两类：「开放地址法（Open ）」和「链地址法（）」。
3.1 开放地址法
开放地址法（Open ）：指的是将哈希表中的「空地址」向处理冲突开放。当哈希表未满时，处理冲突时需要尝试另外的单元，直到找到空的单元为止。
当发生冲突时，开放地址法按照下面的方法求得后继哈希地址：H(i) = (Hash(key) + F(i)) % m，i = 1, 2, 3, ..., n (n ≤ m - 1) 。
举个例子说说明一下如何用以上三种冲突解决方法处理冲突，并得到新地址 H(i) 。例如，在长度为 11 的哈希表中已经填有关键字分别为 28、49、18 的记录（哈希函数为 Hash(key) = key % 11）。现在将插入关键字为 38 的新纪录。根据哈希函数得到的哈希地址为 5，产生冲突。接下来分别使用这三种冲突解决方法处理冲突。
使用这三种方法处理冲突的结果如下图所示：
3.2 链地址法
链地址法（）：将具有相同哈希地址的元素（或记录）存储在同一个线性链表中。
链地址法是一种更加常用的哈希冲突解决方法。相比于开放地址法，链地址法更加简单。
我们假设哈希函数产生的哈希地址区间为 [0, m - 1]，哈希表的表长为 m 。则可以将哈希表定义为一个有 m 个头节点组成的链表指针数组 T 。
举个例子来说明如何使用链地址法处理冲突。假设现在要存入的关键字集合 keys = [88, 60, 65, 69, 90, 39, 07, 06, 14, 44, 52, 70, 21, 45, 19, 32] 。再假定哈希函数为 Hash(key) = key % 13，哈希表的表长 m = 13，哈希地址范围为 [0, m - 1] 。将这些关键字使用链地址法处理冲突，并按顺序加入哈希表中（图示为插入链表表尾位置），最终得到的哈希表如下图所示。
相对于开放地址法，采用链地址法处理冲突要多占用一些存储空间（主要是链节点占用空间）。但它可以减少在进行插入和查找具有相同哈希地址的关键字的操作过程中的平均查找长度。这是因为在链地址法中，待比较的关键字都是具有相同哈希地址的元素，而在开放地址法中，待比较的关键字不仅包含具有相同哈希地址的元素，而且还包含哈希地址不相同的元素。
4. 哈希表总结
本文讲解了一些比较基础、偏理论的哈希表知识。包含哈希表的定义，哈希函数、哈希冲突以及哈希冲突的解决方法。
哈希表的两个核心问题是：「哈希函数的构建」和「哈希冲突的解决方法」。