27.5 Java集合之Set学习(基本概念，存储原理，性能测试)

1.Set接口

在正式学习Set接口之前，我们得先复习一下上面的图片。
我们知道Set接口继承于Collection接口，但是他又有自己的特点，下面我们看一下Set接口不同于Collection的特殊方法定义：

看完源码后，没发现Set中有特殊的方法定义。
1

现在我们思考一下，为何没有呢？ 其实这个问题我们可以思考一下Collection中定义的方法是否能满足Set特性？

1.1 Set的特性是什么？

Set的最大的特性就是存储不重复的元素。
那么我们只需要保证使用Set的add()时具有排重逻辑。 其他的和Collection无异。

注意：我个人认为无序并不是Set的主要特性，无序是Hash存储的特性。

2.具体实现

老规矩，看图复习，然后根据具体的类进行学习。

上面的图片中我们可以看出，实现Set的实现可能有：

HashSet, TreeSet, EnumSet, LinkedHashSet

嗯？ 这不是和HashMap, TreeMap, EnumMap,LinkedHashMap有异曲同工之妙吗？

别着急，更神奇的还在后头！！

2.1 HashSet

通过查阅源码，我们发现了，HashSet中维护的存储结构是HashMap。

2.1.1 存储原理

当进行add(E e)的时候，就会向map中put(e,Object常量)，如果返回的是null,则表示添加成功，如果返回的不是null，则表示Map中已经存在键值对，添加失败。
当进行contains(Object o)的时候，调用的也是Map的containsKey(Object o);

所以HashSet的存储原理就是利用HashMap的键不可重复的特性进行实现的。
由于HashSet借助了HashMap进行存储，所以对其进行存储时无法保证有序存储。

2.1.2 性能测试

//完整代码存放在git仓库中，地址在文章底部
public static void main(String[] args) {
    Set<Integer> set = new HashSet<>();
    long start = System.currentTimeMillis();
    for(int i=0;i<10000000;i++){
        set.add(i);
    }
    System.out.println("存储耗时： "+(System.currentTimeMillis()-start)+" ms");
    long start2 = System.currentTimeMillis();
    for(int i=0;i<10000000;i++){
       boolean c = set.contains(i);
    }
    System.out.println("查询耗时： "+(System.currentTimeMillis()-start2)+" ms");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.2 TreeSet

通过查阅源码，我们可以知道，TreeSet中维护的存储结构是NavigableMap接口，默认实现是TreeMap，
简单来说，TreeSet也是借助TreeMap来进行存储的，TreeMap是Map的有序实现，它会根据键的顺序将元素组织为一个搜索树。

2.2.1 存储原理

当进行add(E e)的时候，就会向map中put(e,Object常量)，如果返回的是null,则表示添加成功，如果返回的不是null，则表示Map中已经存在键值对，添加失败。
当进行contains(Object o)的时候，调用的也是Map的containsKey(Object o);

所以TreeSet的存储原理就是利用TreeMap的键不可重复的特性进行实现的。
由于TreeSet借助了TreeMap进行存储，所以对其进行存储可以保证存储的顺序。

2.2.2 性能测试

//完整代码存放在git仓库中，地址在文章底部
public static void main(String[] args) {
    TreeSet<Integer> set = new TreeSet<>();
    long start = System.currentTimeMillis();
    for(int i=100;i>0;i--){
        set.add(i);
    }
    System.out.println("存储耗时： "+(System.currentTimeMillis()-start)+" ms");
    long start2 = System.currentTimeMillis();
    for(int i=0;i<100;i++){
        boolean c = set.contains(i);
    }
    System.out.println("查询耗时： "+(System.currentTimeMillis()-start2)+" ms");

    for(Integer i:set){
        System.out.print(i+" ");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

可以看到在TreeSet中，存储Integer是自然升序排序的。

2.3 EnumSet（了解即可）

它是一个继承了AbstractSeet的抽象类。
其中一个具体的实现是：RegularEnumSet 它是Set的常规实现, EnumSet的实现并不是一个公共的类，所以它不能作为公共API直接使用。
它是用来存储枚举的Set集合。这个类好像只能存，不能取。

2.3.1 存储原理

我们以RegularEnum为例子进行存储原理的学习。
通过阅读add源码， 我们发现其中关键在于使用了elements这个变量来记录传入的值。

//add操作实际是用位运算，
//将这个long值对应你传入的枚举值的下标的那个bit位改成1，
//比如我传入的是IdentityEnu.DRIVER, 对应的ordinal是1，
//则是将elements的bit位中的第2位改成1，
public boolean add(E e) {
    typeCheck(e);
    long oldElements = elements;
    elements |= (1L << ((Enum<?>)e).ordinal());
    return elements != oldElements;
}
//contains操作就是检查指定位的是否为0来判断
public boolean contains(Object e) {
    if (e == null)
        return false;
    Class<?> eClass = e.getClass();
    if (eClass != elementType && eClass.getSuperclass() != elementType)
        return false;

    return (elements & (1L << ((Enum<?>)e).ordinal())) != 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

比较特殊的一点是，elements用的是long,它只有64位，所以，它存储的枚举类的值不能超过64.

2.4 LinkedHashSet

这个类继承的HashSet，所以它的存储结构仍然是HashMap。查看LinkedHashSet的源码时，你也许会这么想，但是，真的是这样的吗？
但是我们需要实事求是，看下源码到底是怎么运行的：

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

看到这里，我们意识到猜错了，其实LinkedHashSet的存储结构是LinkedHashMap!!
LinkedHashMap是对HashMap的一种增强：
它会记住插入元素的顺序，这样在使用迭代器进行遍历的时候，遍历元素则是有序的。
LinkedHashMap通过重写newNode方法，让其在新创建Node的时候将其插入顺序通过双向链表结构记录下来。

transient LinkedHashMap.Entry<K,V> head;
transient LinkedHashMap.Entry<K,V> tail;
1
2

2.4.1 存储原理

当进行add(E e)的时候，就会向map中put(e,Object常量)，如果返回的是null,则表示添加成功，如果返回的不是null，则表示Map中已经存在键值对，添加失败。
当进行contains(Object o)的时候，调用的也是Map的containsKey(Object o);

所以LinkedHashSet的存储原理就是利用LinkedHashMap的键不可重复的特性进行实现的。
由于LinkedHashSet借助了LinkedHashMap进行存储，所以对其进行存储可以保证存储的顺序。

2.4.2 性能测试

public static void main(String[] args) {

    LinkedHashSet<Integer> set = new LinkedHashSet<>();
    long start = System.currentTimeMillis();
    for(int i=100;i>0;i--){
        set.add(i);
    }
    System.out.println("存储耗时： "+(System.currentTimeMillis()-start)+" ms");
    long start2 = System.currentTimeMillis();
    for(int i=0;i<100;i++){
        boolean c = set.contains(i);
    }
    System.out.println("查询耗时： "+(System.currentTimeMillis()-start2)+" ms");

    for(Integer i:set){
        System.out.print(i+" ");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.4.3 代码地址

Java基础学习/src/main/java/Progress/exa27_5 · 严家豆/Study - 码云 - 开源中国 (gitee.com)