哈希表的实现

Question

5

最近有人问我“如何实现哈希表”。我知道哈希算法对性能至关重要，因为冲突越少，性能就越好。但是，为了实现插入/删除/查找的平摊常数时间{O（1）}，应该使用什么算法/数据结构呢？

- Myles McDonnell

愿数组的力量与你同在 - Thomas Jungblut

你有没有看过《算法导论》这本书，它是由Cormen等人编写的？ - Raphael

那正是我正在获取的书。 - Myles McDonnell

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

哈希表有两个主要的可能性：

开放地址法，它是一个简单的数组 [如果您可以让您的表在运行时增长，则实际上是动态数组]。一旦遇到冲突 - 您需要使用第二个哈希函数来找到元素将映射到的下一个条目。请注意，当您的哈希表也允许删除时，此解决方案会遇到一些问题[特殊标记为“已删除”的条目]。
链接法 - 在这种解决方案中，数组中的每个条目都是一个链表 - 包含所有散列到该条目的元素。在这里 - 所有映射到某个值的元素都在列表中。

哈希表[在两种解决方案中]的重要部分，为了允许自动化的O(1)插入/删除/查找 - 是分配一个更大的表并在达到预定义的负载因子时重新哈希。

编辑: 复杂度分析:
假设负载因子为p，其中p < 1。

每次访问中“碰撞”的概率为p，因此数组访问的平均值为：Sigma(i * p^(i-1) * (1-p)) for each i in [1,n]。这给出了：Sigma(i * p^(i-1) * (1-p)) = (1-p) * Sigma(i * p^(i-1)) <= (1-p) * 1/(p-1)^2 = 1-p = CONST。[请查看在wolfram alpha中验证Sigma(i * p^(i-1)) < 1/(p-1)^2的正确性]。因此，平均情况下对数组进行恒定数量的访问。另外：当负载因子达到后，您可能需要重新散列所有元素，导致对数组进行O(n)次访问。这将导致n * O(1)个操作[添加n个元素]和1 * O(n)个操作[重新散列]，因此您得到：(n * O(1) + 1 * O(n)) / n = O(1)的机械化时间。
与（1）非常相似，但是分析是针对列表访问完成的。每个操作都需要确切的一个数组访问和一个变量数量的列表访问 - 具有与之前相同的分析。