集合深度学习07—Set、HashSet、LinkedHashSet、TreeSet、 底层原理 & 源码解析

一、Set接口

特点：

1. 唯一
2. 无序（相对List接口部分来说的，无序不等于随机）
3. 没有索引相关的方法

遍历方式：

1. 迭代器
2. 增强 for 循环（底层还是 Itr 迭代器）

二、HashSet

1. HashSet的特点

1. add方法添加 成功返回 true，失败则 false

• 注意！对于自定义的数据类型没有 唯一，无序效果。
• 只有系统给的类型，才符合特点。
• 为什么呢？？？？？

2. HashSet的简要原理

HashSet需要根据 hashCode 计算 哈希值，然后使用 equals 比较，放在底层数组中，处理哈希冲突的方法是链地址。
所以 哈希表 = 数组 + 链表

所以为什么 我们 自定义的类 使用HashSet装的时候不能 无序、不重复 知道了吧。

因为没有重新写 hashCode 和 equals 方法。
没有哈希值，又不能比较，怎么做到无序，没法，所以自定义的类才不能 无序、不重复

3. 问题

1.数组的长度是多少。
2.数组的类型是什么？
3.hashCode，equals方法真的调用了吗？验证
4.底层表达式是什么？
5.同一个位置的数据 向前放 还是 向后放？
6.放入数组中的数据，是直接放的吗？是否封装为对象了？

4. 实现原理

底层就是一个HashMap

public class HashSet<E>{
    //重要属性：
    private transient HashMap<E,Object> map;
    private static final Object PRESENT = new Object();
    //构造器：
    public HashSet() {
        map = new HashMap<>();//HashSet底层就是利用HashMap来完成的
    }
        
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }      
}
1
2
3
4
5
6
7
8
9
10
11
12
13

三、LinkedHashSet的使用

特点：

1. 唯一
2. 有序（按照输入顺序进行输出 ）

其实就是在HashSet的基础上，多了一个总的链表，这个总链表将放入的元素串在一起，方便有序的遍历。

四、TreeSet的使用

特点：

1. 唯一
2. 有序（升序）

底层逻辑结构 ： 二叉树
二叉树底层是按中序遍历，所以结果是升序。

系统提供的类型都重写了compare方法，如果自定义类型也想排序存储，需要重写compare比较器接口。

默认TreeSet会使用内部比较器, 自定义类重写 compare方法

public class Student implements Comparable<Student> {
    private int age;
    private String name;
	// get / set / 构造方法省略

    @Override
    public String toString() {
        return "Student{" +
                "age=" + age +
                ", name='" + name + '\'' +
                '}';
    }
   
    @Override
    public int compareTo(Student o) {
        return this.getAge()-o.getAge();
    }
}

public class Test03 {
    //这是main方法，程序的入口
    public static void main(String[] args) {
        //创建一个TreeSet:
        TreeSet<Student> ts = new TreeSet<>();
        ts.add(new Student(10,"elili"));
        ts.add(new Student(8,"blili"));
        ts.add(new Student(4,"alili"));
        ts.add(new Student(9,"elili"));
        ts.add(new Student(10,"flili"));
        ts.add(new Student(1,"dlili"));
        System.out.println(ts.size());
        System.out.println(ts);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

一旦指定外部比较器，那么就会按照外部比较器来比较。比较器类 实现 Comparator 接口，重写 compare 方法。在 TreeSet 的构造方法中传入 比较器对象。

public class Student  {
    private int age;
    private String name;
    
  	// get / set / 构造方法省略 
  	
    @Override
    public String toString() {
        return "Student{" +
                "age=" + age +
                ", name='" + name + '\'' +
                '}';
    }
}
class BiJiao implements Comparator<Student>{
    @Override
    public int compare(Student o1, Student o2) {
        return o1.getName().compareTo(o2.getName());
    }
}


public class Test03 {
    //这是main方法，程序的入口
    public static void main(String[] args) {
        //创建一个TreeSet:
        //利用外部比较器，必须自己制定：
        Comparator<Student> com = new BiJiao();
        TreeSet<Student> ts = new TreeSet<>(com);//一旦指定外部比较器，那么就会按照外部比较器来比较
        ts.add(new Student(10,"elili"));
        ts.add(new Student(8,"blili"));
        ts.add(new Student(4,"alili"));
        ts.add(new Student(9,"elili"));
        ts.add(new Student(10,"flili"));
        ts.add(new Student(1,"dlili"));
        System.out.println(ts.size());
        System.out.println(ts);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

实际开发中多用外部比较器，接口比类扩展性好。

TreeSet源码

底层就是 TreeMap,值也是 PRESENT对象present，是个Object对象

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable{
                //重要属性：
                private transient NavigableMap<E,Object> m;
                private static final Object PRESENT = new Object();
                
                //在调用空构造器的时候，底层创建了一个TreeMap
                public TreeSet() {
                        this(new TreeMap<E,Object>());
                }
                
                TreeSet(NavigableMap<E,Object> m) {
                        this.m = m;
                }
                
                public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20