专栏首页Liusy01Set源码解析(红黑树)

Set源码解析(红黑树)

之前粗略看了一下List和Map,今咱来聊一下Set。

主要看以下几个:

(1)HashSet

(2)Collections.synchronizedSet

(3)LinkedHashSet

(4)CopyOnWriteArraySet

(5)TreeSet

一、HashSet

HashSet是日常搬砖中最常用的,如果有了解过HashMap的实现,那么HashSet你也就理解了。

(1)HashSet底层就是用HashMap实现的,也就是非线程安全。

 private transient HashMap<E,Object> map;
 //构造一个初始容量16,加载因子是0.75的HashMap
public HashSet() {
    map = new HashMap<>();
}

既然是用HashMap实现的,那么问题来了,Set存的只是一个对象,而HashMap存的是<K,V>键值对,怎么用HashMap作为Set的底层呢?

(2)新增元素

private static final Object PRESENT = new Object();
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

可以看到,HashSet只使用了HashMap的key,而值PRESENT是一个对象常量。这也是为什么Set里面的元素都是唯一的。

返回是map.put(e, PRESENT)==null表达式,HashMap在新增值的时候如果已有则返回旧值,反之,返回null,所以这也是Set判断重复添加值的时候是否添加成功。

二、Collections.synchronizedSet

这是用Collections工具类直接生成的,可以知道其是线程安全的

(1)底层使用synchronizedSet实现

public static <T> Set<T> synchronizedSet(Set<T> s) {
    return new SynchronizedSet<>(s);
}

而synchronizedSet又是继承自SynchronizedCollection,其方法都是使用synchronized关键字实现线程安全的。

static class SynchronizedSet<E>
          extends SynchronizedCollection<E>
          implements Set<E> {
        private static final long serialVersionUID = 487447009682186044L;

        SynchronizedSet(Set<E> s) {
            super(s);
        }
        SynchronizedSet(Set<E> s, Object mutex) {
            super(s, mutex);
        }

        public boolean equals(Object o) {
            if (this == o)
                return true;
            synchronized (mutex) {return c.equals(o);}
        }
        public int hashCode() {
            synchronized (mutex) {return c.hashCode();}
        }
    }

三、LinkedHashSet

LinkedHashSet是HashSet的子类,但底层跟HashSet有些区别。

(1)默认构造

public LinkedHashSet() {
    super(16, .75f, true);
}

点进super,可以看到底层是初始容量为16,加载因子为0.75的双向链表

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

具体LinkedHashMap如何实现可看上一篇Map源码解析

四、CopyOnWriteArraySet

这个类名字比较牛掰,写时复制Set,也是JUC包中多线程安全的类。

(1)底层结构

public CopyOnWriteArraySet() {    al = new CopyOnWriteArrayList<E>();}

其底层是用CopyOnWriteArrayList实现的。

关于CopyOnWriteArrayList是如何实现的,可具体查看List源码解析

五、TreeSet

TreeSet的底层是TreeMap,而TreeMap底层数据结构是红黑树。

public TreeSet() {
      this(new TreeMap<E,Object>());
  }

在Map源码解析那一篇并没有说TreeMap,那么今天刚好看一下红黑树。

TreeMap的节点结构如下:

class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left;
        Entry<K,V> right;
        Entry<K,V> parent;
        boolean color = BLACK;
 }

红黑树其实就是平衡二叉树,其还有五点定义:

(1)节点是黑色或者红色。

(2)根节点是黑色。

(3)每个红色节点的两个子节点都是黑色节点。

(4)每个叶子的节点都是黑色的空节点(NULL)。

(5)从任意节点到其每个叶子节点的所有路径都包含相同数量的黑色节点。

下图就是一个红黑树

当插入和删除节点的时候,就会破坏红黑树的平衡,此时需要对节点进行变色和旋转以达到平衡。

比如我插入一个节点21 。

可以看到,此时破坏了规则3(每个红色节点的两个子节点都是黑色节点),

此时我们可以进行变色(此时只关注根节点的右子树)

(1)将22变成黑色

此时变色之后破坏了规则5(从任意节点到其每个叶子节点的所有路径都包含相同数量的黑色节点。),比如17->15只有1个黑色节点,17->21有两个黑色节点。

(2)将25变成红色

此时违反了规则3(每个红色节点的两个子节点都是黑色节点),需要把17和27都变成黑色

(3)将17和27变成黑色

可以看到,此时根节点的右子树已经符合其他规则了,但不是平衡树,接下来看下整棵树

可以看到,整棵树是违反规则5的(从任意节点到其每个叶子节点的所有路径都包含相同数量的黑色节点。),比如13->6有2个黑节点,而13->21有3个,所以这是需要进行左旋转。

(4)左旋转,(以13为点,将右子树向上拨,将17作为根节点,将17原有的左子树15节点作为13节点的右子节点)

此时左右子树违反了规则5的(从任意节点到其每个叶子节点的所有路径都包含相同数量的黑色节点。),比如17->7有3个黑色节点,但17->21才2个黑色节点,此时将13进行变色

(5)13变色,13的子节点相应进行变色。

但此时对左子树来说还是不符合规则5(从任意节点到其每个叶子节点的所有路径都包含相同数量的黑色节点。),比如13->1有1个黑色节点,13->6有两个,此时需要右旋转

(6)右旋转(以8为轴点,将13往下拨,变为8的右节点,8原有的右节点11变成13的左节点)

右旋转之后左子树是不符合规则5的(从任意节点到其每个叶子节点的所有路径都包含相同数量的黑色节点。),所以进行将8进行变色:

变色之后的树是符合红黑树的规则了。

以上就是红黑树增加节点的时候,结构重新恢复平衡的步骤。(插入节点默认是红色的)。

红黑树在增删的时候,需要先进行节点变色,如果变色已经解决不了了,就相应进行旋转,旋转之后如果不成功,再重复上述步骤。

上述就是Set源码解析了,顺带也重新了解了一个红黑树。

本文分享自微信公众号 - Liusy01(Liusy_01),作者:Liusy01

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-01-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Redis底层数据结构详解

    上一篇说了Redis有五种数据类型,今天就来聊一下Redis底层的数据结构是什么样的。是这一周看了《redis设计与实现》一书,现来总结一下。(看书总是非常烦躁...

    Liusy
  • 小白初识Zookeeper

    首先,了解一个Zookeeper是什么,其是一个开源的分布式协调服务,分布式数据一致性的解决方案。

    Liusy
  • JDK动态代理详解

    JDK动态代理是代理模式的一种,且只能代理接口。spring也有动态代理,成为CGLib,现在主要来看一下JDK动态代理是如何实现的?

    Liusy
  • Weka中BP神经网络的实践(参数调整以及结果分析)

    本来想的是以理论和实践相结合,前面讲讲神经网络,后面简单讲下在weka中怎么使用BP神经网络,可惜最后时间不够。因为是讲稿,讲的要比写的多,所以很多地方口语化和...

    机器学习AI算法工程
  • NoSQL-Quorums-仲裁

    作者简介: ? 当你权衡“一致性”或“持久性”的时候,不是一个非此即彼,非黑即白的过程。一个请求中涉及的节点越多,那么我们越有可能避免不一致。这自然就引发了一个...

    ImportSource
  • AlphaGo背后的力量:蒙特卡洛树搜索入门指南

    选自int8 Blog 机器之心编译 我们都知道 DeepMind 的围棋程序 AlphaGo,以及它超越人类的强大能力,也经常会听到「蒙特卡洛树搜索」这个概念...

    机器之心
  • JavaScript快速查找节点

    我们在实际的开发中,经常要获取页面中某个html元素,动态更新元素的样式、内容属性等。 ? 我们已经知道在JavaScript中提供下面的方法获取子、父、兄节...

    okaychen
  • RocketMQ 多副本前置篇:初探raft协议

    Raft协议是分布式领域解决一致性的又一著名协议,主要包含Leader选举、日志复制两个部分。

    丁威
  • 【深入学习MySQL】MySQL的索引结构为什么使用B+树?

    在MySQL中,无论是Innodb还是MyIsam,都使用了B+树作索引结构(这里不考虑hash等其他索引)。本文将从最普通的二叉查找树开始,逐步说明各种树解决...

    Java_老男孩
  • 漫画算法:5分钟搞明白红黑树到底是什么?

    红黑树就是一种平衡的二叉查找树,说他平衡的意思是他不会变成“瘸子”,左腿特别长或者右腿特别长。除了符合二叉查找树的特性之外,还具体下列的特性:

    田维常

扫码关注云+社区

领取腾讯云代金券