在固定大小的哈希表中，使用单独的链接并使用已知的N个条目进行初始化时，最优的存储桶数量是多少？

Question

HT不会重新散列。我们使用一个简单的除法作为哈希函数。我们假设Hash-function在均匀分布条目方面是有效的。目标是有O(1)个插入、删除和查找。

Answer 1

对于预期的使用模式，最优存储桶数量是内存消耗和散列冲突之间的折衷。

例如，如果某个东西使用得非常频繁，您可以将哈希表的大小限制为CPU缓存大小的一半，以减少“缓存未命中访问哈希表”的机会；这可能比使用更大的哈希表更快(缓存未命中更严重，哈希冲突的可能性更低)。或者，如果不经常使用它(因此，无论哈希表的大小如何，您都会期望缓存未命中)，那么更大的大小更有可能是最优的。

当然，真正的系统有多个缓存(L1，L2，L3)，加上虚拟内存转换缓存(TLB)和内存限制(加上交换空间限制)；真正的软件有不止一个哈希表在竞争内存层次结构中的资源；而且通常软件开发人员不知道其他可能正在运行的进程(竞争物理内存，污染缓存等)或任何最终用户的硬件是什么(缓存的大小，等等)。所有这些使得几乎不可能用任何方法(包括广泛的基准测试)来确定“最佳”。

唯一实用的选择是基于各种假设(关于使用情况、数据量和散列函数在实践中的好坏、CPU、其他可能使用CPU和内存的东西等)进行合理的猜测；并使源代码可配置(例如#define HASH_TABLE_SIZE ..)，这样您以后就可以轻松地重新评估猜测。