HashMap-01
HashMap-01
HashMap基础
HashMap存储结构
在JDK1.7中和JDK1.8中有所区别： 在JDK1.7中，由”数组+链表“组成，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的。
在JDK1.8中，由“数组+链表+红黑树”组成。当链表过长，则会严重影响HashMap的性能，红黑树搜索时间复杂度是O(logn)，而链表是O(n)。因此，JDK1.8对数据结构做了进一步的优化，引入了红黑树，链表和红黑树在达到一定条件会进行转换：
当链表超过8且数组长度(数据总量)超过64才会转为红黑树 将链表转换成红黑树前会判断，如果当前数组的长度小于64，那么会选择先进行数组扩容，而不是转换为红黑树，以减少搜索时间。 ArrayList底层是动态数组数据结构，查询快，增删慢（因为Array增删需要移动数据），LinkedList底层是双重链表数据结构，查询相对较慢（因为Link查询需要移动指针），增删块。
HashMap的node属性
HashMap有一个重要的属性Node<K,V>,Node是HashMap的一个内部类实现了Entry接口，本质是一个映射
Node类基本属性有：
hash：key的哈希值
key：节点的key，类型和定义HashMap时的key的类型一致
value：节点的value，类型和定义HashMap时的value的类型一致
next：该节点的下一个节点
next属性记录的是下一个节点本身，也是一个Node节点，这个Node节点也有next属性，也记录了下一个节点，这样的一个链表结构，对于一个HashMap来说，只需要明确记录每个链表的第一个节点，就能顺序遍历链表的所有节点。
HashMap的容量
HashMap的默认容量16
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY =1<<4;//aka 16
HashMap的负载因子
HahhMap的默认加载因子是0.75
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR =0.75
当HashMap的元素超过容量*加载因子时，HashMap会进行扩容
HashMap的hash算法
HashMap的hash返回值：
问题：HashMap⾥⾯的hash()返回值为什么不是的返key.hsahCode()的返回值，⽽是key.hsahCode()^(key.hsahCode()>>>16)的返回值呢？
static final int hash(Object key){
int h;
return(key ==null)?0:(h = key.hashCode())^(h >>>16);
}
提示
这样做的目的是减少hash的冲突概率
HashMap在put的时候，hash冲突时不可避免的，所以如何尽量避免hash冲突，或者在hash冲突时如何快速高效定位到数据的真实存储位置，就是HashMap中最核心的部分key.hsahCode()^(key.hsahCode()>>>16)的逻辑就是先获得key的hashCode值h，然后h和h右移16位做异或运算，这样高16为也参与到hash的逻辑运算中了，减少冲突。
例
比如有两个key的hashCode返回值如下：
key1.hashCode()
1111 1111 1111 1111 0101 0101 0111 0101
key2.hashCode()
1111 1111 1110 1111 0101 0101 0111 0101
如果没有^(key.hsahCode()>>>16)那么，15&hash就分别是
key1在底层的数组索引值是：5
1111 1111 1111 1111 0101 0101 0111 0101
0000 0000 0000 0000 0000 0000 0000 1111
key2在底层的数组索引值是：5
1111 1111 1110 1111 0101 0101 0111 0101
0000 0000 0000 0000 0000 0000 0000 1111
这是因为key1.hashCode()和key2.hashCode()的低16位完全相同，然后15&hash的时候，15的二进制00000000000000000000000000001111的高位全是0，这就造成了15&hash的时候，只有hash的低16为起了作用，而key1.hashCode()和key2.hashCode()的低16位完全相同，所以底层索引值也相同了，这样很容易造成hash冲突。但如果有^(h >>>16)
相关信息
比如有两个key的hashCode返回值如下：
就比如key.hsahCode()也就是h的变量值如下：
1111 1111 1110 1111 0101 0101 0111 0101
然后(h = key.hashCode())^(h >>>16)就变成
1111 1111 1110 1111 0101 0101 0111 0101^
0000 0000 0000 0000 1111 1111 1110 1111
计算结果是：1111 1111 1110 1111 1010 1010 1001 1010
这里可以看出，最终的结果值具备了高16位与低16位共同的特征，这样减少了hash冲突的概率。
HashMap的数组+链表/树
HashMap为什么要引入链表？
HashMap底层是数组，当map进行put操作的时候，会进行hash计算，判断这个对象属于数组的哪个位置，当多个对象在数组的同一位置时，就会有hash冲突，这个时候就引入了链表。
为什么jdk1.8会引入红黑树？
当链表长度大于8时，遍历查找效率较慢，故引入红黑树。并不是只需要链表长度大于8 ，同时需要满足数组长度大于64；还有如果红黑树的节点个数小于6时，红黑树会变成链表。
HashMap为什么不一开始就使用红黑树
这是因为红黑树维护成本比较大，红黑树在插入新数据后，可能会通过左旋，右旋，变色来保持平衡，造成维护成本过高，故链路较短时采用链表。
HashMap底层数组取值时为什么不用取模而是&
tab[i = (n-1) & hash],这是因为在计算机运算时，使用&比取模性能更快，
数组长度为什么是2的次幂。
总共有3个好处：
- 为了减少hash冲突，就是为了数据均匀分布，此时我们一般使用公式（hashCode%size），这样可以达到最大平均分配，而（n-1）& hash，当n为2的次幂时，会满足一个公式（n-1）& hash = hash % n
- &的运算速度快，比取模的运算速度更快，根据计算java的%，/操作比&慢10倍左右
- 能保证索引值肯定在capacity中，不会超出数组长度。
指定数组长度不是2次幂，会破坏2次幂规则吗
不会的，HashMap的tableSizeFor方法做了处理，能保证永远保证2次幂
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap){
//cap-1 后，n的⼆进制最右⼀位肯定和cap的最右⼀位不同，即⼀个为0，⼀个为1，例如cap=17（00010001），n=cap-1=16（00010000）
int n = cap -1;
//n = (00010000 | 00001000) = 00011000
n |= n >>>1;
//n = (00011000 | 00000110) = 00011110
n |= n >>>2;
//n = (00011110 | 00000001) = 00011111
n |= n >>>4;
//n = (00011111 | 00000000) = 00011111
n |= n >>>8;
//n = (00011111 | 00000000) = 00011111
n |= n >>>16;
//n = 00011111 = 31
//n = 31 + 1 = 32, 即最终的cap = 32 = 2的 (n=5)次方
return (n <0)?1:(n >= MAXIMUM_CAPACITY)? MAXIMUM_CAPACITY : n +1;
}
HashMap源码
1.8的put方法
- 如果key对应的索引位置是的值null，那么直接插入
- 如果key对应的索引位置的数组的值不为null，判断这个老值的key和新值的key是否相同，如果相同就把老的值返回，并记录这个位置。
- 如果key对应的索引位置的数组的值不为null，判断这个位置的值是不是树结构，如果是树结构，调用树结构的putTreeVal方法添加数据。
- 如果key对应的索引位置的数组的值不为null，然后这个索引位置的值就是一个链表结构，然后遍历所有链表（当遍历长度大于8时，就会转成树结构），如果链表里的key值和新key值相同就把老的值返回，并记录这个位置。如果遍历到尾部还不相同，就是用尾插法把数据添加进去。
对2步骤和4步骤记录的位置进行处理，一是把标记位置的老值给返回，二是把新插入的值放在标记位置上面。
/**
* Implements Map.put and related methods.
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//table为空或者没有元素时，则扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果首节点的值为空，则创建一个新的首节点
//注意（n-1）& hash才是真正的hash，也就是存储在table位置的index，
//在1.6中是封装成indexFor函数
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {//到这就说明碰撞了，就要处理碰撞
Node<K,V> e; K k;
//如果在首节点，与我们待插入的元素有相同的hash和key值，则先记录
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);
//当遍历节点数目大于8时，采取树话结构
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果找到与我们待插入元素具有相同的hash和key值的节点，则停止遍历，此时e已经记录了该节点
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//表示记录到具有相同元素的节点
if (e != null) { // existing mapping for key
V oldValue = e.value;
//onlyIfAbsent表示如果当前位置已存在一个值，是否替换，false是替换，true是不替换
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);//这是一个空函数可以根据用户需要覆盖
return oldValue;
}
}
++modCount;
//当节点数+1大于threshold时扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);//这是一个空函数可以根据用户需要覆盖
return null;
}
HashMap在put()时,如果put一个已经存在的key，那么会把老的key对应的值返回
1.8的get方法
- 首先获取当前key对应的数组索引位置，然后判断该位置的首节点是否是自己想要的值，根据key和key.hashCode()来判断
- 首节点如果不是的话，判断节点是否是树节点，如果是的话，调用getTreeNode()来实现get()方法，如果不是树节点，那么就是链表，然后死循环遍历链表，查询是否有自己想要的值
如果上面的步骤都没有查询到数据，直接返回null
底层源码：
public V get(Object key) {
//定义一个node对象来接收
Node<K,V> e;
//调用getNode()方法，返回值赋给e，如果取得值为null，就返回null，否则就返回node对象e的value值
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
//取hash值方法，HahsMap的put方法也是调用了这个方法，get方法也调用了这个方法保证存取时key对应的hash值是一致的，这样才能正确对应
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final Node<K,V> getNode(int hash, Object key) {
//定义几个变量
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//首先判断数组的table不能为空，且长度要大于0，同时把数组长度tab.length赋给n
//其次是通过（n-1）& hash获取key对应的索引，同时数组中这个索引要有值，然后赋值给first变量
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
//这个first其实就是链表的头节点了，接下来判断first的hash值是否等于传过来key的hash值。
// always check first node
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
//如果满足上述条件的话，说明要找的就是first节点，直接返回
return first;
//走到这一步，就说明要找的节点不是首节点，那就用first.next找他的后继节点，并赋值给e变量，在这个变量不为空时
if ((e = first.next) != null) {
//如果首节点是树类型的，那就用getTreeNode()去树里寻找
if (first instanceof TreeNode)
//获取树中对应key节点直接返回
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//走到这一步说明结构还是链表
do {
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
//获取e节点的后继节点，赋值给e，不为空进入循环体
} while ((e = e.next) != null);
}
}
//以上条件都不满足说明没有该key对应的数据节点，返回null
return null;
}
1.7HashMap的扩容原理
1.7的扩容原理，什么时候扩容和扩容多少，1.7的扩容从put方法作为入口讲解，put(K,V)操作？
public V put(K key,V value){
if(key==null)
return putForNullKey(value);
int hash = hash(key);//计算key的hash值
int i = indexFor(hash,table.length);//通过hash值对应到桶的位置
for(Entry<K,V> e = table[i]; e != null; e = e.next){
//顺序遍历桶外挂的单链表
Object k;
if(e.hash == hash && ((k = e.key) == key || key.equals(K))){
//注意这里的健的比较方式==或者equals
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//遍历单链表完毕，没有找到与健相对应的Entry，需要新建一个Entry换句话说桶i是一个空桶
addEntry(hash,key,value,i);
return null;
}
既然找到一个空桶，那么新建的Entry必定是这个桶外挂单链表的第一个节点，通过addEntry，找到了扩容的时机
void addEntry(int hash,K key,V value,int bucketIndex){
//size记录的是map中包含entry的含量
//threshold记录的是需要resize的阙值，且threshold=loadFactor*capacity
if((size >= threshold) && (null != table[bucketIndex])){
//当size大于等于某个阙值threshold的时候且该桶并不是一个空桶
resize(2*table.length);//将容量扩容为原来的两倍
hash = (null!=key) ? hash(key) : 0;
bucketIndex = indexFox(hash,table.length);//扩容后，该hash值对应的新的桶的位置
}
createEntry(hash,key,value,bucketIndex);//在指定桶的位置创建一个新的Entry
}
void createEntry(int hash,K key,V value,int bucketIndex){
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash,key,value,e);//链表的头插法插入新建的Entry
//size记录的是map中包含entry的含量
size++；//更新size
}
//capacity其实就是桶的长
threshold=(int)Math.min(newCapacity*loadFactor,MAXIMUM_CAPACITY+1);
因此现在总结出扩容的时机：
当map中包含的Entry的数量大于等于threshold=loadFactor*capacity的时候，且新建的Entry刚好落在一个非空的桶上，此刻触发扩容机制，将其容量扩大为2倍。
这个这样说明比较好理解：因为size已经大于等于阙值了，说明Entry数量较多，hash冲突严重，那么若该Entry对应的桶不是一个空桶，这个Entry的加入必然会把原来的链表拉的更长因此需要扩容；若对应的桶是一个空桶，那么此时没有必要扩容。
重要
当size大于等于threshold的时候，并不一定会触发扩容机制，但是会很可能触发扩容机制，只要有一个新建的Entry出现哈希冲突，则立刻resize。
1.7HashMap的扩容过程
上面有一个很重要的方法，包含了几乎属于的扩容过程，就是resize()；
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY){
//最大容量为1<<30
threshold = lnteger.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity]; //新建一个新表
boolean oldAltHashing = useAltHashing;
useAltHashing |= sun.misc.VM.isBooted() && (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean rehash = oldAltHashing ^ useAltHashing;//是否再hash
transfer(newTable, rehash);//完成旧表到新表的转移
table = newTable;
threshold = (int) Math.min(newCapacity * loadFactor,MAXIMUM_CAPACITY +1);
}
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for(Entry<K,V> e : table){
//遍历同桶数组中的每一个桶
while(null != e){
//顺序遍历某个桶的外挂链表
Entry<K,V> next = e.next; //引用next
if (rehash){
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);//找到新表的桶位置 ;原桶数组中的某个桶上的同一链表中的Entry此刻可能被分散到不同的桶中去了，有效的缓解了哈希冲突
e.next = newTable[i];//头插法插入新表中
newTable[i] = e;
e = next;
}
}
}
对于resize的过程，相对来说是比较简单清晰易于理解的，旧桶数组中的某个桶的外挂单链表是通过头插法，插入新桶数组中的，并且原链表的Entry节点并不一定在新桶数组的同一链表
这很容易就想到在多线程的情况下，这个transfer方法在多线程的环境下会乱套，事实也是这样的，由于缺乏同步机制，当多个线程同时resize时，当某个线程t所持有的引用next（参考上面代码next指向源桶数组中某个桶外挂单链表下一个需要转移的Entry），可能已经被转移到了新桶数组中，那么最后该线程t实际上在对新的桶数组进行transfer操作。
如果有更多的线程出现这种情况，那很可能会出现大量线程都在对新桶数组进行transfer，这样极易造成死循环，数据丢失等等，因此HashMap不是线程安全的，所以考虑在多线程并发环境下使用并发工具包下的ConcurrentHashMap。
1.8HsahMap的扩容原理
JDK1.8对resize()方法进行了很大的调整，JDK1.8的resize()方法如下：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;//定义oldCap参数，记录了table长度
int oldThr = threshold;
int newCap, newThr = 0;//定义了newCap参数，记录了新table长度
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 //扩容newCap时oldCap长度的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);
}
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) {//循环原table，把原table中的每个链表中的每个元素放入新table
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)//指的是链表中只有一个元素，所以直接吧e放入新table，其中e.hash&(newCap-1)就是计算e在新table中的位置，和JDK1.7中indexFor()作用一致
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;
}
HsahMap的不安全的原因
多线程put的时候可能会造成数据丢失
put方法的源码
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//初始化hash表
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//通过hash值计算在hash表中的位置，并将这个位置上的元素赋值给P，如果是空的则new一个新的node放在这个位置上
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//hash表的当前index已经存在元素，向这个元素后追加链表
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) {//#1
p.next = newNode(hash, key, value, null);//#2
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
假设t1和t2同事执行put，假设t1执行put(k2,v2),t2执行put(k3,v3)，并且k2与k3的hash值与图中的k1相同，那么正常情况下，put完成之后，table的状态应该是下图二者其一
或者
假设线程1，线程2现在都执行到put源码中的#1位置，且当前table状态如下
然后两个线程都执行了if((e = p.next)==null)这句代码，来到了#2这行代码
此时假设t1先执行p.next=newNode(hash,key,value,null);那么table会变成如下状态
紧接着t2执行p.next=newNode(hash,key,value,null);此时table会变成如下状态
这样一来，key2元素就丢了
多线程put和get并发的时候，可能造成get为null
线程1执行put时，因为元素隔宿超出threshold而导致rehash，线程2此时执行get，有可能导致这个问题
先看下resize方法源码
大致的意思是，先计算新的容量和threshold，在创建一个新的hash表，最后将旧hash表中元素rehash到新的hash表中
重点代码在于#1和#2两句
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;//定义oldCap参数，记录了table长度
int oldThr = threshold;
int newCap, newThr = 0;//定义了newCap参数，记录了新table长度
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 //扩容newCap时oldCap长度的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);
}
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];//#1
table = newTab;//#2
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {//循环原table，把原table中的每个链表中的每个元素放入新table
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)//指的是链表中只有一个元素，所以直接吧e放入新table，其中e.hash&(newCap-1)就是计算e在新table中的位置，和JDK1.7中indexFor()作用一致
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;
}
在代码#1位置，用新计算的容量new了一个新的hash表，#2将新创建的空的hash表赋值给实例变量table。
此时实例变量table是空的。
如果此时另一个线程执行get时，就会get出null
JDK1.7中HashMap因为头插法，导致get时出现死循环
JDK1.7多线程HashMap并发put的时候为何会发生环形链表，产生死循环？
HashMap扩容源码
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for(Entry<K,V> e : table){
//遍历同桶数组中的每一个桶
while(null != e){
//顺序遍历某个桶的外挂链表
Entry<K,V> next = e.next; //引用next
if (rehash){
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);//找到新表的桶位置 ;原桶数组中的某个桶上的同一链表中的Entry此刻可能被分散到不同的桶中去了，有效的缓解了哈希冲突
e.next = newTable[i];//头插法插入新表中
newTable[i] = e;
e = next;
}
}
}
先创建一个散列表HashMap，Map<String,String> map = new HashMap<>(2);加载因子默认是0.75，当插入第二个元素时，会发生扩容，我们现在map中放入"itqiankun","com"两个元素，假设这两个元素的都在同一个数组的位置
这时有两个线程都执行put操作，那么在此刻两个线程都对HashMap进行扩容，这时候在源码中（关键代码）Entry<K,V> next = e.next,此时发生rehash，线程A和线程B，两个线程都会新建新的数组
假如两个线程分别是A，B两个线程。A线程在执行到关键代码这一行就被挂起，那么此刻A线程中e = "itqiankun",next = "com",接着B线程开始进行扩容，假设新的散列表中，节点"itqiankun"和节点com还是会发生散列冲突，那么B线程的扩容过程为：
将节点"itqiankun"迁移至新散列表
将com迁移至新散列表中
此时B线程的扩容已经完成，即节点com和后继节点为"itqiankun"，节点"itqiankun"的后记节点为null。
此时A线程在执行到关键代码这一行处于挂起状态，那么此刻A线程中e = "itqiankun"，并将next = "com"的节点赋值给e,扩容并迁移节点itqiankun后的状态，如下图：
于是在第二次执行while循环的时候，当前待处理的节点e="com"
在执行（关键代码）这一行时，
接着开始执行第三次while循环，当执行到e.next=newTable[i]的时候，此时结果为
由于节点itqiankun的后继节点为null，所以next=null,执行完第三次循环后，循环结束，此时链表成环，get()时会导致死循环。