C#中Hashtable、Dictionary详解以及写入和读取对比

现在的位置: 首页 > 综合 > 正文

RSS

C#中Hashtable、Dictionary详解以及写入和读取对比

2012年03月16日 ⁄ 综合 ⁄ 共 3720字 ⁄ 字号小中大 ⁄ 评论关闭

转自：http://www.th7.cn/Program/net/201304/132789.shtml

C# 的几种数据结构的查找率之比较

C#与数据结构--树论--红黑树（Red Black Tree）

采用分离链接法的HashTable的实现

哈希算法

在本文中将从基础角度讲解HashTable、Dictionary的构造和通过程序进行插入读取对比。

　　一：HashTable

　　　　1.HashTable是一种散列表，他内部维护很多对Key-Value键值对，其还有一个类似索引的值叫做散列值(HashCode)，它是根据GetHashCode方法对Key通过一定算法获取得到的，所有的查找操作定位操作都是基于散列值来实现找到对应的Key和Value值的。

　　　　2.我们需要使用一个算法让散列值对应HashTable的空间地址尽量不重复，这就是散列函数(GetHashCode)需要做的事。

　　　　3.当一个HashTable被占用一大半的时候我们通过计算散列值取得的地址值可能会重复指向同一地址，这就是哈希冲突。

　　　　在.Net中键值对在HashTable中的位置Position= (HashCode& 0x7FFFFFFF) % HashTable.Length，.net中是通过探测法解决哈希冲突的，当通过散列值取得的位置Postion以及被占用的时候，就会增加一个位移x值判断下一个位置Postion+x是否被占用，如果仍然被占用就继续往下位移x判断Position+2*x位置是否被占用，如果没有被占用则将值放入其中。当HashTable中的可用空间越来越小时，则获取得到可用空间的难度越来越大，消耗的时间就越多。

　　　　4.当前HashTable中的被占用空间达到一个百分比的时候就将该空间自动扩容，在.net中这个百分比是72%,也叫.net中HashTable的填充因子为0.72。例如有一个HashTable的空间大小是100，当它需要添加第73个值的时候将会扩容此HashTable.

　　　　5.这个自动扩容的大小是多少呢？答案是当前空间大小的两倍最接近的素数，例如当前HashTable所占空间为素数71，如果扩容，则扩容大小为素数131.

　　二：Dictionary

　　　　1.Dictionary是一种变种的HashTable,它采用一种分离链接散列表的数据结构来解决哈希冲突的问题。

　　　　2.分离链接散列表是当散列到同一个地址的值存为一个链表中。

　　　　3.这个变种HashTable的填充因子是1

　　三：本文将以代码的形式探索HashTable和Dictionary的插入和三种读取方式的效率(for/foreach/GetEnumerator)

    public class HashTableTest    {        static Hashtable _Hashtable;        static Dictionary<string, object> _Dictionary;        static void Main()        {            Compare(10);            Compare(10000);            Compare(5000000);            Console.ReadLine();        }        public static void Compare(int dataCount)        {            Console.WriteLine("-------------------------------------------------/n");            _Hashtable = new Hashtable();            _Dictionary = new Dictionary<string, object>();            Stopwatch stopWatch = new Stopwatch();            //HashTable插入dataCount条数据需要时间            stopWatch.Start();            for (int i = 0; i < dataCount; i++)            {                _Hashtable.Add("Str" + i.ToString(), "Value");            }            stopWatch.Stop();            Console.WriteLine(" HashTable插入" + dataCount + "条数据需要时间：" + stopWatch.Elapsed);            //Dictionary插入dataCount条数据需要时间            stopWatch.Reset();            stopWatch.Start();            for (int i = 0; i < dataCount; i++)            {                _Dictionary.Add("Str" + i.ToString(), "Value");            }            stopWatch.Stop();            Console.WriteLine(" Dictionary插入" + dataCount + "条数据需要时间：" + stopWatch.Elapsed);            //Dictionary插入dataCount条数据需要时间            stopWatch.Reset();            int si = 0;            stopWatch.Start();            for(int i=0;i<_Hashtable.Count;i++)            {                si++;            }            stopWatch.Stop();            Console.WriteLine(" HashTable遍历时间：" + stopWatch.Elapsed + " ,遍历采用for方式");            //Dictionary插入dataCount条数据需要时间            stopWatch.Reset();            si = 0;            stopWatch.Start();            foreach (var s in _Hashtable)            {                si++;            }            stopWatch.Stop();            Console.WriteLine(" HashTable遍历时间：" + stopWatch.Elapsed + " ,遍历采用foreach方式");            //Dictionary插入dataCount条数据需要时间            stopWatch.Reset();            si = 0;            stopWatch.Start();            IDictionaryEnumerator _hashEnum = _Hashtable.GetEnumerator();            while (_hashEnum.MoveNext())            {                si++;            }            stopWatch.Stop();            Console.WriteLine(" HashTable遍历时间：" + stopWatch.Elapsed + " ,遍历采用HashTable.GetEnumerator()方式");            //Dictionary插入dataCount条数据需要时间            stopWatch.Reset();            si = 0;            stopWatch.Start();            for(int i=0;i<_Dictionary.Count;i++)            {                si++;            }            stopWatch.Stop();            Console.WriteLine(" Dictionary遍历时间：" + stopWatch.Elapsed + " ,遍历采用for方式");            //Dictionary插入dataCount条数据需要时间            stopWatch.Reset();            si = 0;            stopWatch.Start();            foreach (var s in _Dictionary)            {                si++;            }            stopWatch.Stop();            Console.WriteLine(" Dictionary遍历时间：" + stopWatch.Elapsed + " ,遍历采用foreach方式");            //Dictionary插入dataCount条数据需要时间            stopWatch.Reset();            si = 0;            stopWatch.Start();            _hashEnum = _Dictionary.GetEnumerator();            while (_hashEnum.MoveNext())            {                si++;            }            stopWatch.Stop();            Console.WriteLine(" Dictionary遍历时间：" + stopWatch.Elapsed + " ,遍历采用Dictionary.GetEnumerator()方式");            Console.WriteLine("/n-------------------------------------------------");        }    }