C#数据结构-Dictionary

我们熟悉的XX字典，首先是他的一个字根和拼音的目录，后面一部分就是字的解读内容，我们会发现字典的排列并不是无序的，拼音相同的字展示在一个分类里面。

字典存储结构是键值存储，查找十分的快速，那么它内部是如何实现的呢？

我们从c#开源代码中找到实现字典插入的一段代码来做分析，源码地址点击

//	buckets是哈希表，用来存放Key的Hash值								
//	entries用来存放元素列表								
//	count是元素数量								
private void Insert(TKey key, TValue value, bool add)
{
    if (key == null)
    {
        throw new ArgumentNullException(key.ToString());
    }
    //	首先分配buckets和entries的空间												
    if (buckets == null) Initialize(0);
    int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF; //	计算 key值对应的哈希值(HashCode)												
    int targetBucket = hashCode % buckets.Length;   //	对哈希值求余， 获得需要对哈希表进行赋值的位置

    #if FEATURE_RANDOMIZED_STRING_HASHING
    int	collisionCount	=	0; 
    #endif
    //	处理冲突的处理逻辑												
    for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next)
    {
        if (entries[i].hashCode == hashCode && comparer.Equals(en tries[i].key, key))
        {
            if (add)
            {
                throw new ArgumentNullException();
            }
            entries[i].value = value;
            version++;
            return;
        }
        #if FEATURE_RANDOMIZED_STRING_HASHING
            collisionCount++;
        #endif
    }
    int index;	//index记录了元素在元素列表中的位置
    if (freeCount > 0)
    {
        index = freeList;
        freeList = entries[index].next;
        freeCount--;
    }
    else
    {
        //如果哈希表存放哈希值已满，则重新从primers数组中取出值来作为哈希 表新的大小
        if (count == entries.Length)
        {
            Resize();
            targetBucket = hashCode % buckets.Length;
        }
        //大小如果没满的逻辑
        index = count;
        count++;
    }
    //对元素列表进行赋值
    entries[index].hashCode = hashCode;
    entries[index].next = buckets[targetBucket];
    entries[index].key = key;
    entries[index].value = value;
    //对哈希表进行赋值
    buckets[targetBucket] = index;
    version++;
    #if FEATURE_RANDOMIZED_STRING_HASHING
    if(collisionCount > HashHelpers.HashCollisionThreshold && Has hHelpers.IsWellKnownEqualityComparer(comparer))
    {
        comparer = (IEqualityComparer<TKey>)HashHelpers.GetRandomizedEqualityComparer(comparer);
        Resize(entries.Length, true);
    } 
    #endif
}

我们每次添加一个元素的时候字典使用对键取余法获取到该值存储的位置，如果第二次插入的键也是在第一个空间下面，这样会产生一个冲突，因为我第一次添加的元素也是在第一个空间下面，那么字典的解决办法就是通过一个单链表的方式把这些值保存起来，通过头插法进行存储，这样就解决了冲突。

下面看图解答：

插入到第一个空间：

C#数据结构-Dictionary

再插入一个数据到第一个空间：

C#数据结构-Dictionary

下面我们查看他的查找代码：

private int FindEntry(TKey key)
{
    if (key == null)
    {
        throw new ArgumentNullException();
    }
    if (buckets != null)
    {
        //获得Key值对应的哈希值
        int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
        //查找元素在元素列表中的位置，如果没有冲突的情况下，此时查找速度为O (1),存在冲突的情况下为O(N),N为存在冲突的次数
        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;
}

字典中每次存储解决冲突的时候，都会用一条链来存储冲突的数据（有点想桶排序），字典存储都是把一类存储在一起，这样每次操作的时候都会减少拆箱装箱的操作，这相对哈希表查询来说是一个优化。相对于链表来说，每次查找的时候不需要遍历整个字典，因为字典的查找方式类似二叉树查找。字典的存储方式是以空间换时间的存储方式，所以在查找的时候是比较快速的

C#数据结构-Dictionary

相关推荐