Set源码解析（红黑树）

Liusy

发布于 2020-08-31 13:54:28

4770

发布于 2020-08-31 13:54:28

文章被收录于专栏：Liusy01 Liusy01Liusy01

之前粗略看了一下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)从任意节点到其每个叶子节点的所有路径都包含相同数量的黑色节点。

下图就是一个红黑树