Java Set

Set接口

HashSet、LinkedHashSet、TreeSet

HashSet是Set接口的典型实现，大多数时候Set集合都使用这个实现类。HashSet是按Hash算法来存储集合中的元素，因此具有很好的存取、查找、删除性能。底层就是HashMap;HashSet具有以下特点：不能保证元素的排列顺序；HashSet不是线程安全的；集合元素可以是null；HashSet集合判断两个元素相等的标准：两个对象通过hashCode()方法比较相等，并且两个对象的equals()方法返回值也相等。对于存放在Set容器中的对象，对应的类一定要重写equals()和hashCode()方法，以实现对象相等规则。既“相等的对象必须具有相同的hashCode”
LinkedHashSet是HaseSet的子类LinkedHashSet根据元素的hashCode值来决定元素的存储位置，但它同时使用双向链表维护元素的次序，这使得元素看起来是以插入顺序保存的。LinkedHashSet插入性能略低于HashSet，但在迭代访问Set里的全部元素时有很好的性能。LinkedHashSet不允许集合元素重复。
TreeSet是SortedSet接口的实现类，TreeSet可以确保集合元素处于排序状态。TreeSet底层就是TreeMap，而TreeMap底层使用红黑树结构（JDK1.8以后）存储key,TreeSet只是使用TreeMap的keyTreeSet两种排序方法：自然排序和Comparetor比较器排序，默认使用自然排序。

HashSet

HashSet的底层初始化：

private transient HashMap<E,Object> map;
public HashSet() {
    map = new HashMap<>();
}
public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}

可以看到HashSet底层就是一个HashMap，那这里就不多关于HashMap的东西，主要看下对HashSet的测试:

@Test
public void test6(){
    Set<Employee> set = new HashSet<>(10);
    System.out.println(set.size());
    for(int i = 0; i < 5; i++){
        set.add(new Employee("test",(i%2 == 0) ? 2 : 1,(i%2 == 0) ? 2 : 1));
    }
    Iterator<Employee> iterator = set.iterator();
    while (iterator.hasNext()){
        Employee employee = iterator.next();
        System.out.println(employee);
    }
    /**
     * 打印结果：
     * 0
     * run hashCode ... 
     * run hashCode ... 
     * run hashCode ... 
     * run equals()....
     * run hashCode ... 
     * run equals()....
     * run hashCode ... 
     * run equals()....
     * Employee{name='test', age=2, salary=2}
     * Employee{name='test', age=1, salary=1}
     * 2
     */
	/**
     * Employee的equals()重写时加了一句:
     * System.out.println("run equals()....");
     * Employee的hashCode()重写时加了一句:
     * System.out.println("run hashCode ... ");
     * 上面对List进行测试的时候也加了。。。
     */
}

从上面的打印结果可以看到，初始化后set的size为0，后面每次添加一个元素size都会增长1，而再添加过程中如果遇到hashCode相同情况下会进行equals判断，元素内的值相同会导致添加失败。所以最终set中只有2个元素。

LinkedHashSet

LinkedHashSet的底层初始化：

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
	public LinkedHashSet(int initialCapacity, float loadFactor) {
	    super(initialCapacity, loadFactor, true);
	}
	public LinkedHashSet(int initialCapacity) {
	    super(initialCapacity, .75f, true);
	}
	public LinkedHashSet() {
	    super(16, .75f, true);
	}
	public LinkedHashSet(Collection<? extends E> c) {
	    super(Math.max(2*c.size(), 11), .75f, true);
	    addAll(c);
	}
}

父类HashSet下的带有三个参数的构造器：

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

显然，LinkedHashSet底层是使用LinkedHashMap实现的，也就是说它带有LinkedHashMap的特点——可以找到添加过程中的前后元素。具体可以看LinkedHashMap

TreeSet

TreeSet的底层初始化：

public TreeSet() {
    this(new TreeMap<E,Object>());
}
public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}
public TreeSet(Collection<? extends E> c) {
    this();
    addAll(c);
}
public TreeSet(SortedSet<E> s) {
    this(s.comparator());
    addAll(s);
}

使用TreeSet：

@Test
public void test7(){
    Set<Employee> set = new TreeSet<>();
    for(int i = 0; i < 5; i++){
        set.add(new Employee("test",i,i));
    }
    Iterator<Employee> iterator = set.iterator();
    while (iterator.hasNext()){
        Employee employee = iterator.next();
        System.out.println(employee);
    }
    /**
     * 报错:
     * java.lang.ClassCastException: com.chapter12_collection.Employee cannot be cast to java.lang.Comparable
     *
     * 	at java.util.TreeMap.compare(TreeMap.java:1294)
     * 	at java.util.TreeMap.put(TreeMap.java:538)
     * 	at java.util.TreeSet.add(TreeSet.java:255)
     * 	at com.chapter12_collection.CollectionTest.test7(CollectionTest.java:115)
     * 	at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
     * 	...
     */
}

发现必须得把Employee转成Comparable，那么就让Employee实现Comparable接口呗。于是乎重写里面的compareTo（）方法：

// 先按name排序，再按age排序
@Override
public int compareTo(Object o) {
    if(o instanceof Employee){
        Employee employee = (Employee) o;
        if(this.name == employee.getName()){
            return Integer.compare(this.age, employee.getAge());
        }else {
            return this.name.compareTo(employee.getName());
        }
    }else {
        throw new RuntimeException("输入的类型不是Employee");
    }
}

再来跑测试代码：

@Test
public void test7(){
    Set<Employee> set = new TreeSet<>();
    for(int i = 5; i > 0; i--){
        set.add(new Employee("test"+i,i,i));
    }
    Iterator<Employee> iterator = set.iterator();
    while (iterator.hasNext()){
        Employee employee = iterator.next();
        System.out.println(employee);
    }
    /**
     * 打印结果：
     * Employee{name='test1', age=1, salary=1}
     * Employee{name='test2', age=2, salary=2}
     * Employee{name='test3', age=3, salary=3}
     * Employee{name='test4', age=4, salary=4}
     * Employee{name='test5', age=5, salary=5}
     */
}

显然，此时是按照name从小到大排序的，而我们插入的时候是从大到小的，也就是说TreeSet是可以实现Comparable比较器排序的，关于自然排序就看下下面这段代码吧：

@Test
public void test8(){
    Set<Integer> set = new TreeSet<>();
    set.add(11);
    set.add(-1);
    set.add(33);
    set.add(22);
    set.add(44);
    Iterator<Integer> iterator = set.iterator();
    while (iterator.hasNext()){
        System.out.print(iterator.next() + " ");
    }
    /**
     * 打印结果：
     * -1 11 22 33 44 
     */
}

Set接口#

HashSet、LinkedHashSet、TreeSet#

HashSet#

LinkedHashSet#

TreeSet#

Set接口

HashSet、LinkedHashSet、TreeSet

HashSet

LinkedHashSet

TreeSet