HashTable、Dictionary、ConcurrentDictionary三者区别

转载自

1、hashtable

　　hashtable表示键/值对的集合。在.net framework中，hashtable是system.collections命名空间提供的一个容器，用于处理和表现类似key-value的键值对，其中key通常可用来快速查找，同时key是区分大小写；value用于存储对应于key的值。hashtable中key-value键值对均为object类型，所以hashtable可以支持任何类型的keyvalue键值对，任何非 null 对象都可以用作键或值。

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

　　散列函数(gethashcode)让散列值对应hashtable的空间地址尽量不重复。

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

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

2、dictionary

　　dictionary<tkey, tvalue> 泛型类提供了从一组键到一组值的映射。通过键来检索值的速度是非常快的，接近于 o(1)，这是因为 dictionary<tkey, tvalue> 类是作为一个哈希表来实现的。检索速度取决于为 tkey 指定的类型的哈希算法的质量。tvalue可以是值类型，数组，类或其他。

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

3、concurrentdictionary

　　concurrentdictionary是.net4.0推出的一套线程安全集合里的其中一个，和它一起被发行的还有concurrentstack,concurrentqueue等类型，它们的单线程版本（线程不安全的,queue,stack,dictionary）我们一定不会陌生，可以说是经常用到，一个类的实例里，有个属性是个字典，我们不加考虑的会用dictionary，而当这个属性被提升为static静态的（类级别的）时候，我们就要考虑它的线程安全性了，因为它有可能被多个线程同时访问，当然，如果这个对象是只读的，也无所谓线程安全，但如果这个属性是可以被写的，那就需要把它加锁了，但这样的操作在性能上是不被接受的。

　　该类型在命名空间system.collections.concurrent下。

4、总结　　

　　1）大数据插入dictionary花费时间最少

　　2）遍历hashtable最快是dictionary的1/5,concurrentdictionary的1/10

　　3）单线程建议用dictionary，多线程建议用concurrentdictionary或者hashtable（hashtable tab = hashtable.synchronized(new hashtable());获得线程安全的对象）