摘要：我们来深入探讨 HashMap 源码中用于降低哈希冲突概率的算法。哈希冲突是哈希表性能的瓶颈，HashMap 为了尽量减少哈希冲突，并有效地处理冲突，采取了一系列精巧的算法和策略。
我们来深入探讨 HashMap 源码中用于降低哈希冲突概率的算法。哈希冲突是哈希表性能的瓶颈，HashMap 为了尽量减少哈希冲突，并有效地处理冲突，采取了一系列精巧的算法和策略。
主要从以下几个方面来分析 HashMap 如何降低哈希冲突概率：
优秀的哈希函数 (Hash Function)扰动函数 (扰动计算)合理的哈希表容量 (Capacity) 和扩容机制 (Resizing)均匀分布的哈希桶索引计算1. 优秀的哈希函数 (Hash Function)
HashMap 首先依赖于一个好的哈希函数。哈希函数的目标是将键 (Key) 转换为一个整数哈希码 (hash code)。一个好的哈希函数应该具备以下特点：
高效性 (Efficiency): 计算速度快，不成为性能瓶颈。均匀分布性 (Uniform Distribution): 将键均匀地散列到整数范围内，减少哈希值聚集在某些区域的可能性。在 HashMap 中，哈希函数的实现主要体现在 hash(Object key) 方法中：
Java复制代码 static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode) ^ (h >>> 16);}源码分析:
key == null 的情况: 如果键为 null，则哈希值为 0。HashMap 允许键为 null，并且 null 键总是被映射到哈希表索引 0 的位置。key.hashCode: 调用键对象自身的 hashCode 方法来获取初始哈希码。java 中所有的对象都继承自 Object 类，Object 类提供了 hashCode 方法。关键在于，我们通常需要根据键的类型，重写 hashCode 方法，以提供更适合该类型的哈希函数。 例如，String 类的 hashCode 方法就经过精心设计，能够为不同的字符串生成相对均匀分布的哈希码。^ (h >>> 16) (扰动计算): 这是 扰动函数 的核心部分。它将初始哈希码 h 与 h 无符号右移 16 位后的值进行 异或 (XOR) 运算。扰动函数的作用 (降低哈希冲突):
高位信息与低位信息混合: hashCode 方法产生的哈希码通常是一个 32 位的整数。HashMap 的哈希表索引计算通常只使用哈希码的低位 (因为哈希表容量通常小于 2^32)。 扰动函数 (h ^ (h >>> 16)) 的作用是将哈希码的高 16 位与低 16 位进行异或运算，将高位的信息混合到低位中。提高哈希码的随机性: 即使键的 hashCode 方法实现得不是非常均匀，扰动函数也能增加哈希码的随机性，使得最终的哈希值分布更均匀，从而降低哈希冲突的概率。为什么右移 16 位？
经验值和性能考虑: 32 位整数右移 16 位，正好是将高半区移动到低半区。这是一个经验值，在实践中被证明能够有效地提高哈希值的随机性。同时，位运算的效率很高，不会带来明显的性能开销。总结：优秀的哈希函数 + 扰动函数
HashMap 通过结合键对象自身的 hashCode 方法和扰动函数 (h ^ (h >>> 16))，生成最终的哈希值。扰动函数的引入，增强了哈希值的随机性，使得即使初始哈希码分布不均匀，最终的哈希值也能更均匀地分布，从而降低哈希冲突的概率。
2. 合理的哈希表容量 (Capacity) 和扩容机制 (Resizing)
初始容量 (Initial Capacity): HashMap 的初始容量决定了哈希表数组的初始大小。默认初始容量为 16 (DEFAULT_INITIAL_CAPACITY = 1 扩容机制 (Resizing): 当 HashMap 中存储的键值对数量达到扩容阈值 (threshold = capacity * loadFactor) 时，HashMap 会自动进行扩容。扩容会将哈希表容量扩大为原来的两倍 (通常是 2 倍，但也有例外情况，例如达到最大容量时)。容量和扩容对降低哈希冲突的作用:
控制哈希表的填充程度: 通过负载因子 (loadFactor) 控制哈希表的填充程度。负载因子越小，哈希表越 “空”，哈希冲突的概率越低，但空间利用率也越低。负载因子越大，哈希表越 “满”，空间利用率高，但哈希冲突的概率增加。默认负载因子 0.75 是一个在时间和空间效率之间 trade-off 的经验值。动态调整容量，分散元素: 当哈希表填充到一定程度时，扩容操作会增加哈希表的容量。容量的增加会改变哈希桶索引的计算方式 (因为哈希桶索引计算依赖于容量大小)。 扩容后，原本哈希冲突比较严重的桶中的元素，可能会被重新散列到不同的桶中，从而分散元素，降低哈希冲突的概率，提高查找效率。扩容过程中的 rehash (重新哈希):
扩容不仅仅是简单地扩大数组容量。扩容的关键步骤是 rehash (重新哈希)。
创建新的哈希表: resize 方法会创建一个容量是原来两倍的新哈希表 (新的 Node newTab)。重新计算索引: 遍历旧哈希表中的所有键值对，对每个键重新计算哈希值，并根据新的哈希表容量计算新的索引位置。迁移元素: 将旧哈希表中的元素迁移到新的哈希表中对应的索引位置。在迁移过程中，链表可能会被拆分或保持原状，红黑树也需要进行相应的调整。总结：合理的容量和扩容机制
HashMap 通过设置合理的初始容量和负载因子，以及动态的扩容机制，来控制哈希表的填充程度，并在必要时通过扩容和 rehash 操作，分散哈希表中的元素，降低哈希冲突的概率，维持较高的性能。
3. 均匀分布的哈希桶索引计算
在 HashMap 中，计算哈希桶索引的关键代码是：
java复制代码 i = (n - 1) & hash其中：
i: 计算得到的哈希桶索引。n: 当前哈希表的容量 (数组长度)。hash: 键的哈希值 (经过 hash(key) 方法计算后的值)。&: 位与运算符。(n - 1) & hash 的作用:
等价于取模运算 (hash % n): 当哈希表容量 n 是 2 的幂次方 时， (n - 1) & hash 等价于 hash % n。例如，如果 n = 16 (2^4)，则 n - 1 = 15 (二进制 0000 1111)。 (n - 1) & hash 运算实际上是取 hash 的低 4 位 (二进制)。位运算效率更高: 位运算 & 比取模运算 % 的效率更高，尤其是在计算机底层硬件层面。保证索引在数组范围内: (n - 1) & hash 运算的结果始终小于 n，保证计算出的索引 i 始终在哈希表数组的有效索引范围内 [0, n-1]。为什么容量必须是 2 的幂次方？
保证 (n - 1) & hash 等价于 hash % n: 只有当 n 是 2 的幂次方时， (n - 1) & hash 才能有效地将哈希值均匀地映射到 [0, n-1] 的索引范围内。均匀分布索引: 当 n 是 2 的幂次方时，n - 1 的二进制表示形式是低位全为 1，高位全为 0。与哈希值进行位与运算，可以有效地利用哈希值的低位信息，使得哈希桶索引分布更均匀。如果 n 不是 2 的幂次方，则 (n - 1) & hash 运算的结果分布可能会不均匀，增加哈希冲突的概率。总结：均匀分布的索引计算
HashMap 通过强制哈希表容量为 2 的幂次方，并使用位运算 (n - 1) & hash 来计算哈希桶索引，保证了哈希值能够被均匀地映射到哈希表的各个桶中，进一步降低了哈希冲突的概率。
总结：HashMap 降低哈希冲突概率的算法
HashMap 为了降低哈希冲突概率，并提高性能，综合使用了以下算法和策略：
优秀的哈希函数 (hash(key)): 结合键对象自身的 hashCode 方法和扰动函数 (h ^ (h >>> 16)), 增强哈希值的随机性和均匀性。合理的哈希表容量和扩容机制: 通过初始容量、负载因子和动态扩容，控制哈希表的填充程度，并在必要时通过扩容和 rehash 操作分散元素，降低冲突。均匀分布的哈希桶索引计算 ((n - 1) & hash): 强制容量为 2 的幂次方，使用高效的位运算，保证哈希值均匀映射到索引范围。这些算法和策略的综合应用，使得 HashMap 在大多数情况下能够保持较低的哈希冲突概率，实现接近 O(1) 的平均查找、插入和删除性能。
在后续的 HashMap 源码分析中，我们会继续深入探讨扩容机制 resize 方法的实现细节，以及红黑树在处理哈希冲突中的作用。
来源：爱那屋油