Set

苓渊大约 3 分钟

What's Set?

HashSet

HashSet 是 Set 接口的具体实现类。

底层数据结构基于哈希表，是在内部维护一个 HashMap 对象，将所有的数据都交给 HashMap 进行处理。

特性：

元素无序排列。
元素不可重复。依赖两个方法来保证元素唯一性： hashCode() 和 equals().
可以存 null 值，因为底层是 HashMap，可以有 1 个为 null 的元素。
没有实现同步，线程不安全。

LinkedHashSet

LinkedHashSet 是 Set 接口的具体实现类，是 HashSet 的子类。

底层数据结构基于双向列表和哈希表，是对 LinkedHashMap 包装了一层。

适用于对元素的添加顺序读取有要求的场景，如 FIFO，插入性能略低于 HashSet，但在迭代访问 set 里面的全部元素时有很好的性能。

特性：

元素有序排列，底层维护了一个数组 + 双向链表，根据元素的 hashCode 值来决定元素的存储位置，同时使用链表维护元素的次序, 使元素看起来是以插入顺序保存的。
元素不可重复，基于 HashMap 实现元素唯一。
可以存储 null 值，因为底层是 LinkedHashMap，允许存在一个为 null 的元素。
线程不安全。

TreeSet

TreeSet 是 Set 接口的具体实现类。

底层数据结构基于红黑树，是基于 TreeMap 的实现。

add、remove、search等操作时间复杂度为 O(log n)，效率不如 HashSet 的 O(1).

特性：

元素有序排列，根据树结构实现有序性，不按输入顺序排列，默认是按自然顺序排列，也可以自定义排序规则，根据比较器确认排序顺序。
元素不可重复，根据比较的返回值是否是 0 来保证元素唯一性。
JDK8 后元素不允许设置 null 值。TreeSet 不能有 key 为 null 的元素。
线程不安全。

自定义排序规则

TreeSet 添加对象时，如果元素无法按自然顺序排列则报错，

此时需自定义排序规则：使实体类实现 Comparable 接口，实现 compareTo 方法。

public class Person implements Comparable{

    private double grade;
    private int age;
    private String name;

    // 省略 get / set

    /*
     *  返回值规则：
     *  负数：表示后面元素大，即调用者小于参数
     *  正数：表示前面元素大，即调用者大于参数
     *  0：相等
     * */
    @Override
    public int compareTo(Object o) {
        if (this ==o ){
            // 内存地址值相等
            return 0;
        }
        
        if (o instanceof Person){
            if (this == o){
                return 0;
            }
            Person p = (Person)o;
            // 先比较分数
            if (this.grade < p.getGrade()){
                return -1;
            } else if (this.grade > p.getGrade()){
                return 1;
            }else{
                // 分数相等，比较年龄
                if (this.getAge() < p.getAge()){
                    return -1;
                }else if (this.getAge() > p.getAge()){
                    return 1;
                }else{
                    // 年龄相等，比较姓名
                    return this.getName().compareTo(p.getName());
                }
            }
        }
        return 0;
    }
}

ArraySet

Android.util.ArraySet 是 Set 接口的具体实现类，底层数据结构是双数组，实现了有序、实时扩容。

ArraySet 通过调用 System 提供的本地（native）静态方法 arraycopy() 实现数组之间的复制。采取一种用时间换取内存空间的优化思路，其元素扩容是时刻变化的，会随时根据内容动态调整数组的大小。

因为每次操作都要实现数组复制，会影响到元素操作的效率。理论上来说，在大数据量的情况下，更频繁的数据条数大幅度变化下，效率会变低。但实际上，在数万条数据的情况下，速度相差无几。

利用Set去重

/**
 * 统计字符出现的次数
 */
public void statistics(){
    String s1 = "leeLuoUpperWater";
    HashSet<Character> hs = new HashSet<Character>();
    //将字符串插入到 Set 集合，利用 Set 集合去重复的特性找到出现过的字符
    for (int i = 0; i < s1.length(); i++) {
        hs.add(s1.charAt(i));
    }
    // 用出现过的字符与字符串对比
    for (Character s2 : hs) {
        int num = 0;
        for (int i = 0; i < s1.length(); i++) {
            if (s2.equals(s1.charAt(i))){
                num++;
            }
        }
        System.out.println(s2 + "出现" + num + "次");
    }
}