第18章 集合框架(2)-Set接口
Set是Collection子接口，模拟了数学上的集的概念
Set集合存储特点
1.不允许元素重复
2.不会记录元素的先后添加顺序
Set只包含从Collection继承的方法，不过Set无法记住添加的顺序，不允许包含重复的元素，当试图添加两个相同元素进Set集合，添加操作会失败，add()方法返回false
Set判断两个对象是否相等用equals，而不是用===，也就是说两个对象equals比较返回true,Set集合是不会接受新添加的这个对象的。
1.HashSet类
1.1.equals方法和hashCode方法
HashSet是Set接口最常用的实现类，顾名思义，底层采用了哈希表(散列/hash)算法
其实底层也是一个数组，存在的意义是提供查询速度，插入速度也比较快，但是适用于少量数据的插入操作
在HashSet中如何判断两个对象是否相等问题
1.两个对象的equals比较相等，返回true，则说明是相同对象。
2.两个对象的hashCode方法返回值相等。
以上两个条件都要满足才能说明两个对象是相等的
对象的hashCode值决定了在哈希表中的存储位置
而这缺一不可
在往HashSet集合中添加新的对象的时候，先回判断该对象中的hashCode值：
1.不等：直接把该新的对象存储到hashCode指定的位置
2.相等：在继续判断该对象和集合中的对象的equals作比较
2.1.hashCode相同，equals为true，则视为是同一个对象，则保存在哈希表中
2.2.hashCode相同，equals为false，非常麻烦，存储在之前对象同槽位的链表上(拒绝，操作比较麻烦)
对象的hashCode和equals方法的重要性
每一个存储到hash表中的对象，都的提供hashCode和equals方法，用来判断是否是同一个对象
存储在哈希表中的对象，都应该覆盖equals方法和hashCod方法，并且保证equals相等的时候，hashCode也应该相等
1.2.hashSet集合常用方法
常用方法跟Vector类的相似，不再详细描述
2.LinkedHashSet类
之前我们已经学了两个接口
List接口：允许元素重复，记录先后顺序
Set接口：不允许元素重复，不记录先后顺序
但是有第三种需求：不允许元素重复，但是希望能够记录先后添加顺序，这就是LinkedHashSet类。
LinkedHashSet：底层采用哈希表和链表算法
哈希表：用来保证元素唯一性，此时就是HashSet，在哈希表中元素没有先后顺序
链表：来记录元素的先后添加顺序
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;/**
* 测试LinkedHashSet类记录顺序的功能
*/
public class TestLinkedHashSet {
//不记录先后顺序
public static void HashSetDemo(){
Set<String> set = new HashSet<>();
set.add("X");
set.add("C");
set.add("B");
set.add("1");
set.add("2");
System.out.println(set);//[1, B, 2, C, X] } public static void LinkedHashSetDemo(){
//记录先后顺序
Set<String> set = new LinkedHashSet<>();
set.add("X");
set.add("C");
set.add("B");
set.add("1");
set.add("2");
System.out.println(set);//[X, C, B, 1, 2]
} public static void main(String[] args) {
HashSetDemo();
LinkedHashSetDemo();
}
}3.TreeSet类
TreeSet类和Set接口的关系是：
TreeSet继承于NaviageableSet接口（可作范围查询集合），再继承于SortSet接口（可排序的集合），最后再继承Set接口
底层采用红黑树算法，会对存储的元素默认按照使用自然排序(从小到大):
必须保证TreeSet集合中的元素对象是同一种类型的对象。
例下面这个会报错
//编译之后会报错，A和1不是同类型，不能做对比
public class TestTreeSet {
public static void main(String[] args) {
TreeSet set = new TreeSet();
set.add("A");
set.add(1);
System.out.println(set);
}如果是同类型的是可以的(此处是用泛型作的限定)：
import java.util.TreeSet;public class TestTreeSet {
public static void main(String[] args) {
TreeSet set = new TreeSet();
set.add("A");
set.add("D");
set.add("Y");
set.add("1");
set.add("6");
set.add("C");
System.out.println(set);//[1, 6, A, C, D, Y] }
}关于TreeSet类的一些方法：
除了一些通用的方法，这里再举例一些特殊的用法：
import java.util.TreeSet;//验证TreeSet的方法
public class TestTreeSet {
public static void main(String[] args) {
TreeSet set = new TreeSet();
set.add("A");
set.add("D");
set.add("Y");
set.add("1");
set.add("6");
set.add("C");
System.out.println(set);//[1, 6, A, C, D, Y]
//first()返回第一个（最低）元素对象
System.out.println(set.first());//1
//last()返回最后面的一个，也就是最大的一个
System.out.println(set.last());//Y
//floor(E e)返回所有小于或等于给定的元素中的最大的一个对象
System.out.println(set.floor("C"));//C
//lower(E e)返回此 set 中严格小于给定元素的最大元素；如果不存在这样的元素，则返回 null。
System.out.println(set.lower("1"));//null
//ceiling(E e) 返回此 set 中大于等于给定元素的最小元素；如果不存在这样的元素，则返回 null。
System.out.println(set.ceiling("A"));//A
//tailSet(E fromElement)返回此 set 的部分视图，其元素大于等于 fromElement,其实就是给定元素之后的集合对象
System.out.println(set.tailSet("A"));//[A, C, D, Y] }
}以上的方法并不是全部，具体的可以查api
3.1.排序接口
TreeSet的排序规则有两种，一种是自然排序，一种是认为设定。这是TreeSet特有的，往TreeSet里存放元素的时候，必须要用compareTo方法，如果是自己写的对象，要在这个对象里面重写这个方法。
3.1.1.Comparable自然排序
自然排序：
TreeSet调用集合元素的compareTo方法来比较元素的大小关系，然后将集合元素按照升序排列(从小到大)，要求TreeSet集合中元素得实现java.util.Comparable接口
自然排序是按Unicode编码排序。先排数字，然后大写字母，再小写字母，字符是按照字典顺序的，A，AB，AC，a
java.util.Comparable接口：可比较的
覆盖public int compareTo(Object o)方法，在该方法中编写比较规则。
在该方法中，比较当前对象(this)和参数对象o比较(严格上说比较的是对象中的数据，比如按照对象的年龄排序)。
this > 0;返回正整数.1
this < 0;返回负整数.-1
this == 0；返回0，此时认为两个对象为同一个对象
在TreeSet的自然排序中，认为如果两个对象作比较如果返回的是0,则认为是同一个对象
import java.util.Set;
import java.util.TreeSet;//测试comparable自然排序方法
class Person implements Comparable<Person>{
private String name;
private int age;
public Person(String name, int age){
this.name = name;
this.age = age;
} public String toString(){
return "Person [name="+ name +", age="+age+"]";
}
//编写比较规则
public int compareTo(Person other){
if (this.age > other.age){
return 1;
}else if (this.age < other.age){
return -1;
}else {
return 0;
} }
}public class TestTreeSet {
public static void main(String[] args) {
//按照Person对象的年龄做自然排序
Set<Person> set = new TreeSet<>();
set.add(new Person("Rocco",98));
set.add(new Person("Eric",32));
set.add(new Person("Ao",18));
set.add(new Person("Job",5));
System.out.println(set);//[Person [name=Job, age=5], Person [name=Ao, age=18], Person [name=Eric, age=32], Person [name=Rocco, age=98]]
}
}3.1.2.Compartor定制排序
定制排序可以按照自己的需求来排序，比如下面的例子中是按照名字的长短来排序的。
在TreeSet构造器中传递到java.lang.Comparator对象，并覆盖public int compare(Object o1, Object o2)再编写比较规则
对于TreeSet集合来说，要么使用自然排序，要么使用定制排序。
判断两个对象是否相等的规则
自然排序：comparaTo返回0
定制排序：compare方法返回0
import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;/**
* 测试定制排序方法
* 按照名字长短进行排序
*/class Person {
String name;
int age;
public Person(String name, int age){
this.name = name;
this.age = age;
} public String toString(){
return "Person [name="+ name +", age="+age+"]";
}}class NameLengthComparator implements Comparator<Person> { @Override
public int compare(Person o1, Person o2) {
if (o1.name.length() > o2.name.length()){
return -1;
}else if (o1.name.length() < o2.name.length()){
return 1;
}else {
return 0;
}
}
}public class TestTreeSet {
public static void main(String[] args) { Set<Person> set2 = new TreeSet<>(new NameLengthComparator());
set2.add(new Person("Rocco",98));
set2.add(new Person("Eric",32));
set2.add(new Person("Ao",18));
set2.add(new Person("Job",5));
System.out.println(set2);//[Person [name=Rocco, age=98], Person [name=Eric, age=32], Person [name=Job, age=5], Person [name=Ao, age=18]]
}
}4.Set实现性能分析
Set接口的实现类：
共同特点：
1.都不允许元素重复
2.都不是线程安全类
解决方法：Set s = Collections.synchronizedSet(Set对象);
HashSet：
不保证元素的先后添加顺序
底层采用的是哈熙表算法，查询效率极高。
判断两个对喜爱那个是否是否相等的规则：
1.equals比较true
2.hashCode值相同
要求：要求存在哈希中的对象元素都的覆盖equals和HashCode方法
LinkedHashSet
HashSet的子类，底层也采用的是哈希表算法，但是也使用了链表算法来维持元素的先后添加顺序
判断两个对象是否相等的规则和HashSet相同
因为需要多使用一个链表来记录元素的顺序，所以性能相对与HashSet较低
一般少用，如果要求一个集合既要保证元素不重复，又需要记录添加先后顺序，才选择使用LinkedHashSet
TreeSet
不保证元素的先后添加顺序，但是会对集合中的元素做排序操作
底层采用红黑树算法(树结构，比较擅长做范围查询)
TreeSet要么采用自然排序，要么定制排序
自然排序：要求在TreeSet集合中的对象必须实现java.lang.Comparable接口，并覆盖compareTo方法
定制排序：要求在构建TreeSet对象的时候，传入一个比较器对象(必须实现java.lang.Comparator接口)。在比较器中覆盖compare方法，并编写比较规则
TreeSet判断元素对象重复的规则
compareTo/compare方法是否返回0，如果返回0，则视为同一个对象
如何选用
HashSet做等值查询效率高，TreeSet做范围查询效率高
而我们更多的情况都是在做等值查询，在数据库的索引中做范围查询较多，所以数据结构主要用于做索引，用来提高查询效率
