HashMap
HashMap是基于哈希表的数据结构，用于存储键值对(key-value).其核心是将键的哈希值映射到数组索引位置,通过数组+链表(Java8之后是数组+链表/红黑树)来处理哈希冲突.
HashMap使用键的HashCode()方法计算哈希值,并通过indexFor方法(JDK1.7以后移除了这个方法,直接使用(n-1) & hash)确定元素在数组中的存储位置.哈希值是经过一定扰动处理的,防止哈希值分布不均匀,从而减少冲突.
HashMap的默认初始容量是16,负载因子为0.75.也就是说,当存储的元素数量超过16 * 0.75 = 12个时,HashMap会触发扩容操作,容量 * 2并重新分配元素位置.这种扩容是比较耗时的操作,频繁扩容会影响性能.
通过源码深入了解HashMap
首先了解一下比较重要的一些变量定义
/**
* The default initial capacity - MUST be a power of two.
* 默认初始容量 - 必须是2的幂次方
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
* 最大容量,如果构造函数中通过参数隐式指定了更高的值,则使用此最大容量
* 必须是小于等于1 << 30 的 2 的幂次方
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
* 构造函数中未指定时使用的负载因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
* 在向存储单元添加元素时,存储单元使用树结构而不是链表结构的存储单元计数阈值
* 当向存储单元添加元素,且该存储单元至少有此数量的节点时,存储节点将转换为树结构
* 该值必须大于2,并且应该至少为8,以与移除元素时转换回普通存储单元的假设相匹配
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 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,并且最多为6,以与移除元素时的收缩检测相匹配
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
* 存储单元可以树化的最小表容量
* (否则,如果存储单元中有太多节点,表将进行扩容)
* 应该至少是4 * TREEIFY_THRESHOLD,以避免扩容和树化阈值之间的冲突
*/
static final int MIN_TREEIFY_CAPACITY = 64;
通过上面的变量定义可以思考一下问题
DEFAULT_INITIAL_CAPACITY初始容量为什么必须是2的n次方?DEFAULT_LOAD_FACTOR负载因子为什么原则0.75?同时为什么扩容会是两倍?TREEIFY_THRESHOLD为什么从链表转换为红黑树的阈值默认为8?是怎么从链表转换成红黑树的?
HashMap的结构
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; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
return o instanceof Map.Entry<?, ?> e
&& Objects.equals(key, e.getKey())
&& Objects.equals(value, e.getValue());
}
}
从源码上可以看到,HashMap是由Node组成的一个单向链表,因为Node结构中只有next指向后继节点,那么我们可以用图来展示一个完成初始化的HashMap数组.(在JDK1.8之前,HashMap节点是由Entry组成的,原理结构和Node一致)
- 为什么使用链表+红黑树？
数组的使用:
使用数组可以进行快速索引,HashMap内部使用数组来存储元素,数组的每个元素成为一个桶(bucket).使用数组的主要优点是可以通过计算元素的哈希值,将其映射到数组的一个索引位置,从而实现快速的查找,插入和删除操作.
同时对于一个给定的键值对(key-value),通过hash(key) % n可以得到该键值对应存储在数组的哪个位置.在实际的Java实现中,为了提高性能,使用hash(key) & (n-1)来计算索引,因为HashMap的容量总是2的幂次方,这种方式等价于取模运算,而且效率更高.这就回答了上面HashMap的容量为什么总是2的幂次方的问题.
链表的使用:
由于哈希函数的特性,不同的键可能会产生相同的哈希值,或者不同的哈希值映射到数组的同一个索引位置,这就是哈希冲突.为了解决哈希冲突,HashMap在每个数组元素(桶)中使用链表来存储那些映射到相同索引位置的键值对.
当发生哈希冲突时,新插入的元素会添加到该桶对应的链表的末尾.查找时,先找到对应的桶,然后在链表中遍历查找目标元素.
在链表中的查找操作是线性的,时间复杂度是O(n),但当冲突较少时,链表的长度较短,性能影响不大.
当产生哈希冲突的时候,HashMap的结构如下:
PUT方法
源码:
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* 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
*/
/**
* 参数解释
* hash: key的哈希值(经过扰动计算)
* key: 要插入的键
* value: 要插入的值
* onlyIfAbsent: 如果为true,则仅当Key不存在时才插入(不覆盖旧值)
* evict: 用于LinkedHashMap的后续处理(HashMap本身未使用)
*/
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)
n = (tab = resize()).length;
//根据哈希值计算元素在数组中的索引,如果该位置为空,则直接将元素作为新节点添加
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//e: 临时节点,用于记录与待添加元素相同key的节点,如果不存在则为null,表示要插入新节点
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 {
//遍历链表查找元素(key存在)/插入位置(key不存在)
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//链表中不存在该key时,将元素加到链表尾部
p.next = newNode(hash, key, value, null);
//检查是否需要树化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//检查链表中的节点是否与要插入的新元素key相同
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
//找到相同key的位置记录后退出循环
break;
//遍历链表下一个节点(相当于p = p.next)
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;
}
}
//修改计数器(用于fail-fast机制)
++modCount;
if (++size > threshold)
resize();
//LinkedHashMap的后续处理(如移除最老的entry)
afterNodeInsertion(evict);
return null;
}
根据源码和注释可以理解HashMap中put()方法的主要流程
Resize方法
通过上面的流程及源码可以看到除了在hash冲突后形成链表及链表长度大于8之后转换为红黑树,还有就是当元素个数超过最大数组长度*负载因子时就会进行数组扩容,那扩容具体是如何进行的呢,我们看下resize()方法
resize()用于以下两种情况
- 初始化table
- 在table超过threshold之后进行扩容
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
/*
初始化或翻倍哈希表的大小。如果当前表为空，则根据字段 threshold 中保存的初始容量目标进行分配。否则，由于我们使用 2 的幂次扩展（power-of-two expansion），每个桶中的元素要么保持在原索引位置，要么在新表中以 2 的幂次偏移量移动。
返回值：
新的哈希表（table）
*/
final Node<K,V>[] resize() {
//保存旧数组
Node<K,V>[] oldTab = table;
//获取旧数组容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//旧阈值
int oldThr = threshold;
int newCap, newThr = 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; // double threshold
}
//如果旧阈值大于0,表示使用旧阈值作为新容量
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//否则使用默认的初始容量,并根据负载因子计算阈值
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
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;
//抑制编译器产生的特定警告信息
//这里需要创建一个新的哈希表数组(newTab),但由于Java泛型的类型擦除机制,直接创建泛型数组是不允许的,因此需要强制类型转换
//rawtypes警告,触发原因: new Node[newCap]是一个原始类型(raw type)的数组,因为它没有指定泛型参数
//unchecked警告,触发原因: 将Node[]强制转换为Node<K,V>[]时,编译器无法确保类型完全匹配(因为泛型信息在运行时被擦除)
@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)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order 保持顺序
//低位置元素: 哈希值对应高位为0，留在原索引
//高位置元素: 哈希值对应高位为1,移动到 原索引+oldCap
//本质: 通过哈希值的某一位快速拆分链表,实现高效扩容
//用于存储低位置元素的链表头和尾
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;
}
链表拆分的过程，将桶中的链表根据哈希值的某一位分类为lo链表和hi链表，分别对高低位元素向新数组内进行转移
具体流程如下:
GET方法
源码:
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code (key==null ? k==null :
* key.equals(k))}, then this method returns {@code v}; otherwise
* it returns {@code null}. (There can be at most one such mapping.)
*
* <p>A return value of {@code null} does not <i>necessarily</i>
* indicate that the map contains no mapping for the key; it's also
* possible that the map explicitly maps the key to {@code null}.
* The {@link #containsKey containsKey} operation may be used to
* distinguish these two cases.
*
* @see #put(Object, Object)
*/
/*
返回指定键所映射的值，如果此映射中不包含该键的映射关系，则返回 null。
更正式地说，如果此映射包含一个键 k 到值 v 的映射关系，且满足 (key == null ? k == null : key.equals(k))，则该方法返回 v；否则返回 null。（这样的映射关系最多只能有一个。）
返回 null 并不一定表示该映射中不包含此键的映射；也可能是该键显式映射到了 null。可以通过 containsKey 方法来区分这两种情况。
另请参阅：
put(Object, Object)
*/
public V get(Object key) {
Node<K,V> e;
return (e = getNode(key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods.
*
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(Object key) {
//存储元素的数组,以及节点引用和相关参数
Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k;
//检查表不为空且长度大于0,并根据键的哈希值找到对应桶的第一个节点
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & (hash = hash(key))]) != 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)
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;
}