qiyu-lu

个人记录

2 minute read

HashSet 是如何保证元素不重复的？

HashSet 保证元素唯一性的秘诀，完全建立在对存入对象的 hashCode() 和 equals() 方法的正确使用上。理解其内部机制，是 equals() 和 hashCode() 契约的终极考验。

HashSet 的底层实际上是一个 HashMap。当你向 HashSet 中添加元素时，这个元素会作为 HashMap 的 key，而 value 则是一个固定的虚拟对象 (PRESENT)。因此，HashSet.add(element) 的过程，本质上就是 HashMap.put(element, PRESENT) 的过程。

在深入细节之前，我们必须先理解一个核心问题：

1. 为什么需要链表/红黑树：直面“哈希冲突”

一个常见的误区是认为哈希表的目的是实现“一一对应”的唯一映射。但实际上，它的首要目标是实现极快的存取速度 (O(1))。链表和红黑树的存在，正是为了在无法实现完美“一一对应”的现实下，依然能保障高效的性能。

理想 vs. 现实

  • 理想：我们有一个“完美哈希函数”，任何一个 Key 都能计算出一个独一无二的数组索引。这样每个“桶”里永远只有一个元素，不需要任何额外的数据结构。
  • 现实：完美哈希函数几乎不存在。我们面临一个无法避免的问题——哈希冲突 (Hash Collision)。

为什么冲突无法避免？——“鸽巢原理”

  • 键的空间是近乎无限的：理论上，String 等对象可以有无数个。
  • 数组的长度是有限的：HashMap 的容量不可能无限大。

当你要把“无限”的 Key 放入“有限”的数组“桶”中时，必然会出现多个不同的 Key 被计算出相同的数组索引的情况。就像有很多鸽子，但鸽巢数量有限，总有几个鸽子要挤在同一个巢里。

冲突的解决方案

既然冲突不可避免，设计者就必须提供解决方案。

  • 方案一：链表 (拉链法) 这是最基础的方案。所有哈希到同一个桶的元素，以链表的形式串在一起。这解决了冲突，但如果某个链表过长，查找效率会从 O(1) 急剧下降到 O(n)。

  • 方案二：红黑树 (性能优化) 为了应对链表过长的最坏情况，Java 8 引入了优化。当一个桶里的元素超过阈值（默认为8）时，链表会转化为红黑树，将此桶内的查找效率从 O(n) 提升到 O(log n)，保证了整体性能不会急剧恶化。

结论：链表和红黑树并非设计的累赘，而是为了应对“哈希冲突”这个必然问题，所做的健壮性设计和性能优化。

2. add(E element) 方法详解

当你调用 set.add(element) 时，HashSet (即其内部的 HashMap) 会执行以下操作：

  1. 计算哈希码：首先，调用 element.hashCode() 方法，获取该元素的哈希码（一个整数）。

  2. 定位存储位置：HashSet 内部维护着一个数组，称为“哈希表”或“桶数组”。它通过一个内部哈希函数，将上一步得到的哈希码转换成一个数组索引。这个索引就决定了 element 应该被放入哪个“桶”中。

  3. 检查桶内情况：

    • Case A: 桶是空的 如果该索引位置的桶中没有任何元素，说明这个新元素没有与任何已有元素发生“哈希冲突”。系统认定它是一个新元素，直接将其存入桶中。此时，equals() 方法不会被调用。

    • Case B: 桶不是空的 如果该索引位置已经有了一个或多个元素（即发生了哈希冲突），这意味着新元素的哈希码与桶中至少一个已有元素的哈希码相同。 此时，HashSet 会遍历这个桶中的所有已有元素，并用新元素的 equals() 方法与桶中的每一个元素进行比较：

      • 如果 element.equals(existingElement) 返回 true：HashSet 认定新元素与桶中的某个元素是“重复”的。add() 方法会返回 false，新元素不会被添加进来。
      • 如果 equals() 方法与桶中所有元素比较后都返回 false：HashSet 认定新元素与桶中所有已有元素都“不重复”。它是一个新元素，被添加到这个桶中（通常是加在链表的末尾或红黑树的新节点上）。add() 方法返回 true。

2.1 putVal 源码剖析

HashMap中的putVal方法是实现上述逻辑的核心。理解它等于理解了HashMap和HashSet工作的精髓。

这个方法就像一个经验丰富的图书管理员要把一本新书（key, value）放到书架（HashMap）上：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K, V>[] tab; Node<K, V> p; int n, i;

    // 1. 看书架是不是空的，是的话就先搭一个 (resize() 初始化)。
    if ((tab = this.table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

    // 2. 根据书的分类号 (hash) 找到对应的书架格子 (tab[i])。
    // 如果格子是空的，直接把书放进去。
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    
    // 3. 如果格子已经有书了（哈希冲突）
    else {
        Node<K, V> e; K k;
        // 3a. 先看第一本是不是你要更新的书（同一本书的新版），是的话就找到它。
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;

        // 3b. 如果不是，就看看这个格子里是不是因为书太多，已经用了复杂的索引系统（红黑树）
        else if (p instanceof TreeNode)
            // 是的话就按索引系统放进去。
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

        // 3c. 如果只是随便叠在一起（链表）
        else {
            // 就翻一翻，找到一样的就跳出，找不到就把新书放到这堆书的最上面。
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 如果这堆书太高了(>8)，就整理一下，给它们也建个索引系统（转成红黑树）。
                    if (binCount >= TREEIFY_THRESHOLD - 1) 
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }

        // 4. 如果找到了已存在的书 (e != null)
        if (e != null) { 
            V oldValue = e.value;
            // HashSet的场景中，value总是PRESENT，所以这里不会更新
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            // 对于HashSet的add操作，因为key已存在，所以会返回false (HashMap返回oldValue)
            return oldValue;
        }
    }

    // 5. 放完新书后，记录一下操作
    ++modCount;
    // 看看整个书架是不是快满了 (size > threshold)，是的话就赶紧再加一排新书架 (扩容)。
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    // 如果是放了本新书，就告诉调用者（对于HashSet的add，意味着返回true）。
    return null; 
}

3. equals() 与 hashCode() 契约如何在此生效

这个过程完美地诠释了为什么必须同时重写 equals() 和 hashCode()：

  • 契约1：equals() 相等，hashCode() 必须相等。
    • 作用：保证两个被 equals() 方法认定为相等的对象，一定能被定位到同一个桶中。如果它们的 hashCode 不同，就会被分到不同的桶，导致 equals() 方法根本没有机会被调用，从而无法判断它们是重复的。这会使得 HashSet 中存入“重复”元素，破坏其唯一性。
  • 契约2：hashCode() 相等，equals() 不一定相等。
    • 作用：解释了为什么发生哈希冲突后，还需要进行 equals() 比较。不同的对象可能会有相同的哈希码，HashSet 必须通过 equals() 方法做最终的“身份确认”，以区分这些对象。

简而言之：hashCode() 用来快速缩小查找范围，equals() 用来在小范围内进行精确比较。

4. (深度解析) HashMap 的扰动函数

你提供的这段代码正是 HashMap (以及 HashSet) 内部用于计算最终哈希值的 hash() 方法，通常被称为“扰动函数”。理解它对于深入掌握 HashMap 的设计思想非常有帮助。

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

为什么要进行“扰动”处理？

我们知道，一个对象的 hashCode() 返回的是一个32位的 int 值。HashMap 的容量（桶数组的长度）通常是2的幂次方。为了计算一个 key 应该放在哪个桶，HashMap 使用 (n - 1) & hash 这个位运算（等效于 hash % n，但效率更高）。

问题在于：这个位运算只利用了哈希值的低位。如果一个类的 hashCode() 方法生成的哈希值，其高位变化很大而低位变化很小，那么这将导致大量的对象被映射到少数几个桶中，造成严重的哈希冲突，使 HashMap 的性能急剧下降。

扰动函数是如何工作的？

hash() 方法的目的就是为了解决上述问题。它通过将哈希值的高位信息混合到低位中，来增加低位的随机性，从而减少哈希冲突。

让我们分解 (h = key.hashCode()) ^ (h >>> 16) 这行代码：

  1. h = key.hashCode(): 获取原始的32位哈希码 h。
  2. h >>> 16: 将 h 无符号右移16位。这会把 h 的高16位移动到原先低16位的位置上。
  3. ^: 对原始哈希码 h 和右移后的 h 进行异或 (XOR) 操作。

核心思想：通过这个异或操作，原始哈希码的高16位被有效地“混合”到了低16位中。这样，最终得到的哈希值（hash() 方法的返回值），其低位同时包含了原始哈希值的高位和低位信息。

因此，即使 key.hashCode() 本身的低位分布不均，只要其高位是随机的，经过扰动函数处理后，最终用于计算索引的哈希值也会变得更加随机和均匀。

总结

  • 目的：防止因 hashCode() 实现不佳而导致的哈希冲突，让元素在哈希表中分布得更均匀。
  • 方法：将哈希码的高位数据通过位运算（右移和异或）混合到低位中。
  • 效果：增加了最终哈希值的随机性，使得计算出的数组索引更加分散，从而提升 HashMap 的整体性能。

在面试中能够清晰地解释这一点，无疑会让你在众多候选人中脱颖而出。

5. (面试加分项) JDK 8+ 的性能优化

在 Java 8 之前，哈希冲突的桶中，元素是以链表形式存储的。如果大量对象的 hashCode 相同，会导致某个桶的链表变得很长，此时在这个桶中查找元素的效率会从 O(1) 退化到 O(n)。

从 Java 8 开始，HashSet (以及 HashMap) 引入了优化：

  • 当一个桶中的元素数量超过一个阈值 (默认为 8)，并且哈希表的总容量大于 64 时，这个桶的存储结构会从链表动态地转换为红黑树。
  • 优势：红黑树是一种自平衡的二叉查找树，它能将在这个桶内的查找时间复杂度从 O(n) 优化到 O(log n)，显著提高了在哈希冲突严重时的性能。

6. 总结

  • HashSet (及其底层的HashMap) 的首要设计目标是 O(1) 的快速存取，而非实现完美的“一一对应”映射。
  • 由于“键空间无限，数组容量有限”的矛盾，哈希冲突是必然存在的。
  • HashSet 通过 hashCode() 快速定位到存储桶，这是第一步。
  • 如果发生哈希冲突，它通过链表或红黑树来组织桶内元素，并通过 equals() 方法进行精确比较，以保证元素的唯一性，这是第二步和第三步。
  • 正确重写 hashCode() 和 equals() 是 HashSet 能否正常工作的根本保证。
  • HashSet 的工作流程，是哈希表数据结构、链表、红黑树以及位运算等计算机科学基础知识的完美综合体现。

You May Also Enjoy