首页 > 代码库 > dotNet源码解读--HashTable目录扩展的奥秘

dotNet源码解读--HashTable目录扩展的奥秘

dotNet源码解读--HashTable目录扩展的奥秘



摘要:为了探索dotnet中hashtable的目录结构及与目录扩展相关的算法,本文通过对相关源码的阅读与分析,得出如下结论,hashtable的目录是由数组组织,目录元素代表一个数据节点,不是数据桶。目录扩展是扩展当前目录长度2倍往1遍历过程中遇到的第一个素数。目录扩展触发条件:装载因子式的触发,同时考虑到“杂乱程度”需要进行重新散列。目录扩展时需要遍历原有目录中所有的元素。查询过程与探测再散列类似。

关键词:dotnet,hashmap,目录扩展方法,目录扩展触发条件

一、目录结构

本文源自:http://blog.csdn.net/daliaojie/article/details/26366795

首先我们看一下该类主要的成员变量

        private bucket[] buckets;

        private int count;

        private const int InitialSize = 3;

        private float loadFactor;

        private int loadsize;

        private int occupancy;
   

buckets为目录,使用数组维系的。

再看bucket是什么:

        private struct bucket
        {
            public object key;
            public object val;
            public int hash_coll;
        }

原来他是一个结构体,值类型。也就是说,hashtable中的目录位置并不是一个数据桶,而是一个键值对。仅仅一个数据节点。


count就是里面已经装载了多少个元素,loadfactor和loadsize分别是装载因子与阀值。occupancy待会儿说。


二、插入操作

1、散列冲突解决方式

 public virtual void Add(object key, object value)
        {
            this.Insert(key, value, true);
        }
我们追踪insert方法:

 private void Insert(object key, object nvalue, bool add)
        {
            uint num;
            uint num2;
            if (key == null)
            {
                throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key"));
            }
            if (this.count >= this.loadsize)
            {
                this.expand();
            }
            else if ((this.occupancy > this.loadsize) && (this.count > 100))
            {
                this.rehash();
            }
            uint num3 = this.InitHash(key, this.buckets.Length, out num, out num2);
            int num4 = 0;
            int index = -1;
            int num6 = (int) (num % this.buckets.Length);
        Label_0071:
            if (((index == -1) && (this.buckets[num6].key == this.buckets)) && (this.buckets[num6].hash_coll < 0))
            {
                index = num6;
            }
            if ((this.buckets[num6].key == null) || ((this.buckets[num6].key == this.buckets) && ((this.buckets[num6].hash_coll & 0x80000000L) == 0L)))
            {
                if (index != -1)
                {
                    num6 = index;
                }
                Thread.BeginCriticalRegion();
                this.isWriterInProgress = true;
                this.buckets[num6].val = nvalue;
                this.buckets[num6].key = key;
                this.buckets[num6].hash_coll |= (int) num3;
                this.count++;
                this.UpdateVersion();
                this.isWriterInProgress = false;
                Thread.EndCriticalRegion();
            }
            else if (((this.buckets[num6].hash_coll & 0x7fffffff) == num3) && this.KeyEquals(this.buckets[num6].key, key))
            {
                if (add)
                {
                    throw new ArgumentException(Environment.GetResourceString("Argument_AddingDuplicate__", new object[] { this.buckets[num6].key, key }));
                }
                Thread.BeginCriticalRegion();
                this.isWriterInProgress = true;
                this.buckets[num6].val = nvalue;
                this.UpdateVersion();
                this.isWriterInProgress = false;
                Thread.EndCriticalRegion();
            }
            else
            {
                if ((index == -1) && (this.buckets[num6].hash_coll >= 0))
                {
                    this.buckets[num6].hash_coll |= -2147483648;
                    this.occupancy++;
                }
                num6 = (int) ((num6 + num2) % ((ulong) this.buckets.Length));
                if (++num4 < this.buckets.Length)
                {
                    goto Label_0071;
                }
                if (index == -1)
                {
                    throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_HashInsertFailed"));
                }
                Thread.BeginCriticalRegion();
                this.isWriterInProgress = true;
                this.buckets[index].val = nvalue;
                this.buckets[index].key = key;
                this.buckets[index].hash_coll |= (int) num3;
                this.count++;
                this.UpdateVersion();
                this.isWriterInProgress = false;
                Thread.EndCriticalRegion();
            }
        }

插入操作的刚开始,就是判空与判断是否需要扩展和重新散列。扩展(expand)与重新散列(rehash)两个操作的触发条件及操作,我们稍后追踪。

也就是说我们假设目前不需要扩展与重新散列。

插入操作稍后计算了key所对应的目录位置index,如果该位置无数据即可以占用,如果已经被占用,并且key值相等,则默认操作是替换value的值。否则,该目录位置已经

被占用,并且key不相等,那么我们会再选另一个位置来检测是否合适,如果合适,就插入。再次选择位置的方式,不是简单的选取隔壁的位置,而是加上一个数。这样做是为了更快的找到空闲位置,很明显,hash解决冲突的方式的开放地址法。

这里的

occupancy

应该理解为,有多少个元素不在他该在的位置,及key计算出的index不是其所子啊的位置。

2、再散列与扩展方法

再散列触发条件

(this.occupancy > this.loadsize) && (this.count > 100)


也即是说,如果占据错了位置的元素达到这个阀值并且成员装载数目达到100时,才启动再散列

扩展操作的触发条件:

this.count >= this.loadsize

也就是说,负载元素数目达到这个阀值时触发扩展操作,其实还是和负载因子有关系。


我们看他们对应的源码

 private void rehash()
        {
            this.rehash(this.buckets.Length);
        }

 private void expand()
        {
            int prime = HashHelpers.GetPrime(this.buckets.Length * 2);
            this.rehash(prime);
        }

我们发现他们都是调用的

 private void rehash(int newsize)
        {
            this.occupancy = 0;
            Hashtable.bucket[] newBuckets = new Hashtable.bucket[newsize];
            for (int i = 0; i < this.buckets.Length; i++)
            {
                Hashtable.bucket bucket = this.buckets[i];
                if ((bucket.key != null) && (bucket.key != this.buckets))
                {
                    this.putEntry(newBuckets, bucket.key, bucket.val, bucket.hash_coll & 0x7fffffff);
                }
            }
            Thread.BeginCriticalRegion();
            this.isWriterInProgress = true;
            this.buckets = newBuckets;
            this.loadsize = (int) (this.loadFactor * newsize);
            this.UpdateVersion();
            this.isWriterInProgress = false;
            Thread.EndCriticalRegion();
        }

只是,在散列操作传入的是当前目录的长度,而扩展传入的是,从当前目录长度的2倍往2遍历遇到的第一个素数。他们认为素数散列后冲突概率小。

这里求素数时的策略,参考文章:

我们看这个方法:

将站错位置的元素数目置零。

new一个指定长度的bucket数组。

在老的bucket数组目录中遍历每一个存在的元素。

将他们放到新的目录中。

  private void putEntry(bucket[] newBuckets, object key, object nvalue, int hashcode)
        {
            uint num = (uint) hashcode;
            uint num2 = (uint) (1 + (((num >> 5) + 1) % (newBuckets.Length - 1)));
            int index = (int) (num % newBuckets.Length);
        Label_0017:
            if ((newBuckets[index].key == null) || (newBuckets[index].key == this.buckets))
            {
                newBuckets[index].val = nvalue;
                newBuckets[index].key = key;
                newBuckets[index].hash_coll |= hashcode;
            }
            else
            {
                if (newBuckets[index].hash_coll >= 0)
                {
                    newBuckets[index].hash_coll |= -2147483648;
                    this.occupancy++;
                }
                index = (int) ((index + num2) % ((ulong) newBuckets.Length));
                goto Label_0017;
            }
        }

这个操作和插入有些类似,都要做冲突解决的方法。

这里我们知道,目录扩展的方法,是扩展小于2倍当前目录长度的第一个素数的目录。

结尾:

通过本次对dotNet中hashmap源码的分析与解读,得出如下结论,hashtable的目录是由数组组织,目录元素代表一个数据节点,不是数据桶。目录扩展是扩展当前目录长度2倍往1遍历过程中遇到的第一个素数。目录扩展触发条件:装载因子式的触发,同时考虑到“杂乱程度”需要进行重新散列。目录扩展时需要遍历原有目录中所有的元素。查询过程与探测再散列类似。