底层实现红黑树_Set源码解析（红黑树）-白红宇的个人博客

底层实现红黑树_Set源码解析（红黑树）

发布日期：2022-02-03 13:16:53 浏览次数：8 分类：技术文章

本文共 3853 字，大约阅读时间需要 12 分钟。

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

主要看以下几个：

(1)HashSet

(2)Collections.synchronizedSet

(3)LinkedHashSet

(4)CopyOnWriteArraySet

(5)TreeSet

一、HashSet

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

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

private transient HashMap
     
       map; //构造一个初始容量16，加载因子是0.75的HashMappublic 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 
     
       Set
      
        synchronizedSet(Set
       
         s) {    return new SynchronizedSet<>(s);}

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

static class SynchronizedSet
     
                extends SynchronizedCollection
      
                 implements Set
       
         {        private static final long serialVersionUID = 487447009682186044L;        SynchronizedSet(Set
        
          s) {            super(s);        }        SynchronizedSet(Set
         
           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
     
      ();}

其底层是用CopyOnWriteArrayList实现的。

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

五、TreeSet

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

public TreeSet() {      this(new TreeMap
     
      ());  }

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

TreeMap的节点结构如下：

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