散列表 Hashmap、hashtable、concurrentHashMap、hashset；

樹： treemap、treeset、hashset

treeset 繼承自 treemap，hashset 繼承自 hashmap ；

性能分析

Map 是 Java 中的接口，Map.Entry 是 Map 的一個(gè)內(nèi)部接口 Map 提供了一些常用方法，例如 keySet()、entrySet() 方法等；

Entry: key 和 value的組合，即為一個(gè)映射項(xiàng)<K,V>

Treemap 底層數(shù)據(jù)結(jié)構(gòu)是紅黑樹，元素存儲(chǔ)是有序的，因此添加元素需要循環(huán)查找 Entry 插入位置、取出元素時(shí)需要遍歷才能找到合適的 Entry ，比較耗性能；treemap、treeset 對(duì)比 hashmap、hashset 優(yōu)勢(shì)：前者元素都以有序狀態(tài)排列

HashMap 產(chǎn)生沖突原因及解決方法

調(diào)用hashCode() 計(jì)算 hashCode ，兩個(gè)不同對(duì)象可能有相同的 hashCode ，導(dǎo)致沖突產(chǎn)生，

bucket ，哈希表中的數(shù)組中可以存儲(chǔ) hashcode 相同對(duì)象，每個(gè)bucket 都有其指定索引，系統(tǒng)可以根據(jù)索引快速訪問該 bucket 里存儲(chǔ)的元素

HashMap 解決沖突方法

1，開放定址法：通過探測(cè)算法，檔一個(gè)槽位被占用情況下繼續(xù)查找下一個(gè)；

探測(cè)算法的三種方式：

• 線性探查
• 二次探查
• 雙重散列  采用兩個(gè)輔助散列函數(shù)合成一個(gè)：h1 、h2 為兩個(gè)散列函數(shù)

2，鏈地址法：數(shù)組+鏈表，將hash 值相同對(duì)象組織為一個(gè)鏈表放在 hash值對(duì)應(yīng)的 bucket

3，再哈希，準(zhǔn)備多個(gè)散列函數(shù)，當(dāng)發(fā)生沖突時(shí)再選擇一個(gè)散列函數(shù)進(jìn)行散列，原理與雙重散列相似

jdk7 與 jdk8 中HashMap的區(qū)別

發(fā)生沖突

• jdk7 中 hashMap 采用數(shù)組+鏈表。如果過多節(jié)點(diǎn)在 hash 時(shí)發(fā)生碰撞，如果要查找其中一個(gè)節(jié)點(diǎn)，需要 O(n) 的查找時(shí)間。
• jdk8 中 hashMap 采用數(shù)組+鏈表/紅黑樹，出現(xiàn) hash 沖突時(shí)會(huì)進(jìn)行判斷，該節(jié)點(diǎn)是紅黑樹還是量表：

如果是鏈表的話，數(shù)據(jù)插入鏈表尾部并判斷鏈表長(zhǎng)度是否達(dá)到某個(gè)閾值(默認(rèn)閾值為 8 )，如果大于閾值，鏈表將轉(zhuǎn)化為紅黑樹，時(shí)間復(fù)雜度為O(nlogn);

若是紅黑樹的話， 直接插入紅黑樹即可；

數(shù)據(jù)結(jié)構(gòu)紅黑樹的幾個(gè)性質(zhì)，查詢效率非常高，10億數(shù)據(jù)進(jìn)行不到30次比較就能查找到目標(biāo)

1、每個(gè)節(jié)點(diǎn)要么是黑色、要么是紅色；

2、根節(jié)點(diǎn)是黑色；

3、每個(gè)葉子節(jié)點(diǎn)是黑色；

4、每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子結(jié)點(diǎn)一定都是黑色；

5、任意一結(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)的路徑都包含相同數(shù)量的黑節(jié)點(diǎn)；

擴(kuò)容

JDK7 擴(kuò)容時(shí)，在 resize() 過程中采用頭插法，舊數(shù)據(jù)轉(zhuǎn)移到新數(shù)組中，轉(zhuǎn)移操作=正序遍歷倆表，在頭部依次插入，即鏈表逆序；多線程下 resize() 容易出現(xiàn) 死循環(huán)，在多線程下并發(fā)執(zhí)行 put() 操作，一旦出現(xiàn)擴(kuò)容情況，容易出現(xiàn)環(huán)形鏈表，在獲取數(shù)據(jù)、遍歷鏈表時(shí)出現(xiàn)死循環(huán)，即死鎖轉(zhuǎn)發(fā)太；

JDK 8 在擴(kuò)容 resize() 時(shí)，數(shù)據(jù)轉(zhuǎn)移時(shí)在新鏈表尾部依次插入，不會(huì)出現(xiàn)逆序、環(huán)形鏈表情況，但 jdk 1.8 仍是線程不安全的

使用建議

1，使用出初始值，避免多次擴(kuò)容的性能消耗；

2，自定義對(duì)象作為 key,時(shí)需要重寫 hashCode 、equals 方法；

3，多線程下， 使用 CurrentHashMap 代替 HashMap;

Reference

1, http://www.dbjr.com.cn/article/224721.htm

2, https://www.jianshu.com/p/e136ec79235c

3, https://zhuanlan.zhihu.com/p/59250175

以上就是java面試之散列表及樹所對(duì)應(yīng)容器類及HashMap沖突解決的詳細(xì)內(nèi)容，更多關(guān)于java散列表樹所對(duì)應(yīng)容器類HashMap沖突的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論