[Java知识库]Java集合框架图析（Collection-Set）

Java集合框架图析（Collection-Set）

一、前言

前面在Java集合框架图析（Collection-List）中主要总结了List相关的ArrayList和LinkedList，这章总结Set知识点。

Set 集合也实现了 Collection 接口，它主要有两个实现类：HashSet类和 TreeSet类。Set 集合中的对象不按特定的方式排序，只是简单地把对象加入集合，集合中不能包含重复的对象，并且最多只允许包含一个 null 元素。

1.Set框架图：

HashSet和TreeSet是Set的两个典型实现，HashSet的性能总是比TreeSet要好，因为TreeSet需要额外的红黑树算法来维护集合元素的次序。只有当需要一个保持次序的Set时，才应该使用TreeSet，否则都应该使用HashSet。HashSet的子类LinkedHashSet由于需要维护链表，普通操作比如插入、删除会比HashSet稍微慢一些，但是遍历LinkedHashSet会更快。
HashSet有一个LinkedHashSet子类，用hashCode决定存储位置，同时采用链表维护元素次序。当遍历LinkedHashSet时，元素的顺序跟存储时的顺序一致。

二、HashSet 类

实现Set接口，由哈希表（实际上是HashMap实例）支持。 它不保证集合的迭代顺序; 特别是，它不保证订单会随着时间的推移保持不变。 此类允许null元素。 HashSet 利用 HashMap 中的key元素来存放元素，源码可以看出：

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable{

	private transient HashMap<E,Object> map;
    
    // HashMap 变量
    private transient HashMap<E,Object> map;
    
    /**HashSet 初始化*/
    public HashSet() {
        //默认实例化一个 HashMap
        map = new HashMap<>();
    }
}

2.1 构造方法

2.2 常用方法

2.3 add()方法

源码中：

public boolean add(E e) {
		//向 HashMap 中添加元素
        return map.put(e, PRESENT)==null;
    }

//其中变量PRESENT，是一个非空对象
private static final Object PRESENT = new Object();

可以看出在HashSet中，进行add()添加元素等等价于

HashMap map = new HashMap<>();
//e 表示要添加的元素
map.put(e, new Object());

HashMap 在添加元素的时候 ，通过equals()和hashCode()方法来判断传入的key是否相同，如果相同，那么 HashMap 认为添加的是同一个元素，反之，则不是。

从源码上可以分析出，HashSet 正是使用了 HashMap 的这一特性，实现存储元素下标无序、元素不会重复的特点。

2.4 remove()方法

HashSet 的删除方法，同样如此，也是基于 HashMap 的底层实现
源码：

public boolean remove(Object o) {
		调用HashMap 的remove方法，移除元素
        return map.remove(o)==PRESENT;
    }

2.5 查询方法

HashSet 没有像 List、Map 那样提供 get 方法，但是可以通过使用迭代器或者 for 循环来遍历元素

public class demo01 {
    public static void main(String[] args) {
        HashSet<String> bookSet = new HashSet<String>(); // 创建一个空的 Set 集合
        String book1 = new String("Java");
        String book2 = new String("Python");
        String book3 = new String("C++");
        String book4 = new String("PHP");
        bookSet.add(book1); // 将 book1 存储到 Set 集合中
        bookSet.add(book2); // 将 book2 存储到 Set 集合中
        bookSet.add(book3); // 将 book3 存储到 Set 集合中
        bookSet.add(book3); // 将 book3 存储到 Set 集合中
        bookSet.add(book4); // 将 book4 存储到 Set 集合中
        bookSet.add(book4); // 将 book4 存储到 Set 集合中
        bookSet.add(null); // 将 null 存储到 Set 集合中

        System.out.println("新进图书有：");
        
        //增强for循环
        for (String s : bookSet) {
            System.out.println(s);
        }
		
		//迭代器
        Iterator<String> it = bookSet.iterator();
        while (it.hasNext()) {
            System.out.println("《" + (String) it.next() + "》"); // 输出 Set 集合中的元素
        }
        //相同元素会自动覆盖
        System.out.println("共采购 " + bookSet.size() + " 本图书！");
    }
}

输出结果：

新进图书有：
《null》
《Java》
《C++》
《PHP》
《Python》
共采购 5 本图书！

Process finished with exit code 0

需要注意的是HashSet是可以添加null元素的。

三、LinkedHashSet类

3.1 LinkedHashSet简介

LinkedHashSet是Set集合的一个实现，继承自HashSet，但是底层基于 LinkedHashMap 来实现具有set集合不重复的特点，同时具有可预测的迭代顺序，也就是我们插入的顺序。

3.2 构造方法

结合源码看一下：

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {

    public LinkedHashSet() {
        //调用 HashSet 的方法
        super(16, .75f, true);
    }
}

从源码看super()调用的方法:

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    //初始化一个 LinkedHashMap
    // LinkedHashSet里面有一个LinkedHashMap
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

3.3 add()方法

LinkedHashSet没有重写add方法，而是直接调用HashSet的add()方法，又因为map的实现类是LinkedHashMap,所以此处是向LinkedHashMap中添加元素，当进行add()的时候，等价于

HashMap map = new LinkedHashMap<>();
//e 表示要添加的元素
map.put(e, new Object());

3.4 remove()方法

LinkedHashSet中同样没有重写remove()方法，因此直接调用HashSet的删除方法，因为LinkedHashMap没有重写remove方法，所以调用的也是HashMap的remove方法，也可以选择实现Set类中的remove()方法，因为LinkedHashSet继承于HashSet，实现Set<E>接口，源码如下：

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
}

public boolean remove(Object o) {
    //调用HashMap 的remove方法，移除元素
    return map.remove(o)==PRESENT;
}

3.5 查询方法

同样的，LinkedHashSet 没有提供 get 方法，使用迭代器或者 for 循环来遍历元素，实例如下:

public class demo01 {
    public static void main(String[] args) {
        Set<String> linkedHashSet = new LinkedHashSet<String>();
        System.out.println("linkedHashSet初始容量大小："+linkedHashSet.size());
        linkedHashSet.add("111111");
        linkedHashSet.add("222");
        linkedHashSet.add("3333");
        linkedHashSet.add("3333");
        linkedHashSet.add("222");
        linkedHashSet.add(null);
        linkedHashSet.add(null);

        System.out.println("linkedHashSet容量大小："+linkedHashSet.size());
        
        //迭代器遍历
        Iterator<String> iterator = linkedHashSet.iterator();
        while (iterator.hasNext()){
            String str = iterator.next();
            System.out.print(str + ",");
        }

        System.out.println("\n===========");
        
        //增强for循环
        for (String str : linkedHashSet) {
            System.out.print(str + ",");
        }
    }
}

测试结果：

linkedHashSet初始容量大小：0
linkedHashSet容量大小：4
111111,222,3333,null,
===========
111111,222,3333,null,
Process finished with exit code 0

可以看出同HashSet相比，LinkedHashSet是输入输出有序的。

四、TreeSet

4.1 TreeSet简介

TreeSet 是一个排序的集合，实现了NavigableSet、SortedSet、Set接口，底层基于 TreeMap 来实现。源码如下：

public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable {
    
    //TreeSet 使用NavigableMap接口作为变量
    private transient NavigableMap<E,Object> m;
    
    //构造方法
    public TreeSet() {
        //默认实例化一个 TreeMap 对象
        this(new TreeMap<E,Object>());
    }
    
    //对象初始化调用的方法
    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }
}

4.2 构造方法

4.3 常用方法

4.4 add()方法

源码中的add()方法如下:

public boolean add(E e) {
		//向 TreeMap 中添加元素
        return m.put(e, PRESENT)==null;
    }

其中变量PRESENT,是一个Object对象，源码如下：

// Dummy value to associate with an Object in the backing Map
 private static final Object PRESENT = new Object();

其实就等同于用了底层的TreeMap，向TreeMap中add了一个元素；

TreeMa map = new TreeMap<>();
//e 表示要添加的元素
map.put(e, new Object());

TreeSet的自动排序，其实是根据TreeMap会自动将Key按照一定规则排序，因此TreeSet在add添加元素到集合，输出的时候结果已经排序了。

TreeSet是不能添加空元素的，如果添加null的话将会报错：

4.5 remove()方法

同样是基于TreeMap的底层实现的：

public boolean remove(Object o) {
        //调用TreeMap 的remove方法，移除元素
        return m.remove(o)==PRESENT;
}

4.6 查询方法

同样没有重写get方法，需要迭代器或者for循环遍历元素
实例测试：

public class demo01 {
    public static void main(String[] args) {
        TreeSet<String> treeSet = new TreeSet<>();
        System.out.println("treeSet初始容量大小："+treeSet.size());
        treeSet.add("11");
        treeSet.add("22");
        treeSet.add("33");
        treeSet.add("44");
        treeSet.add("55");

        System.out.println("treeSet容量大小："+treeSet.size());
        
        //迭代器遍历
        Iterator<String> iterator = treeSet.iterator();
        while (iterator.hasNext()){
            String str = iterator.next();
            System.out.print(str + ",");
        }

        System.out.println("\n===========");
        
        //增强for循环
        for (String str : treeSet) {
            System.out.print(str + ",");
        }
    }
}

测试结果：

treeSet初始容量大小：0
treeSet容量大小：5
11,22,33,44,55,
===========
11,22,33,44,55,
Process finished with exit code 0

五、总结

• HashSet 为快速查找设计的Set。存入HashSet的对象必须定义hashCode()，对象需要重写 equals() 和 hashCode() 方法来约束是否为相同的元素。
• LinkedHashSet能实现输入输出有序，元素可以为空，底层原理是LinkedHashMap 保存次序的Set, 底层为树结构。使用它可以从Set中提取有序的序列。
• TreeSet 具有HashSet的查询速度，且内部使用链表维护元素的顺序(插入的次序)底层基于 TreeMap 的 key来实现，元素不可以为空，默认按照自然排序来存放元素，也可以使用 Comparable 和 Comparator 接口来比较大小，实现自定义排序。