HashMap 与红黑树

传统 HashMap的缺点

JDK 1.8 以前 HashMap 的实现是 数组+链表,即使哈希函数取得再好,也很难达到元素百分百均匀分布。

当 HashMap 中有大量的元素都存放到同一个桶中时,这个桶下有一条长长的链表,这个时候 HashMap 就相当于一个单链表,假如单链表有 n 个元素,遍历时间复杂度就是 O(n),完全失去了它的优势。

针对这种情况,JDK 1.8 中引入了红黑树(查找时间复杂度为 O(logn))来优化这个问题

JDK1.8中HashMap的数据结构

HashMap是数组+链表+红黑树(JDK1.8增加了红黑树部分)实现的

HashMap 与红黑树

新增红黑树

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;

}

TREEIFY_THRESHOLD static final int TREEIFY_THRESHOLD = 8

一个桶的树化阈值,当桶中元素个数超过这个值时,需要使用红黑树节点替换链表节点

UNTREEIFY_THRESHOLD static final int UNTREEIFY_THRESHOLD = 6

一个树的链表还原阈值,当扩容时,桶中元素个数小于这个值,就会把树形的桶元素 还原(切分)为链表结构

MIN_TREEIFY_CAPACITY

static final int MIN_TREEIFY_CAPACITY = 64

当哈希表中的容量大于这个值时,表中的桶才能进行树形化

否则桶内元素太多时会扩容,而不是树形化

为了避免进行扩容、树形化选择的冲突,这个值不能小于 4 * TREEIFY_THRESHOLD

HashMap 在 JDK 1.8 中新增的操作:桶的树形化 treeifyBin()

在Java 8 中,如果一个桶中的元素个数超过 TREEIFY_THRESHOLD(默认是 8 ),就使用红黑树来替换链表,从而提高速度。

这个替换的方法叫 treeifyBin() 即树形化。//将桶内所有的 链表节点 替换成 红黑树节点

final void treeifyBin(Node<K,V>[] tab, int hash) {

int n, index; Node<K,V> e;

//如果当前哈希表为空,或者哈希表中元素的个数小于 进行树形化的阈值(默认为 64),就去新建/扩容

if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)

resize();

else if ((e = tab[index = (n – 1) & hash]) != null) {

//如果哈希表中的元素个数超过了 树形化阈值,进行树形化

// e 是哈希表中指定位置桶里的链表节点,从第一个开始

TreeNode<K,V> hd = null, tl = null; //红黑树的头、尾节点

do {

//新建一个树形节点,内容和当前链表节点 e 一致

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);

}

1.根据哈希表中元素个数确定是扩容还是树形化

2.如果是树形化遍历桶中的元素,创建相同个数的树形节点,复制内容,建立起联系

3.然后让桶第一个元素指向新建的树头结点,替换桶的链表内容为树形内容

HashMap 与红黑树

1.判断键值对数组table[i]是否为空或为null,否则执行resize()进行扩容;

2.根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加,转向⑥,如果table[i]不为空,转向③;

3.判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,否则转向④,这里的相同指的是hashCode以及equals

4.判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对,否则转向⑤;

5.遍历table[i],判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;

6.插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容。

原文 

https://segmentfault.com/a/1190000023016161

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » HashMap 与红黑树

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址