代码之家  ›  专栏  ›  技术社区  ›  Matthew King

.NET ConcurrentDictionary初始容量设置为任意素数,而不是msdn示例文档中的预期容量。为什么?

  •  11
  • Matthew King  · 技术社区  · 14 年前

    我只是在看 MSDN documentation for ConcurrentDictionary 我在“示例”代码中看到了:

    // We know how many items we want to insert into the ConcurrentDictionary.
    // So set the initial capacity to some prime number above that, to ensure that
    // the ConcurrentDictionary does not need to be resized while initializing it.
    int NUMITEMS = 64;
    int initialCapacity = 101;
    

    作为参考,在msdn示例中的字典初始化如下:

    ConcurrentDictionary<int, int> cd = new ConcurrentDictionary<int, int>(Environment.ProcessorCount * 2, initialCapacity);
    for (int i = 0; i < NUMITEMS; i++) cd[i] = i * i;
    

    在这个例子中,字典包含的项目永远不会超过64个。为什么不将初始容量设置为64,而不是设置为大于64的任意素数?评论说这是为了确保在初始化字典时不需要调整其大小,但是为什么需要调整初始容量为64的类似字典的大小呢?为什么选择这个质数?

    1 回复  |  直到 14 年前
        1
  •  11
  •   VinayC    14 年前

    字典或哈希表依赖于散列键来获取较小的索引以查找相应的存储(数组)。所以哈希函数的选择是非常重要的。典型的选择是获取一个键的散列码(这样我们就可以得到很好的随机分布),然后用一个素数除以该代码,然后使用reminder将其索引为固定数量的bucket。这允许将任意大的哈希代码转换成一组有界的小数字,我们可以为这些小数字定义一个数组来查找。因此,在质数中使用数组大小是很重要的,然后最佳选择的大小将成为大于所需容量的质数。这正是字典实现所做的。

    所以基本上,任何模n(n是质数)字典实现都需要它的能力是质数。所以,如果您说,所需的容量是x,那么这些实现通常会选择比所需容量更大的下一个底漆数量。