HashMap¶

HashMap 初始容量是16，负载因子为 0.75

查找¶

index = (lenght - 1) & hash 计算出桶的位置

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

hash函数使用高位数据与低位数据进行异或，以此加大低位信息的随机性

遍历链表、红黑树查找

遍历¶

会先遍历桶数组，找到包含链表节点，然后遍历该桶所指向的链表。然后继续寻找下一个不为空的桶

插入¶

定位要插入的键值对属于哪个桶
- 桶空，当桶数组 table 为空时，通过扩容的方式初始化 table
查找链表中，要插入的键值对是否已存在。若存在且不同，则覆盖；不存在，则插入。
- 并根据链表长度决定是否将链表转为红黑树
判断键值对数量是否大于阈值，大于的话则进行扩容操作

扩容¶

条件：HashMap中的元素个数（size）超过临界值（threshold）时就会自动扩容

计算新桶数组的新容量 newCap 和新阈值 newThr （ 扩大两倍）
创建新的桶数组
将键值对节点重新映射到新的桶数组里。对于树形节点，需先拆分红黑树再映射。对于链表类型节点，则需先对链表进行分组，然后再映射。链表：计算hash & oldCap，将0与非0的结果分别储存在两个链表。分组后，组内节点相对位置保持不变。

树化¶

链表长度大于等于 TREEIFY_THRESHOLD （默认为8）
桶数组容量大于等于 MIN_TREEIFY_CAPACITY （默认为64）

当桶数组容量比较小时，优先扩容，避免一些列的不必要的树化

其他¶

桶数组 table 被申明为 transient，不会被默认的序列化机制序列化
1. table 多数情况下是无法被存满的，序列化未使用的部分，浪费空间
2. 同一个键值对在不同 JVM 下，所处的桶位置可能是不同的，在不同的 JVM 下反序列化 table 可能会发生错误。
容量为2的幂

h & (length - 1) == h % length
- 使用位运算更快
- Length - 1的值的二进制所有的位均为1，Index的结果等于hashCode的最后几位。只要输入的hashCode本身符合均匀分布，Hash算法的结果就是均匀的。

与1.7对比¶

数据结构：数组 + 链表 -> 数组 + 链表 + 红黑树
初始化方式：单独函数 -> 集成函数 resize( )
插入方法：头插法 -> 尾插法
扩容后 rehash 方法：重新计算 -> 直接使用原位置 or 原位置 + 旧容量

HashSet¶

底层使用 HashMap ，并实现了 Set 接口，把数据作为 Key，一个相同的虚值作为 Value。