代码之家 › 专栏 › 技术社区 › Natalie Perret

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

dictionary .net c#

2

Natalie Perret · 技术社区 · 7 年前

我在理解.NET字典实现的几点方面遇到了困难(考虑到实现) here .NET Core ):

大于旧尺寸两倍的数字。
注意:调整尺寸时尺寸加倍的原因数组是使内部哈希表操作具有渐近性复杂性素数被用来支持

但我仍然不知道它首先与双哈希(这是一种开放寻址哈希表的冲突解决技术)有什么关系,除了 Resize() entries 基于最小素数(基于当前/旧大小)和tbh,我真的看不到“加倍”大小的好处,“渐进复杂性”(我猜这篇文章的意思是当底层数组(条目)已满且需要调整大小时为O(n))。

首先,如果你在使用或不使用素数的情况下将大小增加一倍,这真的不一样吗?

其次,对我来说,.NET哈希表在解决冲突时使用单独的链接技术。

1 回复 | 直到 7 年前

1

0

Natalie Perret 7 年前

我得到了我的答案 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

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