什么是哈希表？

哈希

到目前为止，大多数数据结构在插入、删除和搜索操作上的时间复杂度最多为 O(logn) 或 O(nlogn)，这已经相当不错了。但对于数据量非常大的情况，这种复杂度会开始显著影响算法的执行效率。

理想的数据结构应当能在上述三种操作中都以常数时间完成。而哈希正是为此应运而生！

哈希是一种根据唯一键来存储对象的技术。这意味着哈希总是创建一个键值对。多个这样的键值对集合构成一个字典，其中每个对象或值都可以通过其对应的键进行查找，因此查找操作的时间复杂度可以达到 O(1)。

哈希的概念催生了多种新的数据结构，其中最突出的就是哈希表。

哈希表

如果你的算法对查找操作有较高要求，那么哈希表是最佳的数据结构选择。在 Python 中，哈希表通常使用列表实现，因为列表能够以常数时间访问元素。

Python 提供了多个内置类型，例如 set 和 dict，它们都能提供哈希表的功能。

本节中，我们将手动实现一个哈希表，因为这是编程面试中的热门话题。

首先，我们来定义高效哈希表的基本构成要素。

哈希表的性能取决于三个关键因素：

• 哈希函数
• 哈希表的大小
• 冲突处理方法