字典和哈希表之间的真正区别是什么？

130

字典是将键映射到值的一般概念。有很多方法可以实现这样的映射。

散列表是一种实现字典的特定方式。

除了哈希表，实现字典的另一种常见方式是red-black trees。

每种方法都有自己的优点和缺点。红黑树总是可以在O（log N）中执行查找。哈希表可以在O（1）时间内执行查找，尽管根据输入它可能会降级为O（N）。

2010-01-14 00:29:15

+13

我希望我可以多投一票。 – LJM 2010-01-14 00:41:21

+2

我会重新为您提供帮助。 – 2010-01-14 02:12:23

8

Python字典是在内部使用散列表实现的。

2010-01-13 23:55:33

+0

dict的子类不是字典的Python实现;这是你自己的。 – 2010-01-14 03:33:11

22

字典是将键映射到值的数据结构。

哈希表是一种数据结构，它通过获取密钥的哈希值（通过对其应用一些哈希函数）并将其映射到存储一个或多个值的存储桶来将密钥映射到值。

IMO类似于询问列表和链表之间的区别。

为了清楚起见，可能很重要的一点是，它可能是Python当前使用散列表实现它们的字典的情况，并且在将来Python可以改变该事实而不会导致它们的字典停止成为字典。

2010-01-13 23:57:27 danben

+0

主要区别是字典是否也存储密钥？因此，您可以查询字典中的密钥 - 您无法查找散列表 – 2010-01-14 00:24:01

+1

@Martin Beckett：没有。两者都可以存储密钥。字典是一般的。哈希表是一般概念的具体实现。 – 2010-01-14 00:24:53

+0

@马丁贝克特：嗯，有趣的一点。字典存储密钥和哈希表是不是一定是这种情况？ Java的'Hashtable'存储密钥 - 它不是一个哈希表，然后呢？ – danben 2010-01-14 00:28:22

13

“字典”在编程中有几个不同的含义，因为wikipedia会告诉你 - “关联数组”，Python使用该术语（也称为“映射”）的意义是其中之一意义（但在密码猜测尝试中的“数据字典”和“字典式攻击”也很重要）。

散列表是重要的数据结构; Python使用它们来实现两个重要的内置数据类型，dict和set。

所以，即使是在Python中，你可以不考虑“哈希表”是为“字典”的代名词......因为类似的数据结构也可以用来实现“套” - - ！）

2010-01-14 00:01:41

0

Dictionary是使用散列表实现的。在我看来，2之间的区别可以认为是Stacks和Arrays之间的区别，我们将使用数组来实现Stack。

2010-01-14 00:06:43 Thunderhashy

1

哈希表总是使用某个函数对某个值进行操作来确定值的存储位置。一个字典（我相信你打算这么做）是一个更通用的术语，并且简单地表示一个查找机制，它可能是一个哈希表，或者可能由一个简单的结构实现，该结构在确定其存储位置时并未考虑该值本身。

2010-01-14 00:14:08 mickeyf

回答