Set 接口常用实现类底层分析

一、Set 接口

1.1 特点

        无序(添加和取出的顺序不一致),没有索引。不允许重复元素,所以最多包含一个 null

1.2 常用实现类

        HashSetTreeSetCopyOnWriteArraySet

1.3 常用方法

        和 List 接口一样,Set 接口也是 Collection 的子接口,因此,常用方法和 Collection 接口是一样的。   

1.4 遍历方式

        同 Collection 的遍历方式一样,因为 Set 接口是 Collection 接口的子接口。可以使用迭代器、增强 for 循环、但是不能使用索引的方式来获取。

1.5 代码展示

public class SetTest {
    public static void main(String[] args) {
        // Set 接口的实现类对象不能存放重复元素,可以添加一个 null
        // Set 接口对象存放的数据是无序的(添加的顺序和取出的顺序不一致)
        // 注意:取出元素的顺序虽然不是添加的顺序,但是他每次打印顺序都是固定的
        Set set = new HashSet();
        set.add("zhangSan");
        set.add("liSi");
        set.add("zhangSan");
        set.add(null);
        set.add(null);
        System.out.println("set="+set);
        System.out.println("----------------");
        // 遍历的方式一:使用迭代器
        Iterator iterator = set.iterator();
        while (iterator.hasNext()) {
            Object o =  iterator.next();
            System.out.println(o);
        }
        System.out.println("----------------");
        // 遍历的方式二:使用增强for循环
        for (Object o :set) {
            System.out.println(o);
        }
    }
}

二、HashSet

2.1 特点

        HashSet 实现了 Set 接口,可以存放 null,但只能有一个 nullHashSet 不保证元素是有序的,即不保证存放元素的顺序和取出的顺序一致。HashSet 其实是 HashMap,源码如下:

public HashSet() {
    map = new HashMap<>();
}

2.2 底层机制

        HashSet 底层是 HashMap,添加一个元素的时候,会先使用 hashCode() 方法计算该元素的 hash 值。然后对 hash 值进行运算得到一个索引值,这个索引值即为要存放在哈希表的位置号。

        如果该位置上没有其他元素,则直接存放;如果该位置上已经有其他元素了,则需要进行 equals 判断(equals 方法一般都需要根据业务进行重写),如果相等,则不再添加,如果不相等,则以链表的形式添加到后面。

2.3 扩容机制

        HashSet 底层是 HashMap,第一次添加元素的时候,table 数组扩容到 16,临界值 = 16 * 0.75 = 12;即临界值  = 容量 * 加载因子

        如果 table 数组使用到了临界值 12 ,就会扩容到 16 * 2 = 32,新的临界值就是 32 * 0.75 = 24,依次类推。

2.4 转红黑树机制

        在 java8 中,如果一条链表的元素个数到达 8 个,此时 table 数组的长度是 16,那么此时就会发生数组扩容,此时的状态为:链表长度为 8table 数组的长度为 32;此时再向链表里面添加元素,又会发生扩容,此时的状态为:链表长度为 9table 数组的长度为 64;此时再向链表里面添加元素,就会触发树化,即这一条链表变为红黑树,其他的链表不受任何影响。

        在 java8 中,如果一条链表的元素个数到达 TREEIFY_THRESHOLD (默认是 8 ) 并且 table 数组的大小 >= MIN_TREEIF_CAPACITY(默认是 64),就会进行树化,否则仍然采用数组的扩容机制。

2.5 习题练习

2.5.1 简单

        定义一个 Employee 类,该类包含 private 成员属性 name age,要求:创建 3 个 Employee 对象放入 HashSet 中,当 name age 的值相同时,认为是相同员工,不能添加到 HashSet 中。代码如下:

public class Employee{

    private String name;
    private int age;

    public Employee(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public Employee() {
    }

   // setter、getter、toString()

    // 重写 hashCode 方法,因为这三个元素的 hashCode 都不一样
    @Override
    public int hashCode() {
        String name = this.getName();
        int  age = this.getAge();
        int nameCode = name.hashCode();
        int result = age + nameCode;
        return result;
    }
    // 重写 equals 方法,若 name 和 age 相同就认为是同一个元素
    @Override
    public boolean equals(Object obj) {
        Employee employee =(Employee)obj;
        if(this.getName() == employee.getName() && this.getAge() == employee.getAge()){
            return true;
        }else{
            return false;
        }
    }
}

        测试代码类如下:

public class Test {
    public static void main(String[] args) {

        Set set = new HashSet();

        Employee e1 = new Employee("张三",18);
        Employee e2 = new Employee("李四",18);
        Employee e3 = new Employee("张三",18);
        set.add(e1);
        set.add(e2);
        set.add(e3);

        System.out.println("set = "+set);
    }
}

2.5.2 复杂

        定义一个 Employee 类,该类包含 private 成员属性 name、sal 和 birthday,其中 birthady MyDate 类型(属性包括:yearmonthday)。要求

        1、创建 3 个 Employee 对象放入 HashSet

        2、当 name birthday 的值相同时,认为是相同员工,不能添加到 HashSet 集合中。

public class MyDate {

    private int year;
    private int month;
    private int day;

    public MyDate(int year, int month, int day) {
        this.year = year;
        this.month = month;
        this.day = day;
    }
   // setter、getter、toString()
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        MyDate myDate = (MyDate) o;
        return year == myDate.year && month == myDate.month && day == myDate.day;
    }
    @Override
    public int hashCode() {
        return Objects.hash(year, month, day);
    }
}
class Employee {

    private String name;
    private String sal;
    private MyDate birthday;

   // getter、setter、toString()

    public Employee(String name, String sal, MyDate birthday) {
        this.name = name;
        this.sal = sal;
        this.birthday = birthday;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Employee employee = (Employee) o;
        return Objects.equals(name, employee.name)  && Objects.equals(birthday, employee.birthday);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, birthday);
    }
}
public class Test {
    public static void main(String[] args) {
        Set set = new HashSet();

        set.add(new Employee("张三","30",new MyDate(1992,8,19)));
        set.add(new Employee("李四","30",new MyDate(1993,8,19)));
        set.add(new Employee("张三","50",new MyDate(1992,8,19)));

        System.out.println("set =" + set);
    }
}

三、LinkedHashSet

3.1 特点

        LinkedHashSet HashSet 的子类,LinkedHashSet 底层是一个 LinkedHashMap,底层维护了一个数组+双向链表

        LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置,同时使用链表维护元素的次序,这使得元素看起来是以插入顺序保存的。也是不允许插入重复元素。

3.2 底层机制

        LinkedHashSet 中维护了一个 hash 表和双向链表(LinkedHashSet head tail),每一个节点有 before after 属性,这样就形成了双向链表。

        在添加一个元素时,先求 hash 值再求索引,根据索引确定元素在 table 表中的位置,然后将添加的元素加入到双向链表(如果已经存在则不添加)。

        这样的话,我们遍历 LinkedHashSet 也能确保插入顺序和遍历顺序一致。

3.3 扩容机制

        LinkedHashSet 的底层结构为数组 + 双向链表。第一次添加元素的时候,直接将数组 table 扩容到 16。临界值 = 16 * 0.75 = 12;即 临界值  = 容量 * 加载因子

        如果 table 数组使用到了临界值 12 ,就会扩容到 16 * 2 = 32,新的临界值就是 32 * 0.75 = 24,依次类推。

3.4 转红黑树机制

        在 java8 中,如果一条链表的元素个数到达 8 个,此时 table 数组的长度是 16,那么此时就会发生数组扩容,此时的状态为:链表长度为 8table 数组的长度为 32;此时再向链表里面添加元素,又会发生扩容,此时的状态为:链表长度为 9table 数组的长度为 64;此时再像链表里面添加元素,就会触发树化,即这一条链表变为红黑树,其他的链表不受任何影响。

        在 java8 中,如果一条链表的元素个数到达 TREEIFY_THRESHOLD (默认是 8 ) 并且 table 数组的大小 >= MIN_TREEIF_CAPACITY(默认是 64),就会进行树化,否则仍然采用数组的扩容机制。

3.5 LinkedHashSet 和 HashSet 比较

        LinkedHashSet 和 HashSet 相比,唯一的变化就是由单向链表变成了双向链表,这样做的好处是保证了元素的顺序性。

3.6 习题练习

        有一个 Car 类(属性为 name price),如果 name price 一样,则认为是相同元素,就不能添加。

class Car {
    private String name;
    private String price;

    public Car(String name, String price) {
        this.name = name;
        this.price = price;
    }
   // setter、getter、toString()

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Car car = (Car) o;
        return Objects.equals(name, car.name) && Objects.equals(price, car.price);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, price);
    }
}
public class TestLink {
    public static void main(String[] args) {
        Set set = new LinkedHashSet();

        set.add(new Car("小汽车","30"));
        set.add(new Car("小玩偶","40"));
        set.add(new Car("小汽车","30"));

        System.out.println("set="+set);
    }
}

四、TreeSet

4.1 特点

4.1.1 无参构造

        当我们使用无参构造器创建 TreeSet 时,属于自然排序,当进行去重操作时,会调用 key 默认实现的 Comparable 类的 compareTo() 方法进行去重。

public class TreeSetTest {
    public static void main(String[] args) {
        TreeSet treeSet = new TreeSet();
        // 添加元素
        // 未指定排序方式时会调用 String 本身的 Comparable 类的 compare() 方法进行排序和去重
        treeSet.add("jack");
        treeSet.add("tom");
        treeSet.add("sp");
        treeSet.add("a");
        System.out.println("treeSet="+treeSet);
    }
}

public static void main(String[] args) {
	TreeSet<Object> set = new TreeSet<>();
    // 当执行add 方法时会报错,因为 TreeSet() 构造器没有传入 Comparator 接口的匿名内部类
    // jvm 会尝试着把 Person 对象转换成 Comparable 类型,但是 Person  类并没有实现 Comparator 接口
    // 所以下面的代码会报 ClassCastExecption
	set.add(new Person())
}

4.1.2 有参构造

        TreeSet 提供了一个有参的构造器,可以传入一个比较器(匿名内部类)并指定排序规则。

public class TreeSetTest {
    public static void main(String[] args) {
        TreeSet treeSet = new TreeSet(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                // 下面调用 String 的 compareTo 方法进行字符串大小比较
                return ((String)o1).compareTo((String)o2);
            }
        });
        // 添加元素
        treeSet.add("jack");
        treeSet.add("tom");
        treeSet.add("sp");
        treeSet.add("a");
        System.out.println("treeSet="+treeSet);
    }
}

4.2 底层机制

         构造器把传入的比较器对象,赋给了 TreeSet 的底层为 TreeMap 的属性,在添加元素的时候会调用我们实现的匿名内部类里面指定的排序方法 compare()

        compare() 方法执行完毕后会返回一个 int 类型的结果,若结果小于 0 ,则该元素放在比较元素左边;若结果大于 0,则该元素放在比较元素右边;若结果等于 0,数据不添加进去。

4.3 习题演练

        现在我想要按照长度大小排序,该如何写呢?如下

public class TreeSetTest {
    public static void main(String[] args) {
        TreeSet treeSet = new TreeSet(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                // 按照长度大小排序
                return ((String)o1).length()-((String)o2).length();
            }
        });
        // 添加元素
        treeSet.add("jack");
        treeSet.add("tom");
        treeSet.add("sp");
        treeSet.add("a");
        // 此时 abc 元素是无法添加进去的,因为 tom 的长度也为 3,compare() 方法返回 0 了,认为是相同元素
        treeSet.add("abc");
        System.out.println("treeSet="+treeSet);
    }
}