hashMap 源码分析
2021-09-10 本文已影响0人
java_飞
//new HashMap时只是对设置的大小进行一些判断，
public HashMap(int initialCapacity, float loadFactor) {
//如果小于0则报错，
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//如果大于2的30次就默认设置为2的30次
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//如果小于0 或者 不是数字 则报错
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//设置的是hashmap临界值的大小，初始时设置的大小跟capacity一样
this.threshold = tableSizeFor(initialCapacity);
}
-------------------------------------------------------------------------------------------------------------
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果当前的node表没有初始化，则进行初始化，说明hashmap初始化是在put的时候
if ((tab = table) == null || (n = tab.length) == 0)
//resize() 初始化方法
n = (tab = resize()).length;
//判断元素hashcode的 tab位置是否为空
if ((p = tab[i = (n - 1) & hash]) == null)
//为空就new一个node 放置进去
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//判断是不是同一个key，通过hashcode 和equal比较
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 {
//这里代表是hash冲突的链表操作，
//先进行死循环
for (int binCount = 0; ; ++binCount) {
//判断当前节点链表的第一个位置是否为null
if ((e = p.next) == null) {
//链表节点的插入操作 new Node
p.next = newNode(hash, key, value, null);
//插入完后紧接着判断是否大于等于7 如果大于等于7则进行树的转换操作
//这里说明链表长度一旦达到8就开始将链表转换成树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//树的转换操作
treeifyBin(tab, hash);
break;
}
//判断链表里的key是不是同一个，如果是的话就退出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//走到这里说明当前节点的next节点不为空，赋值，进行下一轮
p = e;
}
}
//这里是对链表里的元素与将要插入的值一样时，进行value的替换
if (e != null) { // existing mapping for key
V oldValue = e.value;
//onlyIfAbsent 当key一样时，是否替换原有的值，如果为true 则不进行替换
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//回调以允许 LinkedHashMap 后操 ，这里hashMap没有实现
afterNodeAccess(e);
return oldValue;
}
}
//hashmap结构修改的次数，作用是，当遍历集合时，集合发生了变化，进行fail-fast
++modCount;
//如果当前hashmap大小大于负载因子乘以容量的大小时，进行扩容
//这里可以知道是在put结束后进行扩容的
if (++size > threshold)
resize();
//空实现，hashmap不用考虑
afterNodeInsertion(evict);
return null;
}
-------------------------------------------------------------------------------------------------------------
//初始化hashmap+以及对hashmap进行扩容
final Node<K,V>[] resize() {
//记录扩容前的table
Node<K,V>[] oldTab = table;
//记录扩容前的table大小
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//记录扩容前的大小临界值
int oldThr = threshold;
int newCap, newThr = 0;
//大于0 说明时扩容场景
if (oldCap > 0) {
//当扩容前容量大于等于MAXIMUM_CAPACITY （MAXIMUM_CAPACITY=2^30）
if (oldCap >= MAXIMUM_CAPACITY) {
//临界值直接设为int的最大值
threshold = Integer.MAX_VALUE;
return oldTab;
}
//oldCap << 1 表示将原来大小乘以2 也就是翻倍
//当2倍后的新容量小于最大值且老容量大于等于默认值时，
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//容量临界值也直接扩大2倍
newThr = oldThr << 1; // double threshold
}
//如果
else if (oldThr > 0) // initial capacity was placed in threshold
//new hashmap时设置了大小就会走到这里
newCap = oldThr;
else {
// zero initial threshold signifies using defaults
//初始化场景，new hashmap时没有设置大小
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//两种情况会走到这里
//1.扩容前大小大于等于MAXIMUM_CAPACITY
//2.new hashmap设置了大小，初始化时重新计算hashmap临界值
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//计算新的扩容临界值，加负载因子*capacity 例如0.75*16=12
threshold = newThr;
//new 一个32容量的新tab
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//赋给原来的table
table = newTab;
//这里是具体扩容后key的移动
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//判断对应索引位置的元素是否为空
if ((e = oldTab[j]) != null) {
//将老的位置置为null
oldTab[j] = null;
//判断该位置元素是否存在链表
if (e.next == null)
//不存在的话，就重新计算hash值放入新的tab
newTab[e.hash & (newCap - 1)] = e;
//存在，则判断是否为树节点
else if (e instanceof TreeNode)
//进行树节点的操作
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//以下操作就是循环将链表元素进行重新计算放入新的tab中，详细不再描述，
//由下面可以知道元素在新tab中如果不在原来位置，则可能在原有位置+原来capacity
//注意：这里也就存在着线程安全的问题，并发时对链表的元素的rehash可能造成死循环，
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
-------------------------------------------------------------------------------------------------------------
//将node节点转换为TreeNode节点，并调用红黑树转换方法
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//这里说明并不是链表长度到达8就开始换成树的，还有其他条件，只有当tab的capacity大于等于MIN_TREEIFY_CAPACITY时，才会进行转换成红黑树的操作，否则将对hashmap进行扩容，(MIN_TREEIFY_CAPACITY=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;
//循环 将原来链表的node类型变成TreeNode类型，再以链表结构组装起来
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);
}
}
-------------------------------------------------------------------------------------------------------------
//红黑树转换方法
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
//对TreeNode类型的链表进行循环
for (TreeNode<K,V> x = this, next; x != null; x = next) {
//获取当前节点的下一个
next = (TreeNode<K,V>)x.next;
//设置当前节点的左右子树为null
x.left = x.right = null;
//如果root节点为空
if (root == null) {
//将当前节点设置为root节点，没有父节点，同时时黑色节点
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;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
//这里就是判断当前key与树上节点key的比较
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
//如果hash一致，且类名一致，就通过系统hashcode计算
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);
}
-------------------------------------------------------------------------------------------------------------
//平衡插入树节点方法，不平衡时对树的左旋 或者右旋，以及着色
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;;) {
//插入节点的父节点为空，则插入节点作为root节点返回
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
//插入节点的父节点是黑色或者插入节点的爷爷节点是空，则返回原来的root节点
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 = 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);
}
}
}
}
}
}
-------------------------------------------------------------------------------------------------------------
//树的左旋
//左旋是将当前p节点下放到它的右节点，同时将右节点上移到p节点所在位置
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> r, pp, rl;
if (p != null && (r = p.right) != null) {
//p节点下放到它的右节点
if ((rl = p.right = r.left) != null)
rl.parent = p;
//如果p节点以及它的右节点都没有爷爷节点，说明p节点为root
if ((pp = r.parent = p.parent) == null)
(root = r).red = false;
else if (pp.left == p)
//将右节点替换为它的父节点
pp.left = r;
else
//将右节点替换为它的父节点
pp.right = r;
r.left = p;
p.parent = r;
}
return root;
}
-------------------------------------------------------------------------------------------------------------
//树的右旋
//右旋是将当前p节点下放到它的左节点，同时将左节点上移到p节点所在位置
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> l, pp, lr;
if (p != null && (l = p.left) != null) {
//p节点下放到它的左节点
if ((lr = p.left = l.right) != null)
lr.parent = p;
if ((pp = l.parent = p.parent) == null)
(root = l).red = false;
else if (pp.right == p)
//将左节点替换为它的父节点
pp.right = l;
else
//将左节点替换为它的父节点
pp.left = l;
l.right = p;
p.parent = l;
}
return root;
}
-------------------------------------------------------------------------------------------------------------
//确保给定的根是其 bin 的第一个节点
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
int index = (n - 1) & root.hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
if (root != first) {
Node<K,V> rn;
tab[index] = root;
TreeNode<K,V> rp = root.prev;
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
rp.next = rn;
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
assert checkInvariants(root);
}
}
-------------------------------------------------------------------------------------------------------------
//树节点插入，跟链表转树方法中的插入一样
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;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(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;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
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;
}
}
}
说明
1.new HashMap，其实只是指定了临界值参数的大小
2.put操作时才是真正初始化了hashmap，同时也将new 时设置的参数设置为hashmap大小，并重新计算临界值大小
2.1.如果为hashmap未初始化，则进行初始化；
2.2.如果对应位置为空，则直接newNode插入
2.3 如果是hash一样，则判断是否为同一个key，如果是直接替换value
2.4 如果是树节点，进行树的put操作，里面涉及了树的平衡，着色，左右旋转等
2.5 如果是链表且长度小于8时，则newNode，原来key位置用链表结构连接上
2.6 判断链表长度是否大于7，如果大于则进行树的转换
2.6.1树转换时，先判断hashmap大小，如果小于64，则进行扩容
2.6.2 链表转树时，先将node链表转换为treeNode链表，然后再进行树的转换，树转换原来就是通过key的比较进行树的构造
2.7 如果链表上的key与插入的key一致时，退出循环，然后替换链表上的值
2.8 正常插入后也会判断下当前hashmap大小是否超过临界值，只有超过临界值时才进行扩容
这里树的构造以及红黑色的着色，左右旋转就不做赘述，想要了解的可以自行查阅源码
