提问



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

最佳参考


对于它的价值,字典(概念上)哈希表。


如果你的意思是为什么我们使用Dictionary<TKey, TValue>类而不是Hashtable类?,那么它就是一个简单的答案:Dictionary<TKey, TValue>是泛型类型,Hashtable是的。这意味着你可以通过Dictionary<TKey, TValue>获得类型安全性,因为你不能将任何随机对象插入其中,并且你不必抛出你拿出的值。


有趣的是,.NET Framework中的Dictionary<TKey, TValue>实现基于Hashtable,正如您可以从其源代码中的注释中看出的那样:



  通用词典是从Hashtable的源代码复制而来的



来源[74]

其它参考1


Dictionary <<< >>> Hashtable 差异:



  • 通用<<< >>> 非通用

  • 需要自己的线程同步<<< >>>通过 Synchronized() 方法提供线程安全版本

  • 枚举项目: KeyValuePair <<< >>>枚举项目: DictionaryEntry

  • 较新(> .NET 2.0 )<<< >>>较早(因为 .NET 1.0 )

  • 位于 System.Collections.Generic <<< >>>位于 System.Collections

  • 请求不存在的密钥抛出异常<<< >>>请求不存在的密钥返回null

  • 对于值类型可能有点更快<<< >>> 慢一点(需要装箱/取消装箱)



Dictionary / Hashtable 相似之处:



  • 两者都是内部哈希表 ==根据密钥快速访问多项数据

  • 两者都需要不可变且唯一的密钥

  • 两者的关键都需要拥有 GetHashCode() 方法



类似 .NET集合(候选使用而不是Dictionary和Hashtable):



  • ConcurrentDictionary - 线程安全(可以同时从多个线程安全地访问)

  • HybridDictionary - 优化的效果(少数项目以及许多项目)

  • OrderedDictionary - 值可以通过int index 访问(按添加项目的顺序)

  • SortedDictionary - 项自动排序

  • StringDictionary - 强类型和为字符串优化


其它参考2


因为Dictionary是一个泛型类(Dictionary<TKey, TValue>),所以访问它的内容是类型安全的(即你不需要从Object强制转换,就像你Hashtable那样。]])。


比较


var customers = new Dictionary<string, Customer>();
...
Customer customer = customers["Ali G"];





var customers = new Hashtable();
...
Customer customer = customers["Ali G"] as Customer;


但是,Dictionary内部实现为Hashtable,所以从技术上讲它的工作方式相同。

其它参考3


仅供参考:在.NET中,Hashtable是多个读取器线程和单个写入线程使用的线程安全,而在Dictionary中,公共静态成员是线程安全的,但任何实例成员都不能保证是线程安全。


因此,我们不得不将所有字典改回Hashtable

其它参考4


在.NET中,Dictionary<,>HashTable之间的区别主要是前者是泛型类型,所以你可以从静态类型检查(和减少拳击,但这不是)中获得泛型的所有好处尽管人们倾向于在性能方面进行思考,但拳击有一定的记忆成本。

其它参考5


人们说词典与哈希表相同。


这不一定是真的。哈希表是字典的实现。这是一个典型的,它可能是.NET中的默认值,但它不是唯一的定义。


您同样可以使用链表或搜索树实现字典,它不会那么高效(对于某些有效度量标准)。

其它参考6


Collections& Generics对于处理对象组很有用。在.NET中,所有集合对象都在IEnumerable界面下,而ArrayList(Index-Value))& HashTable(Key-Value)。在.NET framework 2.0之后,ArrayList& HashTable被替换为List& Dictionary。现在,Arraylist& HashTable在现今的项目中不再使用。


HashTable和[[...]]之间的区别DictionaryDictionary是通用的,因为Hastable不是通用的。我们可以在HashTable中添加任何类型的对象,但在检索时我们需要将其强制转换为所需的类型。所以,它不是类型安全的。但是dictionary,在声明自己时我们可以指定键和值的类型,因此在检索时不需要强制转换。


我们来看一个例子:


哈希表


class HashTableProgram
{
    static void Main(string[] args)
    {
        Hashtable ht = new Hashtable();
        ht.Add(1, "One");
        ht.Add(2, "Two");
        ht.Add(3, "Three");
        foreach (DictionaryEntry de in ht)
        {
            int Key = (int)de.Key; //Casting
            string value = de.Value.ToString(); //Casting
            Console.WriteLine(Key + " " + value);
        }

    }
}


字典,


class DictionaryProgram
{
    static void Main(string[] args)
    {
        Dictionary<int, string> dt = new Dictionary<int, string>();
        dt.Add(1, "One");
        dt.Add(2, "Two");
        dt.Add(3, "Three");
        foreach (KeyValuePair<int, String> kv in dt)
        {
            Console.WriteLine(kv.Key + " " + kv.Value);
        }
    }
}

其它参考7


字典:



  • 如果我们试图找到一个不存在的密钥,它会返回/抛出异常。

  • 它比Hashtable更快,因为没有装箱和拆箱。

  • 只有公共静态成员是线程安全的。

  • Dictionary是一种泛型类型,这意味着我们可以将它与任何数据类型一起使用(创建时,必须指定键和值的数据类型)。


    示例:Dictionary<string, string> <NameOfDictionaryVar> = new Dictionary<string, string>();

  • Dictionay是Hashtable的类型安全实现,KeysValues是强类型的。



哈希表:



  • 如果我们尝试查找不存在的密钥,则返回null。

  • 它比字典慢,因为它需要装箱和拆箱。

  • Hashtable中的所有成员都是线程安全的,

  • Hashtable不是通用类型,

  • Hashtable是松散类型的数据结构,我们可以添加任何类型的键和值。


其它参考8


从.NET Framework 3.5开始,如果你只需要密钥而没有值,HashSet<T>就会提供Dictionary<TKey, TValue>的所有优点。[75] [76]


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

其它参考9


使用MSDN上的C#文章对数据结构的广泛检查表明,冲突解决策略也存在差异:[78]


Hashtable类使用称为 rehashing 的技术。



  Rehashing的工作原理如下:有一组哈希不同的函数,
  H 1 ... H n ,以及从哈希中插入或检索项目时
  表,最初使用H 1 哈希函数。如果这导致了
  如果需要,尝试碰撞,H 2 ,然后再转到H n



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



  通过重新散列,在发生冲突时,重新计算散列,并尝试对应于散列的新槽。然而,通过链接,利用二级数据结构来保持
  任何碰撞
。具体来说,Dictionary中的每个插槽都有一个数组
  映射到该存储桶的元素。在发生碰撞时,
  碰撞元素被添加到桶的列表中。


其它参考10


Hashtable是一种松散类型的数据结构,因此您可以将任何类型的键和值添加到Hashtable中。 Dictionary类是类型安全的Hashtable实现,键和值是强类型的。创建Dictionary实例时,必须为键和值指定数据类型。

其它参考11


请注意,MSDN说:Dictionary<(Of<(TKey,TValue>)>)类实现为哈希表,而不是Dictionary<(Of<(TKey,TValue>) >)类实现为 HashTable


Dictionary不是作为HashTable实现的,而是按照哈希表的概念实现的。由于使用了泛型,实现与HashTable类无关,尽管内部Microsoft可能使用了相同的代码并用TKey和TValue替换了Object类型的符号。


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

其它参考12


Hashtable对象由包含集合元素的存储桶组成。存储桶是Hashtable中虚拟的元素子组,这使得搜索和检索比大多数集合更容易,更快


Dictionary类与Hashtable类具有相同的功能。特定类型的字典(除了Object)对于值类型具有比Hashtable 更好的性能,因为Hashtable的元素是Object类型,因此,如果存储或检索a,则通常会发生装箱和取消装箱。值类型。


进一步阅读:哈希表和词典集类型[79]

其它参考13


哈希表:


键/值将在存储到堆中时转换为对象(装箱)类型。


在从堆读取时,需要将键/值转换为所需类型。


这些操作非常昂贵。我们需要尽可能避免装箱/拆箱。


字典: HashTable的通用变体。


没有拳击/拆箱。无需转换。

其它参考14


我能想到的另一个区别是:


我们不能将Dictionary< KT,VT>(泛型)与Web服务一起使用。原因是没有Web服务标准支持泛型标准。

其它参考15


Dictionary<>是一种通用类型,因此它的类型安全。


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


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

其它参考16


另一个重要的区别是Hashtable是线程安全的。 Hashtable内置多个读取器/单个写入器(MR/SW)线程安全,这意味着Hashtable允许一个编写器与多个读取器一起使用而无需锁定。


在Dictionary的情况下,没有线程安全;如果您需要线程安全,则必须实现自己的同步。


进一步阐述:



  Hashtable通过Synchronized属性提供一些线程安全性,该属性返回集合周围的线程安全包装器。包装器通过在每次添加或删除操作时锁定整个集合来工作。因此,尝试访问集合的每个线程必须等待轮到一个锁。这不可扩展,可能会导致大型集合的性能显着下降。此外,该设计并未完全免受竞争条件的影响。

  
  像List<T>, Dictionary<TKey, TValue>等.NET Framework 2.0集合类不提供任何线程同步;当在多个线程上同时添加或删除项时,用户代码必须提供所有同步



如果您需要类型安全性以及线程安全性,请在.NET Framework中使用并发集合类。在这里进一步阅读。[80]


另一个区别是,当我们在Dictionary中添加多个条目时,将保留添加条目的顺序。当我们从Dictionary中检索项目时,我们将按照插入它们的相同顺序获取记录。而Hashtable并不保留插入顺序。

其它参考17


根据我使用.NET Reflector看到的内容:[81]


[Serializable, ComVisible(true)]
public abstract class DictionaryBase : IDictionary, ICollection, IEnumerable
{
    // Fields
    private Hashtable hashtable;

    // Methods
    protected DictionaryBase();
    public void Clear();
.
.
.
}
Take note of these lines
// Fields
private Hashtable hashtable;


所以我们可以确定DictionaryBase在内部使用HashTable。