HashMap是java中非常常见的一个数据结构,在这篇文章里,我依然以Map中的操作为导向来循序渐进研究HashMap中的源码,阅读这篇文章需要的前置知识有:
- 弱平衡的二叉查找树-红黑树
- 大概了解HashMap的使用方法以及内部结构
该文基于JDK1.8
总结
总结放前面防止太长不看
- HashMap通过数组+链表+红黑树实现,遍历规则是在数组上按槽的顺序,在槽内按节点next的顺序。
- 桶的下标和哈希值的对应关系为:
index = (n - 1) & hash
,n为数组的大小,出于平衡性考虑n必须是2的整数次幂 - 如果一个桶中元素的数量大于8的时候,链表转红黑树(但是实际如果此时数组大小小于64,则扩容重建Hash表而不是树化)
- 一些指标含义:
名称 | 含义 |
---|---|
threshold | 键值对的数量一旦超过这个值就需要进行数组扩容并重建哈希表 |
loadFactor | threshold通常是通过数组的大小*loadFactor 进行计算 |
- 一些指标的值:
名称 | 解释 |
---|---|
DEFAULT_INITIAL_CAPACITY | 初始化数组的大小,默认为16 |
MAXIMUM_CAPACITY | 数组最大大小,是最接近int上限的2的整数次幂1 << 30 |
DEFAULT_LOAD_FACTOR | 负载因子,默认为0.75f ,原因见最后 |
TREEIFY_THRESHOLD | 一旦桶中的元素达到这个值,数组升红黑树,8 |
UNTREEIFY_THRESHOLD | 一旦桶中的元素小于这个值,下次resize的时候会重新降为链表,6 |
MIN_TREEIFY_CAPACITY | 只要数组容量小于这个值,不会进行链表升红黑树,通过resize扩容来解决问题,64 |
- 发生
resize()
的所有情况:- 构造完HashMap之后第一次添加元素,此时调用resize()为数组分配初始空间
- 添加完元素之后键值对的数量大于threshold,发生resize()进行扩容
- 当想要链表升红黑树元素的时候,数组容量小于64,则通过resize()取代树化。
- EntrySet和KeySet都不会建立新的集合,只是在map的基础上做一些操作,不同的是entry获取的是整个Node,而key只有key。
重要方法
我们知道HashMap是Map的重要实现,Map接口的重要方法有:
put()
,get()
,getOrDefault()
,putIfAbsent()
,containsKey()
replace()
remove()
entrySet()
keySet()
下面就让我们开始跟踪这些方法的源码:
put
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
put和get方法是Map最常用的方法了,熟悉哈希表结构的都知道,HashMap的底层就是把哈希值和对象关联起来,但是因为哈希值并不唯一,可能会出现哈希冲突,也就是一个位置可能需要存放多个对象,如果解决Hash冲突是制约查找效率非常重要的问题。
在这个方法里,我们大概能猜到,hash()
是获取哈希值的函数,先来看看哈希值怎么获取的:
hash
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
实际上就是默认Object的hashcode位或自己的高16位,至于Object的hashcode怎么来的,就涉及到JNI层面的理论了,网上有说是对象地址转换而来的,我也有尝试跟踪OpenJdk中c++的源码,最后实在看不懂放弃了QAQ。不过java doc上面说hashcode不要求唯一,也就是说不同的对象可以计算出同一个哈希值,我们就姑且忽略它的具体计算过程,看一下putVal()
方法:
putVal
这个方法最后两个布尔类型参数分别代表onlyIfAbsent:如果原来存在键,就不替换值
和evict:如果是false,代表这个map正处于创建模式
//onlyIfAbsent大概可以联想到和putIfAbsent有关
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赋给tab,可以猜测table是存储所有哈希桶的数组。
if ((tab = table) == null || (n = tab.length) == 0)
//resize,给一个初始容量,n被赋予容量大小
n = (tab = resize()).length;
//先获取原来的桶p,如果hash不冲突,直接插入节点
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//hash冲突
else {
Node<K,V> e; K 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);
//如果binCount大于TREEIFY_THRESHOLD - 1,则树化,可以猜测转红黑树
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;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
//如果onlyIfAbsent不为true或原来的value为null,替换value
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//没有实现,仅在LinkedHashMap中有用到
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//大于threshold则扩容
if (++size > threshold)
resize();
//没有实现,仅在LinkedHashMap中有用到
afterNodeInsertion(evict);
return null;
}
这是一个比较复杂的方法,通过源码跟踪可以总结出:
- HashMap内部是用Node[]来存储数据的,一个哈希值为hash的元素在数组中的下标为
(n - 1) & hash
(n是数组的长度) - 如果binCount大于TREEIFY_THRESHOLD - 1(
static final int TREEIFY_THRESHOLD = 8
),则树化,可以猜测转红黑树(但是实际如果此时数组大小小于64,则扩容重建Hash表而不是树化) - threshold是size的上限,如果size超过threshold,则调用
resize()
扩容
在这个方法里面,我们看到了Node
,TreeNode
,可以推测Node是链表的节点,而TreeNode继承自Node,代表红黑树的节点
内部类:Node
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
//...
}
内部类:TreeNode
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;//代表节点颜色
//...
}
在这个类中实现了许多红黑树的操作,这里就不看它们的实现了。
putIfAbsent
之前我们推测putIfAbsent和putVal中的参数onlyIfAbsent有关,现在我们看看源码,确定一下:
public V putIfAbsent(K key, V value) {
return putVal(hash(key), key, value, true, true);
}
可以看出,推测完全正确,就是把参数onlyIfAbsent设为了true,这样即使把节点取出来了但并不会替换掉它的value。
get
看完了put我们来看get,进一步巩固我们对HashMap结构的认知:
public V get(Object key) {
Node<K,V> e;
//可以猜测getNode能通过hash值和键查找到元素节点,可能是链表节点,也可能是红黑树节点
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
getNode
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;
}
无论是红黑树的情况(搜索二叉树的查找)还是链表的情况查找的实现都挺简单的,这里就不深挖了。
getOrDefault
至于getOrDefault是怎么实现的,由于getNode方法如果没找到节点会返回null,我们可以推测getOrDefault先调用getNode方法,如果返回了null,则把用户给的默认值返回回去。
public V getOrDefault(Object key, V defaultValue) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
}
containsKey
containsKey的判断依据也是调用getNode,如果返回null说明没有查找到对应节点,即不包含这个键。
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
replace
replace其实较为不常用,因为put方法就能更新节点的值,他们的区别主要有:
+ replace还有一个重载方法,仅当旧值符合用户传入的参数时才更新
那么它们实现更新的方法是一样的吗?
public V replace(K key, V value) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) != null) {
V oldValue = e.value;
e.value = value;
afterNodeAccess(e);
return oldValue;
}
return null;
}
可以看出因为replace是已经确定了存在这个元素,直接调用getNode去获取原来的节点,并更新它的值。但是查找的过程本质其实和put一样的。
那么replace还有一个重载方法:
public boolean replace(K key, V oldValue, V newValue) {
Node<K,V> e; V v;
if ((e = getNode(hash(key), key)) != null &&
((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
e.value = newValue;
afterNodeAccess(e);
return true;
}
return false;
}
可以看出,仅当原来节点的值符合用户的输入参数时才更新。
remove
remove方法用于从Map中移除元素,对应的无非也就是链表元素的删除或是红黑树元素的删除,链表元素的删除只需要更新指针,红黑树元素的删除却可能需要重新上色和旋转等一系列繁琐的动作,不难想到,如果红黑树的元素删到一定数量以下时,可能会退化回链表。
看源码:
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
这里涉及到函数removeNode,跟踪进去:
//后面两个布尔值分别代表是否要求值匹配,movable如果是false不允许移动其他节点
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;
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)
//使用getTreeNode先获取红黑树节点
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);
}
}
//如果matchValue为true,必须要比对用户给的旧值是否正确
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
//如果是红黑树,调用该类的removeTreeNode移除节点
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;
//没有实现,仅在LinkedHashMap中有用到
afterNodeRemoval(node);
return node;
}
}
return null;
}
这里我们暂时没看到有红黑树退化为链表的操作,不急,继续看下去。(实际上是在下一次resize的时候退化为链表)
entrySet
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
可以看出直接获得内部的entrySet字段。我们先看一下EntrySet的定义:
//Entry是一个接口,有getKey()、getValue()等方法
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator();
}
public final boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
Object key = e.getKey();
Node<K,V> candidate = getNode(hash(key), key);
return candidate != null && candidate.equals(e);
}
public final boolean remove(Object o) {
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
Object key = e.getKey();
Object value = e.getValue();
return removeNode(hash(key), key, value, true, true) != null;
}
return false;
}
public final Spliterator<Map.Entry<K,V>> spliterator() {
return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
迭代器通过EntryIterator
获得:
EntryIterator
final class EntryIterator extends HashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
它又继承了HashIterator:
HashIterator
abstract class HashIterator {
Node<K,V> next; // next entry to return
Node<K,V> current; // current entry
int expectedModCount; // for fast-fail
int index; // 当前slot
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
//从slot为0处开始遍历
index = 0;
if (t != null && size > 0) { // 找到第一个有节点的slot,并把next赋值为第一个节点
do {} while (index < t.length && (next = t[index++]) == null);
}
}
public final boolean hasNext() {
return next != null;
}
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
// 在当前槽中寻找下一个节点,如果当前槽已经找完了继续向后寻找有节点的slot
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}
keySet
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new KeySet();
keySet = ks;
}
return ks;
}
KeySet的定义:
final class KeySet extends AbstractSet<K> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
//KeyIterator也是继承自HashIterator,但返回的只是节点中的键
public final Iterator<K> iterator() { return new KeyIterator(); }
public final boolean contains(Object o) { return containsKey(o); }
public final boolean remove(Object key) {
return removeNode(hash(key), key, null, false, true) != null;
}
public final Spliterator<K> spliterator() {
return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer<? super K> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.key);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
通过上面的EntrySet和KeySet我们可以看出,EntrySet和KeySet并没有形成一个真正的集合,他们的一些Set操作只是在原map的基础上操作。比如EntrySet的iterator实际上只是使用了HashIterator,next()
返回的是一个Node类型,但由于Node类型实现了Entry接口,所以可以当作一个Entry用。KeySet原理类似,只是使用了HashIterator返回的Node类型提取出了key。这也是为什么《阿里巴巴Java开发手册》中说明:
【推荐】使用 entrySet 遍历 Map 类集合 KV,而不是 keySet 方式进行遍历。
说明: keySet 其实是遍历了 2 次,一次是转为 Iterator 对象,另一次是从 hashMap 中取出key 所对应的 value。而 entrySet 只是遍历了一次就把 key 和 value 都放到了 entry 中,效率更高。如果是 JDK8,使用 Map.foreach 方法。
正例: values()返回的是 V 值集合,是一个 list 集合对象;keySet()返回的是 K 值集合,是一个 Set 集合对象;entrySet()返回的是 K-V 值组合集合。
构造方法与扩容
构造方法
默认无参构造方法:
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
static final float DEFAULT_LOAD_FACTOR = 0.75f;
看到这里似乎有点奇怪,HashMap内部不是有个Node数组嘛!这里怎么没有初始化?不过回想上面的putVal方法,一开始就判断了tab
是不是为null,如果是的话执行resize()
,估计这个resize方法可以初始化。
那么这个DEFAULT_LOAD_FACTOR
是什么东西呢?直译叫做负载因子,看看后面的方法有没有出现。
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;
//tableSizeFor可以返回大于且最接近initialCapacity的2的整数次幂
this.threshold = tableSizeFor(initialCapacity);
}
//其中
static final int MAXIMUM_CAPACITY = 1 << 30;
为什么最大容量是MAXIMUM_CAPACITY
?
- HashMap在确定数组下标Index的时候,采用的是
(length-1) & hash
的方式,只有当length为2的指数幂的时候才能较均匀的分布元素。所以HashMap规定了其容量必须是2的n次方 -
由于HashMap规定了其容量是2的n次方,对于HashMap来说其最大的容量应该是不超过int最大值的一个2的指数幂,即
1 << 30
扩容
终于要来看这个HashMap中最重要的一个函数了-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) {
//如果大于最大容量不扩容直接返回
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 新容量为旧容量的两倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 上限也翻倍
}
// 如果原来长度为0且threshold不为0,初始容量赋值为threshold
// 这种情况发生在使用有参构造函数后,添加第一个元素的时候。
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 如果原来长度和threshold都为0,用DEFAULT_INITIAL_CAPACITY=16充当初始容量
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
//元素上限为0.75倍的数组容量
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)
//split中可能出现红黑树降级为链表
((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);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
看完这个方法我们就大概知道各种指标的含义了。(我放到总结里去了)
《阿里巴巴Java开发手册》中有这样一条建议:
【推荐】集合初始化时,指定集合初始值大小。
说明: HashMap 使用 HashMap(int initialCapacity) 初始化。
正例: initialCapacity =(需要存储的元素个数 / 负载因子) + 1
。注意负载因子(即 loaderfactor)默认为 0.75,如果暂时无法确定初始值大小,请设置为 16(即默认值)。
反例: HashMap 需要放置 1024 个元素,由于没有设置容量初始大小,随着元素不断增加,容量 7 次被迫扩大,resize 需要重建 hash 表,严重影响性能。
问题
- 为什么默认负载因子是0.75?
网上很多博客说这跟泊松分布有关系,原因来自jdk8中的HashMap的一段注释,而我看到有一位博主反驳了这种观点,说官方取默认负载因子为0.75和泊松分布并没有关系,只是一种折中的选择,而对于负载因子为0.75,加上泊松分布公式,推断出一个桶的元素数量超过8的概率非常小,这是为什么要引入红黑树的原因。
参考HashMap defaultLoadFactor = 0.75和泊松分布没有关系_厚积薄发者,轻舟万重山-CSDN博客
- 为什么8升红黑树,6降链表?
如上所述,对于负载因子为0.75时,使用泊松分布公式可计算出一个桶中元素数量分布概率为:
0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
当数量达到8的时候概率已经非常小了,官方认为此时可以使用红黑树解决效率问题。
至于数量降为6的时候再进行resize会退化为链表,官方在javadoc中写道:
The bin count threshold for untreeifying a (split) bin during a resize operation. Should be less than TREEIFY_THRESHOLD, and at most 6 to mesh with shrinkage detection under removal.
首先TREEIFY_THRESHOLD
必须小于TREEIFY_THRESHOLD
,即必须小于8,为了适应移除元素的时候桶的轻微收缩,TREEIFY_THRESHOLD
不超过6。
原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/hashmap%e6%ba%90%e7%a0%81%e5%88%86%e6%9e%90/