JZTXT

set接口

发布时间 2023-04-14 07:19:31作者: Jimmyhus

set接口

HashSet里面有一个HashMap(适配器模式)。
Set的接口和他的实现类都是基于对应Map的来实现，他的存在是为了我们只需要进行对单一数据操作来保证数据不重复等特点的使用的。
存储一组唯一，无序的对象，最多存储一个null值
实现类： HashSet、LinkedHashSet和TreeSet
操作数据的方法与List类似，Set接口不存在get()方法

HashSet：

采用Hashtable哈希表存储结构
添加速度快，查询速度快，删除速度快
唯一，无序，可以为null
HashSet是对HashMap的简单包装，对HashSet的函数调用都会转换成合适的HashMap方法，因此HashSet的实现非常简单，只有不到300行代码。

//HashSet是对HashMap的简单包装
public class HashSet<E>
{
	......
	private transient HashMap<E,Object> map;//HashSet里面有一个HashMap
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
    public HashSet() {
        map = new HashMap<>();
    }
    ......
    public boolean add(E e) {//简单的方法转换
        return map.put(e, PRESENT)==null;
    }
    ......
}

底层原理：哈希表

HashSet底层实现是基于HashMap来实现的，将set中存储的值作为HashMap的key来处理，PRESENT是一个填充的value值（所以是唯一的）
底层原理：数组+链表=哈希表
存入数据时，调用hashcode方法计算哈希值，通过hash值和一个表达式计算在数组中存放的位置，放入hashset中的数据，一定要重写hashCode和equals方法，保持唯一性；

LinkedHashSet：哈希表+链表

其继承自HashSet，其继承了HashSet中所有的属性和方法
采用哈希表存储结构，同时使用链表维护次序
唯一，有序（添加顺序） ,可以为null

底层原理：

哈希表+总的链表
LinkedHashSet的实现是基于LinkedHashMap来实现的
LinkedHashSet数据有序的特征是基于LinkedHashMap来保证的，其底层利用双向链表来实现的数据有序
其实就是在HashSet的基础上，多了一个总的链表，这个总链表将放入的元素串在一起，方便有序的遍历：
（可以看到LinkedHashMap.Entry 继承自HashMap.Node 除了Node 本身有的几个属性外，额外增加了before after 用于指向前一个Entry 后一个Entry。也就是说，元素之间维持着一条总的链表数据结构。）

TreeSet：

采用二叉树（红黑树）的存储结构
查询速度没有HashSet快
1、数据自然有序(自定义排序，实现Comparator接口)
2、数据不能重复
3、数据不能为null

引用对象：实际开发中利用外部比较器多，因为扩展性好（多态）
内部比较器是对象实现：public class Student implements Comparable<Student>
外部比较器是：比较器是单独的一个新对象：class BiJiao01 implements Comparator<Student> 
//创建一个TreeSet:
        //利用外部比较器，必须自己制定：
        /*Comparator<Student> com = new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                return o1.getName().compareTo(o2.getName());
            }
        };*/
        TreeSet<Student> ts = new TreeSet<>(new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                return o1.getName().compareTo(o2.getName());
            }
        });//一旦指定外部比较器，那么就会按照外部比较器来比较
        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);

底层原理：

TreeSet底层是基于treeMap来实现的
底层：二叉树（数据结构中的一个逻辑结构）
TreeSet底层的二叉树的遍历是按照升序的结果出现的，这个升序是靠中序遍历得到的：
image