一、Map、Dictionary、HashTable有哪些異同

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

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

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

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

k1, k2, k3, k4, k4 ….

v1, v2, v3, v4, v5 ….

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

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

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

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

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

比如上面線性存儲的實現(xiàn)，可以調(diào)整一下。當數(shù)據(jù)都放進來之后，先根據(jù) key 來排序，再使用二分查找，就可以很快速地從 key 找到 value, 這種實現(xiàn)簡單快速，并省內(nèi)存，有時會比 hash 的實現(xiàn)更好。適合于一些數(shù)據(jù)不會經(jīng)常變動的情況。

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

延伸閱讀：

二、完全二叉樹判定

1>如果樹為空，則直接返回錯；

2>如果樹不為空：層序遍歷二叉樹；

2.1>如果一個結(jié)點左右孩子都不為空，則pop該節(jié)點，將其左右孩子入隊列；

2.1>如果遇到一個結(jié)點，左孩子為空，右孩子不為空，則該樹一定不是完全二叉樹；

2.2>如果遇到一個結(jié)點，左孩子不為空，右孩子為空；或者左右孩子都為空，且則該節(jié)點之后的隊列中的結(jié)點都為葉子節(jié)點，該樹才是完全二叉樹，否則就不是完全二叉樹。