最近有人问我'你将如何实现一个hastable'。我知道哈希算法至关重要,因为冲突越少,WRT性能就越好,但是应采用哪种算法/数据结构来提供摊销的固定时间{O(1)}进行插入/删除/查找?
最佳答案
哈希表有两种主要的可能性:
可以让您的 table 快速增长]。冲突解决后-您需要使用第二个哈希函数来查找元素将映射到的下一个主菜单。请注意,当您的哈希表还允许删除时,此解决方案会有一些麻烦(可以解决)。 [“已删除”主菜的特殊标记]
为了允许自动化的O(1)插入/删除/查找,在[两种解决方案中]哈希表的重要部分是分配一个更大的表,并在达到预定义的load factor后重新哈希。
编辑:复杂度分析:
假设某些
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
。 [看看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)
自动化时间。 关于algorithm - 哈希表实现,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/9409699/