基于JDK1.8的HashMap部分源码解读。这里就解读一下map的put方法。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* 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<K,V>[] tab; Node<K,V> p; int n, i;
//进行一下判断，若符合判断的，表示该map刚创建，还没存放过元素
if ((tab = table) == null || (n = tab.length) == 0)
//进行map的的一些参数设置，里面会去设置容量，扩容因子等。map的扩容也是调的该方法
n = (tab = resize()).length;
// 判断该索引位是否已经存在元素
if ((p = tab[i = (n - 1) & hash]) == null)
//不存在元素，则在该索引位创建一个Node元素对象
tab[i] = newNode(hash, key, value, null);
else {
//存在元素
Node<K,V> e; K k;
//判断该存在的元素的key是否与要存入的元素一致，若一致，则将e的引用执行该已存在的对象
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
//已存在的元素的key与传入的key不同，且该索引处的数据结构是否已经变成树结构，则增加树节点。其内部设计到数结构的一些算法操作，左旋右旋之类的
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
//TREEIFY_THRESHOLD=8，如果链表的长度大于等于8，则转为树结构，其方法内部有条件要求的，要node[]的长度大于MIN_TREEIFY_CAPACITY=64才会变成树结构，不然会进行一次扩容
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
//如果链表中的元素的key与要存入的key一致，则跳出循环
break;
//获取链表的下一个元素，接着做上述操作
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
//若e对象不为null且onlyIfAbsent 为false，则将传入的value替换原有的value值，并返回原有值。（已存在的元素跟要存入的元素如果key不同，该操作没啥特殊意义）
e.value = value;
//该方法里没做什么，空实现而已
afterNodeAccess(e);
return oldValue;
}
}
//若有增加新的节点，则modCount+1
++modCount;
if (++size > threshold)
//如果添加完元素后，node[]满足扩容条件，则进行扩容
resize();
//该方法里没做什么，空实现而已
afterNodeInsertion(evict);
return null;
}
/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//MIN_TREEIFY_CAPACITY的值为64
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
// 进行node[]的扩容
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
//对生成的数结构进行顺序调整
hd.treeify(tab);
}
}
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
//若原数组长度已经大于等于最多允许长度，则不再扩容了
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//新生产的数组长度扩大为原来的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//新生产的扩容银子也扩大为原来的2倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//创建新容量的数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
//遍历旧node[]数组中的元素，将其更新到新的数组中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
//这里可以直接赋值，不用担心这个索引位置已经有元素存在，细品，这就是采用2的n次方扩容的好处
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//直接判断新增的那一位与元素的hash值的结果。
//该处有疑问可以参考上《关于HashMap的源码解读一》
if ((e.hash & oldCap) == 0) {
//如果结果为0，表示其索引位置没变
if (loTail == null)
//低位链表头
loHead = e;
else
loTail.next = e;
//低位链表尾
loTail = e;
}
else {
if (hiTail == null)
//高位链表头
hiHead = e;
else
hiTail.next = e;
//高位链表尾
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
//因为是扩容一倍，所以该高位索引位置只要加上原来的容量值即可
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
