哈希表的初始化与条目计数有多大？

Question

与条目计数相关的哈希表是否有最佳大小？

因此对于entries = n是否有最优(或推荐)s的哈希表大小取决于n？让我们说2n(条目计数加倍)或其他一些值？

是否取决于内部结构(散列函数,桶大小等)？在提出要求时请提供一些证据.

Answer 1

表的大小与条目数之间的比率称为哈希表的负载因子。

\n\n

负载因子至关重要地决定了预期的运行时行为。对于应用通常的界限（即所有操作的预期时间 O(1)），它必须小于 1。

\n\n

在实践中，皮特·威尔逊（Pete Wilson）的评论是适用的：为了不浪费空间，我们试图将负载系数保持在接近 1；表的素数大小通常用于改善哈希函数 \xe2\x80\x93 的冲突特性，但也存在其他策略。

\n