哈希表，又称散列表，是一种储存键值对的数据结构

哈希表，又称散列表，是一种储存键值对的数据结构。

哈希表的基础思想是拿空间换时间，哈希表的期望复杂度是 $O(1)$ 的。

一般来说，对于某 key 值，哈希后得到对应的下标，代表其在哈希表中的位置。

如果不考虑哈希冲突，就会出现误判的情况。而要解决哈希冲突，往往会使哈希表复杂度退化。

不同的实现方法，本质上就是用不同方法避免哈希冲突。

可以将桶看做一种特殊的哈希表，存储整数型的键值对。

这样能保证在值域范围内不冲突，key 值与其哈希值一一对应，在值域不大时是一种良好的数据结构。

单模数哈希表是使用广泛、代码简单的一种实现方式。

在值域范围较大，无法承受其空间时，可以对值取模来减少使用空间。

上述代码就是一种简单的实现。

为了解决单模数哈希表的哈希冲突，有线性探测法。

拉链法是另一种解决哈希冲突的方法。

在查询时，遍历对应位置的链表。

然而大部分情况下表现良好。注意需要开链表的话，可以将模数适当调小。

或者用类似建图时的写法，开固定大小的内存池。

该方法名称为本人杜撰的。

上面两种方法虽然简单，而随机数据下也称得上有效，但由于广为人知，容易遇到精心构造的数据。

而这种方法不那么常见，而由于随机性较大，也不那么好卡。

可以说，线性探测法是重哈希法的一种特殊实现。

多模数哈希也是一种简单的哈希方法。

模数可以使用随机数，能防止被卡。

值得注意的是，在模数较少的情况下，仍可能出现错误。即多个模数意义下的下标都被占用的情况。

可以直接取很多个模数，尽量减小这种可能性。

哈希表的实现千千万万种，最为常用的线性探测法、拉链法在实际应用中都有不错的表现。

以上仅为几种广为人知的、较为简单的哈希表的实现，供各位读者参考。