字典和哈希表之間的真正區別是什麼？

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

回答