浅谈Hashtable与Dictionary的异同

以前对于这两个集合类的认识只是停留在是否支持泛型上，这几天趁着看算法导论的机会，把两个类的内部的实现机制好好的了解了一下。

创新互联公司专注于当阳企业网站建设,响应式网站,成都商城网站开发。当阳网站建设公司,为当阳等地区提供建站服务。全流程按需网站策划，专业设计，全程项目跟踪，创新互联公司专业和态度为您提供的服务

Hashtable和Dictionary从数据结构上来说都属于Hashtable，都是对关键字（键值）进行散列操作，将关键字散列到Hashtable的某一个槽位中去，不同的是处理碰撞的方法。散列函数有可能将不同的关键字散列到Hashtable中的同一个槽中去，这个时候我们称发生了碰撞，为了将数据插入进去，我们需要另外的方法来解决这个问题。

链接法(chaining)

在链接法中，把散列到同一个槽中的所有元素放在一个链表中，槽中有一个指针，指向链表的头，如果没有的话，则为NIL。对于一个能存放n个元素，具有m个槽位的散列表，我们定义装载因子a为n/m,即一个链中平均存储的元素的个数。

链接法中的加入，删除，寻找操作其实基本上就是链表的基本操作。在这里就不仔细讲了。

开放寻址法(open addressing)

在开放寻址法中，所有的元素都保存在散列表中，而不是像链接法，数据保存在外部的链表中，在开放寻址法中，由于数据全部存储在散列表中，所以槽位一定会大于等于n,也就是说，装载因子一定会小于等于1。

在开放寻址法中，当要插入一个元素时，我们将关键字和探查号(从0开始累加)作为输入传给散列函数，散列函数返回对应的槽位。插入的时候首先查找hash(key,0)这个槽，如果不为空则探查号+1,继续查下一个槽，直到找到空槽，或者得知散列表已满。查找的过程和插入类似，查找关键字的时候如果我们碰到了空槽，查找就结束，因为如果关键字存在的话，那么也应该会出现在这个地方。

开放寻址法中比较特殊的是删除操作，如果删除数据置为null的话，那么就会有一个问题，比如我们插入过程中插入k的时候发现槽i已经被占用，我们插到后面的槽中，如果删除的时候我们简单的将槽i置为null,那么查找的时候关键字k就不会被找到。这个问题我们可以用一个标志位来解决。具体的实现会在下面讲到。

双重散列

开放寻址法的探查方法有多种，在这里只讲一下双重探查，因为这种方法是最好的方法之一，而且它被用在Hashtable中。

这里和为辅助散列函数，第一次为，后续的探查位置在的基础上加上偏移量,然后对m进行模运算。这里需要提一下的是为了查找整个散列表，需要与槽的大小m互质，等下可以看到在Hashtable类中是如何满足这个条件的。

在解释了链接法和开放寻址法后，来讲讲Hashtable和Dictionary。

Hashtable这个类采用的是开放寻址法来解决碰撞的问题，下面来看看Hashtable的一个构造函数

  
 
 
 
    
   
  
  
  
  1. this.loadFactor = 0.72f * loadFactor;    
    2.    
  
  
  
  2.  double num = ((float) capacity) / this.loadFactor;    
    3.    
  
  
  
  3.  if (num > 2147483647.0)    
    4.    
  
  
  
  4.  {    
    5.    
  
  
  
  5.    throw new ArgumentException(Environment.GetResourceString("Arg_HTCapacityOverflow"));    
    6.    
  
  
  
  6. }    
    7.    
  
  
  
  7.  int num2 = (num > 11.0) ? HashHelpers.GetPrime((int) num) : 11;    
    8.    
  
  
  
  8.  this.buckets = new bucket[num2];    
    9.    
  
  
  
  9.  this.loadsize = (int) (this.loadFactor * num2);    
    10.    
  
  
  
  10.  this.isWriterInProgress = false;  
    11.

构造函数会在传入装载因子的基础上乘以0.72,这个值是微软认为的比较理想的一个值。上面已经说过了在双重散列时需要保持和槽的大小m互质，我们只需要保证m为质数，而比m小，这样就能保证他们总是互质。在这里HashHelpers.GetPrime实现的就是传回一个比num大的质数，这样能保证num2这个量总为一个质数，然后把槽数组建立起来。

(this.GetHash(key) & 0x7fffffff)这个相当于双散列公式中的，1 + ((uint) (((seed >> 5) + 1) % (hashsize - 1)));则相当于,

槽中的hash_coll用来存放key对应的hashcode,最高位用来标识是否发生了碰撞，发生碰撞的槽的最高位会被置为1，搜索的时候，如果最高位为1那么搜寻函数会继续搜索，注意contains方法中的while条件,

   
 
 
 
    
    
  
  
  
  1. do   
    2.     
  
  
  
  2.  {    
    3.     
  
  
  
  3.     bucket = buckets[index];    
    4.     
  
  
  
  4.    if (bucket.key == null)    
    5.     
  
  
  
  5.    {    
    6.     
  
  
  
  6.       return false;    
    7.     
  
  
  
  7.     }    
    8.     
  
  
  
  8.     if (((bucket.hash_coll & 0x7fffffff) == num3) && this.KeyEquals(bucket.key, key))    
    9.     
  
  
  
  9.     {    
    10.     
  
  
  
  10.        return true;    
    11.     
  
  
  
  11.    }    
    12.     
  
  
  
  12.     index = (int) ((index + num2) % ((ulong) buckets.Length));    
    13.     
  
  
  
  13.  }    
    14.     
  
  
  
  14.  while ((bucket.hash_coll < 0) && (++num4 < buckets.Length));  
    15.

BTW,我当时看这个方法的时候觉得搜寻函数其实也可以通过跳过bucket.key == this.buckets的项来写，因为在移除方法中如果bucket.hash_coll < 0的话，那么bucket.key = this.buckets， 后来想了一下，bucket.hash_coll < 0这样效率更高，这里就不说为什么了，爱思考的朋友在后面写下你的答案吧。

在Add方法里面需要对count进行检查，如果达到了设定的值，这个时候需要对Hashtable进行扩容，扩大的容量是当前容量的2倍以上的一个质数，然后对里面已经存在的元素重新进行hash操作，相当于重新插入新的槽数组中。对于Insert方法中的index这个变量的作用我在看代码的时候还是有点疑问的，如果有知道的朋友麻烦在留言中告知。

Dictionary这个泛型类采用的是链接法来解决碰撞，其中的bucket存储的是指向Entry的下标，Entry就相当于链表中的节点，Entry中存储的又有指向下一个产生碰撞的元素的下标。稍有不同的是，这里的Entry是一个数组。

   
 
 
 
    
    
  
  
  
  1. public struct Entry    
    2.     
  
  
  
  2. {    
    3.     
  
  
  
  3.    public int hashCode;    
    4.     
  
  
  
  4.    public int next;    
    5.     
  
  
  
  5.   public TKey key;    
    6.     
  
  
  
  6.    public TValue value;    
    7.     
  
  
  
  7.  }  
    8.

Dictionary的Add操作首先计算元素的Hash值，然后根据Hash值寻找bucket,找到相应的bucket后将值存入Entry中，并将bucket指向相应的Entry.查询操作逻辑是根据Hash值找到相应的bucket然后通过bucket到Entry数组中进行寻找。

稍微需要提一下的是Remove方法，为了将删除的节点的Entry进行重用，Dictionary中有一个freeList字段，删除的节点的下标值，为赋给freeList，在Add操作的时候如果freeList>0则将数据插入到freeList指向的Entry中去。

原文链接：http://www.cnblogs.com/MichaelYin/archive/2011/02/14/1954724.html

网站栏目：浅谈Hashtable与Dictionary的异同
当前链接：http://www.shufengxianlan.com/qtweb/news27/513327.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

网站设计知识

行业网站建设

乐山服务器托管　　 　德信企业管理　　 　成都画册设计　　 　德阳机房　　 　成都IDC机房托管　　 　温江网站制作　　 　成都移动主机托管　　 　网站免费收录　　 　重庆app软件开发　　 　成都光华机房　　 　成都网站制作　　 　成都移动服务器托管　　 　中国电信成都枢纽中心　　 　西部信息机房　　 　重庆移动机房托管　　 　成都橡塑保温板　　 　雕琢时光茶叶　　 　重庆网站设计　　 　和正兴机械　　 　网络推广外包