performance - OCaml 中的 Hashtbl 是否有最佳尺寸？

Question

假设我需要存储 20 个键/值，使用 2 的幂（例如 32）会更有效吗？我读了一篇论文，其中作者使用了 251 的大小（用于未知数量的键/值），这只是一个随机数，还是背后有一些原因？

我说的是nin Hashtbl.create n。

Answer 1

你在问什么并不完全清楚。由于您按名称询问Hashtbl，我假设您在谈论标准哈希表模块。此模块始终以 2 的幂大小分配表。所以你不必担心。

哈希表有两种基本的“超好”大小。两个的幂是好的，因为它们可以很容易地找到你的哈希桶。散列过程的最后一步是取散列值以表的大小为模。如果表大小是 2 的幂，则可以通过掩码操作非常快速地完成此模运算。我不确定这在当今世界是否重要，除非您的哈希函数本身计算速度非常快。

第二个好的价值是质数。素数很好，因为它倾向于将值分布在整个表格中。如果您的哈希值恰好是某个数字的主要倍数，这将导致哈希表中出现密集簇，除非哈希表大小与主要数字相对质数。一个大质数对几乎所有事物都是相对质数，因此它可以防止聚类。所以，251 很好，因为它是一个质数。