algorithm - 哈希表实现

Question

我最近被问到“你将如何实现一个 hastable”。我知道哈希算法很关键，因为冲突越少 WRT 性能越好，但是应该采用什么算法/数据结构来为插入/删除/查找提供分摊常数时间 {O(1)}？

Answer 1

哈希表有两种主要的可能性:

1. Open Addressing，这是一个简单数组 [动态数组实际上如果你 可以让你的 table 飞速增长]。一旦遇到冲突 - 您需要使用第二个哈希函数来查找元素将映射到的下一个主条目。请注意，当您的哈希表也允许删除时，此解决方案存在一些问题 [可以解决]。 [“已删除”主菜的特殊标记]
2. 链接 - 在此解决方案中，数组 中的每个条目都是一个链表 - 包含散列到此条目的所有元素。在这里 - 映射到特定值的所有元素都在列表中。

关于哈希表的重要部分 [在两种解决方案中] 为了允许机械化 O(1) 插入/删除/查找 - 分配一个更大的表并在预定义后重新哈希 load factor达到了。

编辑复杂性分析:
假设负载系数为p对于一些 p < 1 .

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 . [看看Sigma(i * p^(i-1)) < 1/(p-1)^2 in wolfram alpha的正确性| ].因此，平均访问数组的次数是恒定的。另外:您可能需要在达到负载因子后重新散列所有元素，从而导致 O(n)访问数组。这导致 n * O(1) ops [添加 n 个元素] 和 1 * O(n) op [rehashing]，所以你得到:(n * O(1) + 1 * O(n)) / n = O(1)武装时间。
2. 与 (1) 非常相似，但分析是针对列表访问进行的。每个操作只需要一次数组访问，以及不同数量的列表访问 - 与之前的分析相同。