Hashtable实现

Question

我最近被问到'你会如何实现一个hastable'。我知道哈希算法是至关重要的，因为碰撞越少，WRT性能越好，但是应该采用什么算法/数据结构来为插入/删除/查找提供分期不变的时间{O（1）}？

Answer 1

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

1. 开放寻址，这是一个简单的阵列 [动态数组actualy如果你 可以让你的桌子生长在飞。一旦遇到冲突 - 您需要使用第二个哈希函数来查找元素将映射到的下一个主元。注意当你的哈希表也允许删除时，这个解决方案有一些麻烦[可以解决]。 [特殊标记为“已删除”主菜]
2. 链接 - 在这个解决方案中，阵列在每个主菜是链表 - containig散列到这个主菜所有元素。在这里 - 映射到特定值的所有元素都在列表中。

以便允许armotorized O（1）插入/删除/查找关于哈希表[在这两种解决方案]重要的部分 - 被分配一个较大的表和重散列一旦达到定义load factor预。

编辑：复杂analsis：
承担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) armotorized时间。
2. 与（1）非常相似，但分析是在列表访问上完成的。每个操作只需要一个数组访问，并且需要不同数量的列表访问 - 具有与之前相同的分析。