数据结构之哈希表

 

    哈希表：哈希表是通常的数组概念的推广。在一个普通的数组中，最有效的查找一个元素的方法是直接寻址，时间复杂度是O(1)。直接寻址的基本思想是：如果存储空间允许,我们可以为每个关键字分配一个位置,每个元素的存储地址就是关键字对应的数组下标。

    使用直接寻址的问题是：当查找表中关键字取值的范围较小时直接寻址是一种非常好的方法，但是，如果关键字的可能取值范围U 非常大,则要在一台典型的计算机上分配足够大的空闲内存来存放一个大小为|U|的表T 也许是不切实际, 甚至是不可能的。

 

    在直接寻址方式下，一个元素关键字k 被存放在位置k。在哈希方式下，这个元素处于位置h(k)；就是说，我们根据关键字K 用哈希函数h 计算出位置。我们可以说，一个具有关键字k 的元素是被哈希到位置h(k)上；我们也可以说，h(k) 是关键字k 的散列（哈希）值。

 

    两个关键字可能哈希到相同的位置，我们称这种情况为冲突。此时这两个关键字称为同义词。理想的情况是希望完全地避免冲突。要试图做到这一点我们可以选择一个适当的哈希函数h。选择h 的主导思想是使h(k)的出现是“随机”的，从而避免冲突或至少使冲突的次数减到最小（当然, 哈希函数 h 必须是确定的，因为给一个输入 k 应该总指向同样输出h(k)） 。

    构造哈希函数的方法很多，然而要构造一个好的哈希函数却需要相当的知识和技巧。一个好的哈希函数应该（近似）满足简单一致分布的假设：即每个关键字等可能地散列到任一个地址中去。

 

 

    解决冲突的方法主要有链地址法和开放地址法。

    链地址法：在链地址法中，把哈希到同一位置的所有元素都放在一个链接表中。

 

    开放地址法：在开放地址法中，所有的元素都存储在哈希表中，即哈希表中的每一个位置要么存储了某个元素，要么是Null。当采用这种方法时，要查找一个元素，我们需要通过一系列的探测才能找到或者判断元素不存在。

    采用开放地址法解决冲突的最简单的一种形式是线性探测。

    具体地说，在执行插入操作时：首先计算h(k, 0)，若T[h(k, 0)]未被占用，则直接插入；否则尝试插入到T[h(k, 1)]。要是T[h(k, 1)]也被占用了，就继续尝试T[h(k, 2)]。如此进行下去直到找到一个未被占用的存储单元。相应地，在执行查找操作时，首次对T[h(k, 0)]的查找失败并不意味着在T 中不包含k，实际上我们未能还需要依次扫描T[h(k, 1)]、T[h(k, 2)]...，直到发现k（查找成功）或到达一个空单元（查找失败）。