本文对JDK11下HashMap的源码进行分析，HashMap的实现在JDK8之后做了比较大的改动，之后就大同小异，对于JDK8也是可以适用的。
存储结构
再JDK1.7以前，HashMap采用位桶+链表来实现，使用链表拉链法来处理Hash冲突，当相同hash值的元素较多时，需要遍历链表查找的效率就比较低。
因此JDK1.8以后采用位桶+链表+红黑树来实现，当冲突链表长度超过阈值（默认为8）并且位桶table元素个数大于64时，将链表转为红黑树，这样能大幅减少hash冲突的key的查找时间，代价是需要更多存储空间以及更大复杂性。
]
不过当map中存储的节点数 > 加载因子 × 数组长度时，位桶会进行扩容，扩容倍数为2，而加载因子取0.75，所以出现Hash冲突并导致Hash链表长度超过阈值（8）的概率低于百万分之一。
其核心存储结构如下，位桶为table，节点为Node类型：
// 序列号
private static final long serialVersionUID = 362498820763181265L;
// 默认的初始容量是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当桶(bucket)上的结点数大于这个值时会转成红黑树
static final int TREEIFY_THRESHOLD = 8;
// 当桶(bucket)上的结点数小于这个值时树转链表
static final int UNTREEIFY_THRESHOLD = 6;
// 桶中结构转化为红黑树对应的table的最小容量
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储元素的数组，总是2的幂次倍
transient Node<k,v>[] table;
// 存放具体元素的集
transient Set<map.entry<k,v>> entrySet;
// 存放元素的个数，注意这个不等于数组的长度。
transient int size;
// 每次扩容和更改map结构的计数器
transient int modCount;
// 临界值(容量*加载因子) 当实际大小超过临界值时，会进行扩容
int threshold;
// 扩容时的加载因子，当 size > loadFactor * table.length 时对table进行扩容
final float loadFactor;
// hash桶列表
transient Node<K,V>[] table;
// hash节点结构
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
// 树节点类结构
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // 父
TreeNode<K,V> left; // 左
TreeNode<K,V> right; // 右
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red; // 判断颜色
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
// 返回根节点
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
}
初始化
HashMap的构造函数可以指定初始容量以及扩容加载因子两个参数，如果没有指定这两个参数则取默认值。
另外注意tableSizeFor函数实现，指定容量cap时，实际取值为大于cap-1的最小2的n次方，比如给定cap=10，则取值为16，给定cap=32则取值32。并且最大取值为 2^{30} ，int类型的最大值为 2^{31} – 1，是没法取到 2^{31} 的。
// 默认构造函数。
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// 包含另一个“Map”的构造函数
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);//下面会分析到这个方法
}
// 指定“容量大小”的构造函数
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 指定“容量大小”和“加载因子”的构造函数
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
hash定位
HashMap使用位桶来进行存储，将key进行hash计算得到桶的下标，然后存入相应的桶中。hash计算函数如下：
static final int hash(Object key) {
int h;
// key.hashCode()：返回散列值也就是hashcode
// ^ ：按位异或
// >>>:无符号右移，忽略符号位，空位都以0补齐
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 通过hash查找元素
Node<K, V> first = table[(table.length - 1) & hash])
如果key为null，直接取0，否则令h等于key的哈希值，将h与h右移16位后的数进行异或运算。这步操作是为了减少哈希碰撞的概率。
哈希值是一个int类型的数值，4个字节，32个bit位，而数组初始化长度为16，那么在参与运算的只有哈希值低位，高位是没有起到任何作用的，所以让高位也参与运算，进一步降低哈希碰撞的概率，使得数据分布更平均，我们把这样的操作称为扰动。
最后通过位与操作(table.length - 1) & hash直接获得下标，而不是用取余操作，位运算更快。这就要求table的容量必须是2的倍数才方便用位与操作。
put操作
put元素时需要考虑如下情况：
- table的延迟初始化
- hash出现冲突的处理，链表，树化操作
- key值相同元素进行替换
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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为null或者长度为0时，初始化hashMap对象中最耗费内存的散列表
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 寻址找到的桶位刚好是 null 即没有hash冲突，直接在该位置插入元素
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 最后遇到hash冲突的处理
else {
Node<K,V> e; K k;
// 该key就在桶中，则赋值给k后续进行替换
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 {
// 从链表头部开始扫描处理
for (int binCount = 0; ; ++binCount) {
// 在链表结尾插入元素
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 链表中存在hash和key都相等的元素，则进行替换
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 已经存在相同key，则替换value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
// 覆写新值
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 修改次数加一，注意如果时替换Node元素则不算修改
++modCount;
// 元素个数加一，并且判断是否大于阈值，大于时需要扩容处理
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
扩容
当元素越来越多时，出现冲突的可能性就会增大，hash之后链表长度就会越长，查找元素时间复杂度从O(1)升到0(n)，为了解决效率下降的问题，就需要扩容，而扩容是比较重量级的操作，其中涉及到拷贝所有元素等。
final Node<K,V>[] resize() {
// 引用扩容之前的哈市表，长度，阈值等数据
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
// 扩容之后的容量和阈值
int newCap, newThr = 0;
// 表示hash表已经初始化过，是一次元素增加导致的扩容
if (oldCap > 0) {
// 超过hashMap容量最大值时，不再扩容，并设置扩容最大阈值位int最大值
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 新table容量增加2倍，没有达到最大容量则相应设置阈值增大2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 延迟初始化，待参数的3个构造函数，new HashMap(intiCap)，new HashMap(map) 并且Map有数据
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// new HashMap();时
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// newThr为0的时候，通过newCap和loadFactor计算出一个newThr
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;
if (oldTab != null) {
// 迭代桶节点，进行复制操作
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null; // 原来的数组置为null，等待GC，原来的数据已经在e里面了
if (e.next == null)
// 单个元素直接计算hash放入即可
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;
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);
// 低位链表，原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 高位链表，原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
get操作
get操作比较简单，主要就是计算hash，然后根据节点类型取值即可。
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;
// 首先判断 table 不是空且长度不为0，并且first部位null
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 桶上的节点匹配hash和key直接返回
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)
// 处理红黑树上的节点
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);
}
}
// 没有找到匹配节点，就返回null
return null;
}
remove操作
删除元素需要注意：如果hash冲突红黑树素比较少，低于6个时，需要转化为链表。
// 暴露的移除元素的API
public V remove(Object key) {
Node<K,V> e;
// 计算hash，然后调用removeNode
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
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;
// 判断 table 是否为空，是否长度为0，且对应的hash值在数组里面存在
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 桶上（链表第一个）的元素匹配
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
// 红黑树处理
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
// 链表匹配，循环查找
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 判断是否找到要删除的节点
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)
// 如果是第一个节点，则直接设置为null
tab[index] = node.next;
else
// 链表中的节点，直接将链表指针指向下一个元素
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node; // 返回删除的节点
}
}
// 如果没有找到元素，则返回null
return null;
}
时间复杂度
HashMap的查找和添加 key-value 键值对的平均时间复杂度为O(1)。- 对于槽位是链表的节点，平均时间复杂度为
O(k)。其中k为链表长度。 - 对于槽位是红黑树的节点，平均时间复杂度为
O(logk)。其中k为红黑树节点数量。
和Hashtable的比较
Hashtable使用synchronized来进行同步。HashMap可以插入键为null的 Entry。HashMap的迭代器是fail-fast迭代器。HashMap不能保证随着时间的推移Map中的元素次序是不变的。
转载请注明出处 Java容器HashMap源码分析
发现宝贝了