Set
继承自Collection的一个接口，特点是：无序，不可重复。注意啊！！只有Collection实现了迭代器！也就是说Map是没有实现迭代器的，需要keySet，values，entrySet这个几个方法
HashSet实现Set接口
SortedSet继承自Set接口，无序，不可重复，但是可以存进去的元素可以自动按照大小进行排序。TreeSet是他的一个实现类。
HashSet的底层是一个HashMap。为什么？因为HashMap中的key无序，不可重复，跟HashSet有一样的特性，一个没有value的HashMap不就是一个HashSet？
public HashSet() { map = new HashMap<>(); }
HashMap底层是一个哈希表
transient Node<K,V>[] table;
哈希表是什么？是数组和单向链表的结合
哈希表的本质是一个数组，只不过这个数组中的每一个元素又是单向链表。类似于现实世界中的字典。
static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } ……… ……… }
代码中的hash是key通过hashCode()方法，再通过哈希算法得到的一个值。在单向链表中，每一个结点的哈希值是相同的。
所以哈希表的查找过程是：通过key来得到哈希值，得到值后定位单向链表，然后遍历该链表。哈希表的增删效率都是比较高的。
向哈希表添加元素：通过key得到一个哈希值，如何在这个表中不存在这个值，就直接添加元素。否则，继续调用equals()，如果返回false则添加该元素，否则不添加，因为返回true的话证明里面已经有这个元素了。
HashSet是HashMap的key部分。
HashSet和HashMap的初始化容量是16 ，默认加载因子是0.75。比方说：容量是100，那么在装了75个元素的时候开始扩容
注意：存储在HashSet和HashMap中key部分的元素，需要重写hashCode()和equals();
public class HashSetTest { public static void main(String[] args) { Set set = new HashSet(); Employee e1 = new Employee("24" , "KOBE"); Employee e2 = new Employee("21" , "TIM"); Employee e3 = new Employee("21" , "KG"); Employee e4 = new Employee("3" , "AI"); Employee e5 = new Employee("3" , "DW"); Employee e6 = new Employee("24" , "KOBE"); set.add(e1); set.add(e2); set.add(e3); set.add(e4); set.add(e5); System.out.println("set.size = " + set.size()); // set.size = 5 } } class Employee{ String no; String name; public Employee(String no , String name){ this.no = no; this.name = name; } @Override public int hashCode() { return no.hashCode(); //String已经重写了hashCode方法，直接用它的 } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj instanceof Employee){ Employee e = (Employee)obj; if ( e.no.equals(this.no) && e.name.equals(this.name)) return true; } return false; } }
SortedSet存储元素为什么可以自动排序？如何实现的？
1 public class SortedSetTest { 2 3 public static void main(String[] args) { 4 User u1 = new User("kobe"); 5 User u2 = new User("tim duncan"); 6 User u3 = new User("ray allen"); 7 User u4 = new User("melo"); 8 9 SortedSet set = new TreeSet(); 10 set.add(u1); 11 set.add(u2); 12 set.add(u3); 13 set.add(u4); 14 } 15 16 } 17 18 class User{ 19 String name; 20 21 public User(String name){ 22 this.name = name; 23 } 24 25 @Override 26 public String toString() { 27 return "[user name = " + name + "]"; 28 } 29 }
上述代码运行时会报错：User cannot be cast to java.lang.Comparable
看下TreeSet的源码
public TreeSet() { this(new TreeMap<E,Object>()); } public boolean add(E e) { return m.put(e, PRESENT)==null; }
发现底层是一个TreeMap。（其实跟HashSet类似，TreeSet也相当于TreeMap的key）
并且add()中是调用的TreeMap的put方法。这里再看下TreeMap的put方法源码。
public V put(K key, V value) { …… …… else { if (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; //强制转换成Compareble do { parent = t; cmp = k.compareTo(t.key); //转换完后调用compareTo方法 if (cmp < 0) //小于0表示比根结点小，放左边 t = t.left; else if (cmp > 0) //大于则放右边 t = t.right; else return t.setValue(value); } while (t != null); } …… }
那么需要去实现这个Compareble接口，并重写compareTo方法。
class User implements Comparable{ String name; int age; public User(String name , int age){ this.name = name; this.age = age; } @Override public String toString() { return "[user name = " + name + " , age = " + age + "]"; } @Override //该方法程序员负责实现，sun(或者说现在要叫oracle了 :) )提供的程序调用了该方法。 public int compareTo(Object o) { //编写一个比较规则 //根据年龄排序 int age1 = this.age; int age2 = ((User)o).age; return age1 - age2; //这个地方要注意只有在age的范围在一个足够小的时候才能这么干，如果age1是一个较大的整数，而age2是一个较小的负整数，age1-age2可能会溢出 /* * [user name = melo , age = 2] [user name = kobe , age = 10] [user name = ray allen , age = 32] [user name = tim duncan , age = 200] */ } }
那么也可以按照名字来排序，String本身实现了compareble接口，所以可以直接用。
//根据名字来排序 return name.compareTo(((User)o).name); /* * [user name = kobe , age = 10] [user name = melo , age = 2] [user name = ray allen , age = 32] [user name = tim duncan , age = 200] */
SortedSet实现排序还有一种方法，TreeSet中还有一个构造函数如下：
public TreeSet(Comparator<? super E> comparator) { this(new TreeMap<>(comparator)); }
通过传入Comparator的实现类的参数来进行比较。
TreeMap中的put方法源码一部分如下：
Comparator<? super K> cpr = comparator; if (cpr != null) { do { parent = t; cmp = cpr.compare(key, t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); }else{ //这个else是之前说的第一种方法，可以看到java是优先使用Comparator这种方法的 }
那么就写一个Comparator的实现类，并删掉之前User实现的Compareble接口以及compareTo方法。如果不删的话，结果也是一样的，因为java优先使用这种方法排序。其实也是推荐这种方式的，因为这样User就是一个更加纯粹的User。这种方式也可以写成匿名内部类的方式，不过为了代码的复用，最好还是单独写出来。
class UserComparator implements Comparator{ @Override public int compare(Object o1, Object o2) { int age1 = ((User)o1).age; int age2 = ((User)o2).age; return age1 - age2; } }
[user name = melo , age = 2]
[user name = kobe , age = 10]
[user name = ray allen , age = 32]
[user name = tim duncan , age = 200]