先说结论

对于一张容量为0的 HashMap，会先调用 resize() 方法建立新表，新表的容量为16，阈值为12。在插入元素之后，当检测到插入后的表超过了阈值大小，就会重新调用 resize() 方法对新表进行扩容，并把老表的值按照新表的尺寸依据 hash 插入原则赋值给新表。扩容的原则根据 tableSizeFor() 方法决定，一般来说，扩容会按照之前的2倍来扩容，并根据扩容后的大小和装填因子确认新阈值。

注意：当删除红黑树结点导致其形成某种结构的时候，会剪枝退化为链表。

源码解读

对于 HashSet 而言，其实现了 Set 接口，是 Set 的一种常用的实现类。它依据散列表的机制，对所有的元素进行整合存储，能够保证元素不会产生重复。与此同时，它也是一个可变长度的数据结构，可以根据元素量进行动态扩充，同时为了保证读写的高效性，也在底层实现上进行了一定的优化，形成了现在数组 + 链表 + 红黑树的实现结构。

HashSet 与 HashMap

查看 HashSet 定义代码可以看到，该类对象本质上就是对一个 HashMap 对象进行了包装，使其能够实现 Set 集合的各种方法。其字段定义部分如下所示：

// 存储单元依然是 HashMap 对象
private transient HashMap<E, Object> map;
// 一个静态常量 Object 对象，没有实际意义，用来给 HashMap 中的value占位
private static final Object PRESENT = new Object();

观察 HashSet 的众多方法也可以看出，许多方法的实现都需要依赖 HashMap 的方法，如：

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

因此，对 HashSet 内部存储机制的解读，本质上就是对 HashMap 存储机制的解读。

HashMap 存储机制

HashMap 的字段显示，其存储实现是一个 HashMap.Node 类的对象数组。可以查看 HashMap 类中的字段声明来加深理解。

private static final long serialVersionUID = 362498820763181265L;
// 默认的最初容量值为16
static final int DEFAULT_INITIAL_CAPACITY = 16;
// HashMap 对象最大容量值
static final int MAXIMUM_CAPACITY = 1073741824;
// 默认的装填因子为0.75
static final float DEFAULT_LOAD_FACTOR = 0.75F;
// 红黑树化阈值为8，当拉链长度达到这个值时，达到红黑树化条件一
static final int TREEIFY_THRESHOLD = 8;
// 不红黑树化阈值为6
static final int UNTREEIFY_THRESHOLD = 6;
// 最小树化容量为64，当表容量达到这个值时，达到红黑树化条件二
static final int MIN_TREEIFY_CAPACITY = 64;
// 元素结点的底层存储为一个 HashMap.Node 类的对象数组
transient HashMap.Node<K, V>[] table;
// Set 包装后的 HashMap 对象，该对象可以使得 HashMap 对象当作 Set 使用
transient Set<Entry<K, V>> entrySet;
// HashMap 实际元素数量
transient int size;
// 操作计数，与多线程和线程同步有关
transient int modCount;
// 当前阈值，用于初始化时指定容量的情况
int threshold;
// 装填因子，用于初始化时指定装填因子的情况
final float loadFactor;

装填因子与默认装填因子

HashMap 可以用带参和无参构造器构造对象，Java 给出了指定 HashMap 装填因子及阈值的方法，如下所示：

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0) {
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    } else {
        if (initialCapacity > 1073741824) {
            initialCapacity = 1073741824;
        }
        if (!(loadFactor <= 0.0F) && !Float.isNaN(loadFactor)) {
            this.loadFactor = loadFactor;
            this.threshold = tableSizeFor(initialCapacity);
        } else {
            throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
        }
    }
}
public HashMap(int initialCapacity) {
    this(initialCapacity, 0.75F);
}
public HashMap() {
    this.loadFactor = 0.75F;
}
static final int tableSizeFor(int cap) {
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    return n < 0 ? 1 : (n >= 1073741824 ? 1073741824 : n + 1);
}
public static int numberOfLeadingZeros(int i) {
    if (i <= 0) {
        return i == 0 ? 32 : 0;
    } else {
        int n = 31;
        if (i >= 65536) {
            n -= 16;
            i >>>= 16;
        }
        if (i >= 256) {
            n -= 8;
            i >>>= 8;
        }
        if (i >= 16) {
            n -= 4;
            i >>>= 4;
        }
        if (i >= 4) {
            n -= 2;
            i >>>= 2;
        }
        return n - (i >>> 1);
    }
}

可以看出，调用有参的构造器时，HashMap 会初始化表的装填因子，并按照一定的策略计算得到表的大小，无论如何都不会超过最大容量值。而对于无参的构造器，则会直接将装填因子默认设置为0.75，且不指定初始容量。

hash()

在讨论 put() 方法之前先讨论 hash() 方法，该方法是用来求得 HashMap 中元素的 hash 值的，从源码中不难看出这个 hash 值与 Object 类中定义的 hashCode() 并不一样，但具有相当的关系。当 key 为 null 值的时候，hash 值固定为空，此方法将用于后续的 put() 方法。

static final int hash(Object key) {
    int h;
    return key == null ? 0 : (h = key.hashCode()) ^ h >>> 16;
}

put()

此处假设创建对象的时候采用的是无参的构造器，以此来查看其扩容机制。由 HashSet 中的 add() 方法可以看出，其通过调用 map 对象的 put() 方法实现元素的添加。put() 方法及其依赖的 putVal() 方法展示如下：

public V put(K key, V value) {
    return this.putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    HashMap.Node[] tab;
    int n;
    // 判断 HashMap 中的 table 是否为 null 或者为空表
    // 如果是就调用 resize() 方法生成一个新表并赋值给临时变量 tab
    if ((tab = this.table) == null || (n = tab.length) == 0) {
        n = (tab = this.resize()).length;
    }
    Object p;
    int i;
    // 判断 tab 表中 (n - 1) & hash 对应的索引是否为空，如果是就把这个结点挂载到对应的位置
    if ((p = tab[i = n - 1 & hash]) == null) {
        tab[i] = this.newNode(hash, key, value, (HashMap.Node)null);
    // 如果索引不是空，进行查重判断
    } else {
        Object e;
        Object k;
        // 变量 p 是 table 该索引中的那个变量
        // 如果当前索引位置的第一个结点的 hash 相同且 key 相同
        // key 相同的条件：为同一个对象，或者在 equals() 的意义上相等
        // 就把原来那个变量 p 赋值给 e
        if (((HashMap.Node)p).hash == hash && 
            ((k = ((HashMap.Node)p).key) == key || key != null && key.equals(k))) {
            e = p;
        // 判断变量 p 是不是一棵红黑树，如果是就采用红黑树的方式进行比较和添加元素
        } else if (p instanceof HashMap.TreeNode) {
            e = ((HashMap.TreeNode)p).putTreeVal(this, tab, hash, key, value);
        // 拉链为链表的情况下的处理方式
        } else {
            int binCount = 0;
            while(true) {
                // 加到最后面
                if ((e = ((HashMap.Node)p).next) == null) {
                    ((HashMap.Node)p).next = 
                        this.newNode(hash, key, value, (HashMap.Node)null);
                    // 添加到第8个元素后，就将链表红黑树化
                    if (binCount >= 7) {
                        this.treeifyBin(tab, hash);
                    }
                    break;
                }
                // 查到重复的了，就跳出循环
                if (((HashMap.Node)e).hash == hash && 
                    ((k = ((HashMap.Node)e).key) == key || key != null && key.equals(k))) {
                    break;
                }
                p = e;
                ++binCount;
            }
        }
        // 如果 e 不为 null，就代表没有插入元素，对于 HashMap 而言需要更新键值对中的值
        if (e != null) {
            V oldValue = ((HashMap.Node)e).value;
            if (!onlyIfAbsent || oldValue == null) {
                ((HashMap.Node)e).value = value;
            }
            this.afterNodeAccess((HashMap.Node)e);
            return oldValue;
        }
    }
    ++this.modCount;
    // 当前表的容量大于阈值的时候，就对表进行扩容
    if (++this.size > this.threshold) {
        this.resize();
    }
    // 在 HashMap 中为一个空方法，方便子类实现更高级的功能
    this.afterNodeInsertion(evict);
    // 返回 null 代表添加成功
    return null;
}
final HashMap.Node<K, V>[] resize() {
    HashMap.Node<K, V>[] oldTab = this.table;
    // 得到之前表格的大小
    int oldCap = oldTab == null ? 0 : oldTab.length;
    // 得到之前表格的阈值
    int oldThr = this.threshold;
    // 新表的阈值
    int newThr = 0;
    // 新表的容量
    int newCap;
    if (oldCap > 0) {
        if (oldCap >= 1073741824) {
            this.threshold = 2147483647;
            return oldTab;
        }
        if ((newCap = oldCap << 1) < 1073741824 && oldCap >= 16) {
            newThr = oldThr << 1;
        }
    // 如果一开始表为空表但阈值不为0，就按照阈值设置新表大小
    } else if (oldThr > 0) {
        newCap = oldThr;
    } else {
        // 当老表的阈值和容量都为0的时候，就用把新表容量设置为16，阈值设置为12
        newCap = 16;
        newThr = 12;
    }
    if (newThr == 0) {
        float ft = (float)newCap * this.loadFactor;
        newThr = newCap < 1073741824 && ft < 1.07374182E9F ? (int)ft : 2147483647;
    }
    // 新表阈值赋值给阈值字段
    this.threshold = newThr;
    // 按照新表容量创建新表
    HashMap.Node<K, V>[] newTab = new HashMap.Node[newCap];
    this.table = newTab;
    // 把老表的内容复制到新表中去
    if (oldTab != null) {
        for(int j = 0; j < oldCap; ++j) {
            HashMap.Node e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null) {
                    newTab[e.hash & newCap - 1] = e;
                } else if (e instanceof HashMap.TreeNode) {
                    ((HashMap.TreeNode)e).split(this, newTab, j, oldCap);
                } else {
                    HashMap.Node<K, V> loHead = null;
                    HashMap.Node<K, V> loTail = null;
                    HashMap.Node<K, V> hiHead = null;
                    HashMap.Node hiTail = null;
                    HashMap.Node next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null) {
                                loHead = e;
                            } else {
                                loTail.next = e;
                            }
                            loTail = e;
                        } else {
                            if (hiTail == null) {
                                hiHead = e;
                            } else {
                                hiTail.next = e;
                            }
                            hiTail = e;
                        }
                        e = next;
                    } while(next != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    // 返回新表
    return newTab;
}

可以看到，对于一张容量为0的 HashMap，会先调用 resize() 方法建立新表，新表的容量为16，阈值为12。在插入元素之后，当检测到插入后的表超过了阈值大小，就会重新调用 resize() 方法对新表进行扩容，并把老表的值按照新表的尺寸依据 hash 插入原则赋值给新表。

插入过程

上节中源码也注释了插入元素的过程，即现根据插入元素的 hash 值计算出应该放入哪个索引中，然后对该索引进行判断：

1. 若该索引中为空值，就直接把元素存储到索引中；
2. 若该索引中不为空值，且已经是一个红黑树结点，就利用 putTreeVal() 方法在该红黑树中查重和插入；
3. 若该索引中不为控制且只是一个链表结点，就依次判断每个结点是否产生重复，若没有重复就在最后插入，插入后立即判断是否达到红黑树建立条件（某个索引链表长度达到8且 table 容量达到64），若满足则将该索引处的结点红黑树化，否则继续扩容，若有重复，就根据 HashMap 的操作法则对 Value 值进行更新。

onlyIfAbsent 参数用于控制 key 出现重复后是否更新 value，默认是更新的，即为 false。HashMap 的其他子类通过 AfterNodeAccess() 和 AfterNodeInsertion() 方法实现结点处理后的高级功能。

注意：当删除红黑树结点导致其形成某种结构的时候，会剪枝退化为链表。