Java 集合源码分析（一）HashMap
2019-08-27 本文已影响0人
希希里之海
附：更这个系列感觉自己像是又挖了一个坑🌚，不过趁自己刚好工作不太忙，有空闲期，静下心来研究学习源码也是一件很值得做的事，自己尽量会把这个坑填完😂。
[TOC]
Java 集合源码分析（一）HashMap
1. 概要
HashMap 作为我们经常使用的 Java 集合工具类，无论是学习研究，帮助自己更上一层楼，还是职场面试等方面，都有理由去深入研究。
其中 JDK 7 和 JDK 8 HashMap 变化较大。所以这里会分为几部分来讲：
- JDK 7 的 HashMap （数组 + 链表）
- JDK 8 的 HashMap （数组 + 链表 + 红黑树）
- JDK 7 的 ConcurrentMap （数组分块 segment）
- JDK 8 的 ConcurrentMap （数组下标的链表头节点加锁）
2. JDK 7 的 HashMap
2.1 原理
简单来说就是：数组 + 链表 结构。
HashMap 会将我们传入的 key 和 value 封装成一个节点对象 Entry(key, value)。
2.2 put 操作
简单实现过程伪代码：
// 计算数组下标
int hashcode = hash(key);
int index = hashcode % table.length;
// 将新的节点赋值到原来的头节点并移动新的头节点（因为是链表结构，所以只需要移动头节点便能移动整个链表）
// 做了两件事：1. 插入头部，2. 移动头节点
table[index] = new Entry(key, value, table[index]);
- 使用 hash 算法，得到 key 的哈希码 hashcode，然后通过取余操作得到数组下标。（取余得到的数组下标肯定是小于数组长度的）
- 如果算出的数组下标已经存在元素，那我们就使用链表结构，放到数组下，每当有一个相同下标的元素，我们便在链表的头节点插入（头节点查询效率高），然后该数组下的链表往下移，让新插入的链表节点成为数组的下标。（这便是解决 hash 碰撞的方法，hash 值相同采用链表方，将 hash 值相同的元素放在一个链表下）
所以一个完整的 HashMap 的结构如下所示：
源代码：
/**
* put 方法，添加元素
*/
public V put(K key, V value) {
// 判断是否为空
if (table == EMPTY_TABLE) {
// 为空进行初始化
inflateTable(threshold);
}
// 可以看到 key 可以为空
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;
// 即 put 的 key 已经存在的话，那么将会覆盖旧值，，并返回旧的 value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// 添加新的 entry 方法
addEntry(hash, key, value, i);
return null;
}
2.4 get 方法
以伪代码简单说明：
int hashcode = hash(key);
int index = hashcode % table.length;
通过计算 key 的 hashcode 值，然后通过取余操作，得到数组下标，再遍历数组下标下的链表，如果 key 相同，便返回 key 的 value。
源代码：
/**
* 查询 key 的方法
*/
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
2.5 两个问题
在讲解这两个问题前，补充一个知识点：
java中有三种移位运算符
<< : 左移运算符，num << 1,相当于 num 乘以 2
>> : 右移运算符，num >> 1,相当于 num 除以 2
>>> : 无符号右移，忽略符号位，空位都以 0 补齐
question 1：
在初始化 HashMap 时，我们可以看到初始化容量大小都为 2 的次方数，所以为什么要 2的次方数？
如下面这段代码通过减一和左移一位（(number - 1) << 1) 的操作，查找比 number 大且相近的 2 的次方数
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;
}
这个就跟我们获取元素数组下标有关了：
/**
* 返回数组下标
*/
static int indexFor(int h, int length) {
// 与操作，之所以要减 1，是为了保证与操作 （length -1） 的低位都是1，这样与 hashcode 相与后取值范围才是符合要求的。
// 奇数的话满足高位为 0，低位为 1，保证最大范围。如 15 ： 0000 1111。相与操作的时候后四位都将是hashcode的值。
return h & (length-1);
}
当容量一定是 2^n 时，h & (length - 1) == h % length，它俩是等价不等效的，位运算效率非常高。
question 2 ：
在进行 hash 运算时时，可以看到 hash 方法中有右移和异或操作，那么为什么要右移以及异或？
/**
* 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();
// 右移和异或操作
// 这是是为了增加散列性（让高位参与运算）
// 比如 hashcode 算出来的为 0110 0111，向右移4位后变成 0000 0110，两两异或后再与原来的 hashcode 参与运算，算出的值即为最终的 hashcode，
// 这样原来的 hashcode 高四位和第四位都参与运算了，增强了散列性。
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
^ 为异或符号其计算机符号为 xor，相同为 0，相异为 1，>>> 为右移动符号，左侧补零。进行右移和异或操作是为了增加散列性。
2.6 JDK1.7 HashMap多线程环境下会出现死锁问题。
原因：
HashMap 使用 transfer 扩容方法进行扩容时链表中的元素节点顺序被相互调换，原来数组和扩容后的数组链表中的元素位置刚好是反过来的，这也是导致出现死锁的根本原因（将原来链表的元素通过指针移动到新的 table 中时会出现死循环 -- 循环链表）
解决方法：
- 使用
ConcurrentHashMap - 防止进行扩容操作：创建 HashMap 时直接指定初始化的容量
- 加锁
3. JDK 1.8 的 HashMap
HashMap 在 JDK 1.8 中增加了红黑树，不再只是以链表的形式存储，当链表长度大于或等于8时，就将链表改为红黑树，增加了查询效率。
3.1 put 方法
/**
* put 方法
*/
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 是否为空，胃为空创建新 table
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);
else {
Node<K,V> e; K k;
// 判断新插入的节点key 和原有节点 key 是否是相等的，相等直接替换后，return 旧 value
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 {
// 如果不是树结构，那么就是链表结构，跟 JDK 1.7 一样的操作
// ++binCount 为遍历链表操作
for (int binCount = 0; ; ++binCount) {
// 当为 null 时，即遍历到了尾节点
if ((e = p.next) == null) {
// 将节点插入尾部（跟1.7 不一样，1.7 是插入到头部），避免扩容时发生死锁（即死循环）
p.next = newNode(hash, key, value, null);
// TREEIFY_THRESHOLD 是树化的阈值且其值为8
// 这里要注意：我们要插入的节点 p 是还没有加到 binCount 中的
// 也就是说这里虽然 binCount>=7 就可以树化，其实真正的树化
// 条件是链表中元素个数大于等于 8
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
// 在遍历链表的过程中也会查找有没有相同的 key，有的话 break，执行存在 key 的操作。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 已经存在 key
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 判断是否需要扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
3.2 get 方法
get 方法和 JDK 1.7 中的基本一致：
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 数组不为空，并且数组的元素大于 0，同时定位的位置元素还不为空
if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {
// 检查第一个元素是否是要找的元素，是的话返回
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// 第一个元素不是要找的元素，而且后面还存在元素，那么判断是否为树结构
if (first instanceof TreeNode)
// 是树，按照树获取节点方法获取
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 是链表结构，循环链表拿到元素
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
3.3 扩容规律
原来数组元素移动到扩容后新数组的元素位置：
JDK 1.8 中，当 hashcode 16 进制的高末位是 0 的话，扩容后的值还是原来相与操作的值，如果高末位为 1：
扩容后的 index = index + oldTable.length;
resize() 方法中这样说明：
newTab[j + oldCap] = hiHead;
这也是与 JDK 7 中的不同。（JDK 1.7 中是循环数组然后通过改变当前数组下的链表指针移动到新扩容的数组中去的）
4. Hashtable
特点
HashTable 跟 HashMap 的不同之处是：
HashTable 的每个方法都进行了加锁：synchronized
缺点
锁太大了，性能不高。
5. JDK 1.7 的 ConcurrentHashMap
5.1 特点
JDK 1.7 的 ConcurrentHashMap 中使用了分段锁：对 table 进行分组，以组为单位进行加锁。
所以有两个数组：
- segment[]（每一个 segment 都是一个 hashmap）
- 在每个 segment 对象中有另外一个数组：真正存元素的数组 HashEntry[]
5.2 初始化 ConcurrentHashMap
- 初始化 segment 数组： segment[]
- 初始化 segment对象的 HashEntry 数组： segment.HashEntry[]
5.3 segment[] 大小
根据并发等级初始化 segment 大小，这里的 segment[] 和 segment.HashEntry[] 容量大小同样都是 2 的次方数
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
if (concurrencyLevel > MAX_SEGMENTS)
concurrencyLevel = MAX_SEGMENTS;
int sshift = 0;
// 根据 concurrencyLevel 并发等级算 ssize，默认并发等级是 16
int ssize = 1;
while (ssize < concurrencyLevel) {
++sshift;
// 左移一位，即 2 的次方数操作（1 -> 2, 2 -> 4, 4 -> 8, 8 -> 16)
ssize <<= 1;
}
this.segmentShift = 32 - sshift;
this.segmentMask = ssize - 1;
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 算出每个 Segment 下的 table
int c = initialCapacity / ssize;
if (c * ssize < initialCapacity)
++c;
int cap = MIN_SEGMENT_TABLE_CAPACITY;
// 如果不是 2 的次方数，那么就又会进行左移操作
while (cap < c)
cap <<= 1;
// 初始化第一个 Segment
Segment<K,V> s0 =
new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
(HashEntry<K,V>[])new HashEntry[cap]);
Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
UNSAFE.putOrderedObject(ss, SBASE, s0);
this.segments = ss;
}
5.4 put 方法
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
int hash = hash(key);
// Segments 的下标，将 Segment 取出来
int j = (hash >>> segmentShift) & segmentMask;
// 如果 Segment 为空，则执行 ensureSegment(j) 方法
if ((s = (Segment<K,V>)UNSAFE.getObject
(segments, (j << SSHIFT) + SBASE)) == null)
s = ensureSegment(j);
return s.put(key, hash, value, false);
}
5.5 ensureSegment() 方法
private Segment<K,V> ensureSegment(int k) {
final Segment<K,V>[] ss = this.segments;
long u = (k << SSHIFT) + SBASE; // raw offset
Segment<K,V> seg;
if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
Segment<K,V> proto = ss[0]; // use segment 0 as prototype
int cap = proto.table.length;
float lf = proto.loadFactor;
int threshold = (int)(cap * lf);
HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
== null) { // recheck
Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
== null) {
if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
break;
}
}
}
return seg;
}
该方法判断 k 位置 的 Segment 是否为空，为空创建一个 新的 Segment，不为空返回存在的 Segment 。
5.6 Segment 对象
我们可以点进去看 Segment 对象，发现和 HashMap 高度相似，只是 Segments 每一个方法上都加了一把锁。
所以也就是在 Segment 对象的 put 方法中，将元素放到 Segment 下的 table 中。
所以 Segment 对象可以理解为一个小的 HashMap，只是在使用前加了一把锁，使用后再进行解锁。
6. JDK 1.8 的 ConcurrentHashMap
JDK 1.8 中的 ConcurrentHashMap 很多操作和 JDK 1.7 中差不多，这里只是讲一下不同的地方。
6.1 特点
JDK 1.8 中是对 table 的每一个下标的头节点加锁，不再使用 segment
put 方法
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
// hash 运算
int hash = spread(key.hashCode());
int binCount = 0;
// 循环 table
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// table 为空，初始化 table
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// table不为空，下标位置元素为空，new Node 创建新节点操作
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break;
}
// 并发扩容，如果发现当前 ConcurrentHashMap 正在扩容，那么该线程将停止 put 操作，帮助 ConcurrentHashMap 转移元素
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
// 下标位置元素不为空
V oldVal = null;
// 对当前数组下标链表头节点的元素加锁
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
然后还是 HashMap 的那套逻辑：
- 判断是否为链表
- 树化
- 循环链表
- 判断key是否相当，相等替换旧址，结果返回旧值；不相等添加 key
7. 最后补充一下 HashMap 中的一些属性和方法
由于属性和方法太多，我将一些属性和方法的注释上传到 GitHub 了，欢迎查看：
