【Java基礎(chǔ)】HashMap原理詳解

• HashMap的實(shí)現(xiàn)
• • 1. 數(shù)組
  • 2.線性鏈表
  • 3.紅黑樹(shù)
  • • 3.1概述
    • 3.2性質(zhì)
  • 4.HashMap擴(kuò)容死鎖
  • 5. BATJ一線大廠技術(shù)棧

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

• ConcurrentHashMap從JDK1.5開(kāi)始隨著java.util.concurrent包一起引入JDK，主要為了解決HashMap線程不安全，和HashTable效率不高的問(wèn)題
• HashMap在多線程編程中是線程不安全的，而HashTable使用Synchronized修飾方法而效率低
• ConcurrentHashMap是一個(gè)在多線程環(huán)境下，線程安全且高性能的HashMap解決方案
• 底層實(shí)現(xiàn)：數(shù)組+鏈表+紅黑樹(shù)（since JDK1.8）

@Testpublic void test() {ConcurrentHashMap<Integer, String> map = new ConcurrentHashMap<>();map.put(1, "a");map.put(2, "b");map.put(3, "c");Set<Map.Entry<Integer, String>> entrySet = map.entrySet();for (Map.Entry<Integer, String> entry : entrySet) {Integer key = entry.getKey();String value = entry.getValue();System.out.println(key + " " + value);}System.out.println(map.get(1));}

1. 數(shù)組

• 使用一段連續(xù)存儲(chǔ)單元存儲(chǔ)數(shù)據(jù)，對(duì)于指定下標(biāo)的查找，時(shí)間復(fù)雜度為O(1)，對(duì)于一般的插入刪除操作，涉及數(shù)組元素的移動(dòng)，其平均時(shí)間復(fù)雜度為O(n)
• 通過(guò)Object.hashCode()方法得到固定長(zhǎng)度哈希值，然后對(duì)數(shù)組長(zhǎng)度取余，得到Object在數(shù)組中的坐標(biāo)
• 默認(rèn)初始化長(zhǎng)度:16，數(shù)組長(zhǎng)度一定是2的倍數(shù)

2.線性鏈表

• 對(duì)于鏈表的新增、刪除操作，在查找到操作位置后，只需要處理結(jié)點(diǎn)間的引用即可，時(shí)間復(fù)雜度為O(1)
• 查找操作需要遍歷鏈表的所有結(jié)點(diǎn)，復(fù)雜度為O(n)
• 解決哈希沖突，避免數(shù)據(jù)被覆蓋

3.紅黑樹(shù)

3.1概述

• 當(dāng)哈希沖突嚴(yán)重時(shí)，鏈表冗長(zhǎng)導(dǎo)致效率低下
• 紅黑樹(shù)是一種接近平衡的二叉搜索樹(shù)，在每個(gè)結(jié)點(diǎn)上增加一個(gè)存儲(chǔ)位表示結(jié)點(diǎn)的顏色，可以是Red或Black。
• 通過(guò)對(duì)任何一條從根到葉子的路徑上，由于各個(gè)結(jié)點(diǎn)著色方式的限制，紅黑樹(shù)確保沒(méi)有一條路徑會(huì)比其他路徑長(zhǎng)出兩倍，因此接近平衡。
• 支持查找、插入、刪除等操作，平均時(shí)間復(fù)雜度為O(logn)

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-NnWwAoYR-1589878270141)(Untitled.png)]

3.2性質(zhì)

• 每個(gè)結(jié)點(diǎn)要么是紅的，要么是黑的
• 根結(jié)點(diǎn)是黑的
• 葉結(jié)點(diǎn)都是黑的
• 如果一個(gè)結(jié)點(diǎn)是紅的，那么兩個(gè)兒子都是黑的
• 對(duì)于任意結(jié)點(diǎn)而言，到葉結(jié)點(diǎn)的每條路徑都包含相同數(shù)目的黑結(jié)點(diǎn)
  

4.HashMap擴(kuò)容死鎖

• 擴(kuò)容因子：0.75
• 鏈表轉(zhuǎn)紅黑樹(shù)時(shí)，鏈表長(zhǎng)度為8

import java.util.HashMap; import java.util.Map; import java.util.concurrent.atomic.AtomicInteger;public class DevThread implements Runnable {private static Map<Integer, Integer> map = new HashMap<>();private static AtomicInteger atomicInteger = new AtomicInteger();@Overridepublic void run() {while (atomicInteger.get() < 1000 * 1000) {map.put(atomicInteger.get(), atomicInteger.get());atomicInteger.incrementAndGet();}} }public class MapDeadLock {public static void main(String[] args) {for (int i = 0; i <10 ; i++) {new Thread(new DevThread()).start();}} }

5. BATJ一線大廠技術(shù)棧

• 分布式架構(gòu)
• 微服務(wù)架構(gòu)
• 源碼分析
• 并發(fā)編程
• 性能優(yōu)化
• 數(shù)據(jù)結(jié)構(gòu)與算法
• 高并發(fā)實(shí)戰(zhàn)
• 工程化協(xié)作

總結(jié)

以上是生活随笔為你收集整理的【Java基础】HashMap原理详解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。