为什么放在一起讲呢？本质上它们俩没有什么区别。

首先，我们来看一下HashSet的源码：

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    private transient HashMap<E,Object> map;
    
    public HashSet() {
        map = new HashMap<>();
    }
}

这不就是HashMap嘛，哈哈。所以，我们先从HashMap讲起。

HashMap也没有什么好说的，都很熟悉的嘛，Key-Value类型的数据结构，通过Key能快速的得到Value。

HashMap的底层也是一个数组：

transient Node<K,V>[] table;

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;

        return o instanceof Map.Entry<?, ?> e
                && Objects.equals(key, e.getKey())
                && Objects.equals(value, e.getValue());
    }
}

put()方法：

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)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        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
                        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;
}

是不是挺复杂度？

不管怎么实现的，逻辑都是相通的。

1. 对Key进行hash计算，得到Key对象的hash值
2. 通过hash值得到命中的数组索引（可以取模或者位运算）
3. 在索引的位置存入对应的Value值

下面来说一下这三步中的细节：

对于第一步来说，我们要求Key必须是不可变对象，并且一定要重写hashcode和equals方法。其实这很好理解，如果对象状态可变，那么就会出现Key无法命中或者其他一些极端情况。Object类中的hashcode方法，会返回一个对象的唯一id，也就是说，不同的对象，使用默认的hashcode方法，得出的hash值是不同的。

我们一般使用String对象当做Key，它是不可变的，并且重写了hashcode。如果没有重写hashcode的话，那么会造成这样一种现象：字符串的字面量是相同的，两个对象所在的内存地址不同，hash值不同，导致互相无法命中的情况。

止于为什么要重写equals，在第三步的时候，下文会详细叙述的。

第二步没有什么好说的，都能理解。但是在这一步会出现一个非常重要的现象，那就是哈希冲突。不同Key对象的hash值是可能重复的，也就是计算后的索引值会相同，此时如果索引对应的位置已经有元素了，就产生了哈希冲突。

HashMap解决哈希冲突采用的是 链表 + 红黑树 的策略。

既然哈希冲突无法避免，那么就装在一起嘛，哈哈。也许你之前听到过桶（bucket）这样一个概念，数组每一个下标就对应一个 bucket。

很形象的嘛，所有起冲突的键值对放在一个桶里面。其实就是用链表串起来。

这时候就需要 equeals 了。Object类默认的 equeals 方法判断是 “==”，即判断是不是相同的对象。还是那个问题，我们需要的逻辑是对象状态相同而不是对象相同，所以必须重写 equeals 。用 equeals 方法来判断对象状态是否相等。（遍历链表）

关于链表的插入，JDK8之前采用头插法，JDK8之后采用尾插法。头插法在多线程的环境下易导致链表成环，线程无限循环，在CPU上空转。

红黑树主要是对查找的优化，当链表长度大于8时，链表转成红黑树；树中的元素小于6时，转成链表。

最后提一点，负载因子这个概念。

随着时间的推移，HashMap中的元素会越来越多，哈希冲突发生的概率越来越高，性能逐渐退化。哈希冲突的本质就是命中同样的数组索引，把数组进行扩大之后，命中相同索引的概率就降低了。而负载因子，就是决定是否扩容的阈值。Java中，默认是0.75：

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

即，当HashMap中的元素格式超过 16 * 0.75 = 12 时，就会触发扩容机制。扩大一倍，并进行rehash。

该操作比较消耗性能，为了降低频繁扩容的概率，最好根据实际的业务场景指定一个合理的初始化容量。

对于 HashSet：

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

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

不必多言了吧。

---

2024.10.29

writeBy kaiven