資訊專欄INFORMATION COLUMN
摘要：考慮兩大情況，已經(jīng)存在這個紅黑樹中當(dāng)中了，就直接放回對應(yīng)的那個節(jié)點從紅黑樹的節(jié)點開始遍歷，定位到要插入的葉子節(jié)點，插入新節(jié)點除了要維護紅黑樹的平衡外可以參考源碼，還需要維護節(jié)點之間的前后關(guān)系，這里似乎同時是在維護雙向鏈表關(guān)系。
舉例一個入口，利用一個Map構(gòu)造HashMap時
/**
* Constructs a new HashMap with the same mappings as the
* specified Map. The HashMap is created with
* default load factor (0.75) and an initial capacity sufficient to
* hold the mappings in the specified Map.
*
* @param m the map whose mappings are to be placed in this map
* @throws NullPointerException if the specified map is null
*/
public HashMap(Map m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
然后就是調(diào)用putMapEntries方法，第二個參數(shù)其實可以看作細節(jié)，個人認為它和HashMap的子類LinkedHashMap有關(guān)，evict是逐出的意思，如果基于LinkedHashMap實現(xiàn)LRU緩存的話，這個evict參數(shù)正好就用上了。
/**
* Implements Map.putAll and Map constructor
*
* @param m the map
* @param evict false when initially constructing this map, else
* true (relayed to method afterNodeInsertion).
*/
final void putMapEntries(Map m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
for (Map.Entry e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
可以看到在for循環(huán)中遍歷舊的entrySet視圖，然后將一個個的key-value對放入新構(gòu)造的HashMap中，
for (Map.Entry e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
展開putVal(hash(key), key, value, false, evict);
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don"t change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node 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 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)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;
}
通過hash(key)定位到HashMap中tab數(shù)組的索引，如果這個數(shù)組元素的頭節(jié)點正好是TreeNode類型，那么就將執(zhí)行
