給新手講清楚HashMapJava入門階段的很多事情一下子就能通。這個(gè)數(shù)據(jù)結(jié)構(gòu)核心就一句話通過(guò)key找到value。登錄系統(tǒng)里拿用戶ID查用戶信息、訂單統(tǒng)計(jì)里按日期聚合金額、緩存場(chǎng)景里用請(qǐng)求URL換響應(yīng)結(jié)果背后全是同一套邏輯——給一個(gè)key立刻得到對(duì)應(yīng)的value。偏偏很多人項(xiàng)目里用了很久HashMap一問(wèn)為什么必須重寫equals和hashCode、為什么容量默認(rèn)16還必須是2的冪、為什么有時(shí)候?qū)懭霂资f(wàn)條數(shù)據(jù)就卡頓就答不上來(lái)了。這篇文章就把這條從key到value的完整鏈路徹底掰開(kāi)順便把源碼、性能坑、排查方法一次說(shuō)清。適合誰(shuí)看正在啃集合源碼的初學(xué)者、準(zhǔn)備面試的人以及寫代碼時(shí)覺(jué)得HashMap“時(shí)而快時(shí)而慢”但說(shuō)不清原因的開(kāi)發(fā)者。我會(huì)把幾個(gè)關(guān)鍵概念用廚房、圖書館這種生活場(chǎng)景做類比再配一套可直接落地的操作建議。1. 先從“key找value”這個(gè)需求說(shuō)起1.1 數(shù)組的尷尬和鏈表的慢假設(shè)你現(xiàn)在要做一個(gè)用戶系統(tǒng)用戶數(shù)據(jù)有ID、姓名、手機(jī)號(hào)。最常見(jiàn)的需求是給我一個(gè)用戶ID把那行用戶信息取出來(lái)。如果數(shù)據(jù)用數(shù)組存你得知道ID對(duì)應(yīng)的下標(biāo)比如第0個(gè)格子里存ID1001的用戶第1個(gè)格子存ID1002的用戶那就只能強(qiáng)行為ID和下標(biāo)建立映射關(guān)系業(yè)務(wù)里根本做不到——用戶ID是1001、1002這種連續(xù)值還好說(shuō)一旦變成訂單號(hào)、手機(jī)號(hào)、短信驗(yàn)證碼這種沒(méi)有規(guī)律、甚至可能重復(fù)的鍵數(shù)組下標(biāo)立刻失效。有人會(huì)說(shuō)那用鏈表不就行了。鏈表每個(gè)節(jié)點(diǎn)可以存兩部分key和value。查找的時(shí)候從頭節(jié)點(diǎn)開(kāi)始逐個(gè)比較節(jié)點(diǎn)的key和你要找的key相等就返回value。這個(gè)方案靈活但代價(jià)是查找復(fù)雜度O(n)數(shù)據(jù)量到一萬(wàn)條還能忍到百萬(wàn)條就完全沒(méi)法用了。每次查找都得把鏈表從頭摸到尾最壞情況下要找滿全場(chǎng)。你真正需要的是一種結(jié)構(gòu)既不用關(guān)心下標(biāo)又不用遍歷全場(chǎng)。這種需求就是哈希表要解決的。1.2 哈希思想的雛形算出一個(gè)位置來(lái)哈希表的想法其實(shí)很樸素。你去圖書館借書管理員不會(huì)帶你從第一排書架開(kāi)始找而是先看索書號(hào)索書號(hào)本身就包含了分類體系走到對(duì)應(yīng)分區(qū)順著編號(hào)一摸就拿到了。你去快遞驛站取件快遞員也不會(huì)把所有包裹拆開(kāi)挨個(gè)翻他先按手機(jī)尾號(hào)分貨架再按包裹上的編號(hào)找。哈希表做的就是同一件事把任意一個(gè)key通過(guò)一個(gè)計(jì)算過(guò)程映射成數(shù)組里的某個(gè)下標(biāo)。這個(gè)計(jì)算過(guò)程叫哈希函數(shù)算出來(lái)的值叫哈希值數(shù)組里的每個(gè)格子叫桶bucket。理論上只要哈希函數(shù)能把不同的key均勻散開(kāi)每次查找就能直接定位到目標(biāo)桶時(shí)間復(fù)雜度接近O(1)。那HashMap只不過(guò)是把這套思想在Java里實(shí)現(xiàn)了并且加了處理沖突、自動(dòng)擴(kuò)容的機(jī)制。所以理解HashMap核心就是理解兩件事key怎么變成一個(gè)桶下標(biāo)以及多個(gè)key落到同一個(gè)桶時(shí)怎么辦。2. HashMap的桶位怎么來(lái)的hash()與下標(biāo)定位2.1 hash()為什么要異或高16位先看JDK 8里HashMap計(jì)算哈希值的源碼static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }這里有兩個(gè)動(dòng)作先調(diào)用key自身的hashCode()拿到一個(gè)int然后把高16位和低16位做異或得到的才是真正參與桶定位的hash值。為什么要折騰這一步因?yàn)楹罄m(xù)定位桶的時(shí)候用的是數(shù)組長(zhǎng)度減一和hash值做按位與。默認(rèn)數(shù)組長(zhǎng)度16對(duì)應(yīng)的二進(jìn)制是0000 0000 0000 1111按位與會(huì)把高28位全部清零只保留最低4位。如果兩個(gè)key的hashCode在高位有差異、低位完全相同那它們就會(huì)落到同一個(gè)桶這就是沖突。而且很多對(duì)象的hashCode恰恰在高位差異較大低位區(qū)分度不足。把高16位異或到低16位相當(dāng)于讓高位的特征也參與低位的運(yùn)算即使數(shù)組很短散列效果也會(huì)好很多。這一步在源碼注釋里叫“擾動(dòng)函數(shù)”確實(shí)是經(jīng)過(guò)權(quán)衡后性價(jià)比很高的一步。2.2 為什么容量必須是2的冪以及取模優(yōu)化定位桶下標(biāo)的核心代碼是這一行i (n - 1) hashn是數(shù)組長(zhǎng)度。這里用按位與代替取模%原因是位運(yùn)算比取?？斓枚?。但要成立前提是n必須是2的冪。當(dāng)n16時(shí)n-115二進(jìn)制是1111n32時(shí)n-131二進(jìn)制是11111全都是低位連續(xù)的1這樣按位與的結(jié)果就等于hash對(duì)n取余而且效率更高。HashMap源碼在構(gòu)造時(shí)對(duì)容量做了一圈處理就是為了保證這一點(diǎn)。你傳入任何初始容量它都會(huì)向上補(bǔ)成2的冪static final int tableSizeFor(int cap) { int n cap - 1; n | n 1; n | n 2; n | n 4; n | n 8; n | n 16; return (n 0) ? 1 : (n MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1; }你傳3它變成4傳10變成16傳100變成128。這套移位運(yùn)算把最高位后面的所有位全部填成1最后加個(gè)1就是最接近且大于等于原值的2的冪。還有一個(gè)好處。擴(kuò)容時(shí)數(shù)組長(zhǎng)度翻倍從16變成32原來(lái)長(zhǎng)度16時(shí)下標(biāo)只由hash低4位決定現(xiàn)在要由低5位決定。新增的那一位如果是0元素留在原地如果是1元素挪到“原下標(biāo)16”的位置。因?yàn)?的冪特性擴(kuò)容時(shí)不需要重新計(jì)算每個(gè)key的hash值只需要看新增比特位就夠了這也是JDK 8里resize能高效拆分鏈表的原因。2.3 沖突不可避免鏈化和樹(shù)化的閾值邏輯哈希函數(shù)設(shè)計(jì)得再好也不能保證每個(gè)key都算到不同桶沖突是必然的。HashMap解決沖突的辦法就是把多個(gè)沖突元素放到同一個(gè)桶里用鏈表串起來(lái)。JDK 8之前一直是這個(gè)方案簡(jiǎn)單可靠但極端情況下所有key都落在同一個(gè)桶鏈表越來(lái)越長(zhǎng)查找就退化成了O(n)。JDK 8改成了鏈表加紅黑樹(shù)的混合結(jié)構(gòu)同一個(gè)桶里節(jié)點(diǎn)數(shù)超過(guò)8并且整個(gè)數(shù)組長(zhǎng)度大于等于64就會(huì)把鏈表轉(zhuǎn)成紅黑樹(shù)。紅黑樹(shù)查找復(fù)雜度O(log n)在一棵深度幾十的樹(shù)里找一個(gè)元素跟遍歷幾千個(gè)節(jié)點(diǎn)的鏈表是完全不同的量級(jí)。為什么閾值是8源碼注釋里給出過(guò)一個(gè)統(tǒng)計(jì)結(jié)論在隨機(jī)哈希碼的情況下桶內(nèi)節(jié)點(diǎn)數(shù)達(dá)到8的概率大約只有千萬(wàn)分之六對(duì)絕大多數(shù)正常業(yè)務(wù)來(lái)說(shuō)幾乎不可能觸發(fā)樹(shù)化。反而如果閾值設(shè)得太低比如2稍微有點(diǎn)沖突就樹(shù)化而樹(shù)節(jié)點(diǎn)的內(nèi)存占用是普通節(jié)點(diǎn)的兩倍左右性能反而下降。等紅黑樹(shù)節(jié)點(diǎn)數(shù)降到6以下又會(huì)變回鏈表這中間留了緩沖區(qū)間避免頻繁在兩種結(jié)構(gòu)之間來(lái)回切換。3. put和get的完整源碼鏈路3.1 put(key, value)時(shí)發(fā)生了什么JDK 8里put的入口很簡(jiǎn)單但背后邏輯值得逐行看public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { NodeK,V[] tab; int n; // 第一次put時(shí)整個(gè)表還是空的先擴(kuò)容初始化 if ((tab table) null || (n tab.length) 0) n (tab resize()).length; // 算出桶下標(biāo)如果槽位是空的直接放進(jìn)新節(jié)點(diǎn) int i (n - 1) hash; if ((p tab[i]) null) tab[i] newNode(hash, key, value, null); else { NodeK,V e; K k; // 桶里已有節(jié)點(diǎn)先比較hash再比較key if (p.hash hash ((k p.key) key || (key ! null key.equals(k)))) e p; else if (p instanceof TreeNode) // 桶里已是紅黑樹(shù)走紅黑樹(shù)插入邏輯 e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value); else { // 桶里是鏈表遍歷找尾部插入如果中途遇到相同key記錄舊節(jié)點(diǎn) for (int binCount 0; ; binCount) { if ((e p.next) null) { p.next newNode(hash, key, value, null); if (binCount TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); break; } if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) break; p e; } } // e不為空說(shuō)明存在相同key覆蓋舊value并返回舊value if (e ! null) { V oldValue e.value; e.value value; return oldValue; } } modCount; // 元素?cái)?shù)量超過(guò)閾值就擴(kuò)容 if (size threshold) resize(); return null; }注意幾個(gè)細(xì)節(jié)。定位到桶以后如果桶里已經(jīng)有節(jié)點(diǎn)先比hash再比對(duì)key。比對(duì)key的時(shí)候用了兩層判斷第一層是引用判斷k key比如你用同一個(gè)String對(duì)象做key直接引用相等就命中第二層是key.equals(k)處理的是內(nèi)容相同但引用不同的情況比如兩次都傳入字符串1001它們不是同一個(gè)對(duì)象但equals相等。只有hash相同才有必要做equals比較hash不同就直接認(rèn)定不是同一個(gè)key。這能夠大大減少equals的調(diào)用次數(shù)畢竟哈希定位已經(jīng)把絕大多數(shù)無(wú)關(guān)key擋在外面了。3.2 get(key)時(shí)為什么能精準(zhǔn)命中g(shù)et的鏈路和put高度對(duì)稱public V get(Object key) { NodeK,V e; return (e getNode(hash(key), key)) null ? null : e.value; } final NodeK,V getNode(int hash, Object key) { NodeK,V[] tab; NodeK,V first, e; int n; K k; // 表非空且目標(biāo)桶位置有節(jié)點(diǎn)才可能找到 if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) { // 先檢查第一個(gè)節(jié)點(diǎn) if (first.hash hash ((k first.key) key || (key ! null key.equals(k)))) return first; // 第一個(gè)節(jié)點(diǎn)沒(méi)命中看是樹(shù)還是鏈表 if ((e first.next) ! null) { if (first instanceof TreeNode) return ((TreeNodeK,V)first).getTreeNode(hash, key); // 鏈表逐個(gè)比較 do { if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) return e; } while ((e e.next) ! null); } } return null; }這個(gè)流程已經(jīng)清晰先通過(guò)hash(key)算出哈希值再用(n - 1) hash定位桶桶里節(jié)點(diǎn)碰運(yùn)氣直接命中命不中就在鏈表或紅黑樹(shù)里繼續(xù)比較。之所以說(shuō)HashMap查詢是“近似O(1)”就是因?yàn)榇蠖鄶?shù)情況下桶里是空的或者只有一兩個(gè)節(jié)點(diǎn)一次定位加一兩次比較就出結(jié)果只有沖突嚴(yán)重時(shí)才會(huì)走到后面的鏈表或樹(shù)遍歷。3.3 equals和hashCode的契約為什么是命中的前提如果你只重寫equals但不同時(shí)重寫hashCode會(huì)出大問(wèn)題。假設(shè)你有一個(gè)訂單類Orderequals比較的是orderNo但hashCode還是Object的默認(rèn)實(shí)現(xiàn)——基于對(duì)象內(nèi)存地址。兩個(gè)orderNo完全一樣的訂單對(duì)象equals返回true但hashCode不同。第一次put進(jìn)去用的是對(duì)象A第二次get時(shí)傳入對(duì)象BB的hash值跟A不同桶下標(biāo)直接不一樣連目標(biāo)桶都找不到equals根本沒(méi)機(jī)會(huì)執(zhí)行。這就是哈希表最核心的契約equals相等的兩個(gè)對(duì)象hashCode必須相等。反過(guò)來(lái)hashCode相等不等于equals相等這是允許的這正是哈希沖突。兩個(gè)不同key算到同一個(gè)桶最終靠equals來(lái)區(qū)分誰(shuí)是誰(shuí)。所以正確做法是參與equals比較的字段必須同時(shí)參與hashCode計(jì)算反之如果hashCode用了某個(gè)字段equals也最好用上否則可能出現(xiàn)兩個(gè)對(duì)象hashCode相同但業(yè)務(wù)上含義不同put時(shí)被當(dāng)成同一個(gè)key覆蓋的情況。后面第4部分我會(huì)給完整示例。4. 實(shí)際開(kāi)發(fā)中容易踩的三個(gè)性能坑4.1 初始容量與加載因子的正確姿勢(shì)HashMap的默認(rèn)容量是16加載因子是0.75。加載因子的含義是當(dāng)元素?cái)?shù)量超過(guò)容量 × 0.75時(shí)觸發(fā)resize擴(kuò)容。也就是說(shuō)默認(rèn)情況下存到第12個(gè)元素HashMap就會(huì)擴(kuò)容到32容量翻倍。很多人不關(guān)心這個(gè)導(dǎo)致寫入數(shù)據(jù)量大時(shí)反復(fù)擴(kuò)容。我實(shí)測(cè)過(guò)往默認(rèn)HashMap里塞100條數(shù)據(jù)會(huì)觸發(fā)至少4次resize每次resize都要重新分配數(shù)組、重新計(jì)算所有已有節(jié)點(diǎn)的桶下標(biāo)、移動(dòng)節(jié)點(diǎn)。1億條級(jí)別的數(shù)據(jù)光是擴(kuò)容的rehash成本就非?？捎^。正確的初始化方式是按預(yù)計(jì)數(shù)據(jù)量反推。如果你預(yù)計(jì)要放100條數(shù)據(jù)int expectedSize 100; MapString, Object map new HashMap((int) (expectedSize / 0.75f) 1);計(jì)算下來(lái)初始容量設(shè)置成134HashMap會(huì)自動(dòng)向上取整為256閾值變成256×0.75192遠(yuǎn)超100整個(gè)過(guò)程不會(huì)觸發(fā)擴(kuò)容。如果直接寫new HashMap(100)容量會(huì)向上取成128閾值是96存到第96個(gè)元素時(shí)還是得擴(kuò)容一次等于白打算。加載因子0.75是JDK團(tuán)隊(duì)在時(shí)間成本和空間成本里取的平衡點(diǎn)。調(diào)小到0.5桶更空、沖突更少、查詢更快但內(nèi)存浪費(fèi)嚴(yán)重調(diào)大到1.0空間利用率高但碰撞概率上升鏈表變長(zhǎng)查詢變慢。普通業(yè)務(wù)場(chǎng)景不要?jiǎng)舆@個(gè)值真要調(diào)先壓測(cè)再調(diào)。4.2 自定義對(duì)象當(dāng)keyequals和hashCode怎么配開(kāi)發(fā)中最容易出問(wèn)題的場(chǎng)景是把自定義對(duì)象塞進(jìn)HashMap當(dāng)key比如訂單、賬號(hào)、設(shè)備信息。先看一個(gè)會(huì)翻車的寫法class Order { private String orderNo; private BigDecimal amount; Override public boolean equals(Object o) { if (this o) return true; if (o null || getClass() ! o.getClass()) return false; Order order (Order) o; return Objects.equals(orderNo, order.orderNo); } // 忘記重寫 hashCode }兩個(gè)orderNo相同的Order對(duì)象equals返回true但hashCode還是默認(rèn)的地址哈希意味著同一筆訂單兩個(gè)不同的對(duì)象實(shí)例放進(jìn)Map會(huì)被當(dāng)成兩個(gè)key。get的時(shí)候傳入另一個(gè)同orderNo的對(duì)象hash定位直接落到另一個(gè)桶結(jié)果永遠(yuǎn)是null。排查了半天最后根源就是hashCode沒(méi)重寫。正確的版本是這樣class Order { private final String orderNo; private BigDecimal amount; public Order(String orderNo) { this.orderNo orderNo; } Override public boolean equals(Object o) { if (this o) return true; if (o null || getClass() ! o.getClass()) return false; Order order (Order) o; return Objects.equals(orderNo, order.orderNo); } Override public int hashCode() { return Objects.hash(orderNo); } }equals只用orderNo比較hashCode也只由orderNo計(jì)算契約一致性滿足。還有一個(gè)進(jìn)階要求key對(duì)象盡量不可變。如果你把key放進(jìn)Map之后又修改了某個(gè)參與hashCode計(jì)算的字段這個(gè)key的hash值就變了再調(diào)用get時(shí)按新hash值定位到另一個(gè)桶舊桶里的數(shù)據(jù)就永遠(yuǎn)找不到了等于內(nèi)存里多了一份永遠(yuǎn)不會(huì)被訪問(wèn)的孤兒節(jié)點(diǎn)。String、Integer這類包裝類天生不可變所以是最常用的key類型。自定義類做key時(shí)核心字段建議設(shè)成final去掉setter從根本上杜絕這個(gè)問(wèn)題。4.3 并發(fā)場(chǎng)景別拿HashMap硬扛HashMap不是線程安全的。多線程同時(shí)put時(shí)兩個(gè)線程可能在同一桶位置寫入后寫的覆蓋先寫的更麻煩的是擴(kuò)容階段多線程同時(shí)觸發(fā)resizeJDK 7里甚至可能形成循環(huán)鏈表get的時(shí)候直接死循環(huán)這是當(dāng)年的經(jīng)典線上事故。JDK 8改成尾插法循環(huán)鏈表問(wèn)題基本被解決但數(shù)據(jù)丟失、覆蓋問(wèn)題依然存在因?yàn)镠ashMap的內(nèi)部操作沒(méi)有同步機(jī)制。并發(fā)場(chǎng)景的正確選擇是ConcurrentHashMap。JDK 8的ConcurrentHashMap放棄了分段鎖改用CAS加synchronized鎖單個(gè)桶節(jié)點(diǎn)鎖粒度更細(xì)并發(fā)讀的時(shí)候基本無(wú)鎖寫入時(shí)只鎖住目標(biāo)桶性能遠(yuǎn)好于給整個(gè)HashMap加synchronized。如果只是低并發(fā)的場(chǎng)景讀多寫少也可以用Collections.synchronizedMap(new HashMap())但這是整表鎖寫操作串行高并發(fā)下吞吐量上不去。記住一個(gè)原則共享可變Map要么用ConcurrentHashMap要么不要共享。5. 常見(jiàn)問(wèn)題排查速查5.1 高頻問(wèn)題對(duì)照表現(xiàn)象可能原因排查方法解決方案查詢?cè)絹?lái)越慢自定義key的hashCode寫得差大量key落同一桶打印桶內(nèi)節(jié)點(diǎn)數(shù)分布看是否有超長(zhǎng)鏈表重寫hashCode讓更多字段參與計(jì)算同一對(duì)象get不到值只重寫equals沒(méi)重寫hashCode或key可變檢查key的equals和hashCode實(shí)現(xiàn)的一致性檢查key是否put后被修改遵守契約key字段設(shè)final修改后重新放入Map寫入量大時(shí)明顯卡頓頻繁擴(kuò)容rehash成本高看日志中resize觸發(fā)次數(shù)或計(jì)算閾值與數(shù)據(jù)量的關(guān)系構(gòu)造時(shí)用expectedSize / 0.75f 1設(shè)置初始容量多線程寫入丟數(shù)據(jù)HashMap并發(fā)不安全高并發(fā)壓測(cè)觀察數(shù)據(jù)丟失換成ConcurrentHashMap遍歷結(jié)果順序不穩(wěn)定HashMap本身不保證順序換用LinkedHashMap按寫入順序遍歷用LinkedHashMap按key排序用TreeMapput一個(gè)null鍵允許null key放在桶下標(biāo)0這是設(shè)計(jì)行為業(yè)務(wù)上自行區(qū)分null和空字符串Map內(nèi)存只增不減key被外部引用無(wú)法回收檢查key生存周期必要時(shí)用WeakHashMap或手動(dòng)remove5.2 一個(gè)快速查看哈希分布的小工具排查自定義對(duì)象哈希質(zhì)量的時(shí)候我經(jīng)常寫一小段代碼打印桶分布直觀看到?jīng)_突是否嚴(yán)重public static void printBucketStats(MapObject, Object map) { try { java.lang.reflect.Field field HashMap.class.getDeclaredField(table); field.setAccessible(true); Object[] table (Object[]) field.get(map); if (table null) { System.out.println(table is empty); return; } int total 0; int maxBin 0; int emptyBin 0; for (Object node : table) { int count 0; Object p node; while (p ! null) { count; p ((java.lang.reflect.Field) p.getClass().getDeclaredField(next)).get(p); } if (count 0) emptyBin; maxBin Math.max(maxBin, count); total count; } System.out.printf(table length%d, total nodes%d, empty bins%d, max bin%d%n, table.length, total, emptyBin, maxBin); } catch (Exception ignored) { // 反射失敗時(shí)直接放棄 } }這段代碼用反射拿到HashMap內(nèi)部的table數(shù)組統(tǒng)計(jì)每個(gè)桶的節(jié)點(diǎn)數(shù)量。如果空桶占比很高、某個(gè)桶節(jié)點(diǎn)數(shù)特別多反過(guò)來(lái)說(shuō)明hashCode分布不夠均勻。正常業(yè)務(wù)數(shù)據(jù)下最大的桶節(jié)點(diǎn)數(shù)應(yīng)該是個(gè)位數(shù)如果出現(xiàn)幾十個(gè)節(jié)點(diǎn)的長(zhǎng)鏈就得回頭查key的hashCode實(shí)現(xiàn)了。我自己的排查經(jīng)驗(yàn)是HashMap相關(guān)的詭異問(wèn)題90%最后都?xì)w結(jié)到key對(duì)象身上。要么equals和hashCode寫得不一致要么key是可變對(duì)象被改壞了要么hashCode分布太差導(dǎo)致桶傾斜。把這三條路排查完基本都能定位到根因。6. 再分享一點(diǎn)個(gè)人的使用體會(huì)文章最后分享一個(gè)我實(shí)際操作中的體會(huì)調(diào)試HashMap問(wèn)題時(shí)不要一上來(lái)就懷疑源碼或者并發(fā)先把key的hashCode和equals擺到桌面上看一遍。這兩個(gè)方法加起來(lái)不到二十行卻是整個(gè)HashMap運(yùn)轉(zhuǎn)的基石絕大多數(shù)“莫名找不到”“莫名覆蓋”的問(wèn)題都從這里來(lái)。另外初始容量這個(gè)參數(shù)很多人覺(jué)得不設(shè)也沒(méi)關(guān)系量大了才知道代價(jià)。我在一個(gè)批量導(dǎo)入功能里往Map里灌了大概幾萬(wàn)條數(shù)據(jù)最初沒(méi)設(shè)容量導(dǎo)入過(guò)程能明顯感覺(jué)到后半程變慢。后來(lái)按expectedSize / 0.75f 1初始化后耗時(shí)直接降了一截代碼只改了一行。這種性價(jià)比極高的優(yōu)化項(xiàng)目里多多益善。把從key到桶下標(biāo)再到節(jié)點(diǎn)的這條鏈路琢磨透了再回頭看ConcurrentHashMap的分段鎖演進(jìn)、TreeMap的紅黑樹(shù)結(jié)構(gòu)甚至是Redis里的哈希表實(shí)現(xiàn)都會(huì)覺(jué)得順理成章。數(shù)據(jù)結(jié)構(gòu)這種東西不怕不熟悉API就怕不理解那個(gè)“根據(jù)key找到value”的核心思想。