Set

继承结构

• Collection (interface)
  • Set (interface)
    • HashSet (class)
      • LinkedHashSet (class)
    • TreeSet (class)

Set (interface) 无序、不可以重复、最多一个null元素
LinkedHashSet (class) 有序，最多一个null元素。
TreeSet (class) 无序，不能有null元素，符合二叉树特征。

类	使用	说明
HashSet	非线程安全 较多使用	基于哈希表（HashMap)实现；判断两个对象是否相同：先判断hashcode，如果hashcode不同直接存储，如果相同，再用equals判断；自定义对象，要重写对象所在类的hashcode和equals方法。 把对象存储到哈希表中：先计算对象的hashcode值，再对数组的长度进行&运算，来决定对象要存储在数组中的位置
LinkedHashSet	非线程安全 较少使用 除非需要保证原来的顺序	有序，哈希表和链接列表实现，维护着一个运行于所有条目的双重链表，此链表定义了迭代顺序；一般插入和删除效率较高，检索效率相对较低。
TreeSet	非线程安全	基于TreeMap（二叉树数据结构），不能有null元素，对象需要比较大小，通过对象比较器实现；对象比较器还可以用来去除重复元素，如果自定义的数据类，必须实现比较器接口class Person implements Comparable<T>{}

HashSet 和 HashMap 的关系

HashSet 就是 HashMap 的 key 那一列
将 HashMap 中的 value 那一列隐藏掉，就变成了HashSet。

HashSet加载和扩充过程

import java.util.HashSet;

public class setDemo {

    public static void main(String[] args) {
        HashSet<Persons> hset = new HashSet<>();
        hset.add(new Persons("person1", 10));
        hset.add(new Persons("person2", 11));
        hset.add(new Persons("person3", 12));
        hset.add(new Persons("person4", 13));
        // 如果不重写 equals() 下面这个对象也会出现在集合中
        hset.add(new Persons("person1", 10));
        
        for (Persons per : hset) {
            System.out.println(per);
        }
    }

}

class Persons {
    private String name;
    private int age;
    
    public Persons(String name, int age) {
        super();
        this.name = name;
        this.age = age;
    }
    
    /**
     * 因为Object类中的hashcode()会根据不同对象，生成不同的数字，这样就没有办法去重。
     * 所以自定义类，要重写hashcode()方法，以便去重。
     */
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + age;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        return result;
    }
    
    /**
     * HashSet使用的equals()方法是对比对象的地址,不符合实际要求
     * 更改为属性相同返回true；
     */
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Persons other = (Persons) obj;
        if (age != other.age)
            return false;
        if (name == null) {
            if (other.name != null)
                return false;
        } else if (!name.equals(other.name))
            return false;
        return true;
    }

    @Override
    public String toString() {
        return "Person [name=" + name + ", age=" + age + "]";
    }
    
}

HashSet基于HashMap实现，很多特性都可以参考HashMap，如果集合中的元素是自定义对象，那么要重 写 hashcode() 和 equals() 方法。

初始化

新建一个HashSet会默认初始化一个大小为16的数组，初始值为null，负载因子为0.75，数组的每个元素都是一个链表。

向集合中添加对象

1. 计算对象的hash值，如果hash值不同（与集合中所有对象对比），直接存储。
   • 如果hash值相同，则进行equals()比较，不同就进行存储，相同则舍弃。
2. 用hash值对数组长度取余，求得数组下标index。
3. 如果此位置没有元素（没有冲突），则直接存储。
4. 如果有冲突，则以链表的形式存在当前存在元素后。
5. 如果冲突导致链表过长(大于等于TREEIFY_THRESHOLD，默认为8)，就把链表转换成红黑树，然后写入
6. 如果写入后，如果数组满了(大于 负载因子*数组当前大小)，进行resize扩容。

集合扩容（其实是HashMap）

1. 新建一个数组，长度为老数组长度的二倍，如果老数组大小如果已经达到最大(2^{30)，修改阈值为int的最大值(2}31-1)，这样以后就不会扩容了
2. 重新计算每个元素在集合中的位置，把对象存储在新数组中，jdk1.8优化了计算hash值这一步，不再需要重复计算hash值，而且jdk1.8之后移动的链表不会倒置
   • 原理：我们使用的是2次幂的扩展，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置，计算hashcode & newCapacity时，只需要看newCapacity相比oldCapacity新增的那一位是0还是1。是0的话索引没变，是1的话索引变成原索引+oldCapcity
     hashmapresize.jpg

扩容是一个特别耗性能的操作，所以使用HashMap的时候，先估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。

参考

1、Java 8系列之重新认识HashMap