<strike id="ca4is"><em id="ca4is"></em></strike>
  • <sup id="ca4is"></sup>
    • <s id="ca4is"><em id="ca4is"></em></s>
      <option id="ca4is"><cite id="ca4is"></cite></option>
    • 二維碼
      企資網

      掃一掃關注

      當前位置: 首頁 » 企資快報 » 服務 » 正文

      HashMap的設計與優化

      放大字體  縮小字體 發布日期:2021-08-19 02:00:58    作者:媒體小英    瀏覽次數:38
      導讀

      前言手執煙花以謀生 心懷詩意以謀愛不論我是否去記錄,在往昔與未來的無限歲月中,仍會有人奮起,有人沉淪,有人成為英雄,有人扮演小丑,有人挺身而出,有人迷惘沉淪。但你只需——“在繁華中自律,在落魄中自愈,

      前言

      手執煙花以謀生 心懷詩意以謀愛

      不論我是否去記錄,在往昔與未來的無限歲月中,仍會有人奮起,有人沉淪,有人成為英雄,有人扮演小丑,有人挺身而出,有人迷惘沉淪。但你只需——“在繁華中自律,在落魄中自愈,在謀生的路上不拋棄良知,在謀愛的路上不丟失最嚴,這次我站在風中,任你大霧四起。”


      HashMap的設計原理

      1. HashMap設計思路:
      1. Map是一種以鍵值對存儲數據的容器,而 HashMap 則是借助了鍵值 Key 的 hashcode 值來組織存儲,使得可以非常快速和高效地地根據鍵值 key 進行數據的存取。
      2. 對于鍵值對,HashMap 內部會將其封裝成一個對應的 Entry 對象,即 Entry 對象是鍵值對的組織形式;
      3. 對于每個對象而言,JVM 都會為其生成一個 hashcode 值。HashMap 在存儲鍵值對 Entry 的時候,會根據 Key 的 hashcode 值,以某種映射關系,決定應當將這對鍵值對 Entry 存儲在 HashMap 中的什么位置上;
      4. 當通過 Key 值取數據的時候,然后根據 Key 值的 hashcode 和 內部映射條件,直接定位到 Key 對應的 Value 值存放在什么位置,可以非常高效地將 Value 值取出。

      HashMap 的哈希函數設計

      hash 函數是先拿到 key 的 hashcode,是一個32位的 int 值,然后讓 hashcode 的高16位和低16位進行異或操 作

      也叫擾動函數,這么設計有二點原因

      1. 一定要盡可能降低 hash 碰撞,越分散越好;
      2. 算法一定要盡可能高效,因為這是高頻操作, 因此采用位運算;

      什么是Hash?

          Hash,一般翻譯做“散列”,也有直接音譯為“哈希”的,就是把任意長度的 `輸入`,通過散列算法變換成固定長度的 `輸出`,該輸出就是散列值。ok,這樣的定義可能比較抽象。咱們結合上面提到的方案二的例子一句一句解釋。
    • 比如:人的姓名就是一個任意長度的輸入。Z-張三 11; L-李四 22;W-王五 33
    • 然后,直接去Z分類里邊兒找,一發入魂。但是如果出現很多姓名的首字母是Z的人,比如Z-趙六 44、Z-周七 55,當我存的電話多起來,我一樣需要找好多次。——我按照姓名的首字母的大寫去進行一個分類,這個劃分的方式我們可以看成是散列算法。
    • 最后,在本子上以姓名的首字母劃分,并記錄電話號碼——固定長度的輸出,即我把所有的電話全部存入了26個分類中。那么這26個字母就是散列值。

      ? HashMap 的數據結構(JDK 1.8)

      本文說的是 JDK1.8 版本的,內部使用數組 + 鏈表紅黑樹

    • 在 Jdk1.8 中 HashMap 的實現方式做了一些改變,但是基本思想還是沒有變得,只是在一些地方做了 優化,下面來看一下這些改變的地方:數據結構的存儲由數組+鏈表的方式,變化為 數組+鏈表+紅黑樹的存儲方式,當鏈表長度超過 閾值(8) 時,將 鏈表轉換為紅黑樹。在性能上進一步得到提升。
    • 數組:數組存儲區間是連續的,占用內存嚴重,故空間復雜度很大。但數組的二分查找時間復雜度小,為O(1);數組的特點是:尋址容易,插入和刪除困難; 空間復雜度:指的是執行算法所需要的內存空間 時間復雜度:執行算法所需要的計算工作量
    • 鏈表:鏈表存儲區間離散,占用內存比較寬松,故空間復雜度很小,但時間復雜度很大,達O(N)。鏈表的特點是:尋址困難,插入和刪除容易。
    • 紅黑樹:

      JDK1.8 對 HashMap 主要做了哪些優化呢?

      1. 數組 + 鏈表改成了數組 + 鏈表或紅黑樹;
      2. 鏈表的插入方式從頭插法改成了尾插法,簡單說就是插入時,如果數組位置上已經有元素,1.7 將新元 素放到數組中,原始節點作為新節點的后繼節點,1.8 遍歷鏈表,將元素放置到鏈表的最后;
      3. 擴容的時候 1.7 需要對原數組中的元素進行重新 hash 定位在新數組的位置,1.8 采用更簡單的判斷邏 輯,位置不變或索引 + 舊容量大小;
      4. 在插入時,1.7 先判斷是否需要擴容,再插入,1.8 先進行插入,插入完成再判斷是否需要擴容;

      ?為什么要做這幾點優化

      1. 防止發生 hash 沖突,鏈表長度過長,將時間復雜度由 O(n) 降為 O(logn) ;
      2. 因為 1.7 頭插法擴容時,頭插法會使鏈表發生反轉,多線程環境下會產生環; A 線程在插入節點 B,B 線程也在插入,遇到容量不夠開始擴容,重新 hash,放置元素,采用頭插法, 后遍歷到的 B 節點放入了頭部,這樣形成了環,如下圖所示:

      1.7 的擴容調用 transfer 代碼,如下所示:

      void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;for (Entry<K,V> e : table) {while(null != e) {Entry<K,V> next = e.next;if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);} int i = indexFor(e.hash, newCapacity);e.next = newTable[i]; //A線程如果執行到這一行掛起,B線程開始進行擴容newTable[i] = e;e = next;}}}  
      1. 擴容的時候為什么 1.8 不用重新 hash 就可以直接定位原節點在新數據的位置 這是由于擴容是擴大為原數組大小的 2 倍,用于計算數組位置的掩碼僅僅只是高位多了一個 1,怎么理 解呢? 擴容前長度為 16,用于計算 (n-1) & hash 的二進制 n-1 為 0000 1111,擴容為 32 后的二進制就高位多 了 1,為 0001 1111。 因為是 & 運算,1 和任何數 & 都是她本身,那就分二種情況,如下圖:原數據 hashcode 高位第 4 位為 0 和高位為 1 的情況; 第四位高位為 0,重新 hash 數值不變,第四位為 1,重新 hash 數值比原來大 16(舊數組的容量)
    •  
      (文/媒體小英)
      免責聲明
      本文僅代表作發布者:媒體小英個人觀點,本站未對其內容進行核實,請讀者僅做參考,如若文中涉及有違公德、觸犯法律的內容,一經發現,立即刪除,需自行承擔相應責任。涉及到版權或其他問題,請及時聯系我們刪除處理郵件:weilaitui@qq.com。
       

      Copyright ? 2016 - 2025 - 企資網 48903.COM All Rights Reserved 粵公網安備 44030702000589號

      粵ICP備16078936號

      微信

      關注
      微信

      微信二維碼

      WAP二維碼

      客服

      聯系
      客服

      聯系客服:

      在線QQ: 303377504

      客服電話: 020-82301567

      E_mail郵箱: weilaitui@qq.com

      微信公眾號: weishitui

      客服001 客服002 客服003

      工作時間:

      周一至周五: 09:00 - 18:00

      反饋

      用戶
      反饋

      午夜久久久久久网站,99久久www免费,欧美日本日韩aⅴ在线视频,东京干手机福利视频
        <strike id="ca4is"><em id="ca4is"></em></strike>
      • <sup id="ca4is"></sup>
        • <s id="ca4is"><em id="ca4is"></em></s>
          <option id="ca4is"><cite id="ca4is"></cite></option>
        • 主站蜘蛛池模板: yy6080久久亚洲精品| 国产天堂亚洲精品| 台湾三级香港三级经典三在线| 久久国产免费福利永久| 麻豆国产精品免费视频| 最新69国产成人精品视频69| 国产真实乱子伦精品视手机观看| 亚洲伦理一区二区| jizzjizz护士| 日韩精品无码免费专区网站| 国产成人亚洲综合| 久久亚洲sm情趣捆绑调教| 里番牝教师~淫辱yy608| 把极品白丝班长啪到腿软| 四虎www成人影院| 一区二区精品在线观看| 男人的天堂视频网站清风阁| 在线免费h视频| 亚洲国产午夜精品理论片| 午夜小视频免费| 日本精品高清一区二区| 四虎影视永久免费观看| 一本伊在人香蕉线观新在线| 狠狠综合亚洲综合亚洲色| 国产裸体美女永久免费无遮挡| 亚洲午夜久久久影院| 黑人解禁濑亚美莉| 日产精品卡二卡三卡四卡乱码视频| 啊灬啊灬啊灬快灬深用口述| ssss国产在线观看| 欧美特黄a级高清免费大片| 国产电影入口麻豆| 久久午夜无码鲁丝片午夜精品| 美女的胸www又黄的网站| 天天做天天躁天天躁| 亚洲国产另类久久久精品黑人| 麻豆女神吴梦梦| 彩虹男gary网站| 亚洲欧美日韩中文高清ww| 黑人操日本美女| 成人欧美一区二区三区的电影|