国产一区二区精品-国产一区二区精品久-国产一区二区精品久久-国产一区二区精品久久91-免费毛片播放-免费毛片基地

千鋒教育-做有情懷、有良心、有品質的職業教育機構

手機站
千鋒教育

千鋒學習站 | 隨時隨地免費學

千鋒教育

掃一掃進入千鋒手機站

領取全套視頻
千鋒教育

關注千鋒學習站小程序
隨時隨地免費學習課程

當前位置:首頁  >  技術干貨  > Map、Dictionary、HashTable有哪些異同?

Map、Dictionary、HashTable有哪些異同?

來源:千鋒教育
發布人:xqq
時間: 2023-10-11 03:36:34 1696966594

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

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。

延伸閱讀:

二、完全二叉樹判定

1>如果樹為空,則直接返回錯;

2>如果樹不為空:層序遍歷二叉樹;

2.1>如果一個結點左右孩子都不為空,則pop該節點,將其左右孩子入隊列;

2.1>如果遇到一個結點,左孩子為空,右孩子不為空,則該樹一定不是完全二叉樹;

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

聲明:本站稿件版權均屬千鋒教育所有,未經許可不得擅自轉載。
10年以上業內強師集結,手把手帶你蛻變精英
請您保持通訊暢通,專屬學習老師24小時內將與您1V1溝通
免費領取
今日已有369人領取成功
劉同學 138****2860 剛剛成功領取
王同學 131****2015 剛剛成功領取
張同學 133****4652 剛剛成功領取
李同學 135****8607 剛剛成功領取
楊同學 132****5667 剛剛成功領取
岳同學 134****6652 剛剛成功領取
梁同學 157****2950 剛剛成功領取
劉同學 189****1015 剛剛成功領取
張同學 155****4678 剛剛成功領取
鄒同學 139****2907 剛剛成功領取
董同學 138****2867 剛剛成功領取
周同學 136****3602 剛剛成功領取
相關推薦HOT