文章目录
-
- 一、HashMap 简单介绍
- 二、HashMap 方法源码阅读
-
- 2.1 HashMap() 方法
- 2.2 put() 方法
- 2.3 get() 方法
- 2.4 remove() 方法
- 三、总结
一、HashMap 简单介绍
HashMap
是 Java 中一个比较重要的集合类，从名字就可以看出来，它实现了
Map
接口。也就是说，
HashMap
存储的是键值对（
key-value
）数据，其中
key
是无序的，不可以重复的，
value
是无序的，可以重复的。
HashMap
的底层数据结构可以理解为一个哈希表，关于哈希表的详细介绍，可以看我的另一篇博客：哈希表 。
我们知道，
HashMap
解决哈希冲突的方案是拉链法，在 JDK1.7 之前，
HashMap
的底层数据结构是 数组+链表，在 JDK1.7 之后，
HashMap
底层改为了 数组+链表/红黑树 这样的数据结构。之所以有这样的改进，是因为当哈希冲突比较严重的时候，其查找性能会退化为 O(n)，而将链表转化为红黑树这样的数据结构，可以有效提高其查找性能。
上面关于
HashMap
我们可以建立起宽泛的概念，知道
HashMap
的特点以及底层数据结构。我们知道
ArrayList
的底层实际上是一个
Object
数组在存储元素，那么
HashMap
的底层实际上是谁在存储元素呢 ？如何存储
key-value
键值对数据呢 ？
通过查看
HashMap
的源码，我们可以看到
HashMap
中有这样一个数组：
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node<K,V>[] table;
这个数组保存的数据类型是
Node
，此类源码如下：
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
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;
}
// setter and getter and so on ......
}
至此，谜底就揭开了：
HashMap
的底层实际上是一个
Node
类型的
table
数组在存储数据，而
Node
封装了键值对的
key
和
value
以及
hash
值和指向下一个结点的指针。
而这个
Node
实际上可以看成是 链表/二叉树 的结点，这也就对应上了上面所说的 JDK1.7 之后，
HashMap
底层是一个 数组+链表/红黑树 这样的数据结构。
二、HashMap 方法源码阅读
2.1 HashMap() 方法
我们一般在使用
HashMap()
的时候，都是直接
new
一个无参的构造方法，方法内容如下：
/**
* Constructs an empty {@code HashMap} with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
我们可以通过注释得知：调用无参的构造方法会创建一个初始大小为 16，默认加载因子为 0.75 的空集合。
可是在方法体内，我们只看到了给加载因子赋值，并没有看到初始化集合的容量大小。基于阅读
ArrayList
源码的经验，我们可以猜测
HashMap
的初始容量将会在第一次调用
put()
方法时才会真正赋予。
2.2 put() 方法
put()
方法的作用是向
HashMap
集合中添加一个键值对数据。它是
HashMap
类的重中之重，这个方法涉及到了许多方法。其源码如下：
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
put()
方法的的方法体代码只有一行，也就是调用
putVal()
方法，
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;
// 判断 table 是否为空
if ((tab = table) == null || (n = tab.length) == 0)
// 如果为空，则调用 resize() 方法扩容
n = (tab = resize()).length;
// 判断 key 对应数组下标是否为 null，即是否发生哈希冲突
if ((p = tab[i = (n - 1) & hash]) == null)
// 如果为 null，则创建一个结点 node，将 hash、key、value 封装进去
// 然后将结点添加到对应数组下标
tab[i] = newNode(hash, key, value, null);
else { // 如果发生了哈希冲突
Node<K,V> e; K k;
// 判断哈希值是否相等且 key 是否相等（也就是判断是不是同一个元素/结点）
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 如果是同一个元素/结点，则获取到这个结点
e = p;
else if (p instanceof TreeNode)
// 如果是红黑树结点，那么调用 putTreeVal() 方法插入值
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;
}
// 判断是不是重复结点
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 结点指针后移
p = e;
}
}
// 如果 e 不是空结点
if (e != null) { // existing mapping for key
// 获取旧值
V oldValue = e.value;
// 如果旧值不为 null
if (!onlyIfAbsent || oldValue == null)
// 更新旧值
e.value = value;
afterNodeAccess(e);
// 返回旧值
return oldValue;
}
}
// 操作次数 +1
++modCount;
// 判断添加了新的结点之后，数组长度是否超过了阈值 threshold(即 0.75*capacity)
if (++size > threshold)
// 如果超过了阈值，那就扩容
resize();
afterNodeInsertion(evict);
return null;
}
对于上面的
putVal()
方法，我已经做了比较详细的注释。
putVal()
方法的流程概括下来就是：
- 首先判断哈希表是否为空，如果为空则调用
resize()
- 接着计算
key
- 如果没有发生哈希冲突，那就将
key
value
hash
Node
threshold
resize()
HashMap
- 如果发生了哈希冲突：
- 首先判断头结点是不是重复元素，如果是重复元素，则用新的
value
value
- 如果没有重复元素，则判断当前数组中存放的结点（头结点）是树结点还是链表结点。
- 如果是红黑树结点，则调用
putTreeVal()
key
value
hash
- 如果是链表结点，则遍历链表，判断是否有重复元素，如果有则覆盖；如果没有，则将新的
Node
- 插入完成之后还需判断链表结点个数是否达到了 8，如果达到了 8，则调用
treeifyBin()
- 首先判断头结点是不是重复元素，如果是重复元素，则用新的
这个
treeifyBin()
方法的作用是什么呢 ？ 是直接将链表转化为红黑树吗 ？带着疑问我们来看它的源码：
/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 首先判断数组是不是为空或者数组的长度是不是小于64，如果符合那么就先 resize()
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) { // 如果数组长度大于 64，那就转换为红黑树
TreeNode<K,V> hd = null, tl = null;
do {
// 将链表结点转换为红黑树结点
TreeNode<K,V> p = replacementTreeNode(e, null);
// 先用双向链表形式来存储红黑树结点
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
// 如果数组中下标 index 对应的的双向链表不为空，那么将其转换为红黑树
if ((tab[index] = hd) != null)
// 转换为红黑树
hd.treeify(tab);
}
}
这个方法我也做了注释，从注释我们就可以看出来，
treeifyBin()
方法中并不是直接将链表转化为红黑树，而是会先判断链表的长度是否达到了 64，再决定是扩容还是转换为红黑树。总结下来就是：如果链表的结点个数达到了 8，并不会直接将链表转换为红黑树，而是会首先会判断数组长度是否小于 64，如果小于 64，则先调用
resize()
方法进行扩容；如果已经达到了 64，再将链表转换为红黑树。
在
putVal()
方法中，我们还需要注意这两行代码：
// 判断添加了新的结点之后，数组长度是否超过了阈值 threshold(即 0.75*capacity)
if (++size > threshold)
// 如果超过了阈值，那就扩容
resize();
它的意思是：当数组中元素的个数超过了
threshold
时，将会触发扩容机制。
对于变量
threshold
，它的定义如下：
/**
* The next size value at which to resize (capacity * load factor).
*/
int threshold;
我一般把
threshold
叫做扩容阈值。它的作用是标识当前容量下的
HashMap
可以容纳元素的最大容量，它的取值为
capacity * load factor
，而
load factor
的取值固定为 0.75，因此
threshold
的大小为
0.75 * capacity
。也就是说：当数组中元素的个数超过了
0.75 * capacity
时，将会触发
HashMap
的扩容机制。
在上面不止一次提到过
resize()
方法的作用是对
HashMap
进行扩容，那这个方法具体是如何进行扩容的呢？
查看
resize()
的源码：
/**
* 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
*/
final Node<K,V>[] resize() {
// 获取原来的 hash 表的信息：包括长度、threshold
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold; // threshold = capacity * load factor
int newCap, newThr = 0;
// 判断原来的数组容量是否大于 0
if (oldCap > 0) {
// 如果原来的数组容量大于了 MAXIMUM_CAPACITY，则仅调整扩容阈值，数组容量不变
if (oldCap >= MAXIMUM_CAPACITY) { // MAXIMUM_CAPACITY = 1 << 30;
threshold = Integer.MAX_VALUE; // 将 threshold 调整为 Integer.MAX_VALUE
return oldTab; // 数组容量保持不变
}
// 如果原来的数组容量*2 之后仍然小于 MAXIMUM_CAPACITY，且原容量大于 DEFAULT_INITIAL_CAPACITY（即16）
// 则将数组容量翻倍，扩容阈值也翻倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 如果原容量小于等于 0，且原 threshold 大于 0，则将数组容量初始化为 threshold
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 如果原容量小于等于 0，且原 threshold 小于等于 0，则将数组初始化为默认容量（16）
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY; // DEFAULT_INITIAL_CAPACITY = 1 << 4;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // DEFAULT_LOAD_FACTOR = 0.75f;
}
// 这部分的作用就是防止扩容阈值溢出
if (newThr == 0) {
float ft = (float)newCap * loadFactor; // 新的容量*0.75
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;
// 接下来会将原来的数组中的元素 rehash 到新的 table 数组中
if (oldTab != null) {
// 下面的逻辑是 rehash 过程
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// 判断数组当前下标的元素是否为空
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 如果只有一个头结点，那就直接 rehash 到新的数组中
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果不止一个结点，且头结点一个红黑树结点，则对红黑树进行 rehash
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 如果不止一个结点，且头结点是链表结点，则对链表进行 rehash
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，可以将任一下标中对应的链表结点分为两类
// 等于 0 时，则该结点放到新数组时的索引位置等于其在旧数组时的索引位置
// 记为低位区链表，以 lo（意为low）开头
// 不等于 0 时,则该头节点放到新数组时的索引位置等于其在旧数组时的索引位置再加上旧数组长度
// 记为高位区链表，以 hi（意为 high）开头
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); // 把整个链表结点 rehash 完成
// 把低位区链表的头结点记录到新的数组中（新的下标与旧的数组下标相同）
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 把高位区链表的头结点记录到新的数组中（新的下标等于其在旧数组时的索引位置再加上旧数组长度）
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
从
resize()
方法的官方注释我们可以得知：
resize()
方法的作用就是初始化数组的大小或者将数组大小翻倍。
当调用
resize()
方法时，具体执行逻辑如下：首先判断数组的长度是否为 0，如果为 0 的话，则初始化数组的长度为 16；如果不为 0，则尝试将数组的长度扩容为原来的 2 倍，同时将扩容阈值调整为原来的 2 倍。如果扩容之前的数组的长度已经达到了最大值（1 << 30，即 1073741824），则只调整扩容阈值为
Integer.MAX_VALUE
。 扩容完毕之后，按照新的容量创建一个数组，然后将判断原数组中每个位置记录的结点是红黑树结点还是链表结点。无论是红黑树或者是链表，本质上都是对它们进行结点拆分，然后再
rehash
映射到新的数组中。
值得注意的是，链表的
rehash
过程是一个很有特色的过程，在这个过程中通过判断
e.hash & oldCap
是否等于 0，将一个链表中的结点分为两类，一类将映射到一个低位区链表，另一类将会映射到高位区链表。而这里的低位区和高位区指的是在新的数组中的位置，而低位区的索引等于链表在原数组中的索引，高位区的索引等于链表在原数组中的索引加上原数组的大小。
如果读者对
rehash
的具体过程感兴趣的话，可以尝试阅读下面两篇文章：
- 让星星⭐月亮告诉你，HashMap扩容时的rehash方法中(e.hash & oldCap) == 0算法推导
- HashMap实现原理分析(源码分析，ReHash，)
put()
方法总结：
当调用
put()
方法时，首先会判断数组的长度是否为 0，如果为 0 的话，则进行
resize()
操作，将数组的容量初始化为 16。接着将
key
和
value
以及
hash
等信息封装到一个
Node
结点中，将这个
Node
结点 添加/更新 到对应下标位置的 链表/红黑树 中。如果链表的长度达到了 8，并不会直接将链表转化为红黑树，而是会首先判断数组长度有没有达到 64。如果数组长度没有达到 64，则先对数组进行扩容，容量扩为原来的 2 倍，然后对链表结点进行
rehash
重新映射到新的数组中，否则才将链表转化为红黑树。
2.3 get() 方法
put()
方法的作用是通过
key
从
HashMap
集合中获取相应的数据。
首先从
put()
方法看起：
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*/
public V get(Object key) {
Node<K,V> e;
// 根据 key 获取 Node，如果获取成功则返回 value，否则返回 null
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
put()
方法的方法体很简单，它的逻辑就是调用
getNode()
方法来根据
key
的
hash
值获取到对应的
Node
结点（因为数据本质上是以
Node
的形式存储在数组中的）。如果获取到了，则返回对应的
value
，否则返回
null
。
也就是说，目前来看，真正查找数据的是
getNode()
方法。其方法体如下：
/**
* 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;
// 如果 tab 数组不为空，且长度大于 0，且 key 对应的 hash 值对应的下标不为空
// 则执行括号里面的逻辑
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 {
// 主要就是判断 hash 和 key 是不是相等或者是 key 相等的话也行
// 因为 put 的时候保证了 key 就是唯一的
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
get()
方法的逻辑相对于
put()
方法就简单很多，没有多少复杂的东西。
经过上面的源码分析，
HashMap
的
get()
方法的过程可以总结为：首先根据
key
计算出
hash
值，然后定位到具体的数组下标，再依次比较
key
是否相等，如果相等，则将
Node
结点返回。如果返回的是
Node
结点不为空，则获取的对应的
value
，如果为空，则返回
null
。
2.4 remove() 方法
remove()
方法的作用是从
HashMap
中移除指定的
key
以及对应的
value
。
remove()
方法实现如下：
/**
* Removes the mapping for the specified key from this map if present.
*/
public V remove(Object key) {
Node<K,V> e;
// 实际上是在调用 removeNode() 方法来执行删除动作
// 如果删除成功，则返回 node，然后根据 node 获取到 value；否则返回 null
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
同样，
remove
中也是调用了别的方法来完成数据的删除操作。这里调用的是
removeNode()
方法：
/**
* Implements Map.remove and related methods.
*/
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 数组不为空，且长度大于 0，且 key 对应的 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;
// 根据 key 判断头结点是不是目标结点，是则记录到 node 中
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
// 从 红黑树/链表 中找目标结点，找到则记录到 node 中
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);
}
}
// 判断上面有没有找到相应的结点，如果有则执行删除逻辑
// 上面查找完毕之后，p 记录的是待删除结点的前一个结点，node 记录待删除结点
// 如果目标结点是头结点，则 p、node 都指向头结点
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;
}
关于
removeNode()
方法，注释也是做得比较详尽。结合源码以及注释，我们可以总结出
HashMap
中
remove()
方法的流程为：首先根据
key
计算出
hash
值然后映射到具体的数组下标，接着在 链表/红黑树 中查找
key
相等的
Node
，如果查找成功则删除对应的
Node
并返回该
key
对应的
value
，否则返回
null
。
三、总结
与
ArrayList
相同，
HashMap
中常用方法中最复杂的一个方法就是添加元素的方法。在
put()
方法中并不是简简单单的直接把元素添加进去，还需要判断是否需要扩容（扩容中还包含着
rehash
过程，如果有数据的话）以及是否需要将链表转化为红黑树等等操作。而
get()
方法和
remove()
方法则是比较常规的操作。
![Java小案例——随机数猜测随机数猜测[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)