此为原创，转载请注明地址
基于JDK1.8
一、带着问题去学习，先问自己几个简单的问题，哪里不会再去争对性学习，效率瞬间提高～
1、hashMap 允许key为 null 吗
2、hash如何计算
3、初始化长度为21时，实际数组长度是多少？
4、扩容为什么是2的n倍？
5、put()里面执行流程
6、get()执行流程?
7、hashMap是如何减小hash碰撞的？
8、查询时间复杂度
9、增删时间复杂度？
10、里面是单链表还是双链表？
11、链表和红黑树如何切换？
12、为什么要用红黑树？
13、里面数组如何扩容、扩容时数据如何迁移？
14、扩容后旧数组是如何处理？
二、 对应学习记录
1、允许,调用put()方法后会对key 求hash(),如果key为null 返回0，也就是存在第一个位置
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
2、首先调用object的hashCode(), 然后再与自己的高16位求异或，此为“扰动函数”实验数据可以降低10%的hash碰撞
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
3、32。跟着源码一步步会走到这个方法，生成一个不小于输入值的2的幂次方数
static int MAXIMUM_CAPACITY = 1 << 30;
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
4、 计算数组下标时可以提升效率。可以通过&运算得到数组保存位，从而提升速度。偶数减1后，求与刚好可以保留低位值，即数组下脚标。
if ((p = tab[i = (n - 1) & hash]) == null){
tab[i] = newNode(hash, key, value, null);
}
5、
6、
7、
（1）加入了扰动函数，实验数据表明可以下降10%
（2）size > length * factor 时，会进行数组扩容
8、 接近于O（1）
9、 接近于O（1）
10、单链表
11、
12、
13、扩容时会重新创建一个数组,新创建大小为元数组2倍。
扩容时的代码如下，数据迁移大约分为3种情况，
1、节点为1个时，直接根据hash计算新的下角标。
2、节点为红黑树时，
3、节点数大于1时，开始进行迁移，部分下角标不变，部分小角标会增加一个oldTab的长度。
//注释2。 0代表下角标不变，1代表下角标改变
(e.hash & oldCap) == 0
链表增加节点的方式为尾部增加。
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; // 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) {
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) {//注释2
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;
}
14、扩容在数据迁移时，旧数组内容会被置为null
if ((e = oldTab[j]) != null) { //遍历旧数组进行数据迁移
oldTab[j] = null;
//To do...
}
younger
2021年10月
