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

评论

>这不一定是正确的。哈希表是字典的实现。那是一个典型的例子,它可能是.NET中的默认例子,但根据定义,它并不是唯一的一个。我不确定ECMA标准是否要求这样做,但是MSDN文档非常清楚地将其称为以哈希表形式实现。他们甚至在替代方法更合理的时候提供SortedList类。

@Promit我一直认为字典是Hashtable的实现。

我认为原因是,您可以在字典中定义键的类型和selfe的值。 Hashtable只能获取对象,并基于哈希(来自object.GetHashCode())保存对。

@Dan您的主张是非常错误的...哈希表仅包含每个键的一个实例,并且搜索从不产生多个条目;如果要与每个键关联多个值,请使哈希表值成为值列表。没有像“字典”这样的数据结构。字典只是一些库用于其哈希表的名称。例如,C#的非通用哈希表称为HashTable。当他们将泛型添加到语言中时,他们称为泛型版本Dictionary。两者都是哈希表。

@Dan您的主张有误...哈希表(en.wikipedia.org/wiki/Hash_table)是字典的一种特殊实现,又名关联数组(en.wikipedia.org/wiki/Associative_array),并且一本字典,每个键只包含一个实例,搜索永远不会产生多个条目;如果要与每个键关联多个值,请使哈希表值成为值列表。 .NET Dictionary和Hashtable类都是哈希表。

#1 楼

对于它的价值,字典(从概念上来说)是一个哈希表。

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

有趣的是, .NET Framework是基于Dictionary<TKey, TValue>的,您可以从其源代码中的以下注释中看出:。


通用词典是从Hashtable的源中复制的。




评论


而且由于没有装箱/拆箱,通用收藏的速度要快得多

–克里斯S
09年1月26日在12:45

不确定上述语句的哈希表,但是对于ArrayList vs List 来说是真的

–克里斯S
09年1月26日在12:46

Hashtable使用Object在内部保存事物(只有非通用的方式可以做到),因此它也必须装箱/拆箱。

–古凡特
09年4月17日在5:29

@BrianJ:“哈希表”(两个词)是这种结构的计算机科学术语;字典是一个特定的实现。 HashTable大致对应于Dictionary (尽管接口略有不同),但两者都是哈希表概念的实现。当然,只是为了进一步混淆,某些语言将其哈希表称为“字典”(例如Python)-但是正确的CS术语仍然是哈希表。

–迈克尔·麦森(Michael Madsen)
13年6月20日在17:57

@BrianJ:HashTable(类)和Dictionary(类)都是哈希表(概念),但是HashTable不是Dictionary,Dictionary也不是HashTable。它们以非常相似的方式使用,Dictionary 可以以与HashTable相同的非类型化方式运行,但是它们不直接共享任何代码(尽管部分可能以非常相似的方式实现)。

–迈克尔·麦森(Michael Madsen)
2013年6月20日21:00

#2 楼

Dictionary <<< >>> Hashtable差异:



泛型<<< >>>非泛型

需要自己的线程同步<< <>>>通过Synchronized()方法提供线程安全版本
枚举项目:KeyValuePair <<< >>>枚举项目:DictionaryEntry

较新(> .NET 2.0)<<< >>>较旧(自.NET 1.0起)
位于System.Collections中。常规<<< >>>位于System.Collections中。
对不存在的键的请求引发异常<<< >>>对非键的请求-现有键会返回null

,对于值类型,可能会更快<<< >>>对于值类型,它会慢一些(需要装箱/拆箱)

Dictionary / Hashtable相似之处:


两者都是内部哈希表==根据密钥快速访问多个项目数据
两者都需要不可变且唯一的密钥

两者都需要密钥自己的GetHashCode()方法

类似的.NET集合(代替字典和哈希表使用的候选对象):



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

HybridDictionary-优化的性能(适用于少量物品,也适用于许多物品)

OrderedDictionary-可以通过int索引访问值(按顺序访问添加了哪些项目)

SortedDictionary-自动排序的项目


StringDictionary-强烈键入并针对字符串进行了优化



评论


@ Guillaume86,这就是为什么您使用TryGetValue而不是msdn.microsoft.com/en-us/library/bb347013.aspx的原因

–Trident D'Gao
13年6月29日在22:18

+1为StringDictionary ... btw当您使用默认构造函数时,StringDictionary与Dictionary 不同。

–陈成
2014年6月25日在6:24



ParallelExtensionsExtras @ code.msdn.microsoft.com / windowsdesktop /…包含一个ObservableConcurrentDictionary,它具有出色的冷杉绑定性和并发性。

–VoteCoffee
2014年10月31日14:28

很棒的解释,也很高兴您也列出了相似之处,以减轻可能会想到的问题

–mkb
16 Mar 25 '16 at 12:23

stackoverflow.com/a/1089142/5035500、net-informations.com/faq/general/dictionary.htm、c-sharpcorner.com/blogs/…

–阿米特·贾
17-10-5在13:51

#3 楼

因为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在内部实现为哈希表,因此从技术上讲,它的工作方式相同。

#4 楼

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

因此,我们不得不将所有的Dictionary重新改回Hashtable

评论


好玩Dictionary 源代码看起来更干净,更快。最好使用Dictionary并实现自己的同步。如果Dictionary的读取绝对需要是最新的,那么您只需要同步对Dictionary的读/写方法的访问即可。将会有很多锁定,但这是正确的。

– Triynko
2010年5月14日在18:09

另外,如果您的读物不必一定是最新的,则可以将字典视为不可变的。然后,您可以通过完全不同步读​​取来获取对Dictionary的引用并获得性能(因为它是不可变的,并且本质上是线程安全的)。要对其进行更新,您可以在后台构造Dictionary的完整更新副本,然后只需将引用与Interlocked.CompareExchange交换(假设有一个写入线程;多个写入线程将需要同步更新)。

– Triynko
2010年5月14日18:15



.Net 4.0添加了ConcurrentDictionary类,该类具有所有实现为线程安全的公共/受保护方法。如果不需要支持旧平台,则可以用多线程代码替换哈希表:msdn.microsoft.com/en-us/library/dd287191.aspx

–丹在火光中摆弄
2012年1月27日20:49

我记得曾经读过HashTable在信息永远不会从表中删除的情况下仅是读写器线程安全的。如果在删除另一个项目时读者要求在表中的项目,并且读者将在一个以上的位置查找该项目,则当读者在搜索时,作者可能会移动该项目从一个未被检查的地方到一个未被检查的地方,从而导致该项目不存在的错误报告。

–超级猫
13年13月13日在23:03

#5 楼

在.NET中,Dictionary<,>HashTable之间的区别主要在于前者是泛型类型,因此您可以从静态类型检查(减少装箱)中获得泛型的所有好处,但这并不像人们倾向于的那样大。从性能方面考虑-拳击有一定的内存成本。)

#6 楼

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

不一定是正确的。哈希表是实现字典的一种方法。一个典型的例子,它可能是Dictionary类中.NET中的默认例子,但根据定义,它并不是唯一的例子。

同样可以使用链接列表或搜索树,它就不会那么高效(对于某种效率指标而言)。

评论


MS docs说:“使用键检索值非常快,接近O(1),因为Dictionary <(Of <(TKey,TValue>)>)类被实现为哈希表。” -因此在处理Dictionary 时应确保您有哈希表。 IDictionary 可以是任何东西,但:)

– snemarch
2010-09-23 13:52



@ rix0rrr-我认为您已经倒过来了,Dictionary使用HashTable,而不是HashTable使用Dictionary。

–约瑟夫·汉密尔顿
2011年8月9日17:22

@JosephHamilton-rix0rrr正确地说:“哈希表是字典的实现。”他的意思是“字典”,而不是阶级(注意小写)。从概念上讲,哈希表实现了字典接口。在.NET中,Dictionary使用哈希表来实现IDictionary。太乱了;)

–罗伯特·亨辛(Robert Hensing)
13年8月8日在9:38

我在.NET中谈论的是,因为这就是他在答复中引用的内容。

–约瑟夫·汉密尔顿
2014年10月14日19:56

@JosephHamilton:实现(或实现)甚至与使用不具有相同的含义。恰恰相反。如果他说的稍有不同(但含义相同),可能会更清楚:“哈希表是实现字典的一种方式”。也就是说,如果您想要字典的功能,那么一种实现(实现字典)的方法是使用哈希表。

–ToolmakerSteve
2015年3月23日在4:41



#7 楼

CollectionsGenerics对于处理对象组很有用。在.NET中,所有集合对象都位于接口IEnumerable下,该接口又具有ArrayList(Index-Value))HashTable(Key-Value)。在.NET Framework 2.0之后,将ArrayListHashTable替换为ListDictionary。现在,ArraylistHashTable在当今的项目中已不再使用。

由于HashTableDictionary之间的区别,Dictionary是通用的,而Hastable不是通用的。我们可以向HashTable添加任何类型的对象,但是在检索时,我们需要将其强制转换为所需的类型。因此,它不是类型安全的。但是对于dictionary,在声明自身的同时我们可以指定键和值的类型,因此在检索时无需进行强制转换。

让我们看一个示例:

HashTable

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


评论


可以使用var来代替为KeyValuePair显式分配数据类型。因此,这将减少键入-foreach(dt中的var kv)...只是一个建议。

–罗恩
16年7月13日在13:43

#8 楼

字典:


如果尝试查找不存在的键,它将返回/抛出异常。
它比Hashtable快,因为没有装箱和装箱。 br />只有公共静态成员才是线程安全的。

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

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

Dictionay是哈希表的类型安全实现,KeysValues是强类型的。

哈希表:


如果尝试查找不存在的键,则返回null。
比字典慢,因为它需要装箱和拆箱。
哈希表中的所有成员都是线程安全,
哈希表不是泛型类型,
哈希表是松散类型的数据结构,我们可以添加任何类型的键和值。


评论


“如果我们尝试查找不存在的密钥,它将返回/引发异常。”如果您使用Dictionary.TryGetValue,则不会

–吉姆·巴尔特(Jim Balter)
18年3月3日在17:21

#9 楼

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

Hashtable类使用一种称为重新哈希的技术。


重新哈希的工作方式如下:有一组哈希不同的函数,
H1 ... Hn,以及从哈希中插入或检索项目时的方法
表中,最初使用H1哈希函数。如果这导致冲突,则尝试使用H2,然后根据需要尝试使用H2。


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


通过重新哈希处理,在发生冲突的情况下,将重新计算哈希,并尝试与哈希相对应的新插槽。但是,通过链接,可以使用辅助数据结构来保存所有冲突。具体来说,字典中的每个插槽都有一个映射到该存储桶的元素数组
。在发生碰撞的情况下,
碰撞元素会放在铲斗列表的前面。


#10 楼

从.NET Framework 3.5开始,如果只需要键而不需要任何值,则还有一个HashSet<T>提供Dictionary<TKey, TValue>的所有优点。

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

#11 楼

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

#12 楼

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

词典不是作为HashTable实现的,而是按照哈希表的概念实现的。该实现与HashTable类无关,因为使用了泛型,尽管Microsoft内部可以使用相同的代码,并用TKey和TValue替换类型为Object的符号。.NET1.0中,泛型实现了不存在;这是HashTable和ArrayList最初开始的地方。

评论


您可以修复该MSDN报价吗?缺少或错误的东西;它不是语法上的,而且有点难以理解。

– Peter Mortensen
17-10-23在8:11

#13 楼

HashTable:

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

读取时,键/值需要转换为所需的类型从堆中删除。

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

词典:HashTable的通用变体。

无装箱/拆箱。无需转换。

#14 楼

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

Dictionary类具有与Hashtable类相同的功能。对于值类型,特定类型(而不是对象)的字典比哈希表具有更好的性能,因为哈希表的元素是对象类型,因此,如果存储或检索值类型,则通常发生装箱和拆箱。

进一步阅读:哈希表和字典集合类型

#15 楼

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

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

要进一步详细说明:


Hashtable通过Synchronized属性提供了一些线程安全性,该属性返回a集合周围的线程安全包装器。包装器通过在每个添加或删除操作上锁定整个集合来工作。因此,每个尝试访问该集合的线程都必须等待其轮换获得一个锁。这是不可扩展的,并且可能导致大型集合的性能显着下降。同样,也不能完全保护设计不受竞争条件的影响。

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


如果同时需要类型安全和线程安全,请在.NET Framework中使用并发集合类。在此处进一步阅读。

另一个不同之处是,当我们在Dictionary中添加多个条目时,将保持条目添加的顺序。当我们从Dictionary中检索项目时,我们将以插入它们的相同顺序获得记录。而Hashtable不会保留插入顺序。

评论


据我了解,哈希集在不涉及删除的使用情况下保证了MR / SW线程安全。我认为这可能是完全MR / SW安全的,但是安全地处理删除操作会大大增加MR / SW安全的费用。虽然Dictionary的设计本可以在无删除方案中以最低的成本提供MR / SW安全性,但我认为MS希望避免将无删除方案视为“特殊”情况。

–超级猫
2月14日下午16:21

#16 楼

我可以弄清楚的另一个区别是:我们不能在Web服务中使用Dictionary (泛型)。原因是没有Web服务标准支持泛型标准。

评论


我们可以在基于soap的Web服务中使用通用列表(List )。但是,我们不能在Web服务中使用字典(或哈希表)。我认为这是因为.net xmlserializer无法处理字典对象。

–悉达思(Siddharth)
15年11月30日在11:04

#17 楼

Dictionary<>是通用类型,因此类型安全。

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

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

#18 楼


在大多数编程语言中,字典比哈希表更受青睐。


我认为这不一定是正确的,大多数语言都有一种或另一种,这取决于它们喜欢的术语。

然而,在C#中,(对我而言)明确的原因是C#HashTables和System.Collections命名空间的其他成员已经过时了。它们存在于c#V1.1中。它们已从C#2.0中被System.Collections.Generic命名空间中的Generic类替换。

评论


哈希表优于字典的优点之一是,如果字典中不存在键,则它将引发错误。如果哈希表中不存在键,则仅返回null。

–比尔·诺曼(Bill Norman)
19年3月20日在19:22

在C#中,我仍然避免使用System.Collections.Hashtable,因为它们没有泛型的优势。如果您不知道该键是否存在,则可以使用Dictionary的TryGetValue或HasKey。

– kristianp
19 Mar 21 '19在0:49



哎呀,不是HasKey,应该是ContainsKey。

– kristianp
19-3-21在1:02



#19 楼

根据我使用.NET Reflector看到的信息:

[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。

评论


System.Collections.Generic.Dictionary 并非从DictionaryBase派生。

– snemarch
2010-09-23 13:48

“因此,我们可以确保DictionaryBase在内部使用HashTable。” -很好,但这与问题无关。

–吉姆·巴尔特(Jim Balter)
18年3月3日在17:11