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) {
//声明局部变量tab和节点p
Node<K,V>[] tab; Node<K,V> p; int n, i;
//将哈希表table赋值给tab，并判断tab是不是为空
//如果为空表示table还没使用，调用resize()创建新表
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//通过(n - 1) & hash找出插入的数据在哈希表中的位置
//如果不存在，则创建一个新的节点
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//要插入的数据在哈希表中存在，
//则判断插入数据的hash值与当前位置的hash值是否相同
//hash值相同，就判断两者的key是否相同
//hash值和key都相同，表示实际要替换原来的value
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 {
//如果当前节点不是红黑树节点并且hash与key值都出入数据不同
//则沿着链表向后查找是否该key
for (int binCount = 0; ; ++binCount) {
//如果遍历都链表尾部还没找到该key，则新建节点，链尾插入
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果插入后链表长度大于阈值，则转换成红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//遍历过程找到hash和key相同的节点，表示该key已存在，跳出for循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { //表示插入的数据已存在，则根据条件判断是否更新
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//回调以允许LinkedHashMap后置操作
afterNodeAccess(e);
return oldValue;
}
}
++modCount;//增加操作次数
//哈希表容量大于阈值，则调用resize进行扩容和元素调整
if (++size > threshold)
resize();
//回调以允许LinkedHashMap后置操作
afterNodeInsertion(evict);
return null;
}
//哈希表初始化或扩容，元素调整
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) {//旧容量>0,表示不是初始化
if (oldCap >= MAXIMUM_CAPACITY) {//旧容量>MAXIMUM_CAPACITY
threshold = Integer.MAX_VALUE;//阈值调到最大，然后返回
return oldTab;
}
//旧容量扩大一倍后如果小于MAXIMUM_CAPACITY,且旧容量大于默认的容量
//将旧阈值扩大一倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//resize（）函数在table为空被调用。
//oldCap 小于等于 0 且 oldThr 大于0，代表用户创建了一个 HashMap，
//但是使用的构造函数为HashMap(int initialCapacity, float loadFactor) 或
// HashMap(int initialCapacity)或
//HashMap(Map<? extends K, ? extends V> m)，
// 导致 oldTab 为 null，oldCap 为0，
//oldThr 为用户指定的 HashMap的初始容量
else if (oldThr > 0)//旧阈值>0，直接复制给新容量
newCap = oldThr;
//resize（）函数在table为空被调用。
//oldCap 小于等于 0 且 oldThr 等于0，用户调用 HashMap()构造函数创建的
//HashMap，所有值均采用默认值
else { //初始化容量和阈值操作
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//？？？如果新的阈值仍然为0
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) {
//旧表调整元素
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//置旧表该节点为空
oldTab[j] = null;
//表示e节点为单节点，在新表上重新计算该节点的位置
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//e节点为红黑树节点，则要进行红黑树节点的调整
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { //链表调整
//记录rehash后位置不发生改变的节点
Node<K,V> loHead = null, loTail = null;
//记录rehash后位置发生改变的节点
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//(e.hash & oldCap)判断e节点rehash后位置是否发生改变
//(e.hash & oldCap) == 0表示最高位为0，位置不发生改变
//将位置不发生改变的节点组成一条链
if ((e.hash & oldCap) == 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;
}
//将位置发生改变的链接入新表，位置为j+oldCap
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
网友评论