文章目录
0.序言
? HashMap 在JDK1.7版本时底层数据结构是数组+链表，但是1.7时HashMap的并发扩容会导致死循环；JDK1.8时底层的数据结构变成数组+链表+红黑树，修改了并发扩容逻辑，并且提升了HashMap的性能。
0.1HashMap 重要属性
DEFAULT_INITIAL_CAPACITY = 1 << 4; Hash 表默认初始容量 8
MAXIMUM_CAPACITY = 1 << 30; 最大 Hash 表容量
DEFAULT_LOAD_FACTOR = 0.75f；默认扩容阈值比率(计算扩容阈值=阈值比率*HashMap容量)
TREEIFY_THRESHOLD = 8；链表转红黑树阈值
UNTREEIFY_THRESHOLD = 6；红黑树转链表阈值
MIN_TREEIFY_CAPACITY = 64；链表转红黑树时 hash 表最小容量阈值，达不到优先扩容
1.0 JKD1.7HashMap组成结构及源码分析
HashMap 底层数据结构是数组+链表：数组就是存放Map 键值对的位置，当Map 中出现相同的Hashcode值时，称作hash碰撞，这时相同位置的值会形成一个链表放在数组的特定位置。如下图
1.1如何确定key在数组的位置
源码如下：
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
// 获取 key 对应的整型 hash值
int hash = hash(key);
// 再将这个hash值转换为小于这个数组的整型值 i，然后将节点插入数组i位置
int i = indexFor(hash, table.length);
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))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
中的 hash 方法源码如下：
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
? 不需要看懂，知道返回一个int 类型的hash值就可以了；怎么一个数值 中获取一个小于数组长度的int值呢？我们可能会想到直接对那个数值求余% (hash值%数组长度)，有实验可知求余运算效率低，HashMap是不会用的，我看下它到底是怎么计算的呢？源码如下用了&运算。
/**
* Returns index for hash code h.
* */
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
1.2 HashMap的容量
为了保HashMap的数组长度必须是2的N次方，HashMap在初始化时的长度为11，数组的长度就是11吗？不是11是16，为什么呢？看以下源码
public V put(K key, V value) {
// 如果数组为空，初始化数组，而不是在HashMap的构造方法中进行的的
if (table == EMPTY_TABLE) {
//初始化数组方法
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
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))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
初始化方法源码：
private void inflateTable(int toSize) {
// 找到第一个大于等于初始化传入的HashMap长度 toSize 的 2的 N次方的值
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
// 巧妙的通过或运算和位移运算得出第一个大于i的 2 的 N 的数值
public static int highestOneBit(int i) {
// HD, Figure 3-1
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
return i - (i >>> 1);
}
1.3 HashMap 扩容
当存入的数据长度 大于 数组长度*阈值率，HashMap自动扩容，扩容后数据的迁移逻辑如下：
/**
* Transfers all entries from current table to newTable.
*/
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) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 重新计算当前节点在新数组中的位置
int i = indexFor(e.hash, newCapacity);//第二行
// 修改节点的指向
e.next = newTable[i];//第三行
newTable[i] = e;// 第四行
// 下一次循环
e = next; //第五行
}
}
}
重点看注释写第N行的代码，这样逻辑更加清晰了。
第一行:记录oldhash表中e.next；
第二行:rehash计算出数组的位置(hash表中链表的位置)
第三行:e要插入链表的头部，所以要先将e.next指向newhash表中的第一个元素；
第四行:将e放入到newhash表的头部
第五行:转移e到下一个节点，继续循环下去；
1.3.1 单线程扩容
假设:hash算法就是简单的key与lenath(数组长度)求余。hash表长度为2，如果不扩容，那么元素kev为3.5.7按照计算(key%table.length)的话都应该碰撞到table[1]上。
扩容:hash表长度会扩容为4重新hash，key=3会落到table[3]上(3%4=3)，当前e.next为key(7)，继续while循环重新hash，key=7会落到table[3上(7%4=3)，产生碰撞，这里采用的是头插入法，所以key=7的Entry会排在key=3前面(这里可以具体看while语句中代码)当前e.next为key(5),继续 while循环重新hash，kev=5会落到table[1]上(5%4=3)，当前e.next为null，跳出while循环，resize结束。途中竖着是数组，横着的是链表
1.3.2多线程扩容
多线程同时put的情况，然后同时进入transfer方法中：假设这里的两个线程同时执行了put操作，并进入了transfer如下环节。
while(null != e) {
Entry<K,V> next = e.next; //第一行，线程1执行到此被任务调度挂起
// 重新计算当前节点在新数组中的位置
int i = indexFor(e.hash, newCapacity);//第二行
// 修改节点的指向
e.next = newTable[i];//第三行
newTable[i] = e;// 第四行
e = next; //第五行
}
从上面的图我们可以看到，因为线程1的e指向了key(3)，而next指向了key(7)，在线程2rehash后，就指向了线程2 rehash后的链表。然后线程1被唤醒了:
1.执行e.next=newTablelil，干是kev(3)的next指向了线程1的新Hash表，因为新Hash表为空，所以e.next=null
2.执行newTable[i]=e，所以线程1的新Hash表第一个元素指向了线程2新Hash表的key(3)。好了，e处理完毕。
3.执行e=next，将e指向next，所以新的e是key(7)
然后该执行key(3)的next节点key(7)了:
1.现在的e节点是key(7)，首先执行Entry<K，V>next=enext，那么next就是key(3)了
2.执行enext=newTable]，于是key(7)的next就成了key(3)
3.执行newTable[]=e，那么线程1的新Hash表第一个元素变成了key(7)
4.执行e=next，将e指向next，所以新的e是key(3)
此时状态为:
然后又该执行key(7)的next节点key(3)了:
1.现在的e节点是kev(3)，首先执行Entrynext=enext那么next就是null
2.执行enext=newTable[i]，于是key(3)的next就成了key(7)
3.执行newTable[i]=e，那么线程1的新Hash表第一个元素变成了kev(3)
4.执行e=next，将e指向next，所以新的e是key(7)
很明显，出现了环形的死循环。
1.4 Jdk1.8 HashMap的优化
? 优化了扩容逻辑，避免了死循环；添加红黑树，在链表数据量大时查询速度提升。
1.4.1 扩容优化
扩容的关键代码：
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;
// 节点的hash值与 旧数组的容量相与，oldCap 是2的N次方
// 一个数和 2的N次方相与时，结果只能是0或 oldCap
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;
}
// 高位节点下标增加 oldCap
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
这里定义了四个指针，将某个链表分为两部分，链表节点和数组长度相与的结果作为分隔，等于0的放在以loHead为头节点的链表中，等1的放在以hiHead为头节点的链表中。如下图:
? 这种移动方式没有改变节点关系的方向，所以并发之下也没有问题 。