哈希表和字典的正式区别是什么？

Question

他们一般的区别是什么？

根据维基百科的说法，字典是关联数组的同义词。

• 抽象数据类型，
• 收藏，
• 包含键值对
• 允许每个键出现一次。

根据维基百科的说法，哈希表是实现字典的常用方法。另一个实现是二进制搜索树。

由此可以看出，字典之于人类，犹如哈希表之于女性，二叉树之于男性；字典之于面食，犹如哈希表之于radiatori；二叉树之于意大利面。

dictionary     :: hash table     :: binary search tree
human          :: male           :: female
pasta          :: radiatori      :: spaghetti

令人困惑的是，文档有时需要一本字典作为论证。PowerShell文档 (许多例子之一)说，

输入哈希表或字典。

这仅仅意味着“输入哈希表或字典的任何其他实现”，还是实际上他们要求的是一个名为字典的具体类型？如果是后者，那么具体类型哈希表与具体类型字典有什么区别呢？

Answer 1

人们可以认为字典是一种抽象数据类型(ADT)，而哈希表(就像您自己通过引用源所暗示的那样)是字典类型的具体实现，与二进制搜索树是一样的。字典只允许您将键与值关联起来，它是一个接口。接口不定义实现。许多类可以实现相同的接口，主要是不同的接口。在内存访问和数据比较相对于执行给定哈希函数的成本可以忽略不计的机器上，通过对键的简单线性迭代实现字典可能是比哈希表更好的选择。特别是对于较小的字典大小。

字典接口，即ADT，是一组函数签名--用给定的键获取值，枚举键和/或值，获取键/值的数量。然后，通过提供与这些签名匹配的实际函数来设计实现接口的类。

Powershell似乎(大部分)同意这一行推理--当然，哈希表是实际的对象，它们属于(非抽象的)类。具体来说，是System.Collections.HashTable类。该类声明实现System.Collections.IDictionary接口。

然而，有趣的是，Powershell确实有一个具体的“泛型”字典类-- System.Collections.Generic.Dictionary<TKey,TValue>。对于这个字典类，似乎没有暗示任何机制。还有其他类似的“泛型”类，它们根据诸如是否允许变异字典(在运行时)、字典是否被“排序”等因素相互区分。但它们也没有暗示，例如，值查找是如何实际完成的。

这些更“通用”的字典实现是否能满足某种纯粹主义者的要求是值得商榷的，但人们可能会再次认为，System.Collections.Generic.Dictionary<TKey, TValue>是为应用程序设计人员不想或不需要考虑如何实现他们的字典而设计的。这个类实际上是这个或另一个字典类的“类型别名”，就像哈希表、二叉树或其他什么东西，而不透露哪一种。不过，我不知道为什么.NET设计人员不把它放在与using Dictionary = System.Collections.HashTable混搭上。

Answer 2

我想说的是，不要太执着于字典对这些术语的定义。

如果我们将重点放在类、[[System.Collections.Generic.Dictionary]](https://msdn.microsoft.com/en-us/library/xfhwa508(v=vs.110%29.aspx)和[System.Collections.Hashtable]上，它应该会有所帮助。

您可以看到，这两个类都实现了IDictionary接口，这可能会使您的问题更加混乱，但这很可能是参数容易接受的关键(它可能会接受实现该接口的任何对象)。

当他们说它需要一个字典，他们可能意味着它接受[IDictionary]。

您还可以看到这个这些类的实现方式有点不同。。[Dictionary]是针对键和值进行模板化的，这在PowerShell中并不是典型的，这可能是您不经常看到它的原因。