一加Ace2 Pro官宣：普及16G內存 引領24G
一加官方今天繼續為本月發布的新機一加Ace2 Pro帶來預熱，公布了內存方面的信息。“淘汰 8GB ，12GB 起步，16GB 普及，24GB 引領，還有呢？#一加Ace2Pro#，2023 年 8 月，敬請期待。”同時
話說這一日，編程語言聯合國準備舉辦一次大會，主題為哈希表，給各大編程語言帝國都發去了邀請函。
很快就到了大會這一天。
聯合國秘書長開場發言：“諸位，為促進技術交流與發展，增強各帝國友誼，聯合委員會特設此盛會，感謝諸位的捧場”
會場傳來一陣鼓掌聲······
秘書長繼續發言：“本次大會的主題是哈希表，程序員們使用最多的數據容器之一，各大編程語言帝國相信都有實現。今天的大會就圍繞哈希表分為幾個議題討論，首先是第一個議題：存儲結構與沖突解決”
來自GoLang帝國的map率先發言：“哈希表，哈希表，首先得是個表嘛，所以最基本的要用一個數組來存儲，數組中的每一個元素叫做bucket。至于hash沖突嘛，就用鏈表來解決嘛”
圖片
GoLang帝國的map說完，有人站了起來：“英雄所見略同！在下C++帝國的unordered_map，我們基本上也是選擇的這種方法”
此時，Python帝國的代表提出了質疑：“鏈表確實可以解決沖突，不過嘛，這要是沖突太多，鏈表太長，搜尋起來豈不費時？”
GoLang帝國的map和C++帝國的unordered_map面面相覷，不知如何應對。
“鏈表太長的話，那就轉成樹結構！”，就在這時，又有人站了起來。
見有人起身，Python帝國代表轉身問道：“在下乃Python帝國的字典dict，敢問閣下怎么稱呼”
“我是Java帝國的HashMap，和前面兩位兄臺的策略大體相同，只是在沖突過多，具體來說鏈表長度超過8的時候就轉換成紅黑樹的結構，以此加快查找”
圖片
說完，map、unordered_map松了一口氣，和HashMap一起坐下了。
dict繼續發問：“在座的都是這個思路，用鏈表解決沖突？”
說完，另外一位代表站了起來，“等等，我們C#帝國的HashTable就沒用鏈表！”
dict露出了滿意的表情，“那你們是怎么解決沖突的呢？”
“咱HashTable內部使用的是雙重散列法，咱內部不止一種哈希計算方式，一次Hash沖突，咱就換一個再算，直到找到有空位的地方存儲”，HashTable回答到。
dict看起來有些失望，估計這也不是他所用的方式。
“你問了半天，還沒說你們Python是怎么處理沖突的呢？”，Java帝國的HashMap開口了。
“是啊，是啊”，其他代表也跟著起哄。
見眾人起哄，dict只好應答：“鏈表法固然不錯，不過需要在插入數據過程中動態分配內存構建鏈表節點，開銷不小，我們沒有采用。”
“那到底用了啥，你倒是說啊，快急死我了”，C++的unordered_map有些急了。
“我們用的是一種叫開放尋址法的策略，如果發現了沖突，就按照制定的策略從這個位置往后找，直到找到有空的位置存儲”，dict{}繼續說到。
圖片
“哪有那么簡單的事，你把別人的位置占了，那對應那個位置的數據來了怎么辦？還有查找怎么找？刪除怎么處理？這不全亂套了嗎”，unordered_map追問不舍。
“是這樣的，按照我們既定的規則，在查找的時候就需要額外做一些工作，另外刪除的時候也不能直接刪除，否則會破壞規則鏈條·····”，接下來一段時間，dict給大家仔細介紹了他們的處理思路。
“你這個也太麻煩了，不如我們鏈表法來的清晰明了”
“這怎么就麻煩了？這好處不顯而易見嘛？”，dict也不甘示弱。
這時，秘書長打斷了大家的爭辯：“諸位，諸位，靜一靜，靜一靜，咱們這個議題到此為止，進入下一個議題：哈希到位置映射”
急性子的C++帝國代表unordered_map第一個說話：“這有什么好討論的，不就是用hash值對哈希表數組長度進行一個求模運算嗎？”
圖片
“就是，這有什么好討論的”，C#帝國的HashTable也附和到。
“哎，此言差矣，我就沒用取模運算”，眾人望去，這Python帝國的dict又要鬧什么新鮮玩意。
GoLang帝國的map問道：“老哥用的什么辦法，別賣關子了，快說來聽聽”
dict掃了眾人一眼說到，“我的辦法就是：”
圖片
這是怎么個映射法？眾代表皆摸不著頭腦，議論紛紛，唯有Java帝國的HashMap聽聞微微一笑。
dict見狀問道：“HashMap兄臺，莫非知曉其中玄機？”
只見HashMap不緊不慢的站了起來說到：“哈希表長度是2的冪次，減1之后的二進制均變成了1，比如長度16，減1變成15，也就是二進制1111。再進行與運算，相當于取了哈希值的低位，直接映射到對應的數組位置，與運算比取模運算要快不少。不瞞諸位，我HashMap中也是使用的這種方式，此乃雕蟲小技，不值得炫耀”
圖片
眾代表聽完紛紛點頭稱贊，dict不知何時卻已坐下。
C#的HashTable問道：“這樣直接取低幾位，會不會造成Hash值到數組的映射不均勻，拿你舉的例子來說，18的二進制是0001 0010，34的二進制是0010 0010，他們的低4位都一樣，和1111與上以后都是0010，也就是都該存到數組的2號位，這豈不是一定程度上的增加了沖突的概率嗎？”
突如其來的質疑并沒有讓HashMap慌亂，反而是從容不迫的解釋到：“C#代表的這個問題提的非常好，不知dict兄臺是如何處理的。我們的方案是在進行與運算映射之前，對hash值進行一個處理，具體來說就是將其高16位與低16位進行一個異或運算，如此一來，最終參與與運算的部分就融合了原始hash的全部信息，而不僅僅是低位。”
圖片
眾代表聽完再次點頭稱贊。
秘書長打破了平靜，“看來大家收獲都頗豐，咱們接著下一個話題吧：初始容量與擴容”
眾代表這一次皆不爭先，互相觀望。
秘書長見狀說到：“沒人主動，那我可就要點名了······”
“那就我先吧”，Java帝國的HashMap站了起來，“我的默認初始容量是16，有一個叫負載因子的參數，默認是0.75。我的策略是，如果內部數組的空間使用了超過75%，那就要準備擴容了，否則后續Hash沖突的概率就會很大。哦對了，擴容時容量得是2的指數次方，原因前面已經交代了”
圖片
dict第二個起身：“嗯，差不多，我的默認初始容量是8，擴容的時候也是要求是2的指數次方，另外我的負載因子是2/3，擴容時機比這位HashMap老哥更早一些”
C#帝國代表HashTable聽聞也起身發言：“我的初始容量是3，至于負載因子嘛，我經過大量實驗測試，得出的數據在兩位之間，是0.72。容量大小方面我就沒有2的指數次方的要求了，而是要求一個素數。之所以要求素數的原因，是因為我使用的求模運算進行的映射，使用素數的話，沖突會少一些。”
這時，C++帝國代表unordered_map也說話了，“巧了！我也是素數哎，你看，我提前把容量都算好存起來了，到時候擴容就挨個取就行了。”
圖片
時間過的很快，在大家熱情的討論中，一上午時間很快就結束了。
大會臨近尾聲，秘書長致辭宣布：“感謝各位代表積極探討，大會取得圓滿成功，本次大會到此結束，咱們下次再會！”
會場再次傳來一陣熱烈的鼓掌聲······
然而就在此時，會場外突然傳來一個聲音：“舉辦如此盛會，怎能少了我”
眾人望去，皆嘆：“他果然還是來了”
本文鏈接：http://www.tebozhan.com/showinfo-26-87483-0.html哈希表哪家強？幾大編程語言吵起來了！
聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。郵件：2376512515@qq.com
上一篇： 事務鉤子函數，打造高效支付系統
下一篇： Java 中的 HTTP 客戶端庫OkHttp、Apache HttpClient和HttpUrlConnection
Copyright ? 2016-2023 天津谷騏科技有限公司 版權所有 sitemap.xml
違法及侵權請聯系：2376512515@qq.com 津ICP備18001702號
津公網安備 12010102000574號