在大多数编程语言中,字典比哈希表更受欢迎。这背后的原因是什么?


当前回答

MSDN上的《使用C#对数据结构进行广泛检查》一文指出,冲突解决策略也存在差异:

Hashtable类使用一种称为rehashing的技术。

Rehashing的工作原理如下:有一组哈希不同的函数,H1。。。Hn,并且当从哈希中插入或检索项时表中,最初使用H1哈希函数。如果这导致如果需要,则尝试H2,然后继续到Hn。

字典使用了一种称为链接的技术。

通过重新散列,在发生冲突时,将重新计算哈希,并尝试与哈希对应的新槽。然而,通过链接,使用辅助数据结构来保存任何碰撞。具体来说,字典中的每个插槽都有一个数组映射到该存储桶的元素。如果发生碰撞冲突元素被添加到桶的列表中。

其他回答

我能发现的另一个区别是:

我们不能在web服务中使用Dictionary<KT,VT>(泛型)。原因是没有web服务标准支持泛型标准。

注意,文档中说:“Dictionary<(Of<(TKey,TValue>)>)类是作为哈希表实现的”,而不是“Dictionary<(Of<(TKey,TValue>)>类是作为HashTable实现的”

字典没有实现为哈希表,但它是按照哈希表的概念实现的。由于使用了泛型,该实现与HashTable类无关,尽管微软内部可能使用了相同的代码,并用TKey和TValue替换了Object类型的符号。

在.NET 1.0中,泛型不存在;这是HashTable和ArrayList最初开始的地方。

在.NET中,Dictionary<,>和HashTable之间的区别主要在于前者是一种泛型类型,因此在静态类型检查方面可以获得泛型的所有好处(以及减少装箱,但这并不像人们在性能方面所想的那么大-尽管装箱会有一定的内存成本)。

Dictionary<>是泛型类型,因此它是类型安全的。

您可以在HashTable中插入任何值类型,这有时可能会引发异常。但是Dictionary<int>只接受整数值,类似地Dictionary><string>只接受字符串。

因此,最好使用Dictionary<>而不是HashTable。

自.NET Framework 3.5以来,还有一个HashSet<T>,它提供了字典<TKey,TValue>的所有优点,如果您只需要键而不需要值。

因此,如果您使用Dictionary<MyType,object>并始终将值设置为null以模拟类型安全哈希表,您可能应该考虑切换到HashSet<T>。