数据结构和算法 – 12.高级查找算法(下)

时间:2021-08-14 08:29:02

哈希(散列)技术既是一种存储方法,也是一种查找方法。然而它与线性表、树、图等结构不同的是,前面几种结构,数据元素之间都存在某种逻辑关系,可以用连线图示表示出来,而哈希技术的记录之间不存在什么逻辑关系,它只与关键字有关联。因此,哈希主要是面向查找的存储结构。哈希技术最适合的求解问题是查找与给定值相等的记录。

Hashtable 与 Dictionary 的区别:

①Hashtable使用闭散列法来解决冲突,而Dictionary使用开散列法解决冲突;

②Dictionary相对Hashtable来说需要更多的存储空间,但它不会发生二次聚集的情况,并且使用了泛型,相对非泛型可能需要的装箱和拆箱操作,Dictionary的速度更快;

③Hashtable使用了填充因子的概念,而Dictionary则不存在填充因子的概念;

④Hashtable在扩容时由于重新计算哈希地址,会消耗大量时间计算,而Dictionary的扩容相对Hashtable来说更快;

⑤单线程程序中推荐使用Dictionary,而多线程程序中则推荐使用Hashtable。默认的Hashtable允许单线程写入,多线程读取,对Hashtable进一步调用Synchronized()方法可以获得完全线程安全的类型。相反,Dictionary不是线程安全的,必须人为使用lock语句进行保护,效率有所降低。

 

数据结构基础温故-6.查找(下):哈希表

http://www.cnblogs.com/edisonchou/p/4706253.html

4.2 测试对比结果

(1)SortedDictionary测试结果:

数据结构和算法 – 12.高级查找算法(下)

SortedDictionary内部是红黑树结构,在插入和删除操作时需要经过大量的旋转操作来维持平衡,因此耗时是三种类型中最多的。此外,在插入过程中,引起了GC大量的垃圾回收操作。

(2)Hashtable测试结果:

数据结构和算法 – 12.高级查找算法(下)

Hashtable插入操作的耗时和SortedDictionary相近,但删除操作却比SortedDictionary快了好几倍。

(3)Dictionary测试结果:

数据结构和算法 – 12.高级查找算法(下)

Dictionary在插入和删除操作上是三种类型中最快的,且对GC的友好程度上也较前两种类型好很多。