Java集合系列源码分析（三）--HashMap
站长
· 阅读数 75
简介
HashMap以key-value的存储形式存在,即主要用来存放键值对。HashMap 的实现不是同步的，这意味着它不是线程安全的。它的 key、value 都可以为 null，key只能存在一个null,而value可以存在多个,此外，HashMap 中的映射不是有序的。jdk1.8以后HashMap底层的数据结构为数组+链表+红黑树,当数组中的数据存在hash冲突的时候则会将数组转换为链表,当链表的长度大于等于8的时候不会直接转换为红黑树,只有在链表的长度大于等于8并且数组的长度大于等于64的时候才会转换为红黑树,如果数组的长度小于64则会对数组进行扩容。
局部变量
//默认初始容量大小(16)
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//数组最大容量大小(1073741824)
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//当链表中的元素数量为8时则将链表转换为红黑树
static final int TREEIFY_THRESHOLD = 8;
//当前红黑树中的元素数量小于等于6时则将红黑树转换为链表
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 最小树化阈值
* 当链表中的节点数量大于等于8时,如果数组的长度小于最小树化阈值则不会将链表转换为红黑树,而是对数组进行扩容
* 将链表中的节点分散到别的索引节点中去,只有当数组的长度大于等于最小树化阈值则会将链表转换为红黑树
*/
static final int MIN_TREEIFY_CAPACITY = 64;
//存放数据的数组
transient Node<K,V>[] table;
/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
transient Set<Map.Entry<K,V>> entrySet;
//数组长度
transient int size;
//数组修改次数
transient int modCount;
//当数组中的key-value的数量大于threshold则会进行扩容
int threshold;
//负载因子
final float loadFactor;
构造函数
- HashMap(int initialCapacity, float loaFactor)：创建一个指定初始容量和指定负载因子大小的HashMap,如果指定的初始容量不是2的次方则会获取最接近并大于指定容量的2的次方数。new HashMap的时候只是初始化阈值和负载因子,并没有真正的初始化数组,只有在添加第一个元素的时候才会初始化数组
- HashMap(int initialCapacity)：创建一个指定容量大小使用默认的负载因子的HashMap
- HashMap()：使用默认的初始容量和默认的负载因子创建HashMap
- HashMap(Map<? extends K, ? extends V> m)：创建一个HashMap并将指定集合中的元素添加到当前集合中
public HashMap(int initialCapacity, float loaFactor) {
if (initialCapacity < 0)
//指定的初始容量大小小于0则抛出异常
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
//指定的初始容量大小大于最大容量大小则使用最大容量创建
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
//指定的负载因子小于等于0或是非数字则抛出异常
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
//设置负载因子
this.loadFactor = loadFactor;
//获取最接近并大于指定容量大小的2的次方
this.threshold = tableSizeFor(initialCapacity);
}
static final int tableSizeFor(int cap) {
//cap-1可以保证当传入的数是2的次方时,可以返回其本身 例: cap等于16时经过运算最终返回的还是16本身
//当传入的数不是2的次方时则会返回大于传入的数并且是2的次方的数 例: cap等于17时经过运算最终返回的结果为32
int n = cap - 1;
//将n的二进制无符号右移1位并将右移的结果与n进行位或运算获取到新的n的值
/**
* 例: n = 16(cap) - 1
* n的二进制为 1111,将n无符号右移一位获取到新的二进制为0111
* 将新的二进制与n的二进制进行位或运算,有1则为1,都为0则为0
* 1111
* 0111
* 1111
*/
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
//经过运算n小于0则返回1
//大于0则判断n是否超出最大容量大小,如果超出最大容量大小则返回最大容量,未超出最大容量大小则返回n+1
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
public HashMap(int initialCapacity) {
//调用HashMap(int initialCapacity, float loaFactor)方法
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
public HashMap(Map<? extends K, ? extends V> m) {
//使用默认的负载因子
this.loadFactor = DEFAULT_LOAD_FACTOR;
//将指定map中的元素添加到当前集合中
putMapEntries(m, false);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
//获取集合的长度
int s = m.size();
if (s > 0) {
if (table == null) {
//当前集合的数组还未初始化时则先对当前集合的阈值进行初始化
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);
}
}
}
- get(Object key)：根据指定的key获取value
public V get(Object key) {
Node<K,V> e;
//先获取key的hash值
//再根据hash值获取到索引位置上的头节点
//如果头节点与指定的key和hash相同则返回该节点的value
//如果不相同则校验头节点是链表还是红黑树
//如果是红黑树则从红黑树的根节点开始匹配
//如果是链表则从链表的头节点开始匹配
//相同则返回该节点的value
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
//获取指定key的hash值
static final int hash(Object key) {
int h;
//key如果为null则返回hash值为0
//key不为null则获取key的hashCode
//将hashCode二进制无符号右移16位获取到新的二进制
//将hashCode二进制与hashCode右移16位的二进制做异或运算获取到新的hash值
//将二进制右移16位的作用主要是让高位与低位做运算减少hash冲突
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//根据key和hash值获取节点
final Node<K,V> getNode(int hash, Object key) {
//存放数据的数组
Node<K,V>[] tab;
//first 头节点
Node<K,V> first, e;
//n 数组长度
//k key
int n; K k;
//校验数组是否不为空并且根据指定key的hash值获取到的索引位置上的头节点不为空
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
//校验头节点的hash值是否跟指定key的hash值相同并且key是否也相同
if (first.hash == hash && ((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 {
//从链表的头节点开始遍历与指定的key和hash值进行匹配
//key和hash值相同则返回该节点
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
- containsKey(Object key)：校验集合中是否包含指定的key
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
- putAll(Map<? extends K, ? extends V> m)：将指定map中的所有元素添加到当前map集合中
public void putAll(Map<? extends K, ? extends V> m) {
putMapEntries(m, true);
}
- remove(Object key)：删除指定key的节点,删除节点前会修改节点关联的指针,如果是红色节点在修改完节点关联的指针则会直接删除,如果是黑色节点则会对节点进行平衡
public V remove(Object key) {
Node<K,V> e;
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;
//校验数组是否不为空并且根据指定key的hash值获取到的索引位置上的节点不为空
if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
//待删除节点
Node<K,V> node = null, e;
//待删除的key
K k;
//待删除的value
V v;
//校验删除的key和hash值是否与索引位置上的节点的key和hash值相同
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)
//红黑树
//从红黑树的根节点开始匹配
//key和hash值相同则返回该节点,将该节点设置为待删除
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);
}
}
//校验待删除的节点是否不为null并且value是否在不相等的情况下删除
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)
//待删除节点为普通节点
//将待删除节点的下一个节点设置为头节点
//待删除节点的下一个节点为null,所有说则是将该节点所在的索引位置置为null
tab[index] = node.next;
else
//待删除节点为链表
//将待删除节点的下一个节点设置为待删除节点的父节点的下一个节点
p.next = node.next;
//更新集合修改次数和集合长度
++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;
//根据hash值获取到该节点在数组中的索引位置
int index = (n - 1) & hash;
//first 头节点
//root 根节点
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
//pred 当前节点的上一个节点
//succ 当前节点的下一个节点
TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
if (pred == null)
//当前节点的上一个节点为null则说明待删除的节点是头节点
//则将当前节点的下一个节点设置为头节点
tab[index] = first = succ;
else
//不为null则将当前节点的上一个节点的next指针指向succ
pred.next = succ;
if (succ != null)
//不为null则将当前节点的下一个节点的prev指针指向pred
succ.prev = pred;
if (first == null)
return;
if (root.parent != null)
//根据hash值获取到的索引位置上的节点不是根节点则根据该节点寻找根节点
root = root.root();
if (root == null || (movable && (root.right == null || (rl = root.left) == null || rl.left == null))) {
//红黑树节点数量太少则将红黑树转换为单向链表
tab[index] = first.untreeify(map);
return;
}
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);
}
删除节点图示：
- clear()：清除集合中所有的元素
public void clear() {
Node<K,V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
//将集合长度置为0
size = 0;
//循环将数组中的节点置为null
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
}
- containsValue(Object value)：.校验集合中是否包含指定的value,遍历集合中的每一个节点进行匹配
public boolean containsValue(Object value) {
Node<K,V>[] tab;
V v;
if ((tab = table) != null && size > 0) {
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value || (value != null && value.equals(v)))
return true;
}
}
}
return false;
}
- getOrDefault(Object key, V defaultValue)：返回指定key的value,如果指定的key对应的节点不存在则返回defaultValue
public V getOrDefault(Object key, V defaultValue) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
}
- putIfAbsent(K key, V value)：将指定的key和value添加到集合中,如果集合中已经存在则不添加并返回已存在的value
public V putIfAbsent(K key, V value) {
return putVal(hash(key), key, value, true, true);
}
- remove(Object key, Object value)：根据key和value删除对应的节点
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}
- replace(K key, V value)：根据指定的key获取到key所在的节点并替换value
public V replace(K key, V value) {
Node<K,V> e;
//根据key和hash值获取key所在的节点并校验节点是否不为null
if ((e = getNode(hash(key), key)) != null) {
//旧值
V oldValue = e.value;
//使用新值替换旧值
e.value = value;
//该方法在hashMap中没有具体的实现
afterNodeAccess(e);
//返回旧值
return oldValue;
}
return null;
}
//获取指定key的hash值
static final int hash(Object key) {
int h;
//key如果为null则返回hash值为0
//key不为null则获取key的hashCode
//将hashCode二进制无符号右移16位获取到新的二进制
//将hashCode二进制与hashCode右移16位的二进制做异或运算获取到新的hash值
//将二进制右移16位的作用主要是让高位与低位做运算减少hash冲突
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//根据key和hash值获取节点
final Node<K,V> getNode(int hash, Object key) {
//存放数据的数组
Node<K,V>[] tab;
//first 头节点
Node<K,V> first, e;
//n 数组长度
//k key
int n; K k;
//校验数组是否不为空并且根据指定key的hash值获取到的索引位置上的头节点不为空
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
//校验头节点的hash值是否跟指定key的hash值相同并且key是否也相同
if (first.hash == hash && ((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 {
//从链表的头节点开始遍历与指定的key和hash值进行匹配
//key和hash值相同则返回该节点
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
- replace(K key, V oldValue, V newValue)：根据key和value获取节点并将节点中的value替换
public boolean replace(K key, V oldValue, V newValue) {
Node<K,V> e;
V v;
//根据key和hash值获取key所在的节点并校验节点是否不为null并且校验指定的oldValue是否与节点中的value相同
if ((e = getNode(hash(key), key)) != null &&
((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
//oldValue与节点中的value相同
//使用newValue替换节点中的value
e.value = newValue;
afterNodeAccess(e);
return true;
}
return false;
}
- replaceAll(BiFunction<? super K, ? super V, ? extends V> function)：对集合中所有的value进行指定的操作
public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
Node<K,V>[] tab;
//校验函数是否为null
//如果函数为null则抛出异常
if (function == null)
throw new NullPointerException();
//校验集合是否不为null
if (size > 0 && (tab = table) != null) {
//预期的修改次数
int mc = modCount;
//遍历每一个节点并对节点中value执行操作
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
e.value = function.apply(e.key, e.value);
}
}
//如果当前集合的修改次数与预期的修改次数不相同则抛出并发修改异常
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
//示例
public static void main(String[] args) {
HashMap<String, String> hashMap = new HashMap<>(3,1);
hashMap.put("1","1");
hashMap.put("2","2");
hashMap.put("3","c");
//对集合中值为1的替换为4
hashMap.replaceAll((key,value)->
value.replace("1","4")
);
//将集合中的值转换为大写
hashMap.replaceAll((key,value)->
value.toUpperCase()
);
}
- merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction)：对指定的key所在的节点的value与指定的value进行指定操作,如果指定的key的节点存在则按照指定的操作获取到新的value,使用新的value将旧的value替换掉,如果指定的key的节点不存在则将指定的key和value添加到集合中
public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
if (value == null)
throw new NullPointerException();
if (remappingFunction == null)
throw new NullPointerException();
//获取key的hash值
int hash = hash(key);
Node<K,V>[] tab;
//头节点
Node<K,V> first;
//n 数组长度
//i 索引
int n, i;
//链表的节点数量
int binCount = 0;
//树节点中的根节点
TreeNode<K,V> t = null;
Node<K,V> old = null;
if (size > threshold || (tab = table) == null || (n = tab.length) == 0)
//数组长度到达了阈值或数组为空则对数组进行初始化或扩容
n = (tab = resize()).length;
//根据key的hash值获取到key所在的索引位置上的头节点
if ((first = tab[i = (n - 1) & hash]) != null) {
if (first instanceof TreeNode)
//索引位置上的节点为红黑树节点
//根据hash值和key从红黑树根节点开始匹配获取到匹配的节点
old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
else {
//索引位置上的节点是链表节点或者是单独的一个节点
Node<K,V> e = first;
K k;
do {
//从头节点开始遍历进行匹配
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
old = e;
break;
}
++binCount;
} while ((e = e.next) != null);
}
}
if (old != null) {
//节点已存在
V v;
if (old.value != null)
//key所在的节点中的value不为null则根据传递的方法执行操作
v = remappingFunction.apply(old.value, value);
else
v = value;
if (v != null) {
//将节点中的旧值替换为新值
old.value = v;
afterNodeAccess(old);
}
else
//新值为null则将该节点删除
removeNode(hash, key, null, false, true);
return v;
}
//节点不存在则将节点添加到集合中
if (value != null) {
if (t != null)
//根节点不为null则将key和value封装成树节点添加到红黑树中
t.putTreeVal(this, tab, hash, key, value);
else {
//根节点不存在则将key和value封装成一个普通的节点并添加到数组中指定的索引位置上
tab[i] = newNode(hash, key, value, first);
//校验指定的索引位置上的链表节点数量是否大于等于链表转换为红黑树的阈值
//从代码来看该if判断中的代码是不会执行的
if (binCount >= TREEIFY_THRESHOLD - 1)
//将链表转换为红黑树
treeifyBin(tab, hash);
}
++modCount;
++size;
afterNodeInsertion(true);
}
return value;
}
//示例
public static void main(String[] args) {
HashMap<String, String> hashMap = new HashMap<>();
hashMap.put("1","1");
hashMap.put("2","2");
//将key为1的value与指定的value 3进行拼接
hashMap.merge("1", "3", (oldValue, newValue) -> oldValue + newValue);
//将key为1的函数方法直接设置为了null则会删除该节点
hashMap.merge("1", "3", (oldValue, newValue) -> null);
}
- computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)：.对指定的key所在的节点中的value执行指定的操作获取到新的value并将新的value替换旧的value
public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
if (remappingFunction == null)
throw new NullPointerException();
//节点
Node<K,V> e;
//节点中的value
V oldValue;
//根据key获取hash值
int hash = hash(key);
//根据key和hash值获取到key所在的节点并校验节点是否不为null并且节点的value不为null
if ((e = getNode(hash, key)) != null && (oldValue = e.value) != null) {
//对节点中的key和value执行指定的操作获取到新的value
V v = remappingFunction.apply(key, oldValue);
if (v != null) {
//新的value不为null则替换节点中的旧value
e.value = v;
afterNodeAccess(e);
return v;
}
else
//新的value为null则删除该节点
removeNode(hash, key, null, false, true);
}
return null;
}
//示例
public static void main(String[] args) {
HashMap<String, String> hashMap = new HashMap<>();
hashMap.put("1","1");
hashMap.put("2","2");
//将key与value进行拼接获取到新的value
hashMap.computeIfPresent("1", (key, value) -> key + value);
//将key为1的函数方法直接设置为了null则会删除该节点
hashMap.computeIfPresent("1", (key, value) -> null);
}
- compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)：对指定的key所在的节点中的value执行指定的操作获取到新的value并将新的value替换旧的value,如果指定的key的节点不存在并且根据指定操作获取到的新的value不为null则将key和value封装成节点添加到数组中
public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
if (remappingFunction == null)
throw new NullPointerException();
//根据key获取hash值
int hash = hash(key);
//数组
Node<K,V>[] tab;
//头节点
Node<K,V> first;
//n 数组长度
int n, i;
//链表节点数量
int binCount = 0;
//红黑树根节点
TreeNode<K,V> t = null;
//指定的key所在的节点
Node<K,V> old = null;
if (size > threshold || (tab = table) == null || (n = tab.length) == 0)
//数组长度到达了阈值或数组为空则对数组进行初始化或扩容
n = (tab = resize()).length;
//根据key的hash值获取索引位置上的节点并校验节点是否不为null
if ((first = tab[i = (n - 1) & hash]) != null) {
if (first instanceof TreeNode)
//节点为红黑树
//从红黑树根节点开始匹配
old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
else {
//节点为链表或单节点
Node<K,V> e = first; K k;
do {
//从头节点开始匹配
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
old = e;
break;
}
++binCount;
} while ((e = e.next) != null);
}
}
//获取节点中的value
V oldValue = (old == null) ? null : old.value;
//根据指定的操作获取到新的value
V v = remappingFunction.apply(key, oldValue);
if (old != null) {
if (v != null) {
//将获取到的新value替换旧value
old.value = v;
afterNodeAccess(old);
}
else
//新value为null则删除该节点
removeNode(hash, key, null, false, true);
}else if (v != null) {
if (t != null)
//新value不为null并且红黑树的根节点不为null则将指定的key和新的value封装成树节点添加到红黑树中
t.putTreeVal(this, tab, hash, key, v);
else {
//将key和value封装成普通节点添加到指定的索引位置上
tab[i] = newNode(hash, key, v, first);
if (binCount >= TREEIFY_THRESHOLD - 1)
//如果链表中的节点数量大于等于链表转换为红黑树的阈值则将链表转换为红黑树
treeifyBin(tab, hash);
}
++modCount;
++size;
afterNodeInsertion(true);
}
return v;
}
- computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)：对指定的key所在的节点中的value执行指定的操作获取到新的value,如果节点中的value不为null则不进行任何操作,反之则将新的value值替换掉null值,如果指定的key不存在,则将指定的key和value封装成节点添加到数组中
public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
if (mappingFunction == null)
throw new NullPointerException();
//根据key获取hash值
int hash = hash(key);
Node<K,V>[] tab;
//头节点
Node<K,V> first;
int n, i;
int binCount = 0;
TreeNode<K,V> t = null;
Node<K,V> old = null;
if (size > threshold || (tab = table) == null || (n = tab.length) == 0)
//数组长度到达了阈值或数组为空则对数组进行初始化或扩容
n = (tab = resize()).length;
//根据key的hash值获取索引位置上的节点并校验节点是否不为null
if ((first = tab[i = (n - 1) & hash]) != null) {
if (first instanceof TreeNode)
//节点为红黑树
//从红黑树根节点开始匹配
old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
else {
//节点为链表或单节点
Node<K,V> e = first;
K k;
do {
//从头节点开始匹配
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
old = e;
break;
}
++binCount;
} while ((e = e.next) != null);
}
V oldValue;
//节点value已存在则直接返回
if (old != null && (oldValue = old.value) != null) {
afterNodeAccess(old);
return oldValue;
}
}
//根据指定的操作获取到新的value
V v = mappingFunction.apply(key);
if (v == null) {
return null;
} else if (old != null) {
//将获取到的新value替换旧value
old.value = v;
afterNodeAccess(old);
return v;
}
else if (t != null)
//红黑树的根节点不为null则将指定的key和新的value封装成树节点添加到红黑树中
t.putTreeVal(this, tab, hash, key, v);
else {
//将key和value封装成普通节点添加到指定的索引位置上
tab[i] = newNode(hash, key, v, first);
//如果链表中的节点数量大于等于链表转换为红黑树的阈值则将链表转换为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
}
++modCount;
++size;
afterNodeInsertion(true);
return v;
}
put()方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
put方法会先调用hash()方法获取到key的hash值再调用putVal()方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
先校验key是否为null,如果key为null则返回hash值为0,key不为null则获取到key的hashCode,将hashCode赋值给h,将h的二进制无符号右移16位获取到新的值,再将h的二进制与右移16位的值的二进制进行异或运算获取到hash值,将二进制右移16位的作用主要是让高位与低位做运算,减少hash冲突。
例：key = 张三 ,张三的hashCode为774889
(774889) ^ (774889 >>> 16)
774889的二进制: 1011 1101 0010 1110 1001
774889右移16位后的二进制: 0000 0000 0000 0000 1011
异或运算后的二进制: 1011 1101 0010 1110 0010(相同为0不相同为1)
putVal方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
//存放数据的数组
Node<K,V>[] tab;
//待添加元素的原索引位置上的元素
Node<K,V> p;
//n 数组长度
//i 数组索引
int n, i;
//校验名称为table的node数组是否为空
if ((tab = table) == null || (n = tab.length) == 0)
//node数组为空则调用resize方法初始化
//将初始化的node数组赋值给tab
//并将初始化的node数组的长度赋值给n
n = (tab = resize()).length;
//使用数组索引长度与hash值进行与运算获取到数组中的一个索引,并获取该索引位置的元素,校验该元素是否为null
if ((p = tab[i = (n - 1) & hash]) == null)
//索引位置的元素为null则将待添加的key和value封装成一个节点添加到索引位置上
tab[i] = newNode(hash, key, value, null);
else {
//索引位置上的元素不为null
Node<K,V> e; K k;
//校验索引位置上的元素的hash值是否与当前待添加的元素的hash值相同
//并且索引位置上的key与待添加的key相同
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
//hash值相同并且key也相同则根据onlyIfAbsent来决定是否将value进行替换
e = p;
//校验索引位置上的元素是否是使用的红黑树
else if (p instanceof TreeNode)
//将元素添加到红黑树中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//将元素添加到链表中
//binCount 节点数量
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//为null则说明已到链表的尾节点
//创建一个新的节点并将新的节点添加到链表的尾节点中
p.next = newNode(hash, key, value, null);
//校验链表的长度是否到达转换红黑树的阈值
if (binCount >= TREEIFY_THRESHOLD - 1)
//当链表中的节点数量大于等于8时,如果数组的长度小于最小树化阈值则不会将链表转换为红黑树,而是对数组进行扩容
//将链表中的节点分散到别的索引节点中去,只有当数组的长度大于等于最小树化阈值则会将链表转换为红黑树
treeifyBin(tab, hash);
break;
}
//待添加的元素的key和hash值与链表中每一个节点的key和hash值进行匹配
//如果key和hash值相同则退出循环并根据onlyIfAbsent决定是否需要将value替换
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) {
//旧值
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
//开启了替换元素或者旧值为null并使用新值替换旧值
e.value = value;
afterNodeAccess(e);
//返回旧值
return oldValue;
}
}
//数组修改次数加1
++modCount;
//数组长度加1
//校验数组的长度是否超出扩容阈值,如果超出则调用resize方法进行扩容
if (++size > threshold)
//扩容
resize();
afterNodeInsertion(evict);
return null;
}
先看putVal方法中的参数,hash、key、value这3个参数就不用说了,onlyIfAbsent则是当前位置的值已存在是否替换,false替换,true不替换,evict则是表是否是在创建模式,在HashMap中将evict参数传递过去的方法是个空方法,在LinkedHashMap中有具体的实现。
1.
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
如果数组为空则会调用resize方法先对数组进行初始化,resize方法放在后面讲。 2.
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
使用数组索引长度与hash值进行与运算获取到数组中的索引位置,并获取该索引位置的节点,校验该节点是否为null,如果该节点为null则将hash值、key、value封装成一个节点并将该节点添加到索引位置上,后续代码中则会对数组的长度和修改次数加1并校验数组的长度是否到达了阈值,如果到达了阈值则调用resize方法对数组进行扩容。 3.
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
p则是在序号2中使用数组索引长度与hash值进行与运算获取到的索引位置上的节点,使用该节点与待添加的元素的hash值和key进行比较,如果相同则将p赋值给e,后续代码中则根据onlyIfAbsent来决定是否将旧值进行替换。 4.
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
校验节点p是否是红黑树节点,如果是红黑树节点则调用putTreeVal方法将hash、key、value封装成一个树节点并将树节点添加到红黑树中。 5.
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
该代码则是将元素添加到链表中,如果序号3和4中的代码都不成立则说明该节点是个链表,则根据节点中的next指针遍历链表中所有的节点,在遍历的时候将待添加的元素的hash值和key与遍历到的节点的hash值和key进行比较,如果相同则退出循环并根据onlyIfAbsent决定是否需要将旧值进行替换,如果链表中所有的节点都不匹配则根据hash、key、value创建一个新的节点,并将该节点设置为链表的尾部节点,再校验链表的长度是否大于等于链表转换为红黑树的阈值(默认为8),此处为什么要-1,因为binCount是从0开始的,如果小于8则退出循环,后续代码中则会对数组的长度和修改次数加1并校验数组的长度是否到达了阈值,如果到达了阈值则调用resize方法对数组进行扩容,如果大于等于8则调用treeifyBin方法校验是否需要将链表转换为红黑树。 6.
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
校验节点e是否为null,如果不为null说明数组、链表、红黑树中存在与待添加元素中的hash值和key相同的节点,获取旧值,当旧值为null或onlyIfAbsent为false则使用新的value值替换旧值并返回旧值,只有在调用putIfAbsent方法的时候onlyIfAbsent才为true,afterNodeAccess方法在HashMap中没有具体的实现。 treeifyBin方法
final void treeifyBin(Node<K,V>[] tab, int hash) {
//n 数组长度
//index hash值所在的索引位置
int n, index;
Node<K,V> e;
//校验数组是否为空或者数组的长度小于最小树化阈值
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
//数组为空或者数组的长度小于最小树化阈值则对数组进行扩容
resize();
//使用数组索引长度与hash值进行与运算获取到hash值所在的索引位置
//并根据索引获取到该索引位置的头节点
else if ((e = tab[index = (n - 1) & hash]) != null) {
//hd 头节点
//tl 尾节点
TreeNode<K,V> hd = null, tl = null;
do {
//循环将数组中的index索引位置的单向链表中的所有普通节点转换为双向链表的树节点
//将普通节点转换为树节点
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
//尾节点为null则将当前树节点设置为头节点
hd = p;
else {
//将当前树节点的prev指针指向上一个树节点
p.prev = tl;
//将上一个树节点的next指针指向当前树节点
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
//将双向链表中的树节点的头节点添加到index位置
if ((tab[index] = hd) != null)
//将双向链表转换为红黑树
hd.treeify(tab);
}
}
1.
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
当链表中的节点的数量大于等于8时,不会直接将链表转换为红黑树,而是先校验数组的长度是否小于最小树化的阈值(64),如果小于则不会将链表转换为红黑树,而是将数组扩容,将链表中的部分节点重新路由到其它索引位置上,只有当数组的长度大于等于64并且链表的节点数量大于等于8时才会将链表转换为红黑树。 2.
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);
}
根据hash值和数组索引长度进行与运算获取到单向链表中的头节点,再根据节点中的next指针遍历单向链表中的所有节点,将单向链表中的所有普通节点都转换为双向链表的树节点,将单向链表中的头节点设置为双向链表中的头节点,并将双向链表中的每个节点使用next和prev指针进行关联,直至单向链表中的普通节点都转换为了双向链表中的树节点,再将双向链表中的头节点将数组中原单向链表的头节点替换掉,为什么只需要替换头节点,因为双向链表中的每个节点都有next和prev指针,有了这两个指针就可以根据指针获取到双向链表中的所有节点,最后调用treeify方法将双向链表转换为红黑树。 treeify方法
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) {
//根节点为null则说明当前节点是头节点
//将当前节点的父节点置为null
x.parent = null;
//当前节点的颜色为黑色
x.red = false;
//将当前节点设置为根节点
root = x;
}else {
//当前节点的key
K k = x.key;
//当前节点的hash值
int h = x.hash;
//当前节点的key的Class类型
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
//ph 父节点的hash值
//dir 方向 -1左子节点 0右子节点
int dir, ph;
//父节点的key
K pk = p.key;
if ((ph = p.hash) > h)
//父节点的hash值大于当前节点的hash值则将当前节点放置根节点的左边
dir = -1;
else if (ph < h)
//父节点的hash值小于当前节点的hash值则将当前节点放置根节点的右边
dir = 1;
//校验当前节点的key的class类型是否为空并且未实现comparable接口或父节点的key的class与当前节点的class是否匹配
else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0)
//使用父节点的key的hash值与当前节点的key的hash值进行比较
dir = tieBreakOrder(k, pk);
//父节点
TreeNode<K,V> xp = p;
//校验当前节点的插入方向并校验该方向的节点是否为null
//不为null则说明该节点已经存在则需要继续向下寻找,直到找到空余的节点
//为null则将该节点插入
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;
}
}
}
}
//校验root节点是否是头节点,如果不是则将root节点移动到头部
moveRootToFront(tab, root);
}
1.
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;
}
根据双向链表中的next指针从双向链表的头节点开始遍历将双向链表转换为红黑树,先初始化遍历到的节点左子节点和右子节点,校验根节点是否为null,如果根节点为null则说明当前遍历到的节点是双向链表中的头节点,则将当前遍历到的节点设置为根节点并将节点的颜色设置为黑色。 2.
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;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
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;
}
}
}
根节点不为null则会执行else里面的代码,从根节点开始循环查找每个节点,将每个节点中的hash值与父节点的hash进行比较,如果大于父节点的hash值则将节点插入到右子节点,如果小于父节点的hash值则将节点插入到左子节点,hash值如果相同则调用tieBreakOrder方法对父节点和当前节点的key的hash值重新比较。
校验元素插入的方向,如果dir小于等于0则获取当前遍历到的节点的左子节点,大于0则获取右子节点,校验左子节点或右子节点是否为null,不为null则继续向下查找,如果为null则将当前节点添加到左子节点或右子节点,再调用balanceInsertion方法使红黑树平衡。
上面的图片则是将双向链表转换为红黑树的过程,只调用了balanceInsertion方法的部分代码,具体的红黑树平衡的代码未调用,因为上面在转换为红黑树的过程中数据本身就是平衡的,不需要其它操作来使红黑树进行平衡。
balanceInsertion方法
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) {
//设置当前节点的颜色为红色
x.red = true;
//xp 当前节点的父节点
//xpp 父节点的父节点
//xppl 父节点的父节点的左子节点
//xppr 父节点的父节点的右子节点
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
//校验当前节点的父节点是否为null
if ((xp = x.parent) == null) {
//设置当前节点为黑色
x.red = false;
return x;
//校验父节点的颜色不为红色或父节点的父节点等于null
} else if (!xp.red || (xpp = xp.parent) == null)
return root;
//校验父节点是不是左子节点
if (xp == (xppl = xpp.left)) {
//校验父节点的父节点的右子节点是否不为null并且节点颜色为红色
if ((xppr = xpp.right) != null && xppr.red) {
//将父节点的父节点的右子节点设置为黑色
xppr.red = false;
//将父节点设置为黑色
xp.red = false;
//将父节点的父节点设置为红色
xpp.red = true;
//将父节点的父节点设置为当前节点
//继续循环校验当前节点的父节点是否为null,当前节点的父节点为null则退出循环并返回当前节点
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 {
//校验父节点的父节点的左子节点是否不为null并且颜色为红色
if (xppl != null && xppl.red) {
//父节点的父节点的左子节点的颜色设置为黑色
xppl.red = false;
//父节点设置为黑色
xp.red = false;
//父节点的父节点设置为红色
xpp.red = true;
//将父节点的父节点设置为当前节点
//继续循环校验当前节点的父节点是否为null,当前节点的父节点为null则退出循环并返回当前节点
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);
}
}
}
}
}
}
1.
if ((xp = x.parent) == null) {
x.red = false;
return x;
} else if (!xp.red || (xpp = xp.parent) == null)
return root;
该代码则是在添加节点之后红黑树进行平衡或红黑树本来就是平衡的状态后退出的条件。
2.
if (xp == (xppl = xpp.left)) {
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;
xp.red = false;
xpp.red = true;
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);
}
}
}
}
当前节点的父节点如果是左子节点则根据红黑树的状态来选择平衡的方法,如果当前节点的父节点的父节点的右子节点不为null并且颜色为红色,则调整节点的颜色使红黑树平衡,反之则先校验当前节点是否是右子节点,如果是右子节点则调用左旋的方法将父节点进行左旋使用父节点和当前节点在同一条线上,然后进行下一次循环则会进入到下面的判断语句中执行右旋使红黑树平衡，如果当前节点不是右子节点则会执行右旋使红黑树平衡。 3.
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);
}
}
}
}
该代码与序号2中的代码大致相同,只是方向不同。
左旋使红黑树进行平衡的过程
右旋使红黑树平衡的过程(具体过程可以参考左旋)
红黑树添加左子节点之后使红黑树节点颜色平衡的过程
红黑树添加右子节点之后使红黑树节点颜色平衡的过程
红黑树多次旋转使红黑树进行平衡的过程(此处只展示了先右旋再左旋的过程,左旋到右旋的过程大致相同)
到这里链表转换为红黑树并使红黑树进行平衡到这里就结束了,接下来看元素添加到红黑树中的代码。
putTreeVal方法
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v) {
//待添加的key的class类型
Class<?> kc = null;
//是否从红黑树中查找过
boolean searched = false;
//校验当前节点的父节点是否为null
//如果父节点为null则当前节点为根节点
//如果父节点不为null则从当前节点向上寻找根节点
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
//dir 方向 -1左子节点 1右子节点
//ph 父节点的hash值
//pk 父节点的key
int dir, ph; K pk;
//校验父节点的hash值是否大于待添加元素的hash值
if ((ph = p.hash) > h)
//父节点的hash值大于当前节点的hash值则将当前节点放置根节点的左边
dir = -1;
else if (ph < h)
//父节点的hash值大于当前节点的hash值则将当前节点放置根节点的右边
dir = 1;
//校验待添加元素的key是否跟父节点的key相同
//相同则返回父节点,根据onlyIfAbsent来决定是否需要将value替换
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
//校验当前节点的key的class类型是否为空并且未实现comparable接口或父节点的key的class与当前节点的class是否匹配
else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
//ch 左子节点或右子节点
TreeNode<K,V> q, ch;
searched = true;
//左子节点或右子节点不为null则在红黑树中从左子节点或右子节点根据给定的key、hash、key的class类型开始查找节点
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;
}
//使用父节点的key的hash值与当前节点的key的hash值进行比较
dir = tieBreakOrder(k, pk);
}
//父节点
TreeNode<K,V> xp = p;
//校验当前节点的插入方向并校验该方向的节点是否为null
//不为null则说明该节点已经存在则需要继续向下寻找,直到找到空余的节点
//为null则将该节点插入
if ((p = (dir <= 0) ? p.left : p.right) == null) {
//父节点的下一个节点
Node<K,V> xpn = xp.next;
//创建一个新的树节点
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
//将父节点的左子节点指针指向新的树节点
xp.left = x;
else
//将父节点的右子节点指针指向新的树节点
xp.right = x;
//父节点的下一个节点的指针指向新的树节点
xp.next = x;
//新的树节点的父节点和上一个节点的指针都指向父节点
x.parent = x.prev = xp;
if (xpn != null)
//如果原来的下一个节点不为空则将原来的下一个节点的上一个节点的指针指向新的树节点
((TreeNode<K,V>)xpn).prev = x;
//将节点插入到红黑树中并使红黑树平衡
//并校验红黑树中的根节点是否变化
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
该方法则是根据待添加元素的key的hash值从根节点开始遍历,与红黑树中的每个节点中的hash值进行比较,获取到节点插入的方向,并将待添加的元素的key、hash值、value封装成一个新的树节点,并将新的树节点添加到红黑树中并使红黑树保持平衡。
扩容
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) {
//旧数组长度超出最大容量大小
//设置数组的扩容阈值为Integer最大值并返回旧数组不进行扩容
threshold = Integer.MAX_VALUE;
return oldTab;
}
//校验旧数组长度扩容两倍之后是否小于最大容量大小
//并且旧数组长度大于等于默认的初始容量大小16
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
//新数组的阈值
newThr = oldThr << 1;
}
else if (oldThr > 0)
//进入当前判断语句表示在创建hashMap对象的时候传入了初始容量和负载因子或只传入了初始容量使用了默认的负载因子
//将阈值赋值给初始容量
newCap = oldThr;
else {
//都为0的情况则是在创建hashMap对象的时候没有传入初始容量和负载因子则使用默认值初始化新的数组
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
//进入当前判断语句表示在创建hashMap对象的时候传入了初始容量和负载因子或只传入了初始容量使用了默认的负载因子或在扩容的时候新数组的长度小于默认初始容量
//使用新数组的初始容量与传入的负载因子或默认的负载因子计算出新数组的阈值
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//更新扩容阈值
threshold = newThr;
//创建一个新的node数组
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//更新数组对象
table = newTab;
//如果旧数组为null则直接返回新创建的数组
if (oldTab != null) {
//旧数组不为null则将旧数组中的数据重新索引到新数组中
for (int j = 0; j < oldCap; ++j) {
//当前遍历到的节点
Node<K,V> e;
//将当前遍历到的节点赋值给e并校验该节点是否不等于null
if ((e = oldTab[j]) != null) {
//将旧数组中当前遍历到的节点置为null
oldTab[j] = null;
//校验当前遍历到的节点的下一个节点是否为null
if (e.next == null)
//为null表示当前节点还不是链表或红黑数
//使用当前节点的hash值与新数组的索引长度进行与运算获取到当前节点在新数组中的索引
//并将当前节点放置新数组中的索引位置
//获取到的新数组的索引位置要么与旧数组的索引位置相同要么则是旧数组的索引位置加上旧数组的容量大小
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
//当前遍历到的节点是红黑数
//将红黑树节点分为低位和高位,如果低位和高位都有节点则将判断节点的长度是否小于等于6
//如果小于等于6则将红黑树转换为链表并将链表的头节点添加到数组中
//如果不小于等于6则将低位和高位的节点转换为红黑树并添加到数组中
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
//当前遍历到的节点是单向链表
//低位头节点和尾节点
Node<K,V> loHead = null, loTail = null;
//高位头节点和尾节点
Node<K,V> hiHead = null, hiTail = null;
//下一个节点
Node<K,V> next;
do {
//获取下一个节点
next = e.next;
//使用当前节点的hash值与旧数组的长度进行与运算
//计算结果为0则将节点放入到新数组中与在旧数组中的索引位置相同
//计算结果不为0则将节点放入到新数组中的其它索引位置,新数组的索引位置的计算方式为旧数组中的索引位置加上旧数组的容量大小
if ((e.hash & oldCap) == 0) {
if (loTail == null)
//低位尾节点指针为null则将低位头节点指针指向当前节点
loHead = e;
else
//低位尾节点不为null则将低位尾节点的下一个节点的指针指向当前节点
loTail.next = e;
//将低位尾节点指针指向当前节点
loTail = e;
}else {
if (hiTail == null)
//高位尾节点指针为null则将高位头节点指针指向当前节点
hiHead = e;
else
//高位尾节点不为null则将高位尾节点的下一个节点的指针指向当前节点
hiTail.next = e;
//将高位尾节点指针指向当前节点
hiTail = e;
}
//下一个节点为null则说明当前索引位置的链表节点已经处理完毕
//下一个节点不为null则继续处理当前索引位置的链表节点
} while ((e = next) != null);
if (loTail != null) {
//将低位尾节点的下一个节点的指针置为null
loTail.next = null;
//将低位头节点放入到新数组中与在旧数组中的索引位置相同
newTab[j] = loHead;
}
if (hiTail != null) {
//将高位尾节点的下一个节点的指针置为null
hiTail.next = null;
//将高位头节点放入到新数组中在旧数组中的索引位置加上旧数组的容量大小的索引位置
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
resize方法主要是对数组进行初始化和数组扩容以及数组扩容之后将旧数组中的元素转移到新的数组中。
1.
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,大于0则再校验是否超出最大容量大小(1073741824),如果超出最大容量大小则不会进行扩容,直接返回旧数组,不超出最大容量大小则校验扩容后的长度是否超出最大容量大小并且大于默认初始容量(16),条件成立则按照旧数组长度的两倍获取到新数组的长度和阈值,不成立则按照旧数组长度的两倍获取到新数组的长度,再根据新数组的长度与负载因子计算获取到新数组的阈值。
2.
else if (oldThr > 0)
newCap = oldThr;
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
两个语句都是对数组进行初始化,第一个则是在创建HashMap的时候传入了初始容量,则使用传递的初始容量来初始化数组,第二个则是在创建HashMap的时候没有传递初始容量和负载因子,则使用默认的初始容量和负载因子。
3.
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
该语句则是在创建HashMap的时候传递了初始容量或在扩容的时候新数组的长度小于默认初始容量大小,在传递了初始容量则使用初始容量与负载因子计算出数组初始化的阈值,小于默认初始容量大小则使用扩容后的新数组长度与负载因子计算出新数组的阈值。
4.
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
遍历数组,对数组中的每一个节点进行校验数组中的节点是否有下一个节点,如果没有下一个节点则表示该节点还不是链表或红黑树,则将该节点路由到新数组中。
5.
else {
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;
}
}
当前遍历到的节点是单向链表,则从单向链表的头节点开始遍历将单向链表中的节点分为低位节点和高位节点,低位节点则放入到新数组中与在旧数组中的索引位置相同,高位节点则放到新数组中的其它索引位置,新数组的索引位置的计算方式位旧数组中的索引位置加上旧数组的容量大小。
6.
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
遍历到的节点是红黑树节点,对红黑树中的节点进行拆分并路由到新数组中。
split方法
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
//低位头节点和尾节点
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;
//将当前节点的下一个节点指针置为null
e.next = null;
//使用当前节点的hash值与旧数组的长度进行与运算
//计算结果为0则将节点放入到新数组中与在旧数组中的索引位置相同
//计算结果不为0则将节点放入到新数组中的其它索引位置,新数组的索引位置的计算方式为旧数组中的索引位置加上旧数组的容量大小
if ((e.hash & bit) == 0) {
//如果低位尾节点为null则说明第一次执行则将当前节点设置为低位头节点和低位尾节点,并使低位节点长度加1
//如果低位尾节点不为null则将当前节点的上一个节点指针指向低位尾节点
//并将低位尾节点的下一个节点指针指向当前节点,并将当前节点设置为低位尾节点,并使低位节点长度加1
if ((e.prev = loTail) == null)
//当前节点设置为低位头节点
loHead = e;
else
//将低位尾节点的下一个节点的指针指向当前节点
loTail.next = e;
//将当前节点设置为低尾节点
loTail = e;
//低位节点长度加1
++lc;
}
else {
//如果高位尾节点为null则说明第一次执行则将当前节点设置为高位头节点和高位尾节点,并使高位节点长度加1
//如果高位尾节点不为null则将当前节点的上一个节点指针指向高位尾节点
//并将高位尾节点的下一个节点指针指向当前节点,并将当前节点设置为高位尾节点,并使高位节点长度加1
if ((e.prev = hiTail) == null)
//当前节点设置为高位头节点
hiHead = e;
else
//将高位尾节点的下一个节点的指针指向当前节点
hiTail.next = e;
//将当前节点设置为高尾节点
hiTail = e;
//高位节点长度加1
++hc;
}
}
//校验低位头节点是否为null
if (loHead != null) {
//校验低位节点长度是否小于等于红黑树转链表的阈值
if (lc <= UNTREEIFY_THRESHOLD)
//小于阈值则将红黑树转换为链表并将低位头节点添加到数组中指定的索引位置
tab[index] = loHead.untreeify(map);
else {
//不小于红黑树转换为链表的阈值则将低位头节点添加到数组中指定的索引位置
tab[index] = loHead;
//校验高位头节点是否为null,如果不为null则说明原先红黑树有改动
if (hiHead != null)
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);
}
}
}
该方法则是将红黑树中的节点分为低位双向链表树节点和高位双向链表树节点,如果低位树节点和高位树节点的长度小于等于红黑树转换为链表的阈值(6)则调用untreeify方法将双向链表中的树节点转换为普通节点,如果大于阈值则调用treeify方法将双向链表的树节点转换为红黑树,treeify方法在前面已经讲过。
untreeify方法
final Node<K,V> untreeify(HashMap<K,V> map) {
//hd 头节点
//tl 尾节点
Node<K,V> hd = null, tl = null;
//this 头节点
//从头节点开始遍历树节点取消树节点之间的关联并将节点使用链表进行关联
for (Node<K,V> q = this; q != null; q = q.next) {
//将树节点替换为普通节点
Node<K,V> p = map.replacementNode(q, null);
//将普通节点进行关联变成链表
if (tl == null)
//尾节点为null则将当前节点设置为头节点
hd = p;
else
//将上一个节点的next指针指向当前节点
tl.next = p;
//将当前节点设置为尾节点
tl = p;
}
//返回头节点
return hd;
}
转载自:https://juejin.cn/post/7172904782951088164