當(dāng)我寫下Map<String,Object> map = new HashMap<>();我到底在寫什么？
- 我什么時候會寫HashMap?
- 一個函數(shù)同時需要返回 多種 狀態(tài)的情況
- 舉例：一個列表有100個數(shù)據(jù)，一個函數(shù)對該列表進(jìn)行處理，并將該列表的數(shù)據(jù)劃分為A,B,C 3部分，此時函數(shù)的返回值就適用用map
- 當(dāng)需要保存鍵值對時
- 一個函數(shù)同時需要返回 多種 狀態(tài)的情況
- HashMap的實現(xiàn)是什么？
- 數(shù)組 + linkedList + 紅黑樹
- 容量閾值 都是指的HashMap中實際存放數(shù)據(jù)的數(shù)組的容量閾值
- 我該怎么寫HashMap?
// 1. 新建一個HashMap對象
Map<String,Object> map = new HashMap<>();
// 2. 向map中添加數(shù)據(jù)
map.put("key", value);
// 3. 從map中刪除數(shù)據(jù)
map.remove("key"); or map.remove("key", value);
// 4.修改map中的數(shù)據(jù)
map.replace("key", value); or map.replace("key", value, value); or map.put("key", value);
// 5. 從map中查找數(shù)據(jù)
map.get("key");
// 6. map的數(shù)據(jù)如何遍歷
String key : map.keySet() // 遍歷鍵
Object boj : map.values() // 遍歷值
Map.Entry<String, Object> entry : map.entrySet() // 遍歷鍵值對
- 當(dāng)新建一個HashMap對象時 到底發(fā)生了什么？
- 從下方HashMap的構(gòu)造函數(shù)可以看出:只是給出了初始容量-16 和加載因子-0.75。
- 從名字就看的出來 這兩個初始值 是決定 什么時候進(jìn)行hashmap 自動擴容的，但 此時內(nèi)部實現(xiàn)的數(shù)組并沒有初始化，并沒有實際用到這兩個值（畢竟構(gòu)造函數(shù)沒有相關(guān)代碼）。
- 這兩個值 實際使用是在 執(zhí)行擴容的resize()方法中，且只有向HashMap中添加數(shù)據(jù)時才會擴容，可以理解為 這里的兩個參數(shù)是在 第一次調(diào)用put才用到。使用時，兩者相乘的結(jié)果轉(zhuǎn)為int類型 作為閾值。
- 順便說一下，擴容時，還會重新決定各個鍵值對在HashMap的實現(xiàn)數(shù)組中的索引（e.hash & （容量 - 1））。如果數(shù)組中存儲的是鏈接表 or 紅黑樹，新的索引由（e.hash & 容量） == 0 比較決定。這個很容易理解，就是看容量左邊那一位是不是0，若是則索引不變，若不是則新索引 = 舊索引+ 容量。這三種情況索引膨脹后 索引不會碰撞，這得益于按2的指數(shù)增長容量的方式
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* Constructs an empty {@code HashMap} with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
- 向map中添加數(shù)據(jù) 又發(fā)生了什么？
哈希碼部分參考：https://www.zhihu.com/question/20733617
- 擾動函數(shù)-hash： 混合 hashcode的高位和低位，加大哈希碼低位的隨機性。將高位和低位的特征都匯集到低位。且由上一個問題的理解里可知哈希碼最終還決定了具體存放在數(shù)組的那個位置，所以這么做，在數(shù)組容量較小的情況下，只會用到低位來決定放置位置，低位具備了更多的特征，也會減少碰撞
- 擴容-每次擴容1倍；擴容時，需重新分配索引
- 對新增對象 判斷放置索引，若該索引處無對象，則放置
- 若該索引處已經(jīng)有對象，且已有對象與新增對象 hash一致,鍵一致，
- 若已有對象是紅黑樹， 則加入樹
- 其他情況則已有對象是 鏈表，新對象加入鏈表
- 若新對象加入鏈表后，鏈表長度 超過鏈表閾值，則將鏈表轉(zhuǎn)為紅黑樹
- 4，5，6中 若 鍵值重復(fù)【 hash一致,鍵一致】，則替換值， 并返回舊值
- 修改后，數(shù)組大小超過 閾值，擴容
- 關(guān)于紅黑樹，見https://www.cnblogs.com/liwei2222/p/8013367.html
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
- 增刪改查就不一一說了，原理都類似于put方法
