HashMap
HashMap主要結(jié)構(gòu)
- 數(shù)組加鏈表
- 數(shù)組加紅黑樹
存放數(shù)據(jù)的對象
- Node <- Map.Entry
- TreeNode <- Node <- Map.Entry
默認構(gòu)造函數(shù)
- 數(shù)組默認初始化容量 1 << 4
- 數(shù)組最大容量 1 << 30
- 默認負載因子 0.75f
- 負載閥值 = 容量 * 負載因子
- 鏈表樹化閥值，鏈表長度大余等于8
- 樹結(jié)構(gòu)鏈化，樹的大小小余等于6
- 樹化最小數(shù)組長度，也就是如果數(shù)組長度小于64，如果遇到鏈表長度大于樹化閥值，則是擴容數(shù)組，而不是將鏈表樹化
初始化
- 構(gòu)造HashMap時，數(shù)組還未真正初始化
- 構(gòu)造HashMap時，主要設(shè)置數(shù)組大小，負載因子，負載閥值
- 使用舊的HashMap構(gòu)造新的HashMap，會resize初始化數(shù)組，并且把舊數(shù)據(jù)加入
- 構(gòu)造一個空HashMap，在第一次put時才會通過resize初始化數(shù)組
數(shù)組長度和擴容規(guī)則
- 數(shù)組長度為2的N次冪，如：1、2、4、8、16
- 擴容就是在原來基礎(chǔ)上乘以2
- 當數(shù)據(jù)個輸超過閥值則擴容
- 當鏈表準備樹化發(fā)現(xiàn)數(shù)組長度小于64時，優(yōu)先擴容
運算方式
- 主要通過位運算
- hash值和數(shù)組長度減一與運算(&)，獲取下標
備注
- HashMap非線程安全
- 計算hash值高16位和低16位進行異或運算，使高低位都參與運算
- 如果是鏈表，則在尾部插入
其他
- & 與
- | 或
- ~ 非
- ^ 異或
Hashtable
默認構(gòu)造參數(shù)
- 默認的數(shù)組容量為 11
- 默認的負載因子為 0.75
- 初始化的時候，負載閥值默認為初始化容量
- 構(gòu)造方面內(nèi)就把數(shù)組初始化
簡介
- Hashtable是線程安全的
- 方法用synchronized關(guān)鍵字修飾，對象級別的鎖
- put的value不能為null，否則報錯
- 下標是通過求余(%)來計算
- 輸入通過鏈表頭部插入
擴容規(guī)則
- 擴容方法rehash()
- 數(shù)據(jù)量大于等于負載閥值開始擴容
- hash值直接通過Object.hashCode()獲取
- 擴容大小為(舊容量 * 2) + 1
- 負責閥值為容量大小 * 負載因子
存放數(shù)據(jù)的對象
- HashtableEntry <- Map.Entry
HashSet
原理
- HashSet有個內(nèi)部成員變量map為HashMap，操作都與map有關(guān)
- 數(shù)據(jù)存放規(guī)則和HashMap一樣
- add存放的值對應(yīng)HashMap的key,value為PRESENT的一個Object(),所以可以為null
- HashSet非線程安全
總結(jié)
- HashSet就是一個只關(guān)心key不關(guān)心value的HashMap封裝類
HashMap和Hashtable的區(qū)別
- 擴容規(guī)則HashMap是2的冪次，Hashtable是當前容量*2+1
- 鏈表插入HashMap是尾部插入，Hashtable是頭部插入
- HashMap會樹化，Hashtable一直是鏈表
- 下標計算HashMap是通過與運算，Hashtable通過求余
- HashMap非線程安全，Hashtable線程安全
- 默認情況下，HashMap在put才會初始化數(shù)組，Hashtable構(gòu)造方法內(nèi)就初始化
- hash值HashMap是高低16位通過異或運算，Hashtable直接獲取Object的hashCode
