日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問(wèn)題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案
作為Java開(kāi)發(fā)，知道HashMap底層存儲(chǔ)原理總不會(huì)害你

概念

  • HasnMap是基于map接口實(shí)現(xiàn)，元素以鍵值對(duì)的方式存儲(chǔ)，并且鍵和值都可以使用null，因?yàn)?key不允許重復(fù)，因此只能有一個(gè)鍵為null
  • HaasnMap是 無(wú)序不重復(fù)的，而且HashMap是線程不安全 的
  • JDK7HashMap的數(shù)據(jù)結(jié)構(gòu)為：數(shù)組+鏈表
  • JDK8HashMap的數(shù)據(jù)結(jié)構(gòu)為：數(shù)組 + 鏈表 + 紅黑樹(shù)

存儲(chǔ)的優(yōu)點(diǎn)

  • 數(shù)組的特點(diǎn)：查詢效率高，插入和刪除效率低
  • 鏈表的特點(diǎn)：查詢效率 低，插入和刪除效率高
  • 在HasnMap底層使用數(shù)組加 (鏈表或紅黑樹(shù)) 的結(jié)構(gòu)完美的解決了數(shù)組和鏈表的問(wèn)題，使的查詢和插入，刪除的效率都 很高
  • HashMap的散列表是懶加載機(jī)制，在第一次put的時(shí)候才會(huì)創(chuàng)建

HashMap存儲(chǔ)元素的過(guò)程

首先將k、v封裝到Node對(duì)象當(dāng)中(節(jié)點(diǎn))

創(chuàng)新互聯(lián)公司是一家集網(wǎng)站建設(shè),鄒城企業(yè)網(wǎng)站建設(shè),鄒城品牌網(wǎng)站建設(shè),網(wǎng)站定制,鄒城網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營(yíng)銷,網(wǎng)絡(luò)優(yōu)化,鄒城網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競(jìng)爭(zhēng)力。可充分滿足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶成長(zhǎng)自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。

調(diào)用k的hasnCode()方法取出hash值;通過(guò)hashcode值和數(shù)組長(zhǎng)度取模得到元素存儲(chǔ)的下標(biāo)

此時(shí)分為兩種情況

  • 下標(biāo)位置上沒(méi)有元素，直接把元素方進(jìn)入
  • 該所以已有元素，判斷該位置的元素和當(dāng)前元素是否相等，使用equals來(lái)比較(默認(rèn)是比較兩個(gè)對(duì)象的地址)。如果兩只相等則直接覆蓋，如果不等則(Hash碰撞)在原元素下面使用鏈表的結(jié)構(gòu)存儲(chǔ)該元素(如果已存在鏈表，則插在鏈表尾部)，每個(gè)元素節(jié)點(diǎn)都有一個(gè)next屬性指向下一個(gè)節(jié)點(diǎn)，這就由數(shù)組結(jié)構(gòu)變成了數(shù)組+鏈表;因?yàn)殒湵碇性靥嗟臅r(shí)候回影響查找效率，所以當(dāng)鏈表的元素個(gè)數(shù)達(dá)到 8 的時(shí)候使用鏈表存儲(chǔ)就轉(zhuǎn)變成了使用紅黑樹(shù)存儲(chǔ)(當(dāng)紅黑樹(shù)上的節(jié)點(diǎn)數(shù)量小于 6 個(gè)，會(huì)重新把紅黑樹(shù)變成單向鏈表數(shù)據(jù)結(jié)構(gòu))，原因就是紅黑樹(shù)是平衡二叉樹(shù)，在查找性能方面比聊表要高

HashMap取值的實(shí)現(xiàn)

  • 先調(diào)用k的hashCode()方法得出哈希值，并通過(guò)hash算法轉(zhuǎn)換成數(shù)組的下標(biāo)
  • 通過(guò)hash值轉(zhuǎn)換成數(shù)組下標(biāo)后，通過(guò)數(shù)組定位到下標(biāo)位置，如果改位置上什么都沒(méi)有，范圍null;如果該位置上有單向鏈表，那么就拿參數(shù)K和單向鏈表上的每一個(gè)節(jié)點(diǎn)的K進(jìn)行equals比較，如果所有equals都返回false，則返回null，如果有一個(gè)節(jié)點(diǎn)的K和參數(shù)K通過(guò)equals返回true，那么此時(shí)該節(jié)點(diǎn)的value就是要獲取的value值

擴(kuò)容

  • HashMap中有兩個(gè)重要參數(shù)，初始容量大小和負(fù)載因子，在HashMap剛開(kāi)始初始化的時(shí)候，使用默認(rèn)的構(gòu)造方法，會(huì)返回一個(gè)空的table，并且 thershold(擴(kuò)容閾值)為 0 ，因此第一次擴(kuò)容的時(shí)候默認(rèn)值就會(huì)是 16 ，負(fù)載因子默認(rèn)為 0.75 ，用數(shù)組容量乘以負(fù)載因子得到一個(gè)值，一旦數(shù)組中存儲(chǔ)的元素個(gè)數(shù)超過(guò)這個(gè)值就會(huì)調(diào)用rehash方法將數(shù)組容量增加到原來(lái)的兩倍，threshold也會(huì)變?yōu)樵瓉?lái)的兩倍
  • 在做擴(kuò)容的時(shí)候會(huì)生成一個(gè)新的數(shù)組，原來(lái)的所有數(shù)據(jù)需要重新計(jì)算哈希碼值重新分配到新的數(shù)組，所以擴(kuò)容的操作非常消耗性能。所以，如果知道要存入的數(shù)據(jù)量比較大的話，可以在創(chuàng)建的時(shí)候先指定一個(gè)比較大的數(shù)據(jù)容量
  • 也可以引申到一個(gè)問(wèn)題HashMap是先插入還是先擴(kuò)容：HashMap初始化后首次插入數(shù)據(jù)時(shí)，先發(fā)生resize擴(kuò)容再插入數(shù)據(jù)，之后每當(dāng)插入的數(shù)據(jù)個(gè)數(shù)達(dá)到threshold時(shí)就會(huì)發(fā)生resize，此時(shí)是先插入數(shù)據(jù)再resize

HashMap中的擴(kuò)容是在元素插入之前進(jìn)行的擴(kuò)容還是元素插入之后進(jìn)行的擴(kuò)容

在 JDK1.7中是在元素插入 前 進(jìn)行的擴(kuò)容，在JDK1.8 中是先加入元素 后 再判斷是否進(jìn)行擴(kuò)容

存儲(chǔ)元素超過(guò)閾值一定會(huì)進(jìn)行擴(kuò)容嗎

在 JDK1.7 中不一定，只有存儲(chǔ)元素超過(guò)閾值并且當(dāng)前存儲(chǔ)位置不為null，才會(huì)進(jìn)行擴(kuò)容，在 JDK1.8 中會(huì)進(jìn)行擴(kuò)容

HashMap和HashTable區(qū)別

線程方面

  • HashMap是非線程安全的，HashTable是線程安全的。 Hashtable的實(shí)現(xiàn)方法里面都添加了synchronized關(guān)鍵字來(lái)確保線程同步，因此相對(duì)而言HashMap性能會(huì)高一些，我們平時(shí)使用時(shí)若無(wú)特殊需求建議使用HashMap，在多線程環(huán)境下若使用HashMap需要使用Collections.synchronizedMap()方法來(lái)獲取一個(gè)線程安全的集合
  • HashMap的key可以為null，HashTable的key不可為null
  • HashMap是對(duì)Map接口的實(shí)現(xiàn)，HashTable實(shí)現(xiàn)了Map接口和Dictionary抽象類
  • HashMap的初始容量為 16 ，Hashtable初始容量為 11 ，兩者的填充因子默認(rèn)都是 0.75 ，HashMap擴(kuò)容時(shí)是當(dāng)前容量翻倍即：capacity * 2，- Hashtable擴(kuò)容時(shí)是容量翻倍+1即：capacity * 2+1

HashMap中的hashcode怎么生成

調(diào)用對(duì)象key的hashCode方法，再對(duì)這個(gè)hashcode方法進(jìn)行一些右移以及異或運(yùn)算(使的hashCode的高位和低位都參與到運(yùn)算中);通過(guò)右移和異或運(yùn)算可以使hashMap的散列化更強(qiáng)，提高h(yuǎn)ashMap的get方法的效率

為什么使用HashCode

HashCode的存在主要是為了查找的快捷性, HashCode是用來(lái)在散列存儲(chǔ)結(jié)構(gòu)中確定對(duì)象的存儲(chǔ)地址的 ( 用hashcode來(lái)代表對(duì)象在hash表中的位置 ) , hashCode存在的重要的原因之一就是在HashMap(HashSet其實(shí)就是HashMap)中使用(其實(shí)Object類的hashCode方法注釋已經(jīng)說(shuō)明了)，HashMap之所以速度 快 ，因?yàn)樗褂玫氖?散列表 ，根據(jù)key的hashcode值生成數(shù)組下標(biāo)(通過(guò)內(nèi)存地址直接查找，不需要判斷，但是需要多出很多內(nèi)存，相當(dāng)于以空間換時(shí)間)

equals方法和hashcode的關(guān)系

歸納總結(jié)：

  • 若重寫(xiě)了equals(Object obj)方法，則有必要重寫(xiě)hashCode()方法
  • 若兩個(gè)對(duì)象equals(Object obj)返回true，則hashCode()有必要也返回相同的int數(shù)
  • 若兩個(gè)對(duì)象equals(Object obj)返回false，則hashCode()不一定返回不同的int數(shù)
  • 若兩個(gè)對(duì)象hashCode()返回相同int數(shù)，則equals(Object obj)不一定返回true
  • 若兩個(gè)對(duì)象hashCode()返回不同int數(shù)，則equals(Object obj)一定返回false
  • 同一對(duì)象在執(zhí)行期間若已經(jīng)存儲(chǔ)在集合中，則不能修改影響hashCode值的相關(guān)信息，否則會(huì)導(dǎo)致內(nèi)存泄露問(wèn)題

key為null怎么辦

key為null的時(shí)候，只會(huì)放在hashMap的0位置(即key的hashCode為0，對(duì)數(shù)組長(zhǎng)度取余后的下標(biāo)也是0)，不會(huì)有鏈表 在HashMap源碼中對(duì)put方法對(duì)null做了處理，key為null的判斷后進(jìn)入putForNullKey(V value)這個(gè)方法，李里面for循環(huán)是在talbe[0]鏈表 中查找key為null的元素，如果找到，則將value重新賦值給這個(gè)元素的value，并返回原來(lái)的value。如果沒(méi)找到則將這個(gè)元素添加到talbe[0]鏈表的表頭

 
 
 
 
    
  
  
  
  
  1. /**
    2. 
  
  
  
  
  2.  * HashMap的put方法
    3. 
  
  
  
  
  3.  */
    4. 
  
  
  
  
  4. public V put(K key, V value) {
    5. 
  
  
  
  
  5.     if (table == EMPTY_TABLE) {
    6. 
  
  
  
  
  6.         inflateTable(threshold);
    7. 
  
  
  
  
  7.     }
    8. 
  
  
  
  
  8. 
  
  
  
  
  9.     // key為null調(diào)用putForNullKey(value)
    10. 
  
  
  
  
  10.     if (key == null) return putForNullKey(value);
    11. 
  
  
  
  
  11. 
  
  
  
  
  12.     int hash = hash(key);
    13. 
  
  
  
  
  13.     int i = indexFor(hash, table.length);
    14. 
  
  
  
  
  14.     for (Entry e = table[i]; e != null; e = e.next) {
    15. 
  
  
  
  
  15.         Object k;
    16. 
  
  
  
  
  16.         if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
    17. 
  
  
  
  
  17.             V oldValue = e.value;
    18. 
  
  
  
  
  18.             e.value = value;
    19. 
  
  
  
  
  19.             e.recordAccess(this);
    20. 
  
  
  
  
  20.             return oldValue;
    21. 
  
  
  
  
  21.         }
    22. 
  
  
  
  
  22.     }
    23. 
  
  
  
  
  23.     modCount++;
    24. 
  
  
  
  
  24.     addEntry(hash, key, value, i);
    25. 
  
  
  
  
  25.     return null;
    26. 
  
  
  
  
  26. }
    27. 
  
  
  
  
  27. 
  
  
  
  
  28. /**
    29. 
  
  
  
  
  29.  * Offloaded version of put for null keys
    30. 
  
  
  
  
  30.  */
    31. 
  
  
  
  
  31. private V putForNullKey(V value) {
    32. 
  
  
  
  
  32.     // for循環(huán)處理key為空的情況
    33. 
  
  
  
  
  33.     for (Entry e = table[0]; e != null; e = e.next) {
    34. 
  
  
  
  
  34.         if (e.key == null) {
    35. 
  
  
  
  
  35.             V oldValue = e.value;
    36. 
  
  
  
  
  36.             e.value = value;
    37. 
  
  
  
  
  37.             e.recordAccess(this);
    38. 
  
  
  
  
  38.             return oldValue;
    39. 
  
  
  
  
  39.         }
    40. 
  
  
  
  
  40.     }
    41. 
  
  
  
  
  41.     modCount++;
    42. 
  
  
  
  
  42.     addEntry(0, null, value, 0);
    43. 
  
  
  
  
  43.     return null;
    44. 
  
  
  
  
  44. }
    45.

本文名稱：作為Java開(kāi)發(fā)，知道HashMap底層存儲(chǔ)原理總不會(huì)害你
網(wǎng)址分享：http://www.5511xx.com/article/dpdgcci.html