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

散列表：hashmap,hashtable,concurrentHashmap

樹：hashset,treemap,treeset

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

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

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

HashMap如何解決沖突

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

HashMap的工作原理

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

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

1.存儲(chǔ)對(duì)象時(shí)，將K/V傳給put（）方法：

2.hash（K）計(jì)算K的hash，結(jié)合數(shù)組長(zhǎng)度，計(jì)算數(shù)組下標(biāo)

調(diào)整數(shù)據(jù)大?。ó?dāng)容器中的元素個(gè)數(shù)大于 capacity * loadfactor 時(shí)，容器會(huì)進(jìn)行擴(kuò)容resize 為 2n）

3.三種情況：

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

獲取對(duì)象時(shí)（get方法）：

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

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

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

最新評(píng)論