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

千鋒教育-做有情懷、有良心、有品質(zhì)的職業(yè)教育機構

手機站
千鋒教育

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

千鋒教育

掃一掃進入千鋒手機站

領取全套視頻
千鋒教育

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

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

Map、Dictionary、HashTable有哪些異同?

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

一、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)方式。

二叉樹哈希(hash)表

二叉樹查找的時間復雜度為 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é)點,該樹才是完全二叉樹,否則就不是完全二叉樹。

聲明:本站稿件版權均屬千鋒教育所有,未經(jīng)許可不得擅自轉(zhuǎn)載。
10年以上業(yè)內(nèi)強師集結(jié),手把手帶你蛻變精英
請您保持通訊暢通,專屬學習老師24小時內(nèi)將與您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
什么是crm管理?

一、crm管理概念 CRM管理也叫客戶管理,亦即客戶關系管理(Customer Relationship Management)的簡稱。CRM管理的主要含義就是通過對客戶詳細資...詳情>>

2023-10-11 05:28:00
單調(diào)棧什么時候從后向前遍歷,什么時候從前向后遍歷?

一、單調(diào)棧什么時候從后向前遍歷,什么時候從前向后遍歷如果是求右邊的名列前茅個最大,那么就是從右向左遍歷,構建單調(diào)遞增棧。如果是求右邊的...詳情>>

2023-10-11 05:23:50
操作系統(tǒng)幾種主要的頁面置換算法分別是用什么數(shù)據(jù)結(jié)構實現(xiàn)的?

一、操作系統(tǒng)幾種主要的頁面置換算法算法通常只是描述解決問題的一個步驟,具體用什么數(shù)據(jù)結(jié)構實現(xiàn)則是視情況而定。LRU“實現(xiàn)起來比較困難,且...詳情>>

2023-10-11 05:20:02
floyd算法為什么要用鄰接矩陣實現(xiàn)而不用鄰接表?

一、floyd算法為什么要用鄰接矩陣實現(xiàn)而不用鄰接表floyd算法要用鄰接矩陣實現(xiàn)而不用鄰接表是因為需要O(1)時間查詢?nèi)我鈨蓚€頂點的邊權值,在這一...詳情>>

2023-10-11 05:00:46
哈希樹hashtree常應用在哪些現(xiàn)實場景?

一、哈希樹hashtree常應用現(xiàn)實場景1、場景一:安全加密日常用戶密碼加密通常使用的都是 md5、sha等哈希函數(shù),因為不可逆,而且微小的區(qū)別加密之...詳情>>

2023-10-11 04:55:54