擅长:python、mysql、java
<p>这里已经写了很多关于开放哈希表的文章,但是有些基本点却被忽略了。在</p>
<p>实际实现通常有O(1)查找和删除,因为它们保证bucket不会包含超过固定数量的项(loadfactor</em>)。但这意味着它们只能实现<em>摊销</em>O(1)时间插入,因为表需要随着表的增长定期重组。在</p>
<p>(有些人可能会选择在删除时重新组织,也可以在负载因子达到某个底部阈值时收缩表,这只会影响空间,而不影响渐近运行时间。)</p>
<p>重组意味着增加(或减少)存储桶的数量,并将所有元素重新分配到新的存储桶位置。有一些方案,例如,<em>可扩展散列</em>,可以使其更便宜一些。但一般来说,这意味着要接触表中的每个元素。在</p>
<p>重组,那么,是O(n)。当任何一个给定的人都可能产生这种成本时,怎么可能是O(1)呢?秘诀是摊销和权力的力量。当表格增长时,它必须由一个大于1的因子来增长,其中两个是最常见的。如果表以1个bucket开始,并且每次负载因子达到F时加倍,那么N个重组的成本是</p>
<pre><code>F + 2F + 4F + 8F ... (2^(N-1))F = (2^N - 1)F
</code></pre>
<p>此时,表包含<code>(2^(N-1))F</code>元素,即上次重组期间表中的数字。一、 我们已经做了<code>(2^(N-1))F</code>插入,重组的总成本如右图所示。有趣的是表中每个元素的<em>平均</em>成本(或插入,自选):</p>
^{pr2}$
<p>这就是摊销O(1)的来源。在</p>
<p>另外一点是,对于现代处理器来说,链表并不是存储桶列表的好主意。对于8字节指针,开销是有意义的。更重要的是,单个列表中堆分配的节点在内存中几乎永远不会是连续的。遍历这样一个列表会降低缓存性能,这会使缓存速度降低一个数量级。在</p>
<p>数组(对包含元素的数据数量使用整数计数)可能效果更好。如果负载因子足够小,只需分配一个大小与第一个元素插入bucket时的负载因子相等的数组。否则,以与桶数组相同的方式按因子增长这些元素数组!所有的东西仍将摊销到O(1)。在</p>
<p>要从这样的bucket中删除一个项目,不要将其标记为已删除。只需将最后一个数组元素复制到已删除元素的位置并减少元素计数。当然,如果允许外部指针进入散列桶,这当然行不通,但无论如何,这是个坏主意。在</p>