Set接口

时间:2024-02-01 15:25:08

Set接口

Set接口中没有定义额外的新的方法,使用的都是Collection中声明的方法

存储数据特点

无序的,不可重复的数据

  • 无序性

    • 不等于随机性
    • 以HashSet为例说明
      • 存储的数据在底层数组中并非按照数组索引的顺序进行添加,而是根据数据的哈希值决定的
  • 不可重复性

    • 保证添加的元素按照equals()判断时,不能返回true,即相同的元素只能添加一个

要求

  1. 向Set中添加数据,其所在的类一定要重写hashCode()和equals()方法,两个方法可以自动生成

    (如果没有重写hashCode()方法,相当于系统随机安排一个数字给该元素的hash值,即使两个元素相同,但是他们的hash值不同,还是会添加到数组中。重写hashCode(),两个元素的hash值根据同一个逻辑算出)

  2. 重写的hashCode()和equals()方法尽可能保持一致性

  3. 相等的对象必须具有相等的散列码(哈希值)

自动生成的hashCode()方法中会出现31这个系数的原因

  • 选择系数的时候尽量选择大的系数,计算出的hash值越大,“冲突”就越少,查找起来效率也会提高
  • 31占用5bits,相乘造成的数据溢出的概率较小
  • 31是个素数,素数本身只能被本身和1整除,可以减少冲突

HashSet(主要实现类)

添加元素的过程

(hashSet底层是一个数组,长度为16)

图解



过程

底层:数组 + 链表

  1. 向HashSet中添加元素a,首先调用元素a所在类的hashCode()方法,计算元素a的哈希值
  2. 此哈希值接着通过某种算法计算出在HashSet底层数组中的存放位置(即为索引位置)
  3. 判断数组此位置上是否已有元素
    • 如果此位置没有其他元素,则元素a添加成功

    • 如果此位置上有其他元素b(或以链表形式存在的多个元素),则比较a与元素b的哈希值

      (存放位置相同的两个元素哈希值不一定相同)

      • 如果hash值不相同,则元素添加成功
      • 如果hash值相同,进而调用元素a所在的equals()方法
        • equals()返回true,元素a添加失败
        • equals()返回false,元素a添加成功

说明

两个元素的hash值不同或者equals返回false时,元素a与已经存在指定索引位置上的数据以链表的方式存储

  • jdk7:元素a放到数组中,指向原来的元素
  • jdk8:原来的元素在数组中,指向元素a
  • 总结:七是头插法,八是尾插法(七上八下)

LinkedHashSet

  • HashSet的子类
  • 遍历其内部数据是可以按照添加的顺序去遍历

注意:即使遍历出的数据顺序是按照添加顺序显示的,但是LinkedHashHashSet中的数据特点依旧是无序的,不可重复的

添加元素的过程

  • 在添加数据的同时,每个数据还维护了两个引用,记录此数据前一个数据和后一个数据的地址值
  • 优点:对于频繁的遍历操作,使用LinkedHashSet效率高于HashSet

TreeSet

  • 要求放入的数据属于同一个类的对象
  • 可以按照添加对象的指定属性,进行排序
  • 会使用到Comparable和Comparator两个排序接口
  • 底层采用红黑树存储结构(小放左,大放右),其特点是有序,查询速度比List快

注意:向TreeSet中添加的数据,要求是相同类的对象

自定义类两种排序方式(Java比较器)

https://www.cnblogs.com/CrabDumplings/p/13339146.html

自然排序(实现Comparable接口)

比较两个函数是否相同的标准为compareTo()方法返回0,不再是equals()方法

代码实现
  • 普通情况,按照名字进行排序
//Students类中的compareTo方法,按照名字进行排序
public int compareTo(Object o) {
        if(o instanceof Students){
            Students s = (Students)o;
            return this.name.compareTo(s.name);
        }else{
            throw new RuntimeException("传入数据类型不一致");
        }

    }

//测试函数
public void test13(){
        TreeSet set = new TreeSet();

        set.add(new Students("Tom",18,90));
        set.add(new Students("Ann",19,75));
        set.add(new Students("Lisa",20,86));
        set.add(new Students("Jack",21,50));
        set.add(new Students("Jerry",19,60));

        Iterator iterator = set.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }

运行结果

  • 排序的信息有相同的情况(名字相同,其他信息不相同)

    利用二次排序

    按照名字进行比较,如果名字相同,在compareTo中比较返回值为0(TreeSet中判断是否相同的标准不再是equals,而是compareTo)

//姓名从小到大排列,姓名相同的年龄从小到大排列
    @Override
    public int compareTo(Object o) {
        if(o instanceof Students){
            Students s = (Students)o;
//            return this.name.compareTo(s.name);
            int compare = this.name.compareTo(s.name);
            //姓名不一样
            if(compare != 0){
                return compare;
            }else {
                //姓名一样
                return Integer.compare(this.age,s.age);
            }
        }else{
            throw new RuntimeException("传入数据类型不一致");
        }

    @Test
    public void test13(){
        TreeSet set = new TreeSet();

        set.add(new Students("Tom",18,90));
        set.add(new Students("Ann",19,75));
        set.add(new Students("Lisa",20,86));
        set.add(new Students("Jack",21,50));
        set.add(new Students("Jerry",19,60));
        set.add(new Students("Jerry",22,70));

        Iterator iterator = set.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }

运行结果

定制排序(实现Comparator接口)

在定制排序中,比较两个对象是否相同的标准为compare(),是否返回0,不再是equals()方法

TreeSet set = new TreeSet();

构造器没有参数的时候直接为自然排序

TreeSet set = new TreeSet(com);

构造器有蚕食的时候,按照com的定制排序进行排序

代码实现
  • 普通情况,按照年龄进行排序
//年龄从小到大进行排序
public void test14(){
        Comparator com = new Comparator() {
            //按照年龄从小到大排列
            @Override
            public int compare(Object o1, Object o2) {
                if(o1 instanceof Students || o2 instanceof Students){
                    Students s1 = (Students)o1;
                    Students s2 = (Students)o2;
                    return Integer.compare(s1.getAge(),s2.getAge());
                }else{
                    throw new RuntimeException("传入数据类型不一致");
                }
            }
        };
        TreeSet set = new TreeSet(com);
        set.add(new Students("Tom",18,90));
        set.add(new Students("Ann",19,75));
        set.add(new Students("Lisa",20,86));
        set.add(new Students("Jack",21,50));
        set.add(new Students("Jerry",19,60));
        set.add(new Students("Jerry",22,70));

        Iterator iterator = set.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }

运行结果

  • 排序的信息有相同的情况(年龄相同,其他信息不相同)
public void test14(){
        Comparator com = new Comparator() {
            //按照年龄从小到大排列
            @Override
            public int compare(Object o1, Object o2) {
                if(o1 instanceof Students || o2 instanceof Students){
                    Students s1 = (Students)o1;
                    Students s2 = (Students)o2;
//                    return Integer.compare(s1.getAge(),s2.getAge());
                    int compare = Integer.compare(s1.getAge(), s2.getAge());
                    if(compare != 0){
                        return Integer.compare(s1.getAge(),s2.getAge());
                    }else{
                        return s1.getName().compareTo(s2.getName());
                    }
                }else{
                    throw new RuntimeException("传入数据类型不一致");
                }
            }
        };
        TreeSet set = new TreeSet(com);
        set.add(new Students("Tom",18,90));
        set.add(new Students("Ann",19,75));
        set.add(new Students("Lisa",20,86));
        set.add(new Students("Jack",21,50));
        set.add(new Students("Jerry",19,60));
        set.add(new Students("Jerry",22,70));

        Iterator iterator = set.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }

运行截图