1 基本定義
數(shù)據(jù)結(jié)構(gòu)
| 數(shù)據(jù)結(jié)構(gòu) | 數(shù)組 | 鏈表 | 紅黑樹 |
|---|---|---|---|
| 用途 | 存儲鍵值對崎溃。數(shù)組下標(biāo)為鍵的哈希值 | 解決哈希沖突 | 解決哈希沖突 |
定義參數(shù)
| 參數(shù) | initialCapacity |
loadFactor |
|---|---|---|
| 用途 | 用于定義數(shù)組容量匪蟀，但數(shù)組是延遲初始化的员寇。如果不是2的整數(shù)冪，會適當(dāng)擴大蛋辈。 | 負載因子色鸳，默認0.75舞萄。用于定義擴容閾值threshold。 |
基本特性
HashMap中允許null值和null鍵誊稚。null鍵對應(yīng)著哈希值0翔始，即數(shù)組的下表0。
HashMap是不保證對象的放入順序的里伯。
基本操作get和`put的時間性能基本為（如果不考慮哈希沖突的情況下）城瞎。
2 基本操作
讀
判斷hash/key，key值是否相等疾瓮，hash值是否相等
判斷是否是TreeNode脖镀，如果是從根節(jié)點二分查找(**問題TreeNode.find的最后的if else)
寫
判斷table是否存在
判斷節(jié)點是否存在
如果是Tree節(jié)點，執(zhí)行RB插入狼电；
如果不是Tree節(jié)點蜒灰，執(zhí)行鏈表插入，如果大于TREEIFY_THRESHOLD肩碟，則樹化强窖。
擴容
計算新容量和新擴容閾值
拷貝
- 如果是桶中是單個節(jié)點，重新hash到新表中削祈。
- 如果是樹節(jié)點翅溺，遍歷樹切分為低于和高于舊閾值的兩個鏈表，然后進行分別判斷是否進行樹化髓抑。
- 如果是鏈表咙崎，遍歷樹切分為低于和高于舊閾值的兩個鏈表。
樹和鏈表轉(zhuǎn)換
保持節(jié)點相對順序吨拍。
使用類和哈希值進行比較褪猛。
3 哈希算法
在哈希值隨機且擴容閾值為默認值0.75的情況下，哈希表每個桶的頻率遵循的泊松分布密末。由于擴容時粒度較大握爷，進而導(dǎo)致泊松分布的方差也很大跛璧。如果忽略方差的因素，哈希表桶列表長度為
的概率為
新啼。第一批值如下：
0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
more: less than 1 in ten million
哈希算法
- 直接尋址法（Identity hash function）
- 識字分析法
- 平方取中法
- 折疊法
- 隨機數(shù)法
- 除留取余法
沖突解決方法
- 開放定址法（線性探測追城、二次/平方探測、雙散列探測）
- 拉鏈法
- 再哈希
- 公共溢出區(qū)
