Map、Dictionary、Hash Table 有哪些異同？

01-30

看到各種各樣的hash map之類的。。不理解。。

dictionary 跟 map 其實是同一個東西，只是在不同場合叫法不同。

dictionary 的中文是字典，map 在中文是映射，也有地圖的意思。查字典，查地圖，都是通過某個信息，去找到另一個信息。比如通過單詞的拼寫找到單詞的具體含義。

類比查字典過程，單詞的拼寫為 key, 單詞的具體含義為 value。dictionary 就是通過key，找到value，有時也將 dictionary 說成是 key-value 結構。只要達到查找目的，都可以叫做 dictionary。具體怎麼找，可以有不同實現。

比如，最簡單是將 key，value 放在一起，線性排。

k1, k2, k3, k4, k4 .... v1, v2, v3, v4, v5 ....

當需要從 key 找到對應的 value 時，就從頭到尾遍歷過去。依次判斷 k1, k2, k3, k4 是不是等於key, 當等於的時候，就找到 key 的具體位置，從而也就找到了value。

但這樣從頭到尾遍歷，速度就太慢了，時間複雜度為 O(N)。N為數據的大小。

為了快速從key找到value。dictionary(或者說map)的通常有兩種實現方式。

二叉樹
哈希(hash)表

二叉樹查找的時間複雜度為 O(logN)，哈希表的時間複雜度大致為 O(1)。二叉樹也分紅黑樹，AVL樹等。哈希表的速度很快，很多語言內置的 dictionary 都使用哈希表來實現，但它通常會浪費一些存儲空間。這部分有興趣去看數據結構的書。

hash_map 其實就是使用 hash 表實現的 map。注意，二叉樹，哈希表僅僅是 dictionary 的實現方式，不能說 hash 就等於 dictionary，實現方式可以有多種多樣。

比如上麵線性存儲的實現，可以調整一下。當數據都放進來之後，先根據 key 來排序，再使用二分查找，就可以很快速地從 key 找到 value, 這種實現簡單快速，並省內存，有時會比 hash 的實現更好。適合於一些數據不會經常變動的情況。

C++ 11 的標準庫中有個 unordered_map，就是採用哈希表使用的 map。在C++ 11之前，沒有標準的哈希實現，很多第三方庫實現了哈希字典，基本都叫做 hash_map, 並應用廣泛。所以C++ 11的實現就不能叫hash_map了，因為會造成很多現存的程序名字衝突。哈希實現的字典是無序，也就取了個不算太好的名字，unordered_map。

這些都是按照key-value方式存儲數據的，可以快速的從key找到value

stl中有個map

.NET中有Dictionary

hashtable即哈希表

微軟的stl中有hash_map

c++11中有unordered_map

.NET中還有SortedDictionary

區別的話，map和SortedDictionary是有序的，Dictionary和hash_map和unordered_map是無序的。有序的好處是有序，無序的好處是更快（一般的）

先贊一下魯哈花的答案

稍微說一下 .net 的 Dictionary& 和 Hashtable

第一區別是泛型

第二區別是 Dictionary 在演算法上做了一點優化比Hashtable 快

所以基本上就算需要用Hashtable 的 string,object 場合也建議用 Dictionary&

另外有 Dictionary&和 SortedDictionary& 的區別

更詳細點說 Dic 是用TK的hash作為索引的一般hash table 演算法， SortedDic 是基於compare紅黑樹，所以跟hash關係不大。

hash是map/dict的一種實現

dict是鍵值對的集合

你也可以用順序查找和單鏈表來實現dict，但就會比較慢，用起來也不方便

java 1.2 之前的集合類比較簡單，只有Vector, Statck, Hashtable, Properties, Dictionary.五個（legacy classes），分別處理不同數據結構，dictionary 屬於最頂層，傳的是&，java 1.5 之後引入泛型就直接可以用map&解決了，推薦使用泛型，五個legacy classes 看得懂別人寫的就好，自己別用。

hash指的是實現方式，拋開這個詞，沒有區別。