Hashtable、Dictionary、SortedDictionary、SortedList的比较应用

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

 

除此以外1些介绍以及连接:http://www.cnblogs.com/plin2008/archive/2009/05/05/1450201.html

Hashtable 对象由包罗集合成分的储存桶组成。存储桶是 Hashtable 中各要素的虚拟子组,与多数成团中开展的探寻和搜索比较,存款和储蓄桶
可令搜索和查找更为便捷。每壹存款和储蓄桶都与一个哈希代码关联,该哈希代码是运用哈希函数生成的并基于该因素的键。

 

图片 1 Dictionary .ctor [http://www.xueit.com\]

 

publicvoid Add(T item)
{
if (this.root ==null)
{
this.root =new Node<T>(item, false);
this.count =1;
}
else
{
Node<T> root =this.root;
Node<T> node =null;
Node<T> grandParent =null;
Node<T> greatGrandParent =null;
int num =0;
while (root !=null)
{
num =this.comparer.Compare(item,
root.Item);
if (num ==0)
{
this.root.IsRed =false;
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
}
if (TreeSet<T>.Is4Node(root))
{
TreeSet<T>.Split4Node(root);
if (TreeSet<T>.IsRed(node))
{
this.InsertionBalance(root, ref node, grandParent,
greatGrandParent);
}
}
greatGrandParent = grandParent;
grandParent = node;
node = root;
root = (num <0) ? root.Left : root.Right;
}
Node<T> current =new Node<T>(item);
if (num >0)
{
node.Right = current;
}
else
{
node.Left = current;
}
if (node.IsRed)
{
this.InsertionBalance(current, ref node, grandParent,
greatGrandParent);
}
this.root.IsRed =false;
this.count ;
this.version ;
}
}

privatestaticvoid DictionaryTest()
{
Dictionary<int, int> dictionary =new Dictionary<int, int>();
Stopwatch watch =new Stopwatch();
watch.Start();
for (int i =1;
i < totalCount; i
)
{
dictionary.Add(i, 0);
}
watch.Stop();
Console.WriteLine(string.Format(“Dictionary添加{0}个成分耗时:{壹}ms”,totalCount,
watch.ElapsedMilliseconds));
watch.Reset();
watch.Start();
dictionary.Select(o => o.Key %1000==0).ToList().ForEach(o => { });
watch.Stop();
Console.WriteLine(string.Format(“Dictionary查找能被一千整除的要素耗费时间:{0}ms”,
watch.Elapsed米尔iseconds));
dictionary.Clear();
}

 

 

 

应用分离链接法的 Dictionary<TKey, 电视机alue>
会在中间维护多个链表数组。对于那些链表数组 L0,L一,…,LM-壹,
散列函数将告诉大家理应把成分 X 插入到链表的怎样职位。然后在 find
操作时告诉我们哪3个表中包涵了 X。
那种格局的盘算在于:尽管搜索一个链表是线性操作,但万一表丰盛小,搜索一点也十分的快(事实也的确如此,同时那也是寻觅,插入,删除等操作并非总是
O(一) 的来由)。尤其是,它不受装填因子的界定。
那种景观下,常见的装满因子是
一.0。更低的堵塞因子并无法鲜明的升高质量,但却必要越多的额外层空间间。

图片 2 Dictionary Remove [http://www.xueit.com\]

buckets数组保存全数数据链的链首,Buckets[i]表示在桶i中数据链的链首成分。entries结构体数组用于保存实际的多寡,通过next值作为链式结构的向后索引。删除的数据空间会被串入到freeList链表的首部,当再一次插入数据时,会率先查找freeList链表,以增长查找entries中空闲数据项地点的频率。在枚举器中,枚举顺序为entries数组的下标递增顺序。

publicbool Remove(TKey key)
{
if (key ==null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
if (this.buckets !=null)
{
int num =this.comparer.GetHashCode(key) &0x7fffffff;
int index = num %this.buckets.Length;
int num3 =-1;
for (int i =this.buckets[index]; i >=0;
i =this.entries[i].next)
{
if ((this.entries[i].hashCode == num) &&this.comparer.Equals(this.entries[i].key, key))
{
if (num3 <0)
{
this.buckets[index] =this.entries[i].next;
}
else
{
this.entries[num3].next =this.entries[i].next;
}
this.entries[i].hashCode =-1;
this.entries[i].next =this.freeList;
this.entries[i].key =default(TKey);
this.entries[i].value =default(TValue);
this.freeList = i;
this.freeCount ;
this.version ;
returntrue;
}
num3 = i;
}
}
returnfalse;
}

privatevoid expand()
{
int prime = HashHelpers.GetPrime(this.buckets.Length *2);
this.rehash(prime);
}
privatevoid 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();
}

二-三-四树插入算法:类似于二叉搜索树的插入(插入数据插入到树的纸牌结点)
,若是插入地点是二-结点还是三-结点,那么直接插入到近年来结点,假如插入地方是四-结点,需求将近日的肆-结点进行拆分,然后再实施后继的插入操作。

最终结出如图:

 

Hashtable 类暗许的回填因子是 一.0,但实际上它默许的装满因子是
0.7二。全数从构造函数输入的堵塞因子,Hashtable
类内部都会将其乘以0.7二。这是贰个渴求苛刻的数字, 有个别时刻将装满因子增减
0.01, 或者你的 Hashtable 存取功用就抓好或降低了
四分之二,其缘由是装满因子决定散列表容积,而散列表体积又影响 Key
的争持可能率,进而影响属性。0.72 是
Microsoft经过大批量试验得出的一个相比较平衡的值。

{
class Program
{
privatestaticint totalCount =10000;staticvoid Main(string[] args)

HashtableTest(); 
DictionaryTest(); 
SortedDictionaryTest(); 
Console.ReadKey();
}

 

 namespace DictionaryTest

Dictionary的插入算法:一、总结key的hash值,并且找到buckets中指标桶的链首索引,二、从链上依次查找是或不是key已经保存,三、如若未有的话,判断是还是不是存在freeList,四、如若存在freeList,从freeList上摘下结点保存数据,不然追加在count地点上。

SortedDictionary<K, V>是遵从K有序排列的(K,
V)数据结构,以红黑树作为内部数据结构对K进行排列保存–
TreeSet<T>,红黑树是1棵二叉搜索树,各个结点具有褐色恐怕赫色的质量。它比日常的②叉搜索树拥有越来越好的平衡性。2-三-肆树是红黑树在“理论”上的数据结构。

上学下解析Hashtable、Dictionary、SortedDictionary、SortedList的可比应用。

Hash算法是把自由长度的输入(又叫做预映射,
pre-image),通过散列算法,变换到固定长度的输出,该出口就是散列值。那种转移是一种压缩映射,也正是,散列值的半空中平日远低于输入的半空中,区别的输入只怕会散列成相同的出口,而不容许从散列值来唯壹的规定输入值。

HashTable数据结构存在难题:空间利用率偏低、受填充因子影响大、扩容时具有的数据必要再行展开散列总结。固然Hash具有O(一)的数据检索作用,但它空间开发却屡见不鲜十分的大,是以空间换取时间。所以Hashtable适用于读取操作频繁,写入操作很少的操作类型。

public Hashtable()
: this(0, (float) 1f)
{
}
public Hashtable(int capacity, float loadFactor)
{
if (capacity <0)
{
thrownew ArgumentOutOfRangeException(“capacity”,
Environment.GetResourceString(“ArgumentOutOfRange_NeedNonNegNum”));
}
if ((loadFactor <0.1f) || (loadFactor > 1f))
{
thrownew ArgumentOutOfRangeException(“loadFactor”,
Environment.GetResourceString(“ArgumentOutOfRange_HashtableLoadFactor”, newobject[] { 0.1, 1.0 }));
}
this.loadFactor =0.72f* loadFactor;
double num = ((float) capacity) /this.loadFactor;
if (num >2147483647.0)
{
thrownew ArgumentException(Environment.GetResourceString(“Arg_HTCapacityOverflow”));
}
int num2 = (num >11.0) ? HashHelpers.GetPrime((int) num) : 11;
this.buckets =new bucket[num2];
this.loadsize = (int)
(this.loadFactor * num2);
this.isWriterInProgress =false;
}

下边深入地分析如题的四个字典的法则。

大家来测试一下Hashtable、Dictionary和SortedDictionary的插入和摸索品质。

咱俩看Hashtable的1些源码:

Dictionary<K,
V>
 也是用的Hash算法,通过数组达成多条链式结构。可是它是采纳分离链接散列法。采纳分离链接散列法不受到装填因子的影响,扩大体量时原有数据不供给重新开始展览散列总结。

privatestaticvoid HashtableTest()
{
Hashtable hastable =new Hashtable();
Stopwatch watch =new Stopwatch();
watch.Start();
for (int i =1;
i < totalCount; i
)
{
hastable.Add(i, 0);
}
watch.Stop();
Console.WriteLine(string.Format(“Hashtable添加{0}个成分耗费时间:{1}ms”,totalCount,
watch.ElapsedMilliseconds));
Console.WriteLine(“Hashtable不做查找测试”);
hastable.Clear();
}

 

  1. SortedList<(Of <(TKey, 电视机alue>)>)  使用的内部存款和储蓄器比
    SortedDictionary<(Of <(TKey, TValue>)>) 少。
  2. SortedDictionary<(Of <(TKey, 电视alue>)>)
    可对未排序的数码实施更快的插入和移除操作:它的岁月复杂度为 O(log
    n),而 SortedList<(Of <(TKey, 电视alue>)>) 为 O(n)。
  3. 设若运用排序数据2次性填充列表,则 SortedList<(Of <(TKey,
    TValue>)>) 比 SortedDictionary<(Of <(TKey,
    电视机alue>)>) 快。

 

MSDN的表明:表示键/值对的成团,这个键/值对遵照键的哈希代码实行组织。

 

图片 3 Hashtable .ctor [http://www.xueit.com\]

SortedDictionary<(Of <(TKey, TValue>)>)
泛型类是摸索运算复杂度为 O(log n) 的二叉搜索树,当中 n
是字典中的成分数。就那一点而言,它与 SortedList<(Of <(TKey,
电视机alue>)>)  泛型类1般。那八个类具有相似的目的模型,并且都享有
O(log n)
的物色运算复杂度。那多个类的分别在于内部存款和储蓄器的采取以及插入和移除成分的快慢:

 图片 4

Hashtable 扩大体量是个耗费时间特别惊人的里边操作,它之所以写入效能仅为读取效用的
百分之十 数量级,频仍的扩大容积是2个要素。当进行扩大容积时,散列表内部要重新 new
三个更加大的数组,然后把原本数组的内容拷贝到新数组,并拓展双重散列。怎么着new这些越来越大的数组也有爱抚。散列表的发端体积壹般来讲是个素数。当扩大容积时,新数组的大小会设置成原数组双倍大小的好像的3个素数。

图片 5 SortedDictionary Add [http://www.xueit.com\]

 

小编们先看Hashtable

privatevoid Insert(TKey key, TValue value, bool add)
{
int freeList;
if (key ==null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
if (this.buckets ==null)
{
this.Initialize(0);
}
int num =this.comparer.GetHashCode(key) &0x7fffffff;
int index = num %this.buckets.Length;
for (int i =this.buckets[index]; i >=0;
i =this.entries[i].next)
{
if ((this.entries[i].hashCode == num) &&this.comparer.Equals(this.entries[i].key, key))
{
if (add)
{
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
}
this.entries[i].value = value;
this.version ;
return;
}
}
if (this.freeCount >0)
{
freeList =this.freeList;
this.freeList =this.entries[freeList].next;
this.freeCount–;
}
else
{
if (this.count ==this.entries.Length)
{
this.Resize();
index = num %this.buckets.Length;
}
freeList =this.count;
this.count ;
}
this.entries[freeList].hashCode = num;
this.entries[freeList].next =this.buckets[index];
this.entries[freeList].key = key;
this.entries[freeList].value = value;
this.buckets[index] = freeList;
this.version ;
}

 而SortedDictionary,MSDN是那样讲述的:

privatestaticvoid SortedDictionaryTest()
{
SortedDictionary<int, int> dictionary =new SortedDictionary<int, int>();
Stopwatch watch =new Stopwatch();
watch.Start();
for (int i =1;
i < totalCount; i
)
{
dictionary.Add(i, 0);
}
watch.Stop();
Console.WriteLine(string.Format(“SortedDictionary添加{0}个要素耗费时间:{1}ms”,totalCount,
watch.ElapsedMilliseconds));
watch.Reset();
watch.Start();
dictionary.Select(o => o.Key %1000==0).ToList().ForEach(o => { });
watch.Stop();
Console.WriteLine(string.Format(“SortedDictionary查找能被一千整除的成分耗费时间:{0}ms”, watch.ElapsedMilliseconds));
dictionary.Clear();
}
}
}

 

图片 6 质量测试代码 [http://www.xueit.com\]

图片 7 Dictionary Add [http://www.xueit.com\]

图片 8 Hashtable expand [http://www.xueit.com\]

public Dictionary()
: this(0, null)
{
}
public Dictionary(int capacity, IEqualityComparer<TKey> comparer)
{
if (capacity <0)
{
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity);
}
if (capacity >0)
{
this.Initialize(capacity);
}
if (comparer ==null)
{
comparer = EqualityComparer<TKey>.Default;
}
this.comparer = comparer;
}
privatevoid Resize()
{
int prime = HashHelpers.GetPrime(this.count *2);
int[]
numArray =newint[prime];
for (int i =0;
i < numArray.Length; i )
{
numArray[i] =-1;
}
Entry<TKey,
TValue>[]
destinationArray =new Entry<TKey, TValue>[prime];
Array.Copy(this.entries, 0, destinationArray, 0, this.count);
for (int j =0;
j <this.count; j )
{
int index = destinationArray[j].hashCode % prime;
destinationArray[j].next = numArray[index];
numArray[index] = j;
}
this.buckets = numArray;
this.entries = destinationArray;
}