put
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)//查看Node数组是否为空或Node数组长度是否为0，//满足条件则进行首次扩容（初始化），默认长度为16，//并且设置阈值为12。判断是否第一次扩容，如果是则进行元素的移动，//反之直接返回初始化后的Node数组n = (tab = resize()).length;if ((p = tab[i = (n - 1) & hash]) == null)//Node数组长度-1&key的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))))//根据上一步的寻址找到对应Node对象，判断hash值是否一致，//或者key的equals一致则赋值给临时变量//考虑数据量不多的情况，链表的第一个Node就是寻址目标e = p;else if (p instanceof TreeNode)//如果是树形结构，那么强转为TreeNode进行put操作e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {//寻址到的Node的后一个兄弟节点为null,加入到链表中p.next = newNode(hash, key, value, null);if (binCount >= 8 - 1) // -1 for 1st//挂载Node大于等于7则进行红黑树转换，跳出循环treeifyBin(tab, hash);break;}if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))//寻址到了Node，经过equals方法确认是当前Node，跳出循环break;//赋值，为下一次判断p = e;}}if (e != null) { // existing mapping for key//对寻址到的Node进行操作，线取出旧的值V oldValue = e.value;//如果存在就不进行赋值操作，此处onlyIfAbsent为false，所以恒真，会将值覆盖if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}//统一处理 修改次数累加，对下次put预扩容++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;}
resize_
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;//当前Node数组长度
int oldThr = threshold;//当前长度阈值
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
//如果容量已经大于等于2的31次方，那么阈值等于int最大值
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
//如果新容量小于2的31次方并且旧容量大于等于默认容量，那么新阈值等于旧阈值*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];
//赋值Node数组
table = newTab;
if (oldTab != null) {
//非初始化操作，进行元素的移动
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
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;
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;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
remove
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
//判断Node数组是否初始化过并且是否长度不为0并且能够寻址到对应下标不为null
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//如果第一个就是要移除的元素，通过hash和equals判断
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
//如果是树形结构，通过树的方法寻找元素
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
//挂载了N个节点，hash+equals寻找
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
//移除元素，但是可能考虑缩容后要重新开辟空间，并且原有的内存需要GC回收而引发STW，所以没做处理
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
get
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//需要Node数组初始化过
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
//第一个就满足，则直接返回
return first;
if ((e = first.next) != null) {
//解决hash碰撞问题，equals确认唯一实例
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
总结
增删改查操作都是基于hash寻址，然后通过equals解决hash碰撞问题。另在寻址期间优先考虑第一个，因为散列大多情况下发生碰撞的几率不高。在扩容时，每次增加一倍，具体操作为向左位移1位，为2的N次幂，主要解决元素移动次数。另不会在移除后缩容，考虑STW带来的效率问题，在链表转红黑树时，也会判断Node数组长度是否大于64，如果小于该容量，也会进行扩容操作
若有收获，就点个赞吧
0 人点赞
