<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>
    • 二維碼
      企資網(wǎng)

      掃一掃關(guān)注

      當(dāng)前位置: 首頁 » 企資快訊 » 匯總 » 正文

      Java中HashMap常見問題___擴容_

      放大字體  縮小字體 發(fā)布日期:2023-02-25 15:29:01    作者:江烽坤    瀏覽次數(shù):110
      導(dǎo)讀

      寫在前邊HashMap屬于比較常用的數(shù)據(jù)結(jié)構(gòu)了,面試過程中也經(jīng)常會被問到,本篇就知識點,展開問答式分析,重點聊聊hash沖突、擴容死鏈、容量為2的n次方等問題~1.7和1.8有什么不同1.7是 數(shù)組+鏈表 1.8是 數(shù)組+鏈表【超

      寫在前邊
    • HashMap屬于比較常用的數(shù)據(jù)結(jié)構(gòu)了,面試過程中也經(jīng)常會被問到,本篇就知識點,展開問答式分析,重點聊聊hash沖突、擴容死鏈、容量為2的n次方等問題~1.7和1.8有什么不同

      1.7是 數(shù)組+鏈表 1.8是 數(shù)組+鏈表【超過閾值會變成紅黑樹】

      如何解決Hash沖突問題擴容條件
      1. 鏈表長度超過8
      2. 元素個數(shù)超過數(shù)組個數(shù)的75%
      樹化規(guī)則條件
      1. 鏈表長度超過8
      2. 此時看看數(shù)組長度是否超過64,超過就進行樹化,否則只是單純擴容
      為什么需要樹化

      其實一般正常的元素,都是不會超過閾值的,只有插入一堆重復(fù)的元素,hash值一樣,才可能達到閾值,這個簡稱Dos攻擊 而元素一旦多起來,鏈表查找的效率就遠(yuǎn)不及紅黑樹了

      ?♂?樹化一定更好嗎?

      不是的,維護紅黑樹需要占用比鏈表更多的空間,而且當(dāng)鏈表長度足夠短的時候,鏈表查找的效率反而比紅黑樹更高??

      為什么選擇0.75和8
    • hash 值如果足夠隨機,則在 hash 表內(nèi)按泊松分布,在負(fù)載因子 0.75 的情況下,長度超過 8 的鏈表出現(xiàn)概率是 0.00000006,樹化閾值選擇 8 就是為了讓樹化幾率足夠小退化規(guī)則擴容的時候鏈表長度<=6remove節(jié)點的時候

      root、root.left、root.right、root.left.left 有一個為 null ,也會退化為鏈表(看的是移除之前的情況)

      為什么需要二次哈希

      先獲得key的hashCode的值 h,然后 h 和 h右移16位 做異或運算。
      實質(zhì)上是把一個數(shù)的末x位低16位與他的高16位做異或運算,因為在前面 (n - 1) & hash 的計算中,hash變量只有末x位會參與到運算。使高16位也參與到hash的運算能減少沖突

      為什么要用2的n次方為了方便 & 操作

      只有2的n次方,去-1,才能用 & 替代 %

      為了方便擴容

      擴容時重新計算索引效率更高: hash & oldCap == 0 的元素留在原來位置 否則新位置 = 舊位置 + oldCap (oldCap:原始的容量)

      因為HashMap的初始容量是2的次冪,擴容之后的長度是原來的二倍,新的容量也是2的次冪,所以,元素,要么在原位置,要么在原位置再移動2的次冪。

      看下這張圖,n為table的長度 圖a表示擴容前的key1和key2兩種key確定索引的位置 圖b表示擴容后key1和key2兩種key確定索引位置。

      元素在重新計算hash之后,因為n變?yōu)?倍,那么n-1的mask范圍在高位多1bit(紅色),因此新的index就會發(fā)生這樣的變化:

      所以在擴容時,只需要看原來的hash值新增的那一位是0還是1就行了【直接 hash & oldCap,就能知道是0還是1了】 是0的話索引沒變,是1的話就變成原索引+oldCap

      不用2的n次方可以嗎

      可以的,因為2的n次方也會有缺陷,比如給定的值全是偶數(shù),無論如何hash之后取模,都是偶數(shù),分布就不均勻

      此時如果用質(zhì)數(shù)作為容量的話,就會分布得比較均勻

      注意

      二次 hash 是為了配合 容量是 2 的 n 次冪 這一設(shè)計前提,如果 hash 表的容量不是 2 的 n 次冪,則不必二次 hash

      容量是 2 的 n 次冪 這一設(shè)計計算索引效率更好,但 hash 的分散性就不好,需要二次 hash 來作為補償,沒有采用這一設(shè)計的典型例子是 Hashtable

      并發(fā)擴容丟失數(shù)據(jù)問題

      主要是第一個節(jié)點才會吧?因為第一個是new Node出來的

      jdk1.7 并發(fā)擴容死鏈問題

      jdk1.7中,采用的是頭插法,用一個e指針表示當(dāng)前要擴容的節(jié)點,next表示接下來要擴容的節(jié)點,一直頭插e更新e為next,直到e為null

      假設(shè)現(xiàn)在有兩個線程1和2,要擴容一個Map

      1. 線程1的局部變量e,指向了a節(jié)點,next指向b節(jié)點
      2. 線程2的局部變量也是如此,此時線程2先進行擴容,由于是頭插法,最終結(jié)果變成了 b->a
      3. 但此時來到線程1先進行,局部變量不會受改變,e還是指向a,next還是b,所以把a頭插,并且更新e為next,也就變成了b
      4. 線程1繼續(xù)頭插b,沒問題,結(jié)果變成了[b->a],看起來是沒問題了,但是接下來判斷e還沒有next:
      5. 發(fā)現(xiàn)e的next是a,又要繼續(xù)頭插a,插完a之后,發(fā)現(xiàn)a的next又是b,寄了這下,無限循環(huán)了


      原文鏈接:https://juejin.cn/post/7160661444143841288

    •  
      (文/江烽坤)
      免責(zé)聲明
      本文僅代表作發(fā)布者:江烽坤個人觀點,本站未對其內(nèi)容進行核實,請讀者僅做參考,如若文中涉及有違公德、觸犯法律的內(nèi)容,一經(jīng)發(fā)現(xiàn),立即刪除,需自行承擔(dān)相應(yīng)責(zé)任。涉及到版權(quán)或其他問題,請及時聯(lián)系我們刪除處理郵件:weilaitui@qq.com。
       

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

      粵ICP備16078936號

      微信

      關(guān)注
      微信

      微信二維碼

      WAP二維碼

      客服

      聯(lián)系
      客服

      聯(lián)系客服:

      在線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>
        • 主站蜘蛛池模板: 四虎地址8848最新章节| 爱豆传媒视频在线网址最新| 日本韩国一区二区| 夜夜精品无码一区二区三区| 国产偷国产偷亚洲高清日韩| 久久这里只有精品66| 国产男女野战视频在线看| 爽爽影院在线看| 壮汉紫黑粗大好深用力| 人人妻人人澡人人爽欧美一区| igao视频网站| 色偷偷狠狠色综合网| 无翼乌日本漫画| 四库影院永久在线精品| 中文国产日韩欧美视频| 美女脱精光给男生摸| 日韩欧美成人乱码一在线| 国产边打电话边被躁视频| 亚洲欧美一区二区三区四区 | 加勒比黑人在线| 一本色道久久综合网| 男女下面无遮挡一进一出| 在线视频一区二区三区四区| 亚洲永久精品ww47| wwwxx在线| 日韩国产成人精品视频| 四虎网站1515hh四虎免费| yellow高清在线观看完整视频在线| 狼群视频在线观看www| 国产精品白嫩在线观看| 乱系列中文字幕在线视频| 一级有奶水毛片免费看| 日韩高清中文字幕| 国产一级生活片| 一人上面一个吃我电影| 污视频免费在线观看| 国产激情视频在线播放| 亚洲乱码无限2021芒果| 91av在线电影| 日韩在线观看免费完整版视频| 国产一区三区二区中文在线|