1 HashSet

1.1 类注释

看源码先看类注释上,我们可以得到的信息有:

底层实现基于HashMap,所以迭代时不能保证按照插入顺序,或者其它顺序进行迭代;
add、remove、contains、size等方法的耗时性能,是不会随着数据量的增加而增加的,这个主要跟HashMap底层的数组数据结构有关,不管数据量多大,不考虑hash冲突的情况下,时间复杂度都是O(1);
线程不安全的,如果需要安全请自行加锁,或者使用Collections.synchronizedSet;
迭代过程中,如果数据结构被改变,会快速失败的,会抛出ConcurrentModificationException异常。

我们之前也看过List、Map的类注释,我们发现2、3、4点信息在类注释中都有提到,所以如果有人问List、Map、Set三者的共同点,那么就可以说2、3、4三点。

1.2 HashSet是如何组合HashMap的

刚才从类注释1中看到,HashSet的实现是基于HashMap的,在Java中,要基于基础类进行创新实现,有两种办法:

继承基础类,覆写基础类的方法,比如说继承HashMap,覆写其add的方法;
组合基础类,通过调用基础类的方法,来复用基础类的能力。

HashSet使用的就是组合HashMap,其优点如下:

继承表示父子类是同一个事物,而Set和Map本来就是想表达两种事物,所以继承不妥,而且Java语法限制,子类只能继承一个父类,后续难以扩展。
组合更加灵活,可以任意的组合现有的基础类,并且可以在基础类方法的基础上进行扩展、编排等,而且方法命名可以任意命名,无需和基础类的方法名称保持一致。

我们在工作中,如果碰到类似问题,我们的原则也是尽量多用组合,少用继承。

组合就是把HashMap当做自己的一个局部变量,以下是HashSet的组合实现:

// 把 HashMap 组合进来，key 是 Hashset 的 key，value 是下面的 PRESENT
private transient HashMap<E,Object> map;
// HashMap 中的 value
private static final Object PRESENT = new Object();

从这两行代码中,我们可以看出两点:

我们在使用HashSet是,比如add方法,只有一个入参,但组合的Map的add方法却又key,value两个入参,相对应上Map的key就是我们add的入参,vaslue就是第二行代码中的PRESENT,此处设计非常巧妙,用一个默认值PRESENT来代替Map的Value;
如果HashSet是被共享的,当多个线程访问的时候,就会有线程安全问题,因为在后序的所有操作中,并没有加锁。

HashSet在以HashMap为基础进行实现的时候,首先选择组合方式,接着使用默认值来代替了Map中的value值,设计的非常巧妙,给使用者的体验很好,使用起来简单方便,我们在工作中也可以借鉴这种思想,可以把底层复杂实现包装一下,一些默认实现可以自己吃掉,使吐出去的接口尽量简单好用。

1.2.1 初始化

HashSet的初始化比较简单,直接 new HashMap 即可,比较有意思的是,当有原始集合数据进行初始化的情况下,会对HashMap的初始容量进行计算,源码如下:

// 对 HashMap 的容量进行了计算
public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

上述代码中: Math.max((int)(c.size()/.75f)+1,16),就是对HashMap的容量进行了计算,翻译成中文就是取括号中两个数的最大值(期望的值/0.75+1,默认值16),从计算中,我们可以看出HashSet的实现者对HashMap的底层实现是非常清楚的,主要体现在两个方面:

和16比较大小的意思是说,如果给定HashMap初始容量小于16,就按照HashMap默认的16初始化好了,如果大于16,就按照给定值初始化。
HashMap扩容的阈值的计算公式是: Map的容量 * 0.75f,一旦达到阈值就会扩容,此处用(int)(c.size/.75f)+1来表示初始化的值,这样使我们期望的大小值正好比扩容的阈值还大,就不会扩容,符合HashMap扩容的公式。

从简单的构造器中,我们就可以看出要很好的组合api接口,并没有那么简单,我们可能需要去了解一下被组合的api底层的实现,这样才能用好api。

1.2.2 小结

HashSet 具体实现值得我们借鉴的地方主要有如下地方,我们平时写代码的时候,完全可以参考参考:

对组合还是继承的分析和把握;
对复杂逻辑进行一些包装,使吐出去的接口尽量简单好用;
组合其他api时,尽量多对组合的api多些了解,这样才能更好的使用api;
HashMap初始化大小值的模板公式: 取括号内两者的最大值(期望的值/0.75+1,默认值16)。

2 TreeSet

TreeSet大致的结构和HashSet相似,底层组合的是TreeMap,所以继承了TreeMap key能够排序的功能,迭代的时候,也可以按照key的排序顺序进行迭代,我们主要来看复用TreeMap时,复用的两种思路:

2.1 复用TreeMap的思路一

场景一: TreeSet的add方法,我们来看下其源码:

public boolean add(E e) {
    return m.put(e, PRESENT)==null;
}

可以看到,底层直接使用的是HashMap的put的能力,直接拿来用就好了。

2.2 复用TreeMap的思路二

场景二: 需要迭代TreeSet中的元素,那应该也是像add那样,直接使用HashMap已有的迭代能力,比如像下面这样:

// 模仿思路一的方式实现
public Iterator<E> descendingIterator() {
    // 直接使用 HashMap.keySet 的迭代能力
    return m.keySet().iterator();
}

这种是思路一的实现方式,TreeSet组合TreeMap,直接选择TreeMap的底层能力进行包装,但TreeSet实际执行的思路却完全相反,我们看源码:

// NavigableSet 接口，定义了迭代的一些规范，和一些取值的特殊方法
// TreeSet 实现了该方法，也就是说 TreeSet 本身已经定义了迭代的规范
public interface NavigableSet<E> extends SortedSet<E> {
    Iterator<E> iterator();
    E lower(E e);
}  
// m.navigableKeySet() 是 TreeMap 写了一个子类实现了 NavigableSet
// 接口，实现了 TreeSet 定义的迭代规范
public Iterator<E> iterator() {
    return m.navigableKeySet().iterator();
}

TreeMap 中对NavigableSet 接口的实现源码截图如下：

从截图中（截图是在 TreeMap 中），我们可以看出 TreeMap 实现了 TreeSet 定义的各种特殊方法。

我们可以看到,这种思路是TreeSet定义了接口的规范,TreeMap负责去实现,实现思路和思路一是相反的。

我们总结下TreeSet组合TreeMap实现的两种思路:

TreeSet直接使用TreeMap的某些功能,自己包装成新的api。
TreeSet定义自己想要的api,自己定义接口规范,让TreeMap去实现。

方案 1 和 2 的调用关系，都是 TreeSet 调用 TreeMap，但功能的实现关系完全相反，第一种是功能的定义和实现都在 TreeMap，TreeSet 只是简单的调用而已，第二种 TreeSet 把接口定义出来后，让 TreeMap 去实现内部逻辑，TreeSet 负责接口定义，TreeMap 负责具体实现，这样子的话因为接口是 TreeSet 定义的，所以实现一定是 TreeSet 最想要的，TreeSet 甚至都不用包装，可以直接把返回值吐出去都行。

我们思考下这两种复用思路的原因：

像 add 这些简单的方法，我们直接使用的是思路 1，主要是 add 这些方法实现比较简单，没有复杂逻辑，所以 TreeSet 自己实现起来比较简单；
思路 2 主要适用于复杂场景，比如说迭代场景，TreeSet 的场景复杂，比如要能从头开始迭代，比如要能取第一个值，比如要能取最后一个值，再加上 TreeMap 底层结构比较复杂，TreeSet 可能并不清楚 TreeMap 底层的复杂逻辑，这时候让 TreeSet 来实现如此复杂的场景逻辑，TreeSet 就搞不定了，不如接口让 TreeSet 来定义，让 TreeMap 去负责实现，TreeMap 对底层的复杂结构非常清楚，实现起来既准确又简单。

2.3 小结

TreeSet 对 TreeMap 的两种不同复用思路，很重要，在工作中经常会遇到，特别是思路二，比如说 dubbo 的泛化调用，DDD 中的依赖倒置等等，原理都是 TreeSet 第二种的复用思想。

HashSet、TreeSet源码解析