java教程散列表和樹所對應(yīng)容器類及HashMap解決沖突學(xué)習(xí)
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ù)組+鏈表/紅黑樹，當(dāng)某個桶位達(dá)到某個閾值時，鏈表將轉(zhuǎn)化為紅黑樹，紅黑樹時間復(fù)雜度O(nlogn)
HashMap如何解決沖突
1.開放定址法： 通過探測算法，當(dāng)一個槽位已經(jīng)被占用情況下繼續(xù)查找下一個
2.鏈地址法（數(shù)組+鏈表）
3.再哈希 準(zhǔn)備多個散列函數(shù)，當(dāng)發(fā)生沖突時，再選擇一個散列函數(shù)進(jìn)行散列。
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ù)組下標(biāo)
調(diào)整數(shù)據(jù)大?。ó?dāng)容器中的元素個數(shù)大于 capacity * loadfactor 時，容器會進(jìn)行擴(kuò)容resize 為 2n）
3.三種情況：
- 當(dāng)K的hash值不在HashMap中，則執(zhí)行插入
- 當(dāng)K的hash值存在HashMap中，發(fā)生碰撞
它們兩者equals為true，更新鍵值對
它們兩者equals為false，插入鏈表尾部或紅黑樹（當(dāng)鏈表長度超過8）中
獲取對象時（get方法）：
- 調(diào)用hash（K），計算K的hash值從而獲取數(shù)組的下標(biāo)
- 順序遍歷鏈表，equal方法查找相同 Node 鏈表中 K 值對應(yīng)的 V 值
轉(zhuǎn)載于:https://my.oschina.net/u/3973793/blog/3100006
以上就是java教程散列表和樹所對應(yīng)容器類及HashMap解決沖突學(xué)習(xí)的詳細(xì)內(nèi)容，更多關(guān)于java散列表樹所對應(yīng)容器類及HashMap解決沖突的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
基于IDEA，Eclipse搭建Spring Boot項目過程圖解
這篇文章主要介紹了基于IDEA，Eclipse搭建Spring Boot項目過程圖解,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-04-04
這篇文章主要介紹了并不是每一臺計算機都可以運行Java程序，要運行Java程序，計算機必須學(xué)習(xí)搭建Java開發(fā)環(huán)境,需要的朋友可以參考下2015-07-07
這篇文章主要為大家詳細(xì)介紹了SpringBoot配置文件格式，文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)SpringBoot有一定幫助，需要的可以參考一下2022-09-09
這篇文章主要介紹了深入理解Java中的EnumMap和EnumSet,一般來說我們會選擇使用HashMap來存儲key-value格式的數(shù)據(jù),考慮這樣的特殊情況,一個HashMap的key都來自于一個Enum類,這樣的情況則可以考慮使用本文要講的EnumMap,需要的朋友可以參考下2023-11-11
相信大家在生活中會收到很多短信，而這些短信都有一個特點是鏈接很短。這些鏈接背后的原理是什么呢？怎么實現(xiàn)的？小編今天就帶你們詳細(xì)了解一下2021-12-12
這篇文章主要介紹了基于SSM框架實現(xiàn)簡單的登錄注冊的示例代碼，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-12-12
本文主要介紹了java中TCP實現(xiàn)回顯服務(wù)器及客戶端，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-02-02
下面小編就為大家?guī)硪黄趈ava中兩個對象屬性的比較。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-09-09
Java使用modbus4j實現(xiàn)modbus?tcp通訊
Modbus是由Modicon（現(xiàn)為施耐德電氣公司的一個品牌）在1979年發(fā)明的,是全球第一個真正用于工業(yè)現(xiàn)場的總線協(xié)議,本文主要介紹了java如何使用modbus4j實現(xiàn)modbus?tcp通訊,感興趣的可以了解下2023-12-12
這篇文章主要介紹了如何使用IDEA從SVN服務(wù)端檢出項目問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-12-12