为什么缓存大小通常定义为质数？

Question

为什么缓存大小通常定义为质数？

cachingdata-structuresprimes

4

我正在研究编写缓存，我发现有几个参考文献提到缓存大小应该是质数。

例如：

最大对象数量必须是一个质数，用于缓存计数值。范围值从3到适合任务且不影响性能的最大数字。非质数将自动向上舍入为下一个更高的质数。如果数字失败，则使用默认值。

请参阅https://www.ibm.com/support/knowledgecenter/SSPREK_7.0.0/com.ibm.isam.doc_70/ref_cache_size_appl.html。

- aaa90210

1

我怀疑这是哈希集合使用质数大小的原因相同，以减少碰撞的数量。虽然我可能错了。 - rossum

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Keith Irwin · Accepted Answer

假设我们有一个包含m个条目的缓存和一个使用模式，导致其呈现跨步行为，其中它击中每个第n个条目以获得一些n。该模式将绕过结尾并再次命中一些条目，同时仍有空位。例如，如果缓存的大小为10且使用模式每6个条目命中一次，则会按以下顺序命中（如果从0开始）：0、6、2、8、4、0、6、2、8、4，...因此，一半缓存将不被使用。在一般情况下，可以准确地说，这样的跨步行为将导致使用1/GCD(n,m)的行，而其他行则保持为空。因此，只有当GCM(n,m)为1时，存在跨度行为时才能充分利用。使缓存具有质数大小可以使这种情况非常可能发生。只有在n=m或n是m的某个倍数的情况下，才会失败，对于不小的质数来说，这种情况相当不太可能。