1. Set接口介绍及常用方法

 

1.1 无序无索引

虽然无序，但取出的顺序是固定的

1.2 不允许重复元素，最多包含一个null

1.3 Set接口也是Collection的子接口，常用方法和Collection一样

1.4 Set接口的遍历方式：

Iterator

增强for

不能用索引方式（即普通for循环）

HashSet set = new HashSet();
set.add("john");
set.add("lucy");
set.add("jack");
set.add(null);
System.out.println("set=" + set);
Iterator it = set.iterator();
System.out.println("--------in iterator---------");
while(it.hasNext()) {
     System.out.println(it.next());
 }
System.out.println("---------in for---------");
for(Object o: set) {
    System.out.println(o);
}

2. HashSet

 2.1 HashSet特点

2.1.1实现了Set接口

2.1.2hashSet实际上是HashMap

HashMap底层是数组+链表+红黑树

2.1.3 可以存放null，但最多只能有一个

2.1.4 HashSet不保证元素是有序的，取决于hash后，再确定索引的结果

2.1.5 不能有重复元素

3.HashSet

3.1 HashSet底层是HashMap

3.2 添加一个元素时，会先得到Hash值，通过算法转成索引值

3.3 找到存储数据表table，看这个索引位置是否已经有元素

3.4 如果没有，直接加入

3.5 如果有，调用equals比较，如果相同就放弃添加，如果不相同，则添加到最后

3.6 Java8中，如果一条链表的元素个数达到TREEIFY_THRESHOLD(默认是8)，并且（需要同时

满足）table的大小大于等于MIN_TREEIFY_CAPACITY(默认64)，就会红黑树化

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //table就是HashMap的一个数组，类型是Node[]
        
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //if语句表示如果当前table是null，或者大小=0，就第一次扩容，到16个空间
        
        //(1)根据key,得到hash去计算key应该存放的索引位置
        //并把这个位置的对象，赋给p
        
        //(2)判断p是否为空
        //(2.1)如果p=null，创建节点(key = "java", value = PRESENT)
        //并放在该位置
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            //如果当前索引位置对应链表的第一个元素和准备添加的key的哈希值一样
            //并且满足下列条件之一：
            //(1)准备加入的key和p指向的Node节点的key是同一个对象
            //(2)或者不是一个对象但是值相同，比如同一个类的两个实例
            //就不能加入
            if (p.hash == hash && 
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //判断p是否是一颗红黑树
            //如果是红黑树，调用putTreeVal(涉及红黑树内容多)
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {//链表，循环比较
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        //无相同元素，添加在最后面
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            //如果达到第八个节点，则红黑树化，
                            //红黑树化时还会进行判断是否满足树化条件
                            // if (tab == null || (n = tab.length) <                                                                 
                            // MIN_TREEIFY_CAPACITY(64))
                            //  resize();
                            //如果上面条件成立，则先扩容，只有上面条件不成立才红黑树化
                            treeifyBin(tab, hash);
                        break;
                    }
                    //有相同元素
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;//指针后移
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

4. afterNodeInsertion(evict);

//此方法为HastMap留给子类的方法，在HashMap中为空方法，可理解为C++里的抽象函数

5. HashSet扩容和转成红黑树机制

5.1 HashSet第一次添加时，table数组扩容到16，临界值(threshold)是16 * 加载因子（DEFAULT_LOAD_FACTOR=0.75），如果table数组已用容量到了临界值12，就会扩容到16 * 2 = 32，新的临界值是32 * 0.75 = 24，以此类推。 

5.2 

Java8中，如果一条链表的元素个数达到TREEIFY_THRESHOLD(默认是8)，并且（需要同时

满足）table的大小大于等于MIN_TREEIFY_CAPACITY(默认64)，就会红黑树化。

如果只是一条链表的元素个数达到TREEIFY_THRESHOLD(默认是8)，则会table扩容，直到table扩容至64，单条链表才会树化。

public class HashSet_p {
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();
        for (int i = 1; i <= 12; i++) {
            hashSet.add(new A(i));
        }
        //在i=9时table会从16扩容到32,单条链表不会树化
        //在i=10时table会从32扩容到64，单条链表不会树化
        //在i=11时，满足树化条件，单条链表树化
        System.out.println("hashset=" + hashSet);
    }
}

class A {
    private int n;
    public A(int n) {
        this.n = n;
    }
    //重写hashCode,使此类的实例化对象的hashCode都相等，都为100
    @Override
    public int hashCode() {
        return 100;
    }
}

5.3 putVal中

每增加一个节点（不必在一条单链上），size都会自增1，当满足条件时，table就会扩容。

6.练习：将多个对象存入HashSet中，如果两个对象的某几个指定属性相同则认为这两个对象相同，在存入前者的前提下后者应无法存入。

trick：在类定义中重写equals()方法

class Employee{

    private String name;
    private int age;
    Employee(String name, int age){
        this.name = name;
        this.age = age;
    }
@Override
    public boolean equals(Object o) {
        if (this == o) return true;
        //是同一个对象
        if (o == null || getClass() != o.getClass()) return false;
        //比较对象为空或者不是一个类的实例
        Employee employee = (Employee) o;
        return age == employee.age &&
                Objects.equals(name, employee.name);
    }
}

h + Enter //重写equalsI() 和 hashCode()