Set接口

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

存储数据特点

无序的，不可重复的数据

无序性

不等于随机性

以HashSet为例说明

存储的数据在底层数组中并非按照数组索引的顺序进行添加，而是根据数据的哈希值决定的

不可重复性

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

要求

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

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

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

相等的对象必须具有相等的散列码（哈希值）

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

选择系数的时候尽量选择大的系数，计算出的hash值越大，“冲突”就越少，查找起来效率也会提高

31占用5bits，相乘造成的数据溢出的概率较小

31是个素数，素数本身只能被本身和1整除，可以减少冲突

HashSet（主要实现类） 添加元素的过程

（hashSet底层是一个数组，长度为16）

图解

过程

底层：数组 + 链表

向HashSet中添加元素a，首先调用元素a所在类的hashCode()方法，计算元素a的哈希值

此哈希值接着通过某种算法计算出在HashSet底层数组中的存放位置（即为索引位置）

判断数组此位置上是否已有元素

如果此位置没有其他元素，则元素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()); } }

运行结果

排序的信息有相同的情况（名字相同，其他信息不相同）

利用二次排序