散列表

理想情况下，散列表（Hash Table）是一个包含关键字的固定大小数组。通过使用散列函数（Hash Function），将关键字映射到数组的不同位置。理想散列表的结构示意图如下：

101894987d086576df954671.png

在理想状态下，哈希函数可以将关键字均匀地分散到数组的不同位置，不会出现两个关键字散列值相同的情况（假设关键字数量小于数组的大小）。但是在实际使用中，经常会出现多个关键字散列值相同的情况（被映射到数组的同一个位置），我们将这种情况称为散列冲突（Hash Collision）。

为了解决散列冲突，主要采用下面两种方式：

  • 分离链表法（Separate Chaining）
  • 开放定址法（Open Addressing）

分离链表法

分离链表法使用链表解决冲突，将散列值相同的元素都保存到一个链表中。当查询的时候，首先找到元素所在的链表，然后遍历链表查找对应的元素。下面是一个示意图：

10189498374cea7684d77627.png

开放定址法

开放定址法不会创建链表。当关键字散列到的数组单元已经被另外一个关键字占用的时候，就会尝试在数组中寻找其他的单元，直到找到一个空的单元。

探测数组空单元的方式有很多，这里介绍一种最简单的——线性探测法（Linear Probing）。线性探测法就是从冲突的数组单元开始，依次往后搜索空单元；如果到数组尾部，再从头开始搜索（环形查找）。如下图所示：

1018949868f21b75bf9f51b0.png

参考资料

关于两种方式的比较，可以参考以下文章：