### 哈希冲突算法

```java
// HashSet.java
public boolean add(E e) {
        return map.put(e, PRESENT)==null;
}

//HashMap.java
public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)//首先判断链表数组是否为null
            n = (tab = resize()).length;//如果为null则进行初始化，初始化长度为1<<<4，即16。这里可以查看`resize`方法，里面会对数组的cap进行定义。
    //newCap = DEFAULT_INITIAL_CAPACITY;
    //static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
        if ((p = tab[i = (n - 1) & hash]) == null)//判断分配的索引上是否为null，如果为null则直接存储
            tab[i] = newNode(hash, key, value, null);
        else {..... //后续省略
}
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
```

> 当我们调用`HashSet`的`add`方法时，其实是调用了`HashMap`的`put`方法，传入的参数作为`put`方法的键参数，然后调用`putVal`方法。在这里要对传入的key做一个`hash(key)`操作，`(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)`这段代码的目的就是为了尽量让key产生的`hashCode`的32位数字都能够参与到后面的运算中去，之所以使用位异或运算，是因为这个位运算是让产生的16位二进制数字上1和0尽量分布均匀的最佳方法。我们把得到的这个值与数组Node链表数组的初始化默认长度16（即n，后续用n-1：01111与hash(key)返回的值进行位与运算，这里之所以要-1是为了让得到的结果奇偶数都有）的值再进行一次运算，这样就可以把key均匀的分布到链表数组的合个索引上了。哈希冲突算法的目的就是为了让`HashSet`添加元素时，能够均匀的分布到数组的各个位上，提升性能。在`java1.8`及之后做了进一步优化，当索引上链表长度大于7时，则会运用红黑二叉树进行优化。

### 哈希冲突算法

```java
// HashSet.java
public boolean add(E e) {
        return map.put(e, PRESENT)==null;
}

//HashMap.java
public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)//首先判断链表数组是否为null
            n = (tab = resize()).length;//如果为null则进行初始化，初始化长度为1<<<4，即16。这里可以查看`resize`方法，里面会对数组的cap进行定义。
    //newCap = DEFAULT_INITIAL_CAPACITY;
    //static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
        if ((p = tab[i = (n - 1) & hash]) == null)//判断分配的索引上是否为null，如果为null则直接存储
            tab[i] = newNode(hash, key, value, null);
        else {..... //后续省略
}
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
```

> 当我们调用`HashSet`的`add`方法时，其实是调用了`HashMap`的`put`方法，传入的参数作为`put`方法的键参数，然后调用`putVal`方法。在这里要对传入的key做一个`hash(key)`操作，`(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)`这段代码的目的就是为了尽量让key产生的`hashCode`的32位数字都能够参与到后面的运算中去，之所以使用位异或运算，是因为这个位运算是让产生的16位二进制数字上1和0尽量分布均匀的最佳方法。我们把得到的这个值与数组Node链表数组的初始化默认长度16（即n，后续用n-1：01111与hash(key)返回的值进行位与运算，这里之所以要-1是为了让得到的结果奇偶数都有）的值再进行一次运算，这样就可以把key均匀的分布到链表数组的合个索引上了。哈希冲突算法的目的就是为了让`HashSet`添加元素时，能够均匀的分布到数组的各个位上，提升性能。在`java1.8`及之后做了进一步优化，当索引上链表长度大于7时，则会运用红黑二叉树进行优化。