HashMap源码解析
-
- 结构图
- 常用变量
- 内部类
- 构造方法
- 常见方法
-
- 核心方法hash、resize、tableSizeFor等
- put
- get
- remove
- 总结
结构图
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
...
}
常用变量
// 序列号 ，序列化使用
private static final long serialVersionUID = 362498820763181265L;
// 默认的初始容量 1<<4 带符号左移 0001 ---> 10000 (2进制) = 16(10进制)
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量 2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
// 加载因子 例如：数组容量为8 当元素数量为6(8*0.75)时，则会触发扩容。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当某个桶节点(桶即为数组的每个格子)数量大于8时，会转换为红黑树。
static final int TREEIFY_THRESHOLD = 8;
//当某个桶节点数量小于6时，会转换为链表，前提是它当前是红黑树结构。
static final int UNTREEIFY_THRESHOLD = 6;
// 整个hashMap中元素数量大于64时，也会进行转为红黑树结构
static final int MIN_TREEIFY_CAPACITY = 64;
// hashmap底层存储数据结构 --数组 transient关键字表示该属性不能被序列化
transient Node<K,V>[] table;
// 将数据转换成set的另一种存储形式
transient Set<Map.Entry<K,V>> entrySet;
// 元素数量
transient int size;
// 统计该map修改的次数
transient int modCount;
// 临界值，也就是元素数量达到临界值时，会进行扩容 (LOAD_FACTOR * INITIAL_CAPACITY)
int threshold;
// 同加载因子
final float loadFactor;
内部类
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;
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;
}
}
// 树节点 注意继承了 LinkedHashMap的Entry，LinkedHashMap的Entry继承了HashMap的Node
// 说明树节点本身也是一种双向链表
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;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
...// 省略树的相关方法
}
构造方法
public HashMap() {
// 加载因子 = 默认加载因子 = 0.75f
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// 给定一个默认容量
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 一个必问必知的方法,在下面核心方法中讲解。
// 返回给定容量的最大2次幂；例如 initialCapacity = 6 返回 8(2的3次方)；initialCapacity = 12 返回 16(2的4次方)
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
// 见下
putMapEntries(m, false);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
// 获取元素个数
int s = m.size();
if (s > 0) {
// 如果 hashmap 还未初始化
if (table == null) { // pre-size
// +1 是为了除不尽的情况
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
// 计算扩容阈值
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
常见方法
核心方法hash、resize、tableSizeFor等
// hash算法
static final int hash(Object key) {
int h;
// ^:异或运算; >>>:无符号右移
// 1^1=0; 1^0=1; 0^1=1; 0^0=0
// 这里又是异或又是位运算，理由呢。可以参照这个大神的解答：https://www.zhihu.com/question/20733617
// 简单来说：这段代码叫“扰动函数”，目的就是为了混合原始hash的高位与低位，以此来增加低位的随机性；减少hash冲突
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// ***** 计算扩容因子 *****
// >>>:无符号右移,a>>>b a向右移动b位，高位用0补，低位舍弃
// |:或运算 有1必为1。 |= ---> a=a|b
// 假设入参为6 6-1=5 转换成2进制即为 0101
// 0101 >>> 1 ---> 0010
// 0101 | 0010 ---> 0111
// 0111 >>> 2 ---> 000111
// 0111 | 000111 ---> 000111
// 同理...
// 最后 n+1 = 0111 + 1 = 1000 (8)
static final int tableSizeFor(int cap) {
// 这里-1就是为了防止 cap 本来就是2次幂。
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;
}
// ***** 扩容 *****
final Node<K,V>[] resize() {
// 底层数组
Node<K,V>[] oldTab = table;
// 底层数组的长度（不是元素数量）
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 扩容因子 threshold = capacity*loadFactor
int oldThr = threshold;
int newCap, newThr = 0;
// 如果长度不为0 也就是说 不是首次加载 hashmap在put时添加数据（懒加载）
if (oldCap > 0) {
// 如果数组长度大于等于最大容量
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 如果 原长度*2 < 最大容量 且 原长度 >= 16 那么就扩容两倍且把扩容因子*2 注意点1
// newCap = oldCap * 2 新长度为旧长度的2倍 ***********
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
// DEFAULT_INITIAL_CAPACITY = 1<<4 = 16
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 扩容因子 * 2
newThr = oldThr << 1;
}
// 如果oldCap<=0，且oldThr>0 说明已经初始化了，例如把元素删除完之后的情况，那么它的临界值肯定还存在;如果是首次初始化，它的临界值则为0
// 如果不是首次初始化
else if (oldThr > 0)
// 这种情况下，数组容量=old扩容阈值
newCap = oldThr;
else { // 如果是首次初始化
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 这里是对 注意点1 的完善，如果注意点1的条件不满足 那么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"})
// 初始化
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) {
// 设为null 方便GC回收。
oldTab[j] = null;
if (e.next == null)
// 下标计算 e.hash & (newCap - 1)
// 如果下一个节点为null，重新计算新的节点位置 并把节点放入新的位置
// newCap为2次幂 所以-1 低位全是1 所以位置信息由e.hash决定。
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode) //红黑树操作
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 链表 resize最重要的操作之一就是对链表的拆分；
// 可以去看看其他博主写的文章：https://blog.csdn.net/weixin_41565013/article/details/93190786
// 链表1
Node<K,V> loHead = null, loTail = null;
// 链表2
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 这里注意：新的位置 = 【原位置】 或 【原位置 + 原数组长度】
do {
next = e.next;
// oldCap 为 2次幂 低位全为0 高位为1
// 所以 (e.hash & oldCap) 只能等于 1 或 0，这里把0,1分成了两个链表
// 如果 等于 0
if ((e.hash & oldCap) == 0) {
// 如果尾节点为null
if (loTail == null)
loHead = e;
else
// 链表尾添加
loTail.next = e;
loTail = e;
}
else { // (e.hash & oldCap) = 1
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
// 把链表头指向数组[j]
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
// 把链表头指向 newTab[原下标+原数组长度]
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
put
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// onlyIfAbsent：如果当前位置已存在一个值，是否替换，false是替换，true是不替换
// evict：表是否在创建模式，如果为false，则表是在创建模式。
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(),详情见上resize()解析
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) // n-1 必为低位全为1
// 如果这个下标下没有数据，那么就赋值。
tab[i] = newNode(hash, key, value, null);
else {
// 如果该下标 已有节点
Node<K,V> e; K k;
// 这里分三种情况
// 1. 如果hash 且 key相等，则直接替换旧值
// 2. 如果是红黑树，则调用红黑树的put方法
// 3. 如果是链表，使用尾插法。接着判断是否达到转树的条件，如果达到条件，那么就转成红黑树
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
// 如果hash 相等 key也相等 那么就是同一个对象。
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);
//static final int TREEIFY_THRESHOLD =8; 当链表长度大于8则会转成红黑树
if (binCount >= TREEIFY_THRESHOLD - 1)//-1 for 1st:-1是为了第一次循环
// 转成红黑树结构
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;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
// 转成树
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 如果数组长度<64 就去扩容；如果长度大于>=64；转成红黑树
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {// 如果数组该下标下有元素
// 定义首、尾节点
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);
// 把原来的单向链表换成双向链表
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
// 初始化
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
// 如果根节点为null
if (root == null) {
x.parent = null; // 父节点为null
x.red = false; // 置为黑色
root = x; // 则把x（当前节点）设为根节点
} else { // 如果已存在根节点
K k = x.key; // 当前节点的key
int h = x.hash; // 当前节点的hash
Class<?> kc = null; // key的class
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
// 如果p(根节点)的hash值 > 当前节点的hash值
if ((ph = p.hash) > h)
// 放到左侧的标记
dir = -1;
else if (ph < h)
// 否则放到右侧
dir = 1;
// 如果hash值还是相等，那么就需要其他方法进行比较
// 如果当前链表节点的key实现了comparable接口，并且当前树节点和链表节点是相同Class的实例，那么通过comparable的方式再比较两者
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
/*
* 如果dir小于等于0 ：当前链表节点一定放置在当前树节点的左侧，但不一定是该树节点的左孩子，也可能是左孩子的右孩子 或者 更深层次的节点。
* 如果dir大于0 ：当前链表节点一定放置在当前树节点的右侧，但不一定是该树节点的右孩子，也可能是右孩子的左孩子 或者 更深层次的节点。
* 如果当前树节点不是叶子节点，那么最终会以当前树节点的左孩子或者右孩子 为 起始节点 再进行下一个循环 重新寻找自己（当前链表节点）的位置
* 如果当前树节点就是叶子节点，那么根据dir的值，就可以把当前链表节点挂载到当前树节点的左或者右侧了。
* 挂载之后,还需要重新把树进行平衡。平衡之后,就可以针对下一个链表节点进行处理了。
*/
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
get
public V get(Object key) {
Node<K,V> e;
// 核心是getNode方法
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
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 // table不为null
&& (n = tab.length) > 0 // 长度>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;
// 如果第一个节点的next节点不为null
if ((e = first.next) != null) {
// 如果是红黑树结构
if (first instanceof TreeNode)
// 使用树的方法
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// while 循环，如果key已经相等，就说明找到了；就返回。
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
final TreeNode<K,V> getTreeNode(int h, Object k) {
// 获取根节点调用 find() 方法
return ((parent != null) ? root() : this).find(h, k, null);
}
// 获取红黑树的根节点
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
// 如果没有父节点，那么当前节点就是根节点。
if ((p = r.parent) == null)
return r;
r = p;
}
}
// 红黑树的查询算法
// kc:k的Class对象，该Class应该是实现了Comparable<K>的，否则应该是null
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
// pl:左子树节点；pr:右子树节点
TreeNode<K,V> pl = p.left, pr = p.right, q;
// 比较根节点的hash跟 需要查询的节点的hash值
// 如果根节点的hash比需查询节点的hash值大，那么就往左子树查询。
if ((ph = p.hash) > h)
p = pl;
else if (ph < h)
p = pr;
else if ((pk = p.key) == k || (k != null && k.equals(pk))) // 如果hash相等且key相等，直接放回当前节点即可。
return p;
else if (pl == null) // 如果左子树为null，那么转到右子树
p = pr;
else if (pr == null) // 如果右子树为null,那么转到左子树
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr; //dir小于0，p指向右孩子，否则指向右孩子。紧接着就是下一轮循环了
// 执行到这里说明无法通过comparable比较 或者 比较之后还是相等
// 从右孩子节点递归循环查找，如果找到了匹配的则返回
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}
remove
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
/**
* Implements Map.remove and related methods.
*
* @param hash: hash for key (key的hash)
* @param key: the key
* @param value: the value to match if matchValue, else ignored 如果是matchValue，则匹配值，否则忽略
* @param matchValue: if true only remove if value is equal 如果为true，只在value相等时移除
* @param movable: if false do not move other nodes while removing 如果为false，则在移除时不要移动其他节点
* @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;
// 如果数组不为null 长度大于0 且根据key得到的数组下标中有值。
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相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) { // 如果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)))) {
// 如果key一致，则跳出循环，并拿到node节点。
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) // 如果链表头==需要删除的节点
// 那么直接让node节点的next节点指向数组当前位置
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
总结
HashMap中最重要的几点：
- 底层结构 数组+链表+红黑树
- 几个关键的数字：16(默认容量) 0.75f(默认扩容因子) 12(16*0.75 默认扩容阈值) 6(当链表长度小于6时，转成链表) 8(当链表长度大于8时，转成红黑树) 64(当底层数组容量大于64时，转成红黑树)
- 扩容方法resize()
- 扩容阈值计算方法
- put方法
- remove方法
- 对于红黑树的理解(加分)
![Java小案例——随机数猜测随机数猜测[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)