哈希与哈希表

哈希

到目前为止，大多数数据结构在插入、删除和搜索操作中的总体时间复杂度最高为 O(logn)。这已经相当不错了。但当数据量非常大时，这种复杂度开始对算法效率产生不利影响。

理想的数据结构应当能够在所有三种操作中都花费恒定的时间。这时，哈希技术便脱颖而出！

哈希是一种根据唯一键来存储对象的过程。这意味着哈希始终会创建一个键值对。多个这样的键值对组合成一个字典，其中每个对象或值都可以通过其键进行查找。因此，搜索操作可以在 O(1) 时间内完成。

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

哈希表

如果你的算法特别重视搜索操作，那么哈希表就是最适合你的数据结构。在 JavaScript 中，哈希表通常使用数组实现，因为数组能够以常数时间访问元素。

[]

在本节中，我们将自行实现一个哈希表，因为它在编程面试中是一个非常热门的话题。

让我们从定义高效哈希表的基本构成开始。

哈希表的性能取决于三个基本因素：

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