介绍
原理
示例
设计哈希表的关键
复杂度分析
如何设计一个工业级hash表
语言内置哈希表
hash表键的设计（参考）
为什么hash表和链表经常会一起使用？
参考链接

介绍

哈希表 是一种使用 哈希函数 组织数据，以支持 快速插入和搜索 的数据结构。

有两种不同类型的哈希表：哈希集合 和 哈希映射。

哈希集合是集合数据结构的实现之一，用于存储 非重复值。
哈希映射是映射数据结构的实现之一，用于存储 (key, value)键值对。
原理
hash表用的就是数组支持按照下标随机访问的时候，时间复杂度是 O(1) 的特性。我们通过散列函数把元素的键值映射为下标（桶），然后将数据存储在数组中对应下标（桶）的位置。当我们按照键值查询元素时，我们用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。

哈希表的关键思想是使用哈希函数 将键映射到存储桶。更确切地说，

当插入一个新的键时，哈希函数将决定该键应该分配到哪个桶中，并将该键存储在相应的桶中；
当想要搜索一个键时，哈希表将使用相同的哈希函数来查找对应的桶，并只在特定的桶中进行搜索。
示例

在上例中，使用 y = x ％ 5 作为哈希函数。让我们使用这个例子来完成插入和搜索策略：

插入：通过哈希函数解析键，将它们映射到相应的桶中。
- 例如，1987 分配给桶 2，而 24 分配给桶 4。
搜索：通过相同的哈希函数解析键，并仅在特定存储桶中搜索。
- 如果我们搜索 1987，我们将使用相同的哈希函数将1987 映射到 2。因此我们在桶 2 中搜索，我们在那个桶中成功找到了 1987。
- 如果我们搜索 23，将映射 23 到 3，并在桶 3 中搜索。我们发现 23 不在桶 3 中，这意味着 23 不在哈希表中。

设计哈希表的关键

哈希函数

哈希函数是哈希表中最重要的组件，用于将键映射到特定的桶。

散列函数将取决于 键值的范围 和 桶的数量。

下面是一些哈希函数的示例：

哈希函数的设计是一个开放的问题。其思想是尽可能将键分配到桶中，理想情况下，完美的哈希函数将是键和桶之间的一对一映射。然而，在大多数情况下，哈希函数并不完美，它需要在桶的数量和桶的容量之间进行权衡。

装载因子

当hash表中空闲位置不多的时候，hash冲突的概率就会大大提高。为了尽可能保证hash表的操作效率，一般晴空下，需要尽可能保证hash表中有一定比例的空闲。一般使用 装载因子 来表示空位的多少。

计算公式：

装载因子 = 填入表中的元素个数 / hash表的长度
_

装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。

哈希冲突

再好的hash函数也无法避免冲突。那究竟该如何解决hash冲突问题呢？常用的方法有两类，开放寻址法和链表法。

开放寻址法

开放寻址法的核心思想是，如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入。那如何重新探测新的位置呢？

一个比较简单的探测方法是线性探测（Linear Probing）。

当往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。

此时删除操作有些特别，删除的时候不能直接删除元素，而是将其标记为 deleted。当线性探测的时候遇到标记为deleted的空间并不是停下来，而是继续往下探测。

线性探测法其实存在很大问题。当散列表中插入的数据越来越多时，散列冲突发生的可能性就会越来越大，空闲位置会越来越少，线性探测的时间就会越来越久。极端情况下，我们可能需要探测整个散列表，所以最坏情况下的时间复杂度为 O(n)。同理，在删除和查找时，也有可能会线性探测整张散列表，才能找到要查找或者删除的数据。

二次探测

所谓二次探测，跟线性探测很像，线性探测每次探测的步长是 1，那它探测的下标序列就是 hash(key)+0，hash(key)+1，hash(key)+2……而二次探测探测的步长就变成了原来的“二次方”，也就是说，它探测的下标序列就是 hash(key)+0，hash(key)+1^2，hash(key)+2^2……

双重散列

所谓双重散列，意思就是不仅要使用一个散列函数。我们使用一组散列函数 hash1(key)，hash2(key)，hash3(key)……我们先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置。**