加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 百科 > 正文

c# – Dictionary.cs中的FindEntry函数

发布时间:2020-12-15 22:33:15 所属栏目:百科 来源:网络整理
导读:我一直在研究.NET的字典实现,因为我想了解是什么让字典ContainsKey和快速查找: http://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs,15debc34d286fdb3 ContainsKey函数基本上导致下面列出的FindEntry: buckets是一
我一直在研究.NET的字典实现,因为我想了解是什么让字典ContainsKey和快速查找: http://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs,15debc34d286fdb3

ContainsKey函数基本上导致下面列出的FindEntry:

buckets是一个整数数组,entry是一个Entry对象数组,它们是包含HashCode,TKey和TValue的结构体.

所以我理解这个查找很快,因为它是一个简单的数组查找.

private int FindEntry(TKey key) {
        if( key == null) {
            ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
        }
   if (buckets != null) {
            int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
            for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next) {
                if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key,key)) return i;
            }
        }
        return -1;
    }

但是我试图理解这两行:

int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
        for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next)

1)如果我没有正确地使用0x7FFFFFFF来确保我们没有得到负值.那么第一行返回的是什么?它是一个简单的整数还是素数?

2)在第二行为什么我们将i初始化为桶[hashCode%buckets.Length]?

解决方法

第一行返回哈希码,高位被关闭以使数字为正.它不一定是素数.从任何哈希中丢弃数据是完全有效的.散列0(常数零)始终是有效散列.这就是为什么这项操作是安全的.

在第二行中,我们需要从哈希码映射到桶索引.任何确定性映射都可以.因此,我们再次通过减少可能值的数量来丢弃哈希中的信息.模运算符可实现非常均匀的映射.其他映射也是可能的,例如简单地掩盖位(再次).

在.NET Dictionary类中,每个存储桶在逻辑上都是链表的开头. int [] buckets包含条目内存储的链表开头的条目索引.

由于性能原因,它很复杂.逻辑上,桶可以是新的LinkedList< Entry> [capacity].这样做会有同样的效果,但需要更多的分配.

网上有关于词典内部的文章.我发现算法非常好而且聪明.它不需要加载因子.该表可以完全加载.

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读