Java Set集合(HashSet、TreeSet)

什么是HashSet？操作过程是怎么样的？

　　1、HashSet底层实际上是一个HashMap,HashMap底层采用了哈希表数据结构

　　2、哈希表又叫做散列表，哈希表底层是一个数组，这个数组中每一个元素是一个单向链表，每个单向链表都有一个独一无二的hash值，代表数组的下标。在某个单向链表中的每一个节点上的hash值是相同的。hash值实际上是key调用hashCode方法，再通过"hash function"转换成的值

　　3、如何向哈希表中添加元素？

　　　　先调用被存储的key的hashCode方法，经过某个算法得出hash值，如果在这个哈希表中不存在这个hash值，则直接加入元素。如果该hash值已经存在，继续调用Key之间的equals方法，如果equals方法返回false，则将该元素添加。如果equals方法返回true，则放弃添加该元素

　　　　HashMap和HashSet初始化容量是16，默认加载因子是0.75

HashSet的数据结构

　　献上我看视频截的图

代码举例

 1 public class Test{
 2     
 3     public static void main(String[] args) {
 4         
 5         Set set = new HashSet();
 6         
 7         Student stu1 = new Student("1", "JACK");
 8         Student stu2 = new Student("2", "TOM");
 9         Student stu3 = new Student("3", "JIM");
10         
11         set.add(stu1);
12         set.add(stu2);
13         set.add(stu3);
14         
15         System.out.println("size :" + set.size());
16     }
17     
18
19     
20 }
21 
22 class Student{
23     String no;
24     String name;
25     
26     Student(String no, String name){
27         this.no = no;
28         this.name = name;
29     }
30 }

　　这个的输出结果显而易见是3，因为我们添加了三个元素，但是如果改一下

1 Student stu1 = new Student("1", "JACK");
2 Student stu2 = new Student("1", "JACK");
3 Student stu3 = new Student("3", "JIM");
4 
5 System.out.println(stu1.hashCode());
6 System.out.println(stu2.hashCode());

　　可以运行试一下，stu1和stu2的hashCode是不一样的，为什么呢？因为这两个对象是New出来的，引用地址不一样。我们不希望出现这样的情况，那就要重写hashCode和equals方法

 1 class Student{
 2     String no;
 3     String name;
 4     
 5     Student(String no, String name){
 6         this.no = no;
 7         this.name = name;
 8     }
 9     
10     public boolean equals(Object o){
11         if(this == o) return true;
12         if(o instanceof Student){
13             Student student = (Student) o;
14             if(student.no.equals(this.no) && student.name.equals(this.name)) return true;
15         }
16         
17         return false;
18     }
19     
20     public int hashCode(){
21         return no.hashCode();
22     }
23 }

　　再次运行，插入两个数据一样的对象，就不会重复了

TreeSet

　　treeset实现了sortedset接口，有个很重要的特点是里面的元素都是有序的

 1 public class Test{
 2     
 3     public static void main(String[] args) {
 4         
 5         SortedSet set = new TreeSet();
 6         
 7         set.add(1);
 8         set.add(100);
 9         set.add(50);
10         
11         System.out.println(set);
12     }
13 
14 }

　　输出结果：[1, 50, 100]

　　那如果我们自定义类可以进行比较吗？

 1 public class Test{
 2     
 3     public static void main(String[] args) {
 4         
 5         SortedSet set = new TreeSet();
 6         
 7         Student stu1 = new Student(22);
 8         Student stu2 = new Student(11);
 9         Student stu3 = new Student(100);
10         
11         set.add(stu1);
12         set.add(stu2);
13         set.add(stu3);
14         
15         System.out.println(set);
16     }
17 
18 }
19 
20 class Student{
21     int age;
22     
23     Student(int age){
24         this.age = age;
25     }
26 }

　　这样运行会出现一个问题，报ClassCastException，这就需要来看看源码了，底层到底是怎么实现的，为什么自定义类就先不行呢？

　　这里可以看到，当我们在创建一个TreeSet的时候，实际上是new了一个TreeMap

　　add的时候调用了TreeMap的put方法，来看看TreeMap中的put方法

　　可以看到第三个红框那里，会对key进行一个强制类型转换，我们上面的代码肯定是就是在这里装换不成功，Comparable是什么？来看看API

　　是一个接口，从翻译就可以看出，只要实现了这个接口，就是可以比较的，下面是实现了这个接口的类

　　随便框了几个，上面就有Integer，这个类实现了comparable接口，因此第一个代码是正确的，现在我们是不是只要实现这个接口就好了呢！

 1 class Student implements Comparable{
 2     int age;
 3     
 4     Student(int age){
 5         this.age = age;
 6     }
 7 
 8     //重写接口中的方法
 9     //要重写比较规则
10     @Override
11     public int compareTo(Object o) {
12         // TODO Auto-generated method stub
13         int age1 = this.age;
14         int age2 = ((Student)o).age;
15         return age2 - age1;
16     }
17 }

　　这样OK了，再来看看上面有红框的源码，cmp<0，cmp>0，left，right都是什么东西，二叉树！所以底层是通过二叉树来排序的

　　如果是自定义类中的String呢，那就return String的compareTo方法就好了