HashMap扩容源码（JDK1.7）
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
//当size超过临界阈值threshold，并且即将发生哈希冲突时进行扩容
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
//扩容后重新计算插入的位置下标
bucketIndex = indexFor(hash, table.length);
}
//把元素放入HashMap的桶的对应位置
createEntry(hash, key, value, bucketIndex);
}
//创建元素
void createEntry(int hash, K key, V value, int bucketIndex) {
//获取待插入位置元素
Entry<K,V> e = table[bucketIndex];
//这里执行链接操作，使得新插入的元素指向原有元素，头插法
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
//将老的表中的数据转移到新的结构中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
//转移完后旧表指向新表
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;
if (rehash) {
//重新hash
e.hash = null == e.key ? 0 : hash(e.key);
}
//定位放入新数组的位置
int i = indexFor(e.hash, newCapacity);
//元素指向新数组第i位
e.next = newTable[i];
//新数组第i位指向新插入元素，完成头插法
newTable[i] = e;
//拿到下一个要转移的元素
e = next;
}
}
} jdk1.7多线程出现循环链表的栗子
要扩容的旧的hashmap：
根据resize方法中的Entry[] newTable = new Entry[newCapacity];，多线程的情况下有多少线程就生成多少个新表，假设有线程A和线程B分别生成了newTableA和newTableB。
又假设两个线程同时走到了transfer方法，线程A的参数为e1、next1，线程B的参数为e2、next2。
然后线程B在if（rehash）判断上阻塞了，线程A用头插法走完了三个元素的转移，就变成了这样：
这时候就发现问题了，因为插入用的是头插法，元素的顺序颠倒了，之前e2.next=next2的，现在变成了next2.next = e2了。
然后线程B不阻塞了，开始执行：
e.next = newTable[i];
newTable[i] = e;//头插法
然后执行e = next;，就是说e2指向2，和next2指向一个元素。然后开始第二次循环：
Entry<K,V> next = e.next;//next2指向3
e.next = newTable[i];//本来就指向3，不变
newTable[i] = e;//头插法
e = next;//e2和next2都指向3
然后开始第三次循环：
Entry<K,V> next = e.next;//next2指向null
e.next = newTable[i];//3的next指向2，形成循环链表
jdk8扩容源码（尾插法）
jdk1.6中，HashMap中有个内置Entry类，它实现了Map.Entry接口；
jdk1.8中，这个Entry类不见了，变成了Node类，也实现了Map.Entry接口，与jdk1.6中的Entry是等价的。
结构：Node数组+链表+红黑树
- oldTab：为数组类型，代表扩容之前HashMap中的数组，也就是所有的桶；
- oldCap：为int类型代表扩容之前总桶数量；
- oldThr：为int类型代表扩容之前下次扩容的阈值；
- newCap：为int类型代表这次扩容之后总桶数量；
- newThr：为int类型代表这次扩容之后下次扩容的阈值；
- newTab：为数组类型，代表扩容之后HashMap中的数组。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;//首次初始化后table为Null
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;//默认构造器的情况下为0
int newCap, newThr = 0;
if (oldCap > 0) {//table扩容过
//当前table容量大于最大值得时候返回当前table
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//table的容量乘以2，threshold的值也乘以2
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
//使用带有初始容量的构造器时，table容量为初始化得到的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) {
HashMap.Node<K,V> e;
if ((e = oldTab[j]) != null) {
// help gc
oldTab[j] = null;
if (e.next == null)
// 当前index没有发生hash冲突，直接对2取模，即移位运算hash &（2^n -1）
// 扩容都是按照2的幂次方扩容，因此newCap = 2^n
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof HashMap.TreeNode)
// 当前index对应的节点为红黑树，这里篇幅比较长且需要了解其数据结构跟算法，因此不进行详解，当树的个数小于等于UNTREEIFY_THRESHOLD则转成链表
((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 把当前index对应的链表分成两个链表，减少扩容的迁移量
HashMap.Node<K,V> loHead = null, loTail = null;
HashMap.Node<K,V> hiHead = null, hiTail = null;
HashMap.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) {
// help gc
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
// help gc
hiTail.next = null;
// 扩容长度为当前index位置+旧的容量
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}注意扩容前桶中的结点分为两种，一种是依旧在之前那个桶对应的下标的桶中，另一种是之前所在的桶的下标+oldCap，因为<<1表示容量翻倍，其实就是前面多了一位二进制，要么是0要么是1，是0的话就不变，是1的话就＋oldCap。
