题 为什么Dictionary优先于Hashtable?


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


1205
2017-11-19 09:24


起源


>这不一定是真的。哈希表是字典的实现。这是一个典型的,它可能是.NET中的默认值,但它不是唯一的定义。我不确定这是ECMA标准所要求的,但是 MSDN文档 非常明确地将其称为哈希表实现。它们甚至在替代方案更合理的时候提供SortedList类。 - Promit
@Promit我一直以为 Dictionary 是一个实施 Hashtable。 - b1nary.atr0phy
我认为原因是,在字典中你可以定义键的类型和你自己的值。 Hashtable只能接受对象并根据哈希(来自object.GetHashCode())保存对。 - Radinator
字典用于查找单个项目。可以在多个键下找到相同的项目。但是你不会从同一把钥匙中获得多件物品。哈希表不是这样。如果您搜索了名称的示例,则可能会找到多个条目,每个条目代表具有相同名称的其他人。这应该是您选择使用哪一个的唯一标准。 - Dan


答案:


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

如果你的意思是“为什么我们使用 Dictionary<TKey, TValue> 而不是 Hashtable 上课?“,那么这是一个简单的答案: Dictionary<TKey, TValue> 是一种通用类型, Hashtable 不是。这意味着你可以获得类型安全 Dictionary<TKey, TValue>,因为您无法在其中插入任何随机对象,并且您不必转换所取出的值。

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

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

资源 


1406
2017-11-19 09:28



并且通用集合也快得多,因为没有装箱/拆箱 - Chris S
不确定具有上述语句的Hashtable,但对于ArrayList vs List <t>,它是真的 - Chris S
Hashtable使用Object在内部保存东西(只有非通用的方式),所以它也必须使用box / unbox。 - Guvante
@BrianJ:“哈希表”(两个词)是这种结构的计算机科学术语;字典是一种特定的实现。 HashTable大致对应于Dictionary <object,object>(虽然接口略有不同),但两者都是哈希表概念的实现。当然,为了进一步混淆问题,有些语言称其哈希表为“词典”(例如Python) - 但正确的CS术语仍然是哈希表。 - Michael Madsen
@BrianJ:两个 HashTable (课)和 Dictionary (类)是哈希表(概念),但是a HashTable 不是一个 Dictionary,也不是 Dictionary 一个 HashTable。它们以非常相似的方式使用,并且 Dictionary<Object,Object> 可以采取与a相同的无类型方式行事 HashTable 确实如此,但他们没有直接共享任何代码(虽然部分可能以非常类似的方式实现)。 - Michael Madsen


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索引访问 (按添加项目的顺序)
  • SortedDictionary  - 物品 自动排序
  • StringDictionary  - 强烈打字和 优化字符串

565
2018-04-21 10:32



我们可以使用concurrentDictionary(在.NET 4.0中)进行线程安全。 - WAP Guy
@ Guillaume86,这就是你使用TryGetValue的原因 msdn.microsoft.com/en-us/library/bb347013.aspx - Aleksey Bykov
+1为 StringDictionary顺便说一句... StringDictionary 是不一样的 Dictionary<string, string> 当您使用默认构造函数时。 - Danny Chen
ParallelExtensionsExtras @code.msdn.microsoft.com/windowsdesktop/... 包含一个ObservableConcurrentDictionary,它具有很强的fir绑定和并发性。 - VoteCoffee
很棒的解释,你真的很好,你也列出了相似之处,以减轻可能出现在你脑海中的问题 - mkb


因为 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 在内部,所以从技术上讲,它的工作方式相同。


163
2017-11-19 09:27





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

我们不得不改变所有字典 Hashtable 因为这个。


80
2017-11-19 11:55



乐趣。 Dictionary <T>源代码看起来更清晰,更快。使用Dictionary并实现自己的同步可能更好。如果Dictionary绝对需要是最新的,那么你只需要同步访问Dictionary的读/写方法。这将是很多锁定,但它是正确的。 - Triynko
或者,如果您的读取不必绝对是最新的,则可以将字典视为不可变。然后,您可以获取对Dictionary的引用,并通过不同步读取来获得性能(因为它是不可变的并且本质上是线程安全的)。要更新它,您需要在后台构建一个完整的Dictionary更新副本,然后只需使用Interlocked.CompareExchange交换引用(假设一个写线程;多个写线程需要同步更新)。 - Triynko
.Net 4.0添加了 ConcurrentDictionary 将所有公共/受保护方法实现为线程安全的类。如果您不需要支持旧版平台,则可以替换 Hashtable 在多线程代码中: msdn.microsoft.com/en-us/library/dd287191.aspx - Dan Neely
匿名救援。很酷的回答。 - unkulunkulu
我记得在没有从表中删除信息的情况下,HashTable只是读写器线程安全的。如果读者在要删除其他项目时要求表中的项目,并且读者会在该项目的多个位置查找,则可能在读者正在搜索作者时可能会移动该项目从未经检查的地方到有检查的地方,从而导致该项目不存在的虚假报告。 - supercat


在.NET中,区别 Dictionary<,> 和 HashTable 主要是前者是泛型类型,因此你可以从静态类型检查(和减少拳击)方面获得泛型的所有好处,但这并不像人们在性能方面所认为的那么大 - 有一定的但是,拳击的记忆成本)。


62
2017-11-19 09:28





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

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

您同样可以使用链表或搜索树来实现字典,它只是效率不高(对于某些效率指标)。


27
2017-11-19 13:03



MS博士说: “通过使用其键来检索值非常快,接近于O(1),因为Dictionary <(Of <(TKey,TValue>)>)类被实现为哈希表。”  - 所以在处理时应该保证哈希表 Dictionary<K,V>。 IDictionary<K,V> 可能是什么,但:) - snemarch
@ rix0rrr - 我认为你已经倒退了,一个Dictionary使用HashTable而不是HashTable使用一个Dictionary。 - Joseph Hamilton
@JosephHamilton - rix0rrr说得对:“哈希表 是 一个实现 字典“他的意思是”字典“,而不是类(注意小写)。从概念上讲,哈希表实现了一个字典界面。在.NET中,Dictionary使用哈希表来实现IDictionary。它很混乱;) - Robert Hensing
我在.NET中讨论过,因为这是他在回复中引用的内容。 - Joseph Hamilton
@JosephHamilton: 器物 (要么 实施)甚至远没有意味着同样的事情 使用。恰恰相反。如果他说的略有不同(但意思相同),也许会更清楚:“哈希表是实现字典的一种方式”。也就是说,如果你想要一个字典的功能,一种方法(到 实行 字典),是使用哈希表。 - ToolmakerSteve


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);
        }
    }
}

21
2017-09-17 11:10



而不是显式地为KeyValuePair分配数据类型,我们可以使用var。所以,这会减少输入 - foreach(dt中的var kv)......只是一个建议。 - Ron


字典:

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

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

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

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

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

  • Dictionay是Hashtable的类型安全实现, Keys 和 Values 是强类型的。

哈希表:

  • 如果我们试图找到一个不存在的密钥,它将返回null。

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

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

  • Hashtable不是通用类型,

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


14
2018-05-28 07:53