HashMap源码解析
HashMap作为java中最常用的集合类之一，虽然在平时工作中经常要使用它，但是对于它的实现原理一直只是停留在从网上各处搜集的"哈希表+链表+红黑树"的概念中，对于它具体的实现原理只是半知半解。因此死磕了下它的源码，现对主要源码进行注释并加了个人的一些理解分享出来，共勉之。（源码基于jdk1.8）
HashMap简介
HashMap是一个可以保存key-value键值对的集合类，它的内部存储结构是一个哈希表(数组)，每个节点存放的是一个元素，这个元素可能是唯一元素，也可能只是一个链表的头节点，或者红黑树的根节点，详见下图：
红黑树简介
红黑树是一个大致平衡的二叉排序树，它有5个性质：
-
每个结点非黑即红
-
根结点是黑的
-
每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的
-
如果一个结点是红的，那么它的两个儿子都是黑的
-
对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点
正是这5条性质保证了红黑树的一个特点：从根节点到叶节点最长路径不会超过最短路径的两倍，实现基本平衡。因篇幅有限，更多与红黑树相关内容就不赘述了。
API介绍文档解读
阅读源码前，根据网上大神的意见，先花时间啃了下hashmap的整体英文介绍，发现之后再阅读源码确实有很大的帮助，简单翻译了下类的介绍：
(1).hashmap与hashtable大致相同，除了它是非线程安全的，并且键值对允许为空外；
(2).hashmap不保证元素的有序性，也不保证元素的顺序随着时间的推移不发生变化；
(3).如果迭代性能很重要，则不要将初始容量设置得太高（或负载因子太低）；
(4).负载因子是作为哈希表扩容的一个参考依据，当已使用的容量占总容量达到负载因子时，开始拓展哈希表容量，大约拓展两倍；默认负载因子为0.75。
(5).创建时，在设置初始容量时，应考虑下预期容量和负载因子，以便最小化重新散列操作的次数；
(6).如果初始容量大于最大容量除以负载因子，则不会进行重新加载操作；
(7).如果hashmap要存储大量数据时，初始化足量大的容量来存储比自动拓展效率更快；
(8).使用具有相同hashcode的键值，容易降低hashmap的性能；为了降低这个的影响，如果key实现了Comparable，可以使用键之间的比较顺序来帮助打破关系；
(9).hashmap是非同步的，如果多个线程同时访问数据，并且至少有一个线程在结构上修改了，则必须在外部进行同步（结构修改是添加和删除操作，仅修改已存在键的值不少结构修改）；
(10).实现同步的一种方法可以使用同步容器：Map m = Collections.synchronizedMap(new HashMap(...));
(11).如果在创建迭代器之后对hashmap进行结构修改，除了迭代器自己的remove方法外，迭代器都将抛出ConcurrentModifycationException；这样做的原因是在并发修改的情况下，让迭代器快速而干净地失败，而不是在未来不确定的时间冒不确定的风险。
源码解析
全部属性
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
//序列号
private static final long serialVersionUID = 362498820763181265L;
// 默认的初始容量，即16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量，即2的31次方
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;
// 负载因子
final float loadFactor;
}
复制代码
构造方法
// 初始容量+负载因子
public HashMap(int initialCapacity, float loadFactor) {
// 初始容量不能小于0，否则报错
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
// 初始容量大于最大值时，置为最大值
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 填充因子不能小于或等于0，且不能为非数字
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
// 初始化填充因子
this.loadFactor = loadFactor;
// 初始化threshold大小，实现如下
this.threshold = tableSizeFor(initialCapacity);
}
// 返回大于initialCapacity的最小的二次幂数值。比如输入容量为30，则返回32作为真实容量
static final int tableSizeFor(int cap) {
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;
}
// 初始容量+默认负载因子
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 无参构造，使用默认负载因子
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// 使用相同实现的Map构造hashmap
public HashMap(Map<? extends K, ? extends V> m) {
// 默认负载因子
this.loadFactor = DEFAULT_LOAD_FACTOR;
// 将制定的Map元素插入到新的hashmap中
putMapEntries(m, false);
}
复制代码
扩容方法-resize()
说明
- 将容量扩容2倍，同时将阀值threshold扩容两倍
- 扩容后，需要将原哈希表中的数据复制到新哈希表中，复制时，根据元素类型使用不同的赋值方式
- 因为扩容后，key的hash值跟哈希表长度按位与时得出的位置可能会发生改变，所以需要调整发生改变的元素的位置
- 红黑树复制元素时，需要考虑元素被调整到高位后，高位的元素是否达到构建红黑树的个数而进行红黑树转链表操作，或者原红黑树因为元素被拆分在高位和地位后而需要重新平衡操作。低位操作也类似
源码
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;
}
//扩容两倍后新容量小于最大容量且老容量大于默认基本容量(也就是16)
//这里开始有点疑惑：为啥不校验容量扩为2倍后的大小，不怕扩容后超过最大容量吗。后来想到，hashmap的容量本来就是2的n次幂的，前面校验了扩容前的容量是小于最大容量的，所以这次扩容最多出现等于最大容量的情况。
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold 阈值也扩大两倍
}
else if (oldThr > 0) // initial capacity was placed in threshold 如果哈希表为空，但是阈值大于0，则置哈希表容量为阈值
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;
@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
//lohead指low低位的头结点，loTail表示低位的尾结点
Node<K,V> loHead = null, loTail = null;
//hohead指low低位的头结点，hoTail表示低位的尾结点
Node<K,V> hiHead = null, hiTail = null;
//用来表示下一个结点
Node<K,V> next;
do {
next = e.next;
/*
举个栗子：
odlCap为16，则减1后为： 000000 1111
key1的hash值为： 110000 1010
key2的hash值为： 110001 1010
容量拓展之后，newCap减1后为：000001 1111
所以key2的hash值与容量计算出来的位置改变了，因此需要调整key2的数据到高位部分去
*/
//元素的hash值与旧容量按位与，如果结果等于0则表示继续保持当前位置，不需要调整位置
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;
//使用j+oldCap将元素移动到高位
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
//扩容时对红黑树的调整，可能会出现红黑树转链表，或者链表转红黑树的情况
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
//获取当前元素
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
从根节点开始遍历红黑树，统计出需要放到低位和需要移动到高位的元素个数，以便下面能通过个数重新平衡红黑树或者转换为链表
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
//元素需要放到哈希表低位的处理
if (loHead != null) {
//如果元素个数小于等于红黑树转链表的阀值时，进行转链表操作
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {//不需要转换链表
//将根节点放入哈希表首元素
tab[index] = loHead;
//判断是否有需要移动到高位的，如果有则需要重新平衡红黑树，没有的话则说明红黑树元素个数不变，位置也不需要调整了
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
//元素需要放到哈希表高位的处理，操作跟上述差不多，只不过是在哈希表高位进行操作
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
复制代码
红黑树与链表之间转换--treeify()和untreeify()
/*
1.将链表中的元素逐个添加到创建的红黑树中;
2.创建红黑树时，元素的排序优先级为:key的hash值 > 实现Comparable接口的compareTo() > 强制比较对象生成的hash值方法-tieBreakOrder();
3.每添加一个元素时，通过balanceInsertion()方法保证红黑树的平衡;
*/
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;
//初始化根节点，将链表首个元素作为根节点，置为黑色
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {//非根节点操作
K k = x.key;
int h = x.hash;
Class<?> kc = null;
//从根节点开始遍历红黑树，找到插入位置
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
//首先根据hash值排序
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
//当出现hash冲突，key没有实现Comparable接口，或者实现了Comparable接口但是还无法区分顺序时，使用终极PK方法tieBreakOrder决出顺序
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
//备份当前节点的父节点
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);
}
/*将红黑树转换为链表
因为红黑树的TreeNode节点包含了链表属性，所以直接通过链表的方式遍历红黑树的节点，并整合到新的链表上
*/
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
//循环遍历将红黑树中的每个元素取出来并串联成一个单向链表，返回头节点
for (Node<K,V> q = this; q != null; q = q.next) {
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
复制代码
红黑树保证平衡方法--balanceInsertion()
-
红黑树保持平衡的方法其实就是CLR中算法的实现;
-
主要使用的是变色和旋转(左旋转和右旋转)来保证红黑树的平衡
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
//默认新节点是红色
x.red = true;
//循环处理所有节点，它们符合红黑树平衡规则，一下父节点等都是基于遍历到的当前节点而言
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
//如果没有父节点，说明当前节点是根节点
if ((xp = x.parent) == null) {
//因为是根节点，所以变色为黑色
x.red = false;
return x;
}
//如果父节点是黑色或者祖父节点为空(说明父节点是根节点，直接返回根节点)
else if (!xp.red || (xpp = xp.parent) == null)
return root;
//父节点是祖父节点的左节点
if (xp == (xppl = xpp.left)) {
//祖父节点的右节点(即叔节点)不为空，且为红色，则进行变色处理，将父节点和叔节点的右节点置为黑色(因为当前节点为红色)，祖父节点置为红色
if ((xppr = xpp.right) != null && xppr.red) {
//叔节点置为黑色
xppr.red = false;
//父节点置为黑色
xp.red = false;
//祖父节点置为红色
xpp.red = true;
//进行下一轮循环比较x父父节点
x = xpp;
}
else { //叔节点为空 或者 叔节点为黑色
//当前节点是右节点，则需多做一次左旋转
if (x == xp.right) {
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateRight(root, xpp);
}
}
}
}
else { //父节点是祖父节点的右节点
//叔节点不为空且为红色
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
//如果当前节点是左孩子，则需做一次右旋转
if (x == xp.left) {
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}
复制代码
新增元素--put()
操作流程：
- 根据key的hash值与哈希表的长度减1后的值进行按位与操作得出元素将插入哈希表的位置
- 如果已存在相同key时，则直接覆盖值value
- 根据元素的类型执行不同的值插入操作，比如红黑树插入还要保证平衡，链表则要遍历是否已存在相同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;
//哈希表为空或者表长度为0，则拓展哈希表
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/*
使用key的hash值与哈希表长度按位与计算出元素位置，判断当前位置上是否有值，若没有则直接将元素放入,否则进一步判断
*/
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//若key已存在，则更新value值
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);
//如果链表上元素个数达到了转换数的阈值(默认6)时，将链表转换为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//执行链表转红黑树操作
treeifyBin(tab, hash);
break;
}
//如果键值已存在则直接返回(因为之前e= p.next()时已经取到了旧值)
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//与前面的e= p.next()组成循环遍历
p = e;
}
}
//e!=null表示存在key相同的元素
if (e != null) { // existing mapping for key
V oldValue = e.value;
//存在相同key时，判断是否需要覆盖值value
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//回调函数，hashmap中没有实现，提供给linkedHashMap使用的
afterNodeAccess(e);
return oldValue;
}
}
//结构修改次数增加，迭代时检查发现此值变了则抛出ConcurrentModificationException异常
++modCount;
//哈希表键值对数量增加，若超过阈值时则进行扩容
if (++size > threshold)
resize();
//回调函数，hashmap中没有实现，提供给linkedHashMap使用的
afterNodeInsertion(evict);
return null;
}
/**
* Tree version of putVal.红黑树的插入方法
*/
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
//获取根节点
TreeNode<K,V> root = (parent != null) ? root() : this;
//从根节点开始遍历
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
/*
因为hashmap中的红黑树是根据key的hash值来排序的，所以先判断新插入的key的hash值与当前父节点hash值
*/
//hash值小于父节点哈希值，取左节点
if ((ph = p.hash) > h)
dir = -1;
//hash值大于父节点哈希值，取右节点
else if (ph < h)
dir = 1;
//执行到此说明hash值相等，继续比较键值是否相等，若相等则说明已存在相同键值，故直接返回当前节点的位置
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
//hash相等，但是key不相等
else if ((kc == null &&
//key未实现了Comparable接口
(kc = comparableClassFor(k)) == null) ||
//或者key实现了Comparable接口但是比较结果返回为0，说明还是无法判断出key的顺序，此时产生了hash碰撞
(dir = compareComparables(kc, k, pk)) == 0) {
//判断是否已经执行过查找，貌似一个红黑树只能查找一次
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
//分别查找左右树，查找相同的对象，如果找不到，说明确实没有相同对象存在
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
//hash相等，key不相等，并且key没有实现Comparable接口，保持一致的处理规则，也就是想办法统一的排序规则，以便继续往下遍历
dir = tieBreakOrder(k, pk);
}
//备份当前节点
TreeNode<K,V> xp = p;
//若遍历完红黑树，还是没有找到相同key的结点，则进行新插入操作
if ((p = (dir <= 0) ? p.left : p.right) == null) {
/*
备份当前节点的下一个节点：相当于在链表的两个节点a,b之间插入c时，先备份a.next，然后将a.next指向c，最后再将b.prev指向c
这些操作是给LinkedHashMap预留的
*/
Node<K,V> xpn = xp.next;
//创建新节点
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
//根据之前比较hash值结果，将新节点放到的当前节点的左子节点或者右子节点
if (dir <= 0)
xp.left = x;
else
xp.right = x;
//将当前节点的next指向新节点
xp.next = x;
//设置新节点的父节点和前驱节点为当前节点
x.parent = x.prev = xp;
//如果当前结点还有后继节点时，将新节点作为它的前驱
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
//重排红黑树使其保证平衡(调用balanceInsertion方法实现，实现代码改编自CLR-公共语言运行库，使用变色和左右旋转的原理)，并将root节点放到哈希表的首元素
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
//将链表转红黑树
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//如果哈希表为空或哈希表长度小于最小允许转为红黑树的长度时，先进行扩容处理(因为一般由于hash表长度太小时，更容易出现hash冲突，此时通过扩容解决更方便，性能也更高)
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
//取出当前hash值对应的哈希表位置
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);
}
}
复制代码
删除元素-remove()
- 删除操作主要是要先获取到该元素的节点位置，获取方法根据不同的类型使用不同的方式：链表循环遍历，红黑树使用递归遍历
- 只有一个节点时，直接删除即可,链表则遍历后找到元素并删除
- 红黑树上的节点删除后需要根据情况调整平衡,调整的方式与插入类似
public V remove(Object key) {
Node<K,V> e;
//如果找到元素则返回元素的值value，否则返回null
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;
//哈希表不为空+根据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与所删除的key相等时，直接找到该元素
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)
tab[index] = node.next;
//执行链表中的删除，移动指针即可
else
p.next = node.next;
//结构化调整次数加1，键值对总个数减1
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
//红黑树删除元素执行方法
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
int n;
//哈希表为空时直接返回
if (tab == null || (n = tab.length) == 0)
return;
int index = (n - 1) & hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
//前驱节点为空时，说明要删除元素是哈希表首元素，此时将首元素指定下一个元素(实现删除)
if (pred == null)
tab[index] = first = succ;
//前驱节点不为空，将删除节点的前驱指向后继(实现删除)
else
pred.next = succ;
//后继不为空，则将删除节点的后继的前驱指向删除节点的前驱(其实就是a<->b<->c,要删除b,变成a<->c)
if (succ != null)
succ.prev = pred;
//该位置没有元素时直接返回
if (first == null)
return;
//删除节点不为根节点时找到根节点
if (root.parent != null)
root = root.root();
//根节点为空 或 根节点右节点为空 或 根节点左节点为空 或根节点左节点的左节点为空时,将红黑树变为链表并返回(说明删除元素后元素太少)
if (root == null || root.right == null ||
(rl = root.left) == null || rl.left == null) {
tab[index] = first.untreeify(map); // too small
return;
}
//初始化，p是删除节点，pl是左节点，pr是右节点，replacement是要移动的子节点
TreeNode<K,V> p = this, pl = left, pr = right, replacement;
//删除节点有左右两个节点
if (pl != null && pr != null) {
TreeNode<K,V> s = pr, sl;
//找到删除节点的右节点的左节点
while ((sl = s.left) != null) // find successor
s = sl;
//交换删除节点和右节点的左节点的颜色
boolean c = s.red; s.red = p.red; p.red = c; // swap colors
TreeNode<K,V> sr = s.right;
TreeNode<K,V> pp = p.parent;
if (s == pr) { // p was s's direct parent
p.parent = s;
s.right = p;
}
else {
TreeNode<K,V> sp = s.parent;
if ((p.parent = sp) != null) {
if (s == sp.left)
sp.left = p;
else
sp.right = p;
}
if ((s.right = pr) != null)
pr.parent = s;
}
p.left = null;
if ((p.right = sr) != null)
sr.parent = p;
if ((s.left = pl) != null)
pl.parent = s;
if ((s.parent = pp) == null)
root = s;
else if (p == pp.left)
pp.left = s;
else
pp.right = s;
if (sr != null)
replacement = sr;
else
replacement = p;
}
//删除节点只有左节点
else if (pl != null)
replacement = pl;
//删除节点只有右节点
else if (pr != null)
replacement = pr;
//删除节点是叶节点
else
replacement = p;
//删除节点非叶节点时，将它的子节点连接上它的父节点
if (replacement != p) {
TreeNode<K,V> pp = replacement.parent = p.parent;
if (pp == null)
root = replacement;
else if (p == pp.left)
pp.left = replacement;
else
pp.right = replacement;
p.left = p.right = p.parent = null;
}
//删除节点后进行红黑树平衡处理，原理差不多，使用变色和旋转
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
//删除节点是叶子节点，则解除该节点的所有树相关关联
if (replacement == p) { // detach
TreeNode<K,V> pp = p.parent;
p.parent = null;
if (pp != null) {
if (p == pp.left)
pp.left = null;
else if (p == pp.right)
pp.right = null;
}
}
//根据标识决定是否将根节点转移到哈希表首元素
if (movable)
moveRootToFront(tab, r);
}
复制代码
查找元素--get()
思路基本差不多：
- 先根据hash值与哈希表容量按位与得到位置
- 根据节点类型使用不同的遍历方式:链表用循环遍历，红黑树用递归遍历
public V get(Object key) {
Node<K,V> e;
//找到返回元素值，找不到返回null
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 && (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)
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;
}
//红黑树查找节点方法
final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}
/*递归查找红黑树，获取指定节点
1.根据hash值顺序进行遍历;
2.若hash值存在相等时，则根据key实现的Comparable接口来获取顺序继续遍历;
3.如果以上都没有得出遍历顺序则统一递归调用find从右节点继续遍历;
*/
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
//hash值小于当前遍历的节点hash值，下一次比较它们的左子树
if ((ph = p.hash) > h)
p = pl;
//hash值大于当前遍历的节点hash值，下一次比较它们的右子树
else if (ph < h)
p = pr;
//hash值相等且key相等时直接返回节点
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
//左节点为空则遍历右节点
else if (pl == null)
p = pr;
//右节点为空则遍历左节点
else if (pr == null)
p = pl;
//key的类实现了Comparable接口则比较根据compareTo方法比较大小获取顺序
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
//若上述操作都没有得出遍历顺序时，则统一从右结点开始继续递归遍历
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}
复制代码
迭代方法--entrySet()
- entrySet迭代方法相比keySet来说性能相对而言要快点，因为keySet是先获取key，然后再根据key调用前面介绍的get()方法获取值，get方法会有一定的性能开销。而entrySet是直接返回key-value的Set集合
- 迭代其实就是借助于每个hashmap的节点都有next节点的链表结构，相当于就是循环地遍历链表
- 通过迭代的源码也可以看出迭代不保证与插入顺序一致的原因：因为迭代是从哈希表的第一个存储单元开始，逐个遍历每个单元的节点或节点链表或者红黑树，而插入的时候是根据key的hash值从哈希表中任一位置插入的
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
//迭代类可以复用，实际使用的是内部的EntrySet类
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
//内部迭代类
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
//内部实现迭代方法，返回的是内部的迭代类EntryIterator
public final Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator();
}
}
final class EntryIterator extends HashIterator
implements Iterator<Map.Entry<K,V>> {
//主要通过该next方法获取下一个元素
public final Map.Entry<K,V> next() {
return nextNode();
}
}
//实际迭代的内部类
abstract class HashIterator {
Node<K,V> next; // next entry to return 下一个节点
Node<K,V> current; // current entry 当前节点
int expectedModCount; // for fast-fail 预期的结构性修改次数，避免遍历期间进行结构性修改(插入和删除操作)
int index; // current slot 当前位置
HashIterator() {
//备份结构修改次数，作为遍历时的预期
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
//遍历哈希表，定位到第一个有元素的位置
if (t != null && size > 0) { // advance to first entry
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();
//保证下一次取到的元素不为空
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;
}
}
复制代码
其他方法
/*检查对象的class是否实现了Comparable接口
1.主要检查key键的类class是否实现了Comparable接口，而且是要实现的是参数化的接口，比如Comparable<String>;
2.String类是最常见作为key的类，且它有完整的Comparable实现，所以该方法为String类开了绿灯;
*/
static Class<?> comparableClassFor(Object x) {
//对象要求是Comparable的实例
if (x instanceof Comparable) {
Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
//对象为string时，开绿灯直接pass(因为String类最常用作key，且它对Comparable有具体的实现)
if ((c = x.getClass()) == String.class) // bypass checks
return c;
//获取对象的所有实现接口
if ((ts = c.getGenericInterfaces()) != null) {
for (int i = 0; i < ts.length; ++i) {
/*
1.所实现的接口是参数化类型，比如Colloction<String>
2.该接口参数化类型的头部是Comparable，例如Collocation<String>的头部是Collocation
3.该接口的参数化类型只有一个，例如Collocation<String>只有String一个类型;
4.该接口的参数化类型为对象的class本身;例如Integer实现了Comparable<Integer>中的参数就是Integer;
符合以上四个条件表示该对象的类实现了Comparable<对象的class>接口
*/
if (((t = ts[i]) instanceof ParameterizedType) &&
((p = (ParameterizedType)t).getRawType() ==
Comparable.class) &&
(as = p.getActualTypeArguments()) != null &&
as.length == 1 && as[0] == c) // type arg is c
return c;
}
}
}
return null;
}
/*将根节点放到哈希表中的首个元素
主要就是确保根节点是哈希表首个元素，调整时同步调整它们的前驱和后继
*/
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
//保证root和哈希表不为空
if (root != null && tab != null && (n = tab.length) > 0) {
//用root的hash值与哈希表长度做按位与操作得出存储位置
int index = (n - 1) & root.hash;
//获取当前位置的元素
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
//若根节点不是当前hash位置的首元素则进行调整
if (root != first) {
Node<K,V> rn;
//将当前hash位置首元素放root节点
tab[index] = root;
//备份root的前驱节点
TreeNode<K,V> rp = root.prev;
//将root后继节点的前驱指向root的前驱，类似a->b->c，rp是a,root是b.rn是c，调整为a->c
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
//root前驱不为空时，将root前驱指向root后继
if (rp != null)
rp.next = rn;
//当前hash位置上的原元素不为空，则将其作为root的后继
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
assert checkInvariants(root);
}
}
复制代码
总结
本文是作者第一次完整地阅读源码，虽然过程很枯燥，但是坚持下来后发现学习到的东西确实比直接看别人总结出来的结论要深刻，而且更透彻了。本文作为开篇，以后有源码阅读也会记录下来，作为一种学习笔记共勉。
正文到此结束
- 本文标签： root swap API 遍历 总结 文章 equals java 数据 解析 final 1111 HashTable https UI App 参数 ACE HashMap node map CTO list 删除 集合类 递归 tab 安全 CEO value http id 并发 源码 cat 注释 key 统计 Collection zab 翻译 线程 时间 Collections src IO synchronized 备份 find 代码 实例 同步 微信公众号 构造方法
- 版权声明： 本文为互联网转载文章，出处已在文章中说明(部分除外)。如果侵权，请联系本站长删除，谢谢。
- 本文海报： 生成海报一 生成海报二
热门推荐
相关文章
近期评论
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
搞个gitee的项目
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
