P9 get和resize操作（Java 13）
标签：hold 需要 原来 移动 ihe 搬运 power 数据 ini
直奔主题，奉上HashMap中get 函数源码解析：
public V get(Object key) {
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods.
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node getNode(int hash, Object key) {
Node[] tab; Node first, e; int n; K k;
// 拿到 table 中对应位置的节点 p
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 如果该位置头结点就是要找的，直接返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 如果后边还有元素
if ((e = first.next) != null) {
// 如果是红黑树，去红黑树里找
if (first instanceof TreeNode)
return ((TreeNode)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;
}
get其实就是put的逆向过程，你可能直接从table[i]中取走键值对，也可能是从红黑树或者链表中取走一个节点。
只满足equlas相等并不能有效取出元素，还必须满足哈希值相等，所以要考虑重写key的hashCode()方法。
扩容机制
扩容(resize)就是重新计算容量。向HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然Java里的数组是无法自动扩容的，方法是采用再散列方法，即使用一个新的数组代替已有的容量小的数组，就像我们用一个小桶装水，如果想装更多的水，就得换大水桶。
扩容函数resize源码解析：
/**
* 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[] resize() {
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length; // 注意这里
int oldThr = threshold;
int newCap, newThr = 0;
// oldCap > 0, table 非空
if (oldCap > 0) {
// 如果超过最大容量
if (oldCap >= MAXIMUM_CAPACITY) {
// 扩容阈值设为最大值，返回旧table，不允许再扩容
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 旧容量大于默认初始化容量且扩容两倍后小于最大容量，则扩容两倍
else if ((newCap = oldCap
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr // double threshold
}
// oldCap // oldThr > 0, 非默认构造函数的情况
// 直接用oldThr 当做新的容量。oldThr由tableSizeFor()方法得出，一定是2的幂
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);
}
// 如果上边没有给出新的扩容阈值，则用 newCap * loadFactor 计算
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 新 扩容阈值 赋值
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])new Node[newCap];
// 用新的容量创建新的 table 并赋值
table = newTab;
// 如果旧 table 不是空，需要搬运数据
if (oldTab != null) {// 把每个bucket都移动到新的buckets中
for (int j = 0; j j) {
// j 位置的节点
Node e;
// 如果节点不为空
if ((e = oldTab[j]) != null) {
// 置空旧table
oldTab[j] = null;
// 如果只有一个元素，直接赋值
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果是树节点
else if (e instanceof TreeNode)
// 处理。。。
((TreeNode)e).split(this, newTab, j, oldCap);
// 如果是链表
else { // preserve order
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do {
next = e.next;
// 扩容一倍后，原来位置的链表节点，要被分配到新 table 的两个位置上去
// 如果去高位
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);
// 低位放在新 table j 位置
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 高位放在新 table j + oldCap 位置
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
P9 get和resize操作（Java 13）
标签：hold 需要 原来 移动 ihe 搬运 power 数据 ini
原文地址：https://www.cnblogs.com/east7/p/12797716.html
评论