对于.NET字典,双哈希是如何工作的?

我得到了我的答案 Reddit ,所以我想在这里总结一下:

碰撞分辨技术

首先,冲突解决方案似乎正在使用 Separate Chaining technique 而不是 Open addressing technique 因此不存在 Double Hashing strategy :

private struct Entry 
{
    public int hashCode;    // Lower 31 bits of hash code, -1 if unused
    public int next;        // Index of next entry, -1 if last
    public TKey key;        // Key of entry
    public TValue value;    // Value of entry
}

它只是将所有共享相同hashcode/索引的条目(如每个bucket的列表或诸如此类的内容)存储在同一个entries数组中,而不是使用一个专用存储。

关于质数,答案在这里: https://cs.stackexchange.com/a/64191/42745 这都是关于多个:

因此,为了使碰撞最小化,减少m和K元素之间的公因式的数量是很重要的。这怎么可能呢 质数。

将基础项数组大小加倍

通过将阵列的大小增加足够多的插槽,有助于避免调用过多的调整大小操作(即副本)。

https://stackoverflow.com/a/2369504/4636721

例如,通过恒定增量调整大小。那样的话 调整大小的成本(随着哈希表的大小而增加) 将使一次插入的成本与插入的总数量成线性关系 随着桌子的大小,它必须“越来越少地”发生在桌子上 保持插入的摊余成本不变。