Set - HashSet - 《Java 基础知识》

HashSet底层机制说明：

分析HashSet底层时Hashmap,HashMap底层是（数组+链表+红黑树） ```

HashSet底层是HashMap
添加一个元素时，先得到hash值 - 会转化成 -> 索引值
找到存储数据表table，看这个索引位置是否已经存放有元素
如果没有直接加入
如果有，调用equals进行比较，如果相同，就放弃添加，如果不相同，则添加到最后
在java8中，如果一条链表的元素个数超过8，并且table的大小>= 64,就会进行树化（红黑树）注意：如果一条链表的元素个数到达8个，但是table的大小<64，则不进行树化，相对的会对table表进行扩容 ```

分析HashSet的扩容和转化成红黑树机制 ```

HashSet底层是HashMap，第一次添加时，table数组扩容到16，临界值是16*加载因子是0.75 = 12
如果table数组使用到了临界值12，就会扩容到162 = 32，新的临界值就是320.75 = 24，以此类推
在java8中，如果一条链表的元素个数到达TREEIFY_THRESHOLD(默认是8)，并且table的大小>=MIN_TREEIFY_CAPACITY(默认64)，就会进行树化，否则仍然采用数组扩容机制 ```

分析HashSet的添加元素，底层是如何实现的(hash() + equals()) ```

先获取元素的哈希值(hashCode方法)
对哈希值进行运算，得出一个索引值即为要存放在哈希表中的位置号
如果该位置上没有其他元素，则直接存放，如果该位置上已经有了其他元素，则需要进行equals判断，如果相等则不再添加，如果不相等则以链表的方式添加。
```
HashSet源码解析
```java
public class HashSetSource {
 public static void main(String[] args) {
     HashSet hashSet = new HashSet();
     hashSet.add("java");
     hashSet.add("php");
     hashSet.add("java");
     System.out.println("set = " + hashSet);
 }
}
```
```java // HashSet源码解读 // 1.执行 HashSet() public HashSet() { map = new HashMap<>(); }

// 2.执行add() public boolean add(E e) { return map.put(e, PRESENT)==null; //(static) PRESENT = new Object(); }

// 3.执行put() public V put(K key, V value) { // key = “java” value = PRESENT 共享 return putVal(hash(key), key, value, false, true); }

// 4.执行putVal final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; // 定义了辅助变量 // table 就是HashMap的一个数组，类型是Node[] // if 语句表示如果当前table时null或者大小=0时，就进行第一次扩容到16个空间 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length;

    // (1)根据key值，得到hash 去计算该key应该存放到table表的哪个索引位置，并把这个位置的对象赋给p
    // (2)判断p是否为null
    // (2.1) 如果p为null，表示还没有存放元素，就创建一个Node（Key="java",value=PRESENT)
    // (2.2) 就放在该位置 tab[i] = newNode(hash, key, value, null);
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // 一个开发的小技巧提示：在需要局部变量（辅助变量）时候，在创建
        Node<K,V> e; K k;
        // 如果当前索引位置对应的链表的第一个元素和准备添加的key的hash的值一样
        // 并且满足下面两个条件之一
        // (1)准备加入的key和p直线大哥Node结点的key是同一个对象
        // (2)p指向的Node结点的key 的equals() 和准备加入的key比较后相同
        // 就不能加入
        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 {
        // 如果table对应索引位置，已经是一个链表，就用for进行比较
        // (1)依次和链表的每一个元素进行比较后，立即判断，该链表是否已经到达八个结点，
        // 就调用treeifyBin()对当前这个链表进行树化（转化成红黑树）
        // 注意：在转化成红黑树时，要进行判断，判断条件
        // if(tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY(64))
        //     resize();
        // 如果上面条件成立，先table扩容，只有上面条件不成立时才进行
        // (2)依次和该链表的每一个元素比较过程中，如果有相同的情况，就直接break
            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
                        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;
    // size 就是我们每加入一个节点Node(k,v,h,next),size++
    if (++size > threshold)
        resize();   // 扩容
    afterNodeInsertion(evict);
    return null;
}

```