java中散列表、樹所對應(yīng)的的容器類

散列表：hashmap,hashtable,concurrentHashmap

樹：hashset,treemap,treeset

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

jdk7中hashMap采用數(shù)組+鏈表，如果過多的節(jié)點在hash時發(fā)生碰撞，如果要查找其中一個節(jié)點，需要O(n）的查找時間。

jdk7中hashMap采用數(shù)組+鏈表/紅黑樹，當某個桶位達到某個閾值時，鏈表將轉(zhuǎn)化為紅黑樹，紅黑樹時間復(fù)雜度O(nlogn)

HashMap如何解決沖突

1.開放定址法： 通過探測算法，當一個槽位已經(jīng)被占用情況下繼續(xù)查找下一個
2.鏈地址法（數(shù)組+鏈表）
3.再哈希 準備多個散列函數(shù)，當發(fā)生沖突時，再選擇一個散列函數(shù)進行散列。

HashMap的工作原理

HashMap 底層是數(shù)組和單向鏈表實現(xiàn)，數(shù)組中的每個元素都是鏈表，由 Node 內(nèi)部類（實現(xiàn) Map.Entry<K,V>接口）實現(xiàn)，HashMap 通過 put & get 方法存儲和獲取。

HashCode是定位（存儲位置），equals是定性（兩者是否相等）

1.存儲對象時，將K/V傳給put（）方法：

2.hash（K）計算K的hash，結(jié)合數(shù)組長度，計算數(shù)組下標

調(diào)整數(shù)據(jù)大小（當容器中的元素個數(shù)大于 capacity * loadfactor 時，容器會進行擴容resize 為 2n）

3.三種情況：

• 當K的hash值不在HashMap中，則執(zhí)行插入
• 當K的hash值存在HashMap中，發(fā)生碰撞
     它們兩者equals為true，更新鍵值對
     它們兩者equals為false，插入鏈表尾部或紅黑樹（當鏈表長度超過8）中

獲取對象時（get方法）：

• 調(diào)用hash（K），計算K的hash值從而獲取數(shù)組的下標
• 順序遍歷鏈表，equal方法查找相同 Node 鏈表中 K 值對應(yīng)的 V 值

轉(zhuǎn)載于:https://my.oschina.net/u/3973793/blog/3100006

以上就是java教程散列表和樹所對應(yīng)容器類及HashMap解決沖突學習的詳細內(nèi)容，更多關(guān)于java散列表樹所對應(yīng)容器類及HashMap解決沖突的資料請關(guān)注服務(wù)器之家其它相關(guān)文章！

原文鏈接：https://blog.csdn.net/chuangjizai7518/article/details/101010546