HashMap源码分析
2020-05-12 本文已影响0人
浪够_
本文主要针对HashMap的以下几个问题展开分析，由浅入深，由使用到原理，上下关联，尽量把HashMap的实现原理阐述明白。
- 什么是HashMap？
- HashMap使用方式？
- HashMap的几个重要方法的源码是怎么实现的？
- HashMap 1.7 ~ 1.8 有什么不同？
一. 构造方法
接触一个类，先从它的构造方法看起：
看过源码的会知道HashMap重载了四个构造方法
/**
* 创建一个默认的初始容量，负载因子为0.75的HashMap对象
*/
public HashMap() {
//默认为0.75，该变量主要用于扩容触发，当HashMap存储超过设定容容量75%时触发扩容。
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
*创建一个初始容量为initialCapacity，负载因子为默认0.75的HashMap对象
* @param initialCapacity 初始化容量，
* @throws IllegalArgumentException 如果传入的初始化容量是负数则报这个异常
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 创建一个初始容量为initialCapacity，负载因子为loadFactor 的HashMap对象。
*
* @param initialCapacity 初始容量
* @param loadFactor 负载因子
* @throws IllegalArgumentException 如果初始容量或loadFactor有一个为负数则抛该异常。
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
//如果初始容量 > 2^30则设定initialCapacity = 2^30
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//如果loadFactor是负数或者非数字值则抛异常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
//这个逻辑是一个将initialCapacity转换为2的n次方的一个过程，具体细节我们后续详细分析
this.threshold = tableSizeFor(initialCapacity);
}
/**
* 构造一个和指定Map有相同mappings的HashMap，初始容量能充足的容下指定的Map,负载因子为0.75
*
* @param m the map whose mappings are to be placed in this map
* @throws NullPointerException if the specified map is null
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
以上构造方法已经逐行写了注释，针对 tableSizeFor(int cap) 我们展开分析下。
/**
* 直接翻译英文注释的意是
* 返回给定目标容量的两个大小的幂
*/
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;
}
非常简单首先进行了cap-1，该操作是为了防止当前入参已是2的幂了，结果最后返回的却是入参的2倍。
后续都是或运算和移位预算。
比如入参是25，25-1 =24， 二进制为11000，经过一系列位或和移位运算最后会变成11111，最后return 在将11111+1，最后返回32。
其实上述方法只是返回了离入参的最近的2的n次幂，比如入参是3则返回4，入参是5则返回8。
我们写个demo验证下
public class StringTest {
static 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 >= 1 << 30) ? 1 << 30 : n + 1;
}
public static void main(String[] args) {
System.out.println("tableSizeFor(0)->:" + tableSizeFor(0));
System.out.println("tableSizeFor(1)->:" + tableSizeFor(1));
System.out.println("tableSizeFor(2)->:" + tableSizeFor(2));
System.out.println("tableSizeFor(3)->:" + tableSizeFor(3));
System.out.println("tableSizeFor(4)->:" + tableSizeFor(4));
System.out.println("tableSizeFor(5)->:" + tableSizeFor(5));
}
}
输出结果
tableSizeFor(0)->:1
tableSizeFor(1)->:1
tableSizeFor(2)->:2
tableSizeFor(3)->:4
tableSizeFor(4)->:4
tableSizeFor(5)->:8
HashMap构造方法小结，我们梳理下new HashMap()后都做了什么操作：
- new HashMap()进行了局部变量赋默认值 this.loadFactor = DEFAULT_LOAD_FACTOR;
- new HashMap(1)调用了this.HashMap(1, DEFAULT_LOAD_FACTOR)
- new HashMap(1, 0.8)进行了初始容量大小判断，负载因子合规判断，以及调用了tableSizeFor(initialCapacity)进行了初始容量转2^n转化。
二. 几个重要的方法
HashMap添加数据通过put方法，我们看下put方法：
/**
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return 如果当前key下之前没有数据则返回null，否则返回之前的老数据。
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
下面这段代码叫“扰动函数”，key.hashCode()函数调用的是key键值类型自带的哈希函数，返回int型散列值。然后把hashCode进行右位移16位，正好是32bit的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* 存放数据
* @param hash 通过key计算的hashCode
* @param key 键
* @param value 值
* @param onlyIfAbsent 如果是true并且该key下原来有值，则不替换原来的值
* @param evict 如果是false则代表table处于创建模式。
* @return 如果之前有值则返回，如果之前没值则返回null
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//初始化数组，如果tab为null或者长度为0则通过resize()方法创建一个 Node<K,V>[]赋值给tab。
//resize()方法后续单独分析
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果当前key的位置没有数据，则直接存入当前数据。
if ((p = tab[i = (n - 1) & hash]) == null)
//通过newNode()方法创建并存入数据。
tab[i] = newNode(hash, key, value, null);
else {
//如果当前key位置有数据，说明发生的hash冲突。
Node<K,V> e; K k;
//判断当前的key和之前老数据的key是否相同，如果相同则把老数据赋值给局部变量e。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//判断该位置的结构是否为红黑树，如果是红黑树则启用putTreeVal()方法处理数据，如果有key相同的则将老数据赋值给局部变量e
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//当前位置的结构是链表，则在循环在链表后添加当前数据。
for (int binCount = 0; ; ++binCount) {
//循环到最后一个元素，没有key重复则在链表尾添加Node<K,V>对象，此时e为null
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;
}
//如果本次循环的key和当前key相同则退出循环，并在下边逻辑中进行替换操作。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//如果本次循环的key不相同的，且当前不是链表尾，则继续下次循环
p = e;
}
}
//替换值操作
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//LinkedHashMap预留的方法。
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//判断扩容
if (++size > threshold)
resize();
//LinkedHashMap预留的方法。
afterNodeInsertion(evict);
return null;
}
/**
* 向红黑树插入/更新数据
* 遍历红黑树判断该节点的key是否与需插入的key相同，相同则返回老数据，不同则插入并返回null
*/
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
HashMap put()方法小结，我们梳理下调用put()后干了啥事？主要分为以下7步
-
首先将全局变量table赋值给局部tab，并判断tab是否为null，如果为null则调用resize()方法初始化，创建table。
-
通过 tab[i = (n - 1) & hash]获取当前key的hashCode值位置的数据，如果为null，则说明该位置之前未存放数据，直接通过newNode()创建 Node<K,V>对象存储。
-
如果key hashCode对应的位置不为null则发生了hash碰撞，判断带插入key和碰撞的key是否相同，相同则直接替换对象。
-
如果碰撞位置的数据结构是否为红黑树，如果是则通过putTreeVal()方法处理数据，如果发现有key相同则返回老数据并赋值给局部变量e。
-
如果碰撞位置的数据结果为链表，则循环判断是否有和当前key相同的，如果有则返回老的数据，并赋值给e，如果没有则循环到链表尾，插入新数据。然后判断链表长度，如果>=8则通过treeifyBin()转换为红黑树。
6.判断局部变量e，如果!=null,则通过入参onlyIfAbsent 判断是否替换旧的值，然后调用afterNodeAccess()，该方法默认实现为空，LinkedHashMap有用到。
- 判断数据个数是否大于扩容阀值，如果大于则调用resize()扩容。并调用afterNodeInsertion()，该方法默认实现为空，LinkedHashMap有用到。
HashMap.put()中用到resize()方法，这个方法主要是干啥的？
/**
* 该函数有两个功能
* 1. 初始化hash表
* 2. 扩容
*
* @return the table
*/
final Node<K,V>[] resize() {
// 保存之前的table；
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;// 保存之前的table的容量。
int oldThr = threshold;// 保存之前的阀值（threshold值为oldTab.length*load_factor）
int newCap, newThr = 0;
//如果oldCap > 0说明之前的table不为空
if (oldCap > 0) {
//如果老table的长度已经>=最大整型值则将阀值设置为Integer.MAX_VALUE，后续也不在进行扩容。
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果容量翻倍后<最大整型值，且老容量>=16,则将新阀值也翻倍。（<<1可代表翻倍）
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//此时说明oldTab 为 null，oldCap 为0,如果oldThr > 0说明，HashMap被调用以下三构造方法之一。
//HashMap(int initialCapacity, float loadFactor)
//HashMap(int initialCapacity)
//HashMap(Map<? extends K, ? extends V> m)
//oldThr 为用户指定的 HashMap的初始容量（initialCapacity）。
else if (oldThr > 0) // initial capacity was placed in threshold
//table未初始化时oldThr为初始容量initialCapacity
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// oldCap <= 0 且 oldThr =0，说明通过HashMap()创建的HashMap，所有值均采用默认值，oldTab（Table）表为空，oldCap为0，oldThr等于0，直接设置新容量为16，新阀值为16*0.75
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 新阈值为0
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"})
//初始化table
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//如果老table!=null则将旧数据移值到新table中
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//如果是单个节点则直接放到newTab的指定位置
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
//如果是红黑树则进行红黑树的rehash操作
((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;
// 将同一桶中的元素根据(e.hash & oldCap)是否为0分成2个不同的链表，完成rehash
//索引不变得链表
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);
//索引不变的链表尾指针!=null则将尾指针.next制空
if (loTail != null) {
loTail.next = null;
//将头指针放在桶的第一个位置
newTab[j] = loHead;
}
//索引改变的链表尾指针!=null,则将尾指针.next制空
if (hiTail != null) {
hiTail.next = null;
//新的位置为原位置+oldCap
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
HashMap.resize()方法小结，我们梳理下调用resize()后干了啥事？主要分为以下7步
-
首先resize()有两个功能，一个是初始化table，一个是扩容。
-
如果之前table!=null 则判断 if( table.lenth>=整型最大值 ) { 则将扩容阀值设置为整型最大值，并停止扩容。} else if ( table.lenth*2<整型最大值 ) {则扩容为原来2倍，且阀值扩大为原来2倍}
-
如果通过构造函数创建了HashMap则赋值容量变量和阀值变量，如果没有设置容量和负载因子则用默认的赋值。
-
如果table未初始化则通过new Node[newCap]初始化，如果进行了扩容则通过new Node[newCap]创建新的容器。
-
如果老table!=null则将老数据移值到新容器中，存储位置为原位置/原位置+原容量，移值过程采用尾插法，转移数据时统一计算存储位置。
DK1.7 ~ JDK1.8在resize()的区别有哪些？
-
扩容时机：1.7是先判断>阀值扩容后再插入数据，1.8是先插入数据然后判断>阀值扩容。
-
存储位置计算：1.7 重新hashCode，扰动处理然后取模运算，并且每一个数据单独计算，1.8 原位置/原位置+旧容量，在转移数据时统一计算。
-
扩容后转移数据：1.7使用头插法，原位置数据往后移动，会出现逆序/环形链表死循环问题，1.8使用尾插法，防止出现死循环，逆序，环形链表等问题。
HashMap.get()方法主要做了什么？这个方法主要是干啥的？
//返回key对应的值，如果返回为null，可能是值为空也可能是key不存在，如需判断是哪种情况可用containsKey()判断
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//如果第一个值就是则返回链表头
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
//如果是红黑树则通过getTreeNode获取
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;
}
至此HashMap1.8的核心方法已经分析结束了。
补充：
- 为什么是桶的位置是通过(n - 1) & hash 来计算(为什么不是hash % n),为什么是初始容量是16以及每次增加都是2的幂次方？
首先可能会想到采用%取余的操作来实现。但是，重点来了：“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。” 并且 采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是2的幂次方。
那么 a % b 操作为什么等于 a & ( b - 1 )呢? (前提是b等于2的n次幂)
举例说明:
若 a = 10 , b = 8 , 10与8取余应得2.
8的二进制为: 1000 ; 7的二进制为: 0111.
也就是说-----2的n次幂减一这样的数的二进制都是如0000111111这样前半部分是0后半部分是1的形式.
所以, 用2的n次幂减一这样的数 & 另一个数就相当于 这个数取余 (%) 2的n次幂
