在本文中将从基础角度讲解 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-------------------------------------------------");
- }
- }
四: 从上面的结果可以看出
1.HashTable 大数据量插入数据时需要花费比 Dictionary 大的多的时间.
2.for 方式遍历 HashTable 和 Dictionary 速度最快.
3. 在 foreach 方式遍历时 Dictionary 遍历速度更快.
五: 在单线程的时候使用 Dictionary 更好一些, 多线程的时候使用 HashTable 更好.
因为 HashTable 可以通过 Hashtable tab = Hashtable.Synchronized(new Hashtable()); 获得线程安全的对象.
当然因为各自电脑的情况不一样, 可能会有部分误差. 如有问题, 敬请斧正.
来源: http://www.bubuko.com/infodetail-3358320.html