HashMap
源码解析
添加源码解析
resize()
这个方法在putval中执行，因为要确保你数组不是null
resize就是重新计算容量；向HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素；当然java里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组；就像我们用一个小桶装水，如果想装更多的水，就得换大水桶。
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;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
}
else if (oldThr > 0)
newCap = oldThr;
else {
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) {
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 {
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;
}
int oldThr = threshold;
第一次的时候threshold，初始化是0
int oldCap = (oldTab == null) ? 0 : oldTab.length;
oldTab是那个原来的数组，第一次没东西所以长度是0，进else语句
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
这行说的是第一次进来我们的容量是16，负载因子是0.75，按照这个结果也就是12，当数组长度超过12时进行扩容
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
第一次初始化，newCap = DEFAULT_INITIAL_CAPACITY;，也就是16，所以初始化数组长度为16
if (oldTab != null) {
oldTab是原来的table，原来table默认初始化是null
至此直接return newTab；
总结：
第一次进来，首先会看你这个数组的长度，没有就是0。所以接下来他就去初始化临界值为12，根据默认长度初始化数组为16个容量，因为是第一次oldTable是null，所以直接返回初始化的结果，此时table初始化成功，长度为16（Node<K,V>[16])
putVal()
首次添加
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)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
~~~~~
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
if ((p = tab[i = (n - 1) & hash]) == null)
初始化完成后，他会去根据数组长度-1与计算的hash码进行与运算的出来放的数组位置，他会去看这个位置有没有元素
有呢就创建一个Node放到这个位置就可以了
如果不是null那就只能链表操作了，那个操作等会说
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
之后呢，我们要变更size的大小，因为size是记录有多少个真正的元素在这个数组中，threshold就是临界值，我们初始化好了，这个值就是12，这个if呢就是为了判断，你添加到数组的元素，你不能大于这个临界值，那你要是大于了，那我就去扩容去了，否则了那就没事了
afterNodeInsertion(evict);
这玩意是为了LinkedHashMap服务的，是为了保证顺序而存在的，在hashmap中没意义。
下次添加
本次添加不会再进第一个if，因为第一个if是判断table是否为null进行初始化的，所以他会先走这句
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
还是判断计算出位置看有没有值，没值的话直接插入就行
当出现相同的值时，他所的出来的位置是一样的，所以上面的判断不成立，直接走到else语句。
也就是说出现了可能出现hash冲突
else {
Node<K,V> 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<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)
treeifyBin(tab, hash);
break;
}
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;
afterNodeAccess(e);
return oldValue;
}
}
在这里面有三种情况
第一种 判断全都是否一致
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
因为
if ((p = tab[i = (n - 1) & hash]) == null)
这句话虽然判断不成立，但也会给p这个变量赋值，这个p就代表了这次相同位置的元素的值Node
首先p.hash == hash 这句，是当前位置的hash值是否与你现在的哈希值是否一样（此处的哈希值是无符号右移16位在异或的值）
之后((k = p.key) == key || (key != null && key.equals(k)))这个是一个整体先看第一部分
(k = p.key) == key ，他会去看p节点的key值是否与你传入的key是不是同一个对象
(key != null && key.equals(k))，会判断你传入的是不是一个null 并且不是的话调用equals()方法判断是不是相等
那么就把当前位置的这个值p拿出来给e
第二种
p instanceof TreeNode
看当前节点是不是一个TreeNode对象类型
是的话
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
走这个，强转赋值
第三种，啥也不是那就是真正的出现了hash冲突
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
依次判断当前这个节点的next节点有没有东西，没有的话那就直接指向这个新的节点也就是你传入的
if (binCount >= TREEIFY_THRESHOLD - 1)这句话很关键，也就是说他会一直循环看看你这个链表的长度是多少，如果你比8大，也就是转成红黑树的因子还要大的时候，treeifyBin(tab, hash);给你穿成了红黑树，break掉
第二个if呢，是看当前链表节点的next节点的hash值是否如你的传入的hash是一样的，并且next节点的key值如你的key是否是一个对象或者在你这key不是空的条件下，调用equals方法判断是否一致。说白了就是tm的你传入的节点的值，引用和当前节点完全一样就是同一个东西那就直接break了，什么也不干；（注意此时比较的是next与你传入的是否一致）
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
就是一个值的覆盖
再说一下树化，发生在第三种for循环里的添加，那时候会判断是否满足先决的树化条件
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
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);
}
}
首先会把table和hash传入，判断table也就是数组是不是空的，或者数组的长度是不是小于64（MIN_TREEIFY_CAPACITY）如果满足了就进行扩容而不是树化
也就是说树化必须是：存在链表长度大于8，数组长度必须大于64的时候才会发生
之后呢，(e = tab[index = (n - 1) & hash]) != null这行也就是说你添加的key要插入在数组中的位置必须不等于空才能树化，这不是废话吗。
do while（(e = e.next) != nul）不断循环当前这个数组的节点位置上的链表，把每一个转换成TreeNode（replacementTreeNode(e, null)），进行添加树节点prev是上边的next下边的
|