首页 java source

# 字段

# table: Entry<K, V>[]

哈希表，数组实现，用于存放元素；每一格是一个哈希桶（链表实现）。

HashMap$Entry<K, V> {
    key: K;
    value: V;
    next: Entry<K, V>;
    hash: int;
}

# threshold: int

扩容的阈值，如果达到此阈值，则进行扩容；下一扩容容量 * loadFactor。

# loadFactor: float

用于计算扩容阈值（threshold）。

# size: int

元素个数。

# modCount: int

  1. modifyCount 修改次数，只会累加；执行修改操作影响到 key 才会 + 1，如：put, remove, clear；如果只是修改 value，则 modCount 不会变化。
  2. 目的是为了迭代器遍历时判断集合的结构（key 变化）是否被修改。
    a. 初始化迭代器时会保存此值，每次迭代会比较集合的 modCount 和迭代器的 modCount 是否一致
    如果发生变化，就认为集合被修改了，然后立即抛出异常 ConcurrentModificationException

# hashSeed: int

用于生成 hash，0 或 随机值（为了降低 hash 碰撞）

# 构造函数

constructor

  1. 检查入参 ：initialCapacity [初始容量]、loadFactor [负载因子]：
    a. initialCapacity 的范围 [0,1≪30][0, 1 \ll 30]
    b. loadFactor 大于 0，且非 NaN
  2. 赋值 threshold，loadFactor：
    a. 默认 threshold = 16, loadFactor = 0.75
  3. init 空函数钩子：
    a. 初始化集合后可自定义额外功能；子类继承可以实现此方法
  4. table 是懒初始化

# 初始化 table

按需初始化，插入元素时才开始初始化 table。

init_table-put

  1. 插入元素，先判断 table 是否为空表；如果是，执行初始化 table 操作

# inflateTable

init_table-inflateTable

  1. 将初始化的大小转换为 2 的 n 次幂形式，但不超过本身值，转换后作为容量值
  2. 设置阈值 threshold = 容量值 * loadFactor；不能超过最大值 (1 << 30) + 1
  3. 创建 table 数组，容量值为第 1 步计算出来的值
  4. 按需初始化 hashSeed，后续根据 key 计算 hash 时需要

# roundUpToPowerOf2

roundUpToPowerOf2

  1. 判断入参的范围 [1,1≪30][1, 1 \ll 30] 的边界值，超出范围则设置为边界值
  2. 非边界值，且在范围 [1,1≪30][1, 1 \ll 30] 内，则转换为：最大的 2 的幂数，且不大于本身
    如：
    16 --> 16
    15 --> 8
  3. 2 的幂数：取整数的二进制形式的最高位即可 Integer.highestOneBit ()

# highestOneBit

Integer-highestOneBit

  1. 如何将低位全部置为 1
    a. 32 位整数：5 次 [右移 + 相加] 即可，右移分别为：1, 2, 4, 8, 16
    binary-set-all-to-1
  2. 获取整数的二进制形式的最高位 1
    a. 低位全部置为 1
    b. 无符号右移 1 位
    c. 相减
    highestOneBit

# initHashSeedAsNeeded

initHashSeedAsNeeded

一、此函数的目的是设置 hashSeed 的值

  1. 容量达到一定数量后，hash 碰撞机率会逐渐增大，因此到达一定阈值，需要使用随机 hashSeed
  2. 扩容容量低于替换阈值，使用 0；扩容容量高于替换阈值，使用随机值（降低 hash 碰撞）
    a. 第一次：hashSeed 默认值 0，容量 [未达到] 替换阈值，switching = false
    switching = currentAltHashing ^ useAltHashing;
    // false = false ^ false
    b. 第二次：hashSeed 默认值 0，容量 [达到] 替换阈值，switching = true，生成随机 hashSeed
    switching = currentAltHashing ^ useAltHashing;
    // true = false ^ true
    c. 第三次：hashSeed 是随机值，容量 [达到] 替换阈值，switching = false；已经是随机值，不需要再次生成
    switching = currentAltHashing ^ useAltHashing;
    // false = true ^ true
    d. 第四次：hashSeed 是随机值，容量 [未达到] 替换阈值，switching = true；容量已经下降到阈值以下，hashSeed 随机值重置为 0
    switching = currentAltHashing ^ useAltHashing;
    // true = true ^ false

二、控制 hashSeed 的参数

  1. currentAltHashing：当前 hashSeed 是否为随机值
  2. useAltHashing：扩容容量是否超出替换阈值，且 VM 是否已启动
  3. switching：hashSeed 需要替换；由 currentAltHashing ^ useAltHashing 决定

三、随机值生成：ThreadLocalRandom.current ().nextInt ()
randomHashSeed

四、替换阈值，在 HashMap$Holder 中持有
holder-threshold

初始化 Holder.ALTERNATIVE_HASHING_THRESHOLD 规则；根据 jdk.map.althashing.threshold 配置来初始化静态成员变量：

  1. 不配置（默认）或 -1：阈值设置为 Integer.MAX_VALUE 值，表示不启用随机 hashSeed。
    a. 由于阈值是 Integer.MAX_VALUE，此阈值是条件无法达到的，因此表示关闭。
    b. 不启用随机的 hashSeed，但 hashSeed 默认值为 0，使用 0 作为 seed。
  2. 小于 0：抛出 Error 异常。
  3. >= 0：当容量 >= 阈值时，开启随机 hashSeed。

Holder 的作用是为了懒加载，用到此类才加载此类；静态代码块在加载类期间执行，jvm 会保证线程安全。

# 添加 null key 元素

null_key_put-put

  1. 插入元素，如果 key 为 null，则执行 putForNullKey 操作。

# putForNullKey

putForNullKey

key 为 null 的元素，存放到 table [0] 下面：

  1. 先判断 null key 元素在 table [0] 的链表上是否已经存在，for 循环遍历 Entry 链表。
  2. null key 存在于链表上：for 循环定位到具体 Entry，则修改 Entry 的值，然后返回旧值。
    a. recordAccess 是钩子函数，在 HashMap 是空方法；LinkedHashMap 中实现了重排序。
    b. recordAccess 只有在 put 方法中覆盖 value 时（key 已经存在）才调用；可以实现扩展功能，如 LinkedHashMap 的 accessOrder 属性。
  3. null key 不存在于链表上：modCount++ 然后在 table [0] 下面添加新 Entry，返回旧值 null（新增没有旧值）。
    addEntry
    a. 如果元素超过扩容阈值，且当前数组下标下链表为空（当前桶为空）；则进行扩容
    b. 在此数组下标下的链表添加元素，size++：头插法
    createEntry

# 添加非 null key 元素

put

  1. 计算 key 的 hash 值。
  2. 计算 hash 值对应的桶下标：h & (length-1)；确保 length 是 2 的 n 次幂，则等价于 h % length。
  3. 得到桶在数组里的下标后，遍历桶元素，判断此 key 是否已经存在于桶（链表）中。
    a. 如果存在于桶中：hash, key 要一致；在遍历过程中得到 Entry，更新 Entry 的值，然后返回旧值。
    b. 不存在于桶中：modCount++ 然后在桶中添加新元素：头插法。

# hash 计算

hash

如果 hashSeed 不等于 0，且是字符串，则使用 sun.misc 的工具类计算。

  1. hashSeed 异或 key 的 hashCode。
  2. 扰动函数 / 计算，高位和低位进行异或，增加随机性，为了降低 hash 的冲突。

# 获取 key 元素

get

  1. 判断 key 是否为 null，如果为 null，则调 getForNullKey 函数。
    getForNullKey
    a. 判断 size 是否有元素。
    b. 从数组第 0 个桶里遍历，是否存在 key 为 null 的元素，然后返回 Entry 的值；找不到返回 null。
  2. 如果 key 不为 null，调 getEntry 获取 Entry。
    getEntry
    a. 判断 size 是否有元素。
    b. 计算 key 的 hash 值，计算 hash 对应 table 数组的下标，即桶的位置。
    c. 遍历桶里是否存在 hash, key 都相等的元素，然后返回 Entry；找不到就返回 null。
  3. 返回 entry.value，需要进行空指针判断。

# 移除 key 元素

remove

移除元素，然后取得元素对应的 Entry，最后返回 Entry 的值

removeEntryForKey

# 扩容

put() -> addEntry()

元素个数达到扩容阈值，且当前桶元素不为空，才执行扩容；新扩容容量是原容量的 2 倍。

addEntry

# resize

resize

  1. 如果原 table 的容量已经是最大值，则设置扩容的阈值为 Integer.MAX_VALUE；然后直接退出。
  2. 创建新表 newTable，容量是原容量的 2 倍。
  3. 旧表的数据迁移到新表，以及按需重新计算全部元素的 hash（hashSeed 变化则需要重新计算 hash）。
    transfer
    a. 遍历旧表所有桶；遍历桶里的所有元素。
    b. 先记录当前处理的结点的后继结点（下一轮循环需要），否则 e.next 在迁移结点过程中被覆盖。
    c. 如果需要重新计算 hash（入参 rehash），则重新计算当前结点元素 key 的 hash 值。
    d. 根据 hash 值和新表的容量，计算新表的下标；然后头插法将当前结点迁移到新表中。
    e. 继续下一轮循环：e == null 则表示到达链表的尾部，终止链表循环，进行下一个桶的循环。
  4. 新表替换旧表。
  5. 重新计算下次扩容的阈值，扩容阈值 = 新容量 * 负载因子；不能超出最大容量 + 1。

# 死链的原因

  1. 多线程扩容后，都执行完 next = e.next
    扩容
  2. 线程 2 的 CPU 时间片用完而暂停，线程 1 继续执行迁移代码
    线程1迁移
  3. 线程 1 执行完成后，线程 2 继续运行，执行迁移代码，导致链表出现环状
    线程2迁移
  4. 调用 hashmap.get (key) 后，如果访问到环，且 key 不存在，则导致死循环

# 死链的复现

# 设置断点

JDK 1.7 版本代码，设置断点：

设置断点

  1. 在 next = e.next 的下一行代码设置条件断点，即 if (rehash) 这里
    a. 条件断点："t1,t2".contains (Thread.currentThread ().getName ())
    b. 使用 contains 或 equals 来比较，不要用 == 比较；字符串对象可能内存不同
  2. 等到 t1, t2 线程都停在此处后，删除断点；然后依次执行完 t1, t2 线程的代码，这样就构造出环状的链表了。

# 构造模拟代码

// 在 HashMap 的 transfer 代码里的 if (rehash) 这条语句里
// 添加条件断点："t1,t2".contains (Thread.currentThread ().getName ())
// 添加普通断点也是可以的，这里为了防止其它线程干扰
// 在启动 main 方法前设置断点，debug 模式运行
public static void main(String[] args) throws InterruptedException {
    // 初始化容量为 16，扩容阈值 = 16 * 0.75 = 12，即超过 12 个就触发扩容
    final HashMap<Integer, Integer> map = new HashMap<>();
    // 填充 10 个元素
    for (int i = 2; i < 12; i++) {
        map.put(i, i);
    }
    // 构造特定的 key，让它们都在同一个桶下面，还要考虑扩容后的下标也是一致的
    // 以下 key 计算出来的下标都一样（容量为 16 且 32 时）：
    // 1, 35, 69, 103, 136, 170
    map.put(1, 1);
    map.put(35, 35);
    // 以上插入了 12 个元素，1 和 35 都在下标为 1 的桶里
    // 触发扩容条件：哈希表里元素个数达到扩容阈值，且新插入的元素的桶里有元素，
    // 这里下标 1 的桶里有 1, 35
    // 线程 1， 线程 2 同时触发扩容
    Thread t1 = new Thread(new Runnable() {
        public void run() { // 1.7 不支持 lambda 表达式
            map.put(56, 56);
        }
    }, "t1");
    Thread t2 = new Thread(new Runnable() {
        public void run() {
            map.put(56, 56);
        }
    }, "t2");
    t1.start(); t2.start();
    t1.join(); t2.join();
    //t1, t2 同时进入断点后，先放开 t1 线程的断点，让 t1 跑完
    // 然后再放开 t2 线程的断点，让 t2 跑完
    // 此时，下标为 1 的桶，形成了环状链表
    // 导致死循环：69 的下标也是 1，但这个位置的桶已经形成环状链表
    // 但里面没有此元素，则死循环地查找
    map.get(69);
}
  1. 10 个任意的元素 + 2 个特殊的元素（在同一个桶里） = 12
  2. 插入第 13 个元素，且此元素的桶里有元素（上面构造 2 个特殊元素），才能触发扩容
  3. 以下 key 是在容量 16 或 32 的时候，桶下标一致的：
    1, 35, 69, 103, 136, 170