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

dictionary 跟 map 其實(shí)是同一個(gè)東西，只是在不同場(chǎng)合叫法不同。

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

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

比如，最簡(jiǎn)單是將 key，value 放在一起，線性排。

k1, k2, k3, k4, k4 ….

v1, v2, v3, v4, v5 ….

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

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

為了快速?gòu)膋ey找到value。dictionary(或者說(shuō)map)的通常有兩種實(shí)現(xiàn)方式。

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

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

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

C++ 11的標(biāo)準(zhǔn)庫(kù)中有個(gè)unordered_map，就是采用哈希表使用的 map。在C++11之前，沒有標(biāo)準(zhǔn)的哈希實(shí)現(xiàn)，很多第三方庫(kù)實(shí)現(xiàn)了哈希字典，基本都叫做 hash_map, 并應(yīng)用廣泛。所以C++11的實(shí)現(xiàn)就不能叫hash_map了，因?yàn)闀?huì)造成很多現(xiàn)存的程序名字沖突。哈希實(shí)現(xiàn)的字典是無(wú)序，也就取了個(gè)不算太好的名字，unordered_map。

延伸閱讀：

二、完全二叉樹判定

1>如果樹為空，則直接返回錯(cuò)；

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

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

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

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