HashMap线程不安全,底层数组+链表+红黑树
面试重点是put方法,扩容
总结
put方法
HashMap的put方法,首先通过key去生成一个hash值,第一次进来是null,此时初始化大小为16,i = (n - 1) & hash计算下标值,第一次获取是null,直接放入一个Node节点,如果不是null,分成下面三种情况
1)如果发现hash和key相等,将原来的覆盖
2)不相等,就要用到链表,通过尾插法插入到尾部。超过8转成红黑树
3)如果是TreeNode,插入即可
扩容
首先,上面put方法每次都会计算大小
如果超过16*0.75,即12就会r调用resize方法
这里主要是老数组上面元素转到新数组上面去的逻辑
遍历,如果老数组上面元素不是null
这里又是几种情况
1)如果next下标是null,
说明只有一个元素,直接重新计算下标放入新数组
2)判断是否是TreeNode
对TreeNode树进行拆分,转到新数组,不一定在一起。拆分后不一定还是树,这里各种情况,看节点对应的是高位还是低位。判断低位个数如果不超过6,转成链表(TreeNode转成Node)。高位也一样。否则重新生成红黑树(根据是否有高地位判断是否需要重新生成红黑树)
3)否则说明是个链表,
将链表转到新数组上面去,扩容后重新计算hash后下标不一定还是相同的,所以不能直接转到新数组,但是扩容后下标是有规律的。扩容后只有两种情况,低位和高位。 哪些节点是在低位链表上面,哪些节点是在高位链表上面。然后放到新数组即可。
源码如下:
/**
* 默认的初始容量-必须是二的幂。2的4次方=16,
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 如果隐式指定了更高的值,则使用最大容量由带有参数的构造函数中的任何一个执行。必须是二次方<=1<<30。
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 在构造函数中未指定时使用的负载系数。
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 使用树而不是列表作为存储箱的存储箱计数阈值。当向至少有这么多节点的bin添加元素时,bin会转换为树。该值必须大于2,并且应至少为8,以符合树木移除中关于收缩后转换回普通垃圾箱的假设。
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 在调整大小操作期间取消尝试(拆分)垃圾箱的垃圾箱计数阈值。应小于TREEIFY_THRESHOLD,并且最多6个,以便在去除时进行收缩检测。
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 可以将垃圾箱树化的最小桌子容量。(否则,如果一个bin中的节点太多,则会调整表的大小。)应至少为4*TREEIFY_THRESHOLD,以避免调整大小阈值和树化阈值之间的冲突。
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* 基本hash bin节点,用于大多数条目。(TreeNode子类见下文,Entry子类见LinkedHashMap。)
*/
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;
}
}
new HashMap,默认无参构造,负载因子0.75
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // 这个是0.75f
}
/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
transient int modCount;//记录修改次数
put方法
//put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* 计算key.hashCode()并将哈希的高位扩展(XOR)到低位。因为该表使用了两个掩码的幂,所以仅在当前掩码之上以位为单位变化的哈希集总是会发生冲突。(已知的例子包括在小表中保存连续整数的浮点键集。)因此,我们应用了一种变换,将高位的影响向下扩展。比特扩展的速度、效用和质量之间存在权衡。由于许多常见的哈希集已经合理分布(因此不会从扩展中受益),并且因为我们使用树来处理箱中的大型冲突集,所以我们只需以最便宜的方式对一些移位的比特进行异或,以减少系统损失,并将最高比特的影响纳入其中,否则由于表绑定,这些比特将永远不会用于索引计算
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
首先通过hash方法,传入key计算出一个int类型的hash值。
这里为什么不直接用key.hashCode()的值呢?
key.hashCode()计算出一个hash值,然后赋值给h,h右移16位,然后两个做异或运算
计算的值右移16位,右移之前和右移之后的值进行异或^运算,得到最终的hashcode,这个最终的值时通过低位和高位一起异或运算算出来的。这样高位也参加到了计算中,高位都是0.
下面还有计算数组下标的
i = (n - 1) & hash,第一次n=16,做&运算,何为&运算,即都为1则为1。
比方15的二进制时是 0000 1111 而上面计算得到的hash值和这个做&运算,值在0-15之间。这样(n - 1) & hash计算是为了使均匀分布。0-15出现频率都差不多。hash值比较均匀,最后计算的i就比较均匀。为啥要n-1,如果16的话,做&运算得到结果就两种
然后调用putVal方法,入参事key的hash值,key,value,false,true
这里是put的核心方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//定义tab,p,n,i,初始化一些变量
Node<K,V>[] tab; Node<K,V> p; int n, i;
//这里为啥不直接用table?性能问题,我们自己初始化变量是属于栈中,而table是堆中,不用每次从堆中去拿table。
//第一次进来是null
if ((tab = table) == null || (n = tab.length) == 0)
//这里调用resize,初始化及扩容,第一次返回16
n = (tab = resize()).length;//那=16
//下面这个i是如何来的?i = (n - 1) & hash,算出数组下标,如果没有值,是null,就放到这里。
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//如果这个位置不是null,这里就涉及到链表
else {
//如果这个位置上不是null,说明这个位置有东西
Node<K,V> e; K k;
//如果发现hash和key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//直接赋值到e,下面不会走了
e = p;
//如果这个位置上的是TreeNode类型
else if (p instanceof TreeNode)
//进行红黑树的插入
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//不相等,就要用到链表,这里for循环,
//如何加?通过Node对象的next属性
for (int binCount = 0; ; ++binCount) {
//binCount=0,有一个节点,所以下面要8-1=7,binCount=8
//尾插法,找到尾节点,尾节点的next==null
if ((e = p.next) == null) {
//将新的节点给到next属性,完成链表插入
p.next = newNode(hash, key, value, null);
//如果bincount的大小>=8-1=7,binCount=7,链表有8个节点,但是你自己上面newNode还新增了一个,其实现在有9个节点
//为啥超过8个转红黑树,这个和红黑树的性能有关
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不是null,
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
更新value
e.value = value;
afterNodeAccess(e);
//将原来老的value返回
return oldValue;
}
}
++modCount;
//统计++size,hashmap大小,和域值threshold(16*0.75)比较
//不停往集合put,如果大于12(threshold)个,就会调用resize扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
/**
* 初始化或加倍表大小。如果为null,则根据字段阈值中的初始容量目标进行分配。否则,因为我们使用的是二次幂展开,所以每个bin中的元素必须保持在同一索引,或者在新表中以二次幂偏移量移动。
*
* @return the table
*/
transient Node<K,V>[] table;
int threshold;
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
//一开始时null
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;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//左移1位,翻倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//一开始0,走到这里执行
newCap = DEFAULT_INITIAL_CAPACITY;//默认16(1>>4)
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//16*0.75=12这个和扩容有关系,扩容的一个域值
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;//第一次将12赋值给threshold
@SuppressWarnings({"rawtypes","unchecked"})
//这里开始创建Node,第一次newCap=16,这里创建出一个16大小的node数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//将16给到table,table=16
table = newTab;
//老数组上面元素转到新数组上面去
if (oldTab != null) {
//遍历老数组
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//如果老数组这个元素不是null
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//如果为null,说明只有一个元素
if (e.next == null)
//重新计算放到新数组中
newTab[e.hash & (newCap - 1)] = e;
//判断是不是TreeNode
else if (e instanceof TreeNode)
//对TreeNode树进行拆分,转到新数组,不一定在一起。拆分后不一定还是树,这里各种情况,看节点对应的是高位还是低位。判断低位个数如果不超过6,转成链表(TreeNode转成Node)。否则还是TreeNode,然后判断高位低位,如果低位,不用动,如果有高位,说明树进行了拆分,重新生成红黑树。
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//是个链表,将链表转到新数组上面去,扩容后重新计算hash后下标不一定还是相同的,所以不能直接转到新数组,但是扩容后下标是有规律的。只有两种情况,低位和高位
//哪些节点是在低位链表上面,哪些节点是在高位链表上面
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在低位
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);
//低位链表放到newTab
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//高位链表放到newTab
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;//第一次调用的最后返回16
}
转红黑树的方法
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//MIN_TREEIFY_CAPACITY=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 {
//将这个链表上面的Node节点遍历变成TreeNode节点,完成转换
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
//将prev也赋值,改成双向链表,方便去拿前一个节点
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
//将TreeNode节点转成红黑树
hd.treeify(tab);
}
}
红黑树查询删除等时间复杂度都是log(n),要快一点,提升查询性能
并不是超过8就一定转成红黑树,而是还要判断数组长度,64比较,小于64扩容
为啥要判断数组长度?和扩容有关,resize扩容,将链表拆分成两个短链表。
扩容,两个地方进行扩容
一个是计算hashmap大小大于12进行扩容
一个是链表长度大于8,不一定转成红黑树,而是通过判断数组长度是否小于64进行扩容
扩容先生成新数组,再把老数组上面元素放到新数组位置上
扩容,如果是TreeNode情况
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;
}
}
//如果低位不是null
if (loHead != null) {
//如果低位数量不超过6
if (lc <= UNTREEIFY_THRESHOLD)
//将TreeNode转成Node,转成了链表
tab[index] = loHead.untreeify(map);
else {
//如果超过,说明要用红黑树,
tab[index] = loHead;
//如果高位不是null,说明有高位,此时需要重新生成红黑树,如果没有高位,就不用走到treeify方法,用之前的就行。不需要重新再生成红黑树。
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);
}
}
}
红黑树
-
根节点是黑色的;
-
每个叶子节点都是黑色的空节点(NIL),也就是说,叶子节点不存储数据;
-
任何相邻的节点都不能同时为红色,红色节点是被黑色节点隔开的;
-
每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数目的黑色节点
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;;) {
//如果是null,父节点,返回
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
//如果父节点是黑色,不用调整,返回root
else if (!xp.red || (xpp = xp.parent) == null)
return root;
//父节点是红色的情况,
//父节点正好是xpp的左节点
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);
}
}
}
}
}
}
HashMap为什么用红黑树
R-B Tree。它是一种不严格的平衡二叉查找树
引入RB-Tree是功能、性能、空间开销的折中结果。
红黑是用非严格的平衡来换取增删节点时候旋转次数的降低,任何不平衡都会在三次旋转之内解决,而AVL是严格平衡树,因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑树要多。
就插入节点导致树失衡的情况,AVL和RB-Tree都是最多两次树旋转来实现复衡rebalance,旋转的量级是O(1)
删除节点导致失衡,AVL需要维护从被删除节点到根节点root这条路径上所有节点的平衡,旋转的量级为O(logN),而RB-Tree最多只需要旋转3次实现复衡,只需O(1),所以说RB-Tree删除节点的rebalance的效率更高,开销更小!
hashmap使用红黑树的原因是:这样可以利用链表对内存的使用率以及红黑树的高效检索,是一种很有效率的数据结构。AVL树是一种高度平衡的二叉树,所以查找的效率非常高,但是,有利就有弊,AVL树为了维持这种高度的平衡,就要付出更多代价。每次插入、删除都要做调整,复杂、耗时。对于有频繁的插入、删除操作的数据集合,使用AVL树的代价就有点高了。而且红黑树只是做到了近似平衡,并不严格的平衡,所以在维护的成本上,要比AVL树要低。所以,hashmap用红黑树。
红黑树相比avl树,在检索的时候效率其实差不多,都是通过平衡来二分查找。但对于插入删除等操作效率提高很多。红黑树不像avl树一样追求绝对的平衡,他允许局部很少的不完全平衡,这样对于效率影响不大,但省去了很多没有必要的调平衡操作,avl树调平衡有时候代价较大,所以效率不如红黑树,在现在很多地方都是底层都是红黑树的天下啦。
java8不是用红黑树来管理hashmap,而是在hash值相同的情况下(且重复数量大于8),用红黑树来管理数据。 红黑树相当于排序数据,可以自动的使用二分法进行定位,性能较高。一般情况下,hash值做的比较好的话基本上用不到红黑树。
AVL树用于自平衡的计算牺牲了插入删除性能,但是因为最多只有一层的高度差,查询效率会高一些。红黑树的高度只比高度平衡的AVL树的高度(log2n)仅仅大了一倍,在性能上却好很多。
HashMap为什么要转成树?为什么阈值是8?
当链表长度不断变长,肯定会对查询性能有一定的影响,所以才需要转成树。
选择8,是根据概率统计决定。
HashMap源码里有一段注解,大概意思是:
理想情况下使用随机的哈希码,容器中节点分布在hash桶中的频率遵循泊松分布(具体可以查看http://en.wikipedia.org/wiki/Poisson_distribution),按照泊松分布的计算公式计算出了桶中元素个数和概率的对照表,可以看到链表中元素个数为8时的概率已经非常小,再多的就更少了,所以原作者在选择链表元素个数时选择了8,是根据概率统计而选择的。
这里看到8的时候概率小的可怜了。
空间和时间的权衡
TreeNodes占用空间是普通Nodes的两倍,所以只有当bin包含足够多的节点时才会转成TreeNodes,而是否足够多就是由TREEIFY_THRESHOLD的值决定的。当bin中节点数变少时,又会转成普通的bin。并且我们查看源码的时候发现,链表长度达到8就转成红黑树,当长度降到6就转成普通bin。
为什么不用B+Tree
B+树在数据库中被应用的原因是其“矮胖”的特点,B+树的非叶子结点不存储数据,所以每个结点能存储的关键字更多。所以B+树更能应对大量数据的情况。Mysql就是用的B+Tree。
jdk1.7中的HashMap本来是数组+链表的形式,链表由于其查找慢的特点,所以需要被查找效率更高的树结构来替换。如果用B+树的话,在数据量不是很多的情况下,数据都会“挤在”一个结点里面。这个时候遍历效率就退化成了链表。
结论:b+树不属于二叉树,因为二叉查找树的查找效率是最高的,如果内存能装下完整的树,最好使用二叉查找树,b+树是退而求其次的方式。文章来源:https://www.toymoban.com/news/detail-432856.html
所以就是根据数据量去选择,HashMap数据量不大,,没有必要用B+Tree。文章来源地址https://www.toymoban.com/news/detail-432856.html
到了这里,关于HashMap底层源码解析及红黑树分析的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!