HashMap源码分析（JDK1.8）
2019-05-20 本文已影响0人
MrFengZH
前言
本文将对HashMap（基于JDK1.8）的源码进行具体分析，包括构造方法以及增、删、改、查等基本操作。
源码分析
需要先了解的知识
将会用到的实例常量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默认初始容量，为2^4
static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量，为2^30
static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认加载因子
static final int TREEIFY_THRESHOLD = 8; //树化阀值
将会用到的实例变量
final float loadFactor; //加载因子
int threshold; //扩容的阀值，当键值对的数量超过这个阀值就扩容
/*
* table（一般称为哈希桶）在首次使用时初始化，并根据需要调整大小。
* 分配时，长度始终是2的幂（某些情况下可以为0）。
*/
transient Node<K,V>[] table;
transient int modCount; //HashMap被结构修改的次数
transient int size; //当前的键值对数量
Node（存储键值对的节点）
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
//每个节点的hashCode是将key和value的hashCode进行异或操作后得到的
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
//设置新的value，返回旧的value
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
//只有当两节点的key和value通过equals方法比较后都返回true时，equals方法才返回true
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
构造方法
HashMap的构造方法有4种。
默认的构造方法
public HashMap() {
//加载因子设置为默认的0.75f
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
带一个Map类型参数的构造方法
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR; //加载因子设置为默认的0.75f
putMapEntries(m, false);
}
该构造方法的作用是深拷贝一个HashMap
带一个int参数的构造方法
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
该构造方法直接调用另一构造方法，其参数的作用是指定初始化容量
带两个int参数的构造方法
/*
* @param initialCapacity 指定的初始容量
* @param loadFactor 指定的加载因子
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY; //初始化容量不能大于2^30
if (loadFactor <= 0 || Float.isNaN(loadFactor)) //加载因子必须大于0
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor; //指定加载因子
this.threshold = tableSizeFor(initialCapacity); //根据指定初始容量获取扩容的阀值
}
下面来看下是如何通过初始容量来获取扩容阀值的
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;
}
最终返回的结果是一个大于或等于初始化容量的2^n，例如输入6，则返回8；输入16，则返回16。
put方法（增）
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
put方法又调用了putVal方法，先看一下hash方法
static final int hash(Object key) {
int h;
//h保存key的hashCode，最终返回的hash值是h和h无符号右移16位后的数进行异或操作
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
为什么要计算一个hash值，而不是直接用hashCode呢？
因为哈希桶容量通常是很小的，而hashCode是32位。所以在进行(n - 1) & hashCode这个运算时，通常只能用上低16位。这可能会导致键值对在哈希桶中的分布不均匀，一些桶的链表过长。所以无符号右移16位就相当于把高16位推到了低16位，再与低16位进行异或操作，并把结果作为hash值，就间接地利用了高16位，从而可以在一定程度上使得键值对分布更加均匀，降低hash冲突的概率。
putIfAbsent
put方法插入元素时，如果该元素已存在，会将旧的value替换为新的value（实现改的效果），如果不希望旧的value被替换，可以使用putIfAbsent方法。
@Override
public V putIfAbsent(K key, V value) {
return putVal(hash(key), key, value, true, true);
}
可以看出，该方法同样是调用了putVal方法。在看putVal方法之前，需要先了解resize方法。
resize方法（扩容）
该方法的作用是初始化或加倍哈希桶的容量，并返回新的哈希桶。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; //旧的哈希桶
int oldCap = (oldTab == null) ? 0 : oldTab.length; //旧桶的容量
int oldThr = threshold; //旧的扩容阀值
int newCap, newThr = 0; //新桶容量和新的扩容阀值初始化为0
if (oldCap > 0) { //如果旧桶容量大于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) {
//如果旧桶容量为0，但旧的扩容阀值大于0，那么将新桶容量设置为该扩容阀值
newCap = oldThr;
} else {
//如果旧的桶容量和扩容阀值都为0
newCap = DEFAULT_INITIAL_CAPACITY; //新桶容量设置为默认初始容量
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); //新的扩容阀值设置为：默认初始容量*默认加载因子
}
//如果此时新的扩容阀值为0，对应情况为：旧桶容量为0但旧的扩容阀值大于0
if (newThr == 0) {
float ft = (float)newCap * loadFactor; //ft为新桶容量*加载因子
//当新桶容量和ft都小于最大容量时，新的扩容阀值为ft，否则为最大值
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; //e用于保存旧的节点
if ((e = oldTab[j]) != null) {
oldTab[j] = null; //将旧节点置空
if (e.next == null) { //如果该节点后面没有节点（说明没有发生哈希冲突）
/*
* 将当前节点放到新哈希桶的相应位置
*
* 注意：由于newCap的值为2^n，所以(newCap-1)与e.hash作与运算其实是一个
* 取模运算（e.hash对newCap取模），但这样写效率更高。
*/
newTab[e.hash & (newCap - 1)] = e;
} else if (e instanceof TreeNode) { //如果当前节点是一棵红黑树
//需要先将树拆分，然后再移动到新哈希桶中
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
} else { //如果当前节点是一个节点数小于8的链表
//将原链表拆分为两个链表（low链表和high链表）
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do { //当e不为null时执行该循环
next = e.next;
//将当前节点的hash值与oldCap作与运算（有两种结果，0或oldCap，而且这两种结果出现的概率各占50%）
if ((e.hash & oldCap) == 0) { //结果为0，加入low链表
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
} else { //结果为oldCap，加入high链表
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//将low链表存在原索引上
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//将high链表存在原索引加上旧桶容量上
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
//返回新的哈希桶
return newTab;
}
总共包含以下几个步骤：
- 获取新哈希桶的容量，更新扩容阀值
- 创建新哈希桶，并更新哈希桶
- 将旧哈希桶中的所以节点移动到新哈希桶上
- 返回新的哈希桶
putVal
/**
* 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;
//当哈希桶为空或其长度为0时
if ((tab = table) == null || (n = tab.length) == 0) {
//在resize方法中初始化哈希桶，并且将其长度赋给n
n = (tab = resize()).length;
}
//i为新节点的索引，如果该索引对应的节点为空，说明没有哈希冲突，直接创建一个新节点
if ((p = tab[i = (n - 1) & hash]) == null) {
tab[i] = newNode(hash, key, value, null);
} else { //发生哈希冲突
Node<K,V> e; //e用于存储已存在的节点
K k;
//p为新节点索引对应的原节点，k为p的key
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) {
/*
* 如果p的哈希值和新节点相等，并且p的key和新节点的key通过equals方法比较后返回true，
* 说明新节点已存在。
*/
e = p;
} else if (p instanceof TreeNode) {
//如果p节点为红黑树
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
} else {
//此时p节点为链表，将新节点放到链表的末尾
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;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
//说明新节点已存在
break;
}
p = e;
}
}
//如果e不为空，说明新节点已存在
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null) {
//如果onlyIfAbsent为false或者旧的value为null，更新节点的value
e.value = value;
}
afterNodeAccess(e);
return oldValue; //返回旧值
}
}
++modCount; //结构修改次数加一
if (++size > threshold) { //当前键值对数量大于扩容阀值的时候
//进行扩容操作
resize();
}
afterNodeInsertion(evict);
return null; //新加入的节点不重复时返回null
}
putVal方法的执行步骤如下：
- 先判断哈希桶是否有初始化，没有初始化的话先初始化（所以哈希桶的初始化是发生在第一次添加元素的时候，之所以不在HashMap初始化的时候为哈希桶分配空间，是为了防止只创建集合而不添加元素时造成的空间浪费）
- 根据插入元素的hash值寻找相应的位置，判断该位置是否为空，为空则直接创建节点并插入，不为空时：
- 判断是否存在相等的key
- 判断该位置存储的是红黑树还是链表，根据不同情况有不同的插入
- 插入完成后，如果key相等，则判断是否要替换value，并返回旧的value。
- 更新修改次数、当前键值对数量。如果当前键值对数量超过了扩容阀值，则进行扩容操作。
- 能够执行到最后，说明插入的键值对是新的，没有旧value，所以返回null。
remove方法（删）
remove有两个重载方法：
删除指定key的remove方法，如果删除成功，返回删除键值对的value，否则返回null。
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
删除指定键值对的remove，如果删除成功，返回true，否则返回false。
@Override
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}
这两个方法都是调用了removeNode方法
removeNode
/**
* Implements Map.remove and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to match if matchValue, else ignored
* @param matchValue if true only remove if value is equal
* @param movable if false do not move other nodes while removing
* @return the node, or null if none
*/
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
//tab用于存储哈希桶，n存储哈希桶的容量,index存储hash值对应的哈希桶索引,p存储hash值所对应的头节点
//如果哈希桶不为空且长度大于0，并且该key存在对应的节点，才会执行删除操作，否则直接返回null
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; //node存储要删除结点
K k; V v; //k存储p节点对应的key
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) {
//如果要删除的节点的hash值和key都与p节点相等
node = p;
} else if ((e = p.next) != null) {
if (p instanceof TreeNode) //如果p节点是红黑树
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else { //p节点是单链表
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e; //p记录要删除节点的上一节点
} while ((e = e.next) != null);
}
}
//如果找到了要删除的节点（如果还指明了要删除的value的话，还要比较value是否一致）
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode) { //删除红黑树中的节点
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
} else if (node == p) { //要删除节点是链表的头结点
tab[index] = node.next;
} else { //要删除节点不是链表的头结点
p.next = node.next;
}
++modCount; //增加修改次数
--size; //减少哈希桶的容量
afterNodeRemoval(node);
return node; //返回删除节点
}
}
return null;
}
删除节点的步骤如下：
- 先要确保哈希桶不为空且长度大于0，并且要删除的key在哈希桶中有对应节点。如果不满足这些条件，直接返回null。
- 如果对应节点就是要删除的节点，那么直接记录下该节点。如果不是的话，还要判断对应节点是红黑树还是单链表，分情况找到要删除的节点。
- 如果最终没有找到要删除的节点，返回null。如果找到了要删除的节点，就把该节点从红黑树或链表中删除，并返回该节点。
replace方法（改）
replace有两个重载方法
带三个参数的重载方法传入要修改的键值对的key和value，以及要更新后的value。如果找到该键值对并修改成功，返回true，否则返回false。
@Override
public boolean replace(K key, V oldValue, V newValue) {
Node<K,V> e; V v; //e存储要修改的节点，v存储修改节点的旧value
//如果找到要修改的节点并且该节点的value和oldValue一致，执行修改操作，否则直接返回false
if ((e = getNode(hash(key), key)) != null &&
((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
e.value = newValue; //更新该节点的value
afterNodeAccess(e);
return true;
}
return false;
}
带两个参数的重载方法传入要修改的键值对的key以及更新后的value。如果修改成功，返回旧的value，否则返回null。
@Override
public V replace(K key, V value) {
Node<K,V> e;
//如果找到要修改的节点，执行修改操作，否则直接返回null
if ((e = getNode(hash(key), key)) != null) {
V oldValue = e.value;
e.value = value; //更新该节点的value
afterNodeAccess(e);
return oldValue; //返回该节点的旧value
}
return null;
}
这两个重载方法都调用了getNode方法
getNode
getNode方法的作用是根据传入的hash值和key值，找到对应的节点并返回，若没有找到则返回null。
/**
* 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; //tab存储哈希桶，first存储hash值所对应的头节点
int n; K k; //n存储哈希桶容量
/*
* 当哈希桶不为空并且其长度大于0，同时存在要查找的hash值所对应的头节点时，
* 才执行相关查找操作，否则直接返回null。
*/
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;
}
get方法（查）
public V get(Object key) {
Node<K,V> e;
//如果找到对应节点，则返回该节点的value，否则返回null。
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
可以看到，get方法也是通过getNode方法来查找节点。在分析replace方法时已经分析过该方法，这里不再多说。
小结
本文对HashMap的构造方法以及增删改查等基本操作进行了源码分析，分析过后，对于HashMap有了更深的认识，在这里小结一下：
- HashMap有4种构造方法，除了默认的方法外，我们还可以通过其他的构造方法初始化HashMap的元素，或者根据需要设置哈希桶的初始化容量和加载因子。
- 哈希桶的初始化不是发生在创建HashMap的时候，而是发生在第一次插入元素的时候，通过扩容操作初始化。
- 哈希桶在扩容时，如果旧桶容量大于0并且小于最大容量（2^30），那么新桶容量是旧桶容量的两倍。旧桶中的链表会被拆分为两个链表存到新桶中。
- 哈希桶的数据结构是数组，在处理哈希冲突时，如果发生冲突的元素小于8个的时候，是用单链表存起来的。一旦冲突的元素个数大于等于8个，那么单链表将转化为红黑树。
