MK
摩柯社区 - 一个极简的技术知识社区
AI 面试

Java HashSet的哈希算法与冲突处理机制

2023-08-167.3k 阅读

Java HashSet 基础概述

在 Java 集合框架中，HashSet 是一个非常常用的集合类，它实现了 Set 接口，用于存储不重复的元素。HashSet 基于 HashMap 来实现，它的内部使用一个 HashMap 实例来存储元素。

从特性上来说，HashSet 具有以下几个关键特点：

  • 元素唯一性：HashSet 不允许存储重复的元素。当试图添加一个已经存在的元素时，HashSet 会忽略这个操作，集合的大小不会改变。
  • 无序性：HashSet 中元素的存储顺序并不是按照元素的插入顺序，也不是按照元素的自然顺序。这意味着每次遍历 HashSet 时，得到的元素顺序可能是不同的。

下面是一个简单的 HashSet 使用示例：

import java.util.HashSet;
import java.util.Set;

public class HashSetExample {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();
        set.add("apple");
        set.add("banana");
        set.add("cherry");
        set.add("apple"); // 尝试添加重复元素

        for (String element : set) {
            System.out.println(element);
        }
    }
}

在上述代码中，我们创建了一个 HashSet 并向其中添加了一些字符串元素，包括一个重复的 “apple”。当遍历集合时，你会发现 “apple” 只出现了一次，这体现了 HashSet 的元素唯一性。

哈希算法基础原理

哈希算法，也称为散列算法，是一种将任意长度的数据映射到固定长度的哈希值的函数。哈希算法的目标是尽量减少不同输入产生相同哈希值（哈希冲突）的可能性。

在理想情况下，哈希算法应该具备以下几个重要特性：

  • 一致性：对于相同的输入，哈希算法应该始终返回相同的哈希值。例如，对于字符串 “hello”，无论在何时何地调用哈希函数，都应该得到相同的哈希值。
  • 高效性：计算哈希值的过程应该尽可能快速，以便在大规模数据处理时不会成为性能瓶颈。
  • 均匀性：哈希函数应该将输入数据均匀地分布在哈希值空间中，这样可以减少哈希冲突的发生。例如，如果哈希值空间是 0 到 99，那么对于大量不同的输入，哈希值应该大致均匀地分布在这个范围内。

常见的哈希算法有很多种，比如 MD5、SHA-1、SHA-256 等。这些算法主要用于数据完整性验证、密码存储等领域。而在 Java 集合框架中，哈希算法主要用于快速定位元素在集合中的存储位置。

Java 中的哈希算法实现

在 Java 中，每个对象都有一个 hashCode 方法，这个方法返回一个 int 类型的哈希值。Object 类中的 hashCode 方法是基于对象的内存地址计算出来的，但是很多类都会重写这个方法以提供更合理的哈希值计算方式。

例如，String 类就重写了 hashCode 方法。String 的 hashCode 计算方式如下：

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

在这个算法中，String 的每个字符都参与了哈希值的计算，并且通过乘以 31 来增加字符之间的权重差异。这种方式使得不同的字符串能够尽可能地产生不同的哈希值，减少哈希冲突。

再看 Integer 类，它的 hashCode 方法就非常简单，直接返回其内部表示的整数值：

public int hashCode() {
    return value;
}

因为 Integer 的值本身就是唯一标识，所以直接返回值作为哈希值是合理的。

HashSet 中的哈希算法应用

HashSet 在存储和查找元素时，会利用元素的哈希值来确定元素在内部存储结构中的位置。HashSet 内部实际上是通过一个 HashMap 来存储元素的，HashMap 使用数组和链表（在 Java 8 及之后，链表长度超过一定阈值会转换为红黑树）来实现哈希表。

当向 HashSet 中添加一个元素时，HashSet 会首先调用元素的 hashCode 方法获取其哈希值。然后，通过对哈希值进行一些运算（通常是与数组长度进行取模运算），得到该元素应该存储在数组中的索引位置。

例如，假设 HashSet 内部维护的数组长度为 16（实际上 HashMap 的初始容量通常为 16），元素的哈希值为 h，那么计算存储索引的公式大致如下：

int index = h & (16 - 1);

这里使用按位与运算 & 来模拟取模运算，因为在数组长度为 2 的幂次方时，h % length 与 h & (length - 1) 的结果是相同的，但按位与运算效率更高。

下面我们通过自定义一个类，并在 HashSet 中使用它来进一步说明：

class Person {
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int hashCode() {
        int result = 17;
        result = 31 * result + name.hashCode();
        result = 31 * result + age;
        return result;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return age == person.age && name.equals(person.name);
    }
}

public class HashSetCustomClassExample {
    public static void main(String[] args) {
        HashSet<Person> set = new HashSet<>();
        Person person1 = new Person("Alice", 25);
        Person person2 = new Person("Bob", 30);
        set.add(person1);
        set.add(person2);

        for (Person person : set) {
            System.out.println(person.name + " - " + person.age);
        }
    }
}

在上述代码中，我们定义了 Person 类，并为其重写了 hashCode 和 equals 方法。hashCode 方法综合考虑了 name 和 age 两个属性来计算哈希值。这样在 HashSet 中存储 Person 对象时，就能根据合理的哈希值进行存储和查找。

哈希冲突问题

尽管哈希算法的目标是尽量减少哈希冲突，但在实际应用中，哈希冲突是难以完全避免的。哈希冲突是指不同的输入数据经过哈希算法计算后得到相同的哈希值。

例如，考虑以下两个字符串：

String str1 = "abc";
String str2 = "bca";

虽然这两个字符串内容不同，但由于 String 的 hashCode 计算方式存在一定的概率性，有可能它们计算出的哈希值是相同的。这就产生了哈希冲突。

在哈希表中，如果发生哈希冲突，就意味着多个元素会被映射到数组的同一个索引位置。如果不妥善处理，就会导致数据丢失或者查找效率降低。

HashSet 的冲突处理机制

链地址法

HashSet 采用链地址法（也称为拉链法）来处理哈希冲突。在链地址法中，当多个元素映射到数组的同一个索引位置时，这些元素会被存储在一个链表中。

在 Java 的 HashMap（HashSet 基于 HashMap 实现）中，数组的每个元素实际上是一个链表头节点（在 Java 8 及之后，链表长度超过一定阈值会转换为红黑树）。当添加一个新元素时，如果该元素计算出的索引位置已经有其他元素存在，那么新元素会被添加到该位置的链表末尾（或根据具体情况插入到合适位置）。

例如，假设有三个元素 A、B、C，它们的哈希值经过计算后都映射到数组的索引位置 5。那么在 HashMap 内部，数组索引 5 处会存储一个链表，链表节点依次为 A、B、C。

查找元素时，首先根据哈希值计算出索引位置，然后在该位置的链表（或红黑树）中进行线性查找（或树查找），直到找到目标元素或确定元素不存在。

再哈希法

虽然 HashSet 主要采用链地址法，但在一些情况下也会涉及到再哈希法的概念。再哈希法是指当发生哈希冲突时，使用另一个哈希函数对元素重新计算哈希值，以得到另一个可能的存储位置。

在 HashMap 中，当哈希表的容量达到一定阈值（负载因子 * 容量）时，会进行扩容操作。扩容时，会重新计算每个元素的哈希值和存储位置。这个过程类似于一种再哈希操作，因为元素的存储位置会根据新的哈希表容量重新确定。

例如，假设初始哈希表容量为 16，当元素数量达到 16 * 0.75（默认负载因子为 0.75）即 12 个时，哈希表会扩容到 32。此时，原来的元素会根据新的容量重新计算存储位置，这在一定程度上缓解了哈希冲突。

链地址法的具体实现细节

在 Java 的 HashMap 源码中，我们可以看到链地址法的具体实现。HashMap 中有一个 Node 内部类来表示链表节点：

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    // 省略其他方法
}

HashMap 还有一个 put 方法来添加元素，其中涉及到链地址法的处理逻辑：

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

在 putVal 方法中，首先计算元素的哈希值 hash，然后根据哈希值确定在数组中的索引位置 i。如果该位置为空，则直接创建新节点存储元素。如果该位置已有元素，那么会进入链表（或红黑树）处理逻辑。如果链表节点的哈希值和键都与要插入的元素相同，则更新值；否则，遍历链表直到找到合适位置插入新节点。当链表长度超过一定阈值（TREEIFY_THRESHOLD，默认为 8）时，链表会转换为红黑树以提高查找效率。

扩容机制与哈希冲突缓解

负载因子与扩容阈值

HashMap（HashSet 基于 HashMap）有一个负载因子（load factor）的概念，默认值为 0.75。负载因子是哈希表中已存储元素数量与哈希表容量的比值。当负载因子达到一定阈值（通常就是负载因子本身的值）时，哈希表会进行扩容。

例如，假设哈希表初始容量为 16，负载因子为 0.75，那么当哈希表中存储的元素数量达到 16 * 0.75 = 12 个时，哈希表会进行扩容。扩容时，哈希表的容量会变为原来的两倍（在 HashMap 中，新容量必须是 2 的幂次方），即从 16 变为 32。

扩容过程与哈希冲突重新分布

扩容过程中，原来哈希表中的所有元素会被重新计算哈希值，并根据新的容量重新确定存储位置。这个过程实际上是对哈希冲突的一种重新分布，因为新的容量会改变元素哈希值与数组索引的映射关系。

例如，假设原来有两个元素 A 和 B，它们在容量为 16 的哈希表中发生了哈希冲突，都存储在索引位置 5 的链表中。当哈希表扩容到 32 时，A 和 B 的哈希值经过重新计算（与新容量 32 进行相关运算），可能会被映射到不同的索引位置，从而缓解了哈希冲突。

在 HashMap 的 resize 方法中，实现了扩容和元素重新分布的逻辑：

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null)? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> 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;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

在这个方法中，首先计算新的容量 newCap 和新的阈值 newThr。然后创建新的数组 newTab，并将旧数组中的元素重新分配到新数组中。对于链表节点，会根据元素哈希值与旧容量的按位与结果，将节点分为高低两组，分别存储在新数组的不同位置，从而实现元素的重新分布和哈希冲突的缓解。

自定义类在 HashSet 中的哈希冲突处理注意事项

当我们在 HashSet 中使用自定义类时，需要特别注意正确重写 hashCode 和 equals 方法，以确保哈希冲突能够得到合理处理。

重写 hashCode 方法

重写 hashCode 方法时，应该尽量保证不同的对象返回不同的哈希值。通常可以综合考虑对象的多个属性来计算哈希值，并且使用一些合适的常量（如 31）来增加属性之间的权重差异。

例如，对于之前的 Person 类，我们重写的 hashCode 方法：

@Override
public int hashCode() {
    int result = 17;
    result = 31 * result + name.hashCode();
    result = 31 * result + age;
    return result;
}

这样可以根据 name 和 age 属性计算出相对唯一的哈希值，减少哈希冲突的可能性。

重写 equals 方法

同时，还需要重写 equals 方法。equals 方法用于判断两个对象是否相等，当两个对象的哈希值相同时，HashSet 会进一步调用 equals 方法来确定它们是否真的相等。如果两个对象的 equals 方法返回 true，那么 HashSet 会认为它们是同一个元素，不会重复添加。

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    Person person = (Person) o;
    return age == person.age && name.equals(person.name);
}

在这个 equals 方法中，我们根据 name 和 age 属性来判断两个 Person 对象是否相等。

一致性保证

特别要注意的是，hashCode 和 equals 方法的重写必须保持一致性。即如果两个对象通过 equals 方法比较返回 true，那么它们的 hashCode 方法返回值必须相同。反之，如果两个对象的 hashCode 方法返回值不同，那么它们通过 equals 方法比较必然返回 false。

性能影响与优化策略

哈希冲突对性能的影响

哈希冲突会对 HashSet（以及基于 HashMap 的其他集合）的性能产生显著影响。当哈希冲突频繁发生时，链表（或红黑树）的长度会增加，查找元素时需要遍历更长的链表（或进行更复杂的树操作），导致查找时间复杂度从理想的 O(1) 退化为 O(n)（n 为链表长度）。插入和删除操作的性能也会受到类似影响。

例如，如果大量元素都映射到哈希表的同一个索引位置，形成一个很长的链表，那么每次查找元素都需要遍历整个链表，性能会急剧下降。

优化策略

  • 合理设置初始容量：在创建 HashSet（或 HashMap）时，可以根据预估的数据量合理设置初始容量。如果能够提前知道大致的数据量，设置一个合适的初始容量可以减少扩容的次数，从而提高性能。例如，如果预计要存储 100 个元素，由于负载因子默认为 0.75，那么初始容量设置为 128（2 的幂次方且大于 100 / 0.75）比较合适。
  • 选择合适的哈希算法：对于自定义类，设计一个好的 hashCode 方法至关重要。尽量使哈希值分布均匀，减少哈希冲突。可以参考一些优秀的开源库中类的 hashCode 实现方式，学习如何根据对象属性设计高效的哈希算法。
  • 避免频繁扩容：扩容操作会涉及到重新计算哈希值和重新分配元素，是一个比较耗时的操作。通过合理设置初始容量和负载因子，以及控制元素的添加速度，可以避免频繁扩容，保持较好的性能。

与其他集合类冲突处理机制的对比

与 TreeSet 的对比

TreeSet 与 HashSet 不同，它是基于红黑树实现的，元素是有序存储的。TreeSet 不依赖哈希算法来处理元素存储和冲突，而是通过比较元素的自然顺序（或自定义比较器）来确定元素的位置。

在 TreeSet 中，当添加元素时，会按照元素的顺序将其插入到红黑树的合适位置。不存在哈希冲突的概念，因为每个元素的位置是根据比较结果确定的，而不是哈希值。

例如：

import java.util.Set;
import java.util.TreeSet;

public class TreeSetExample {
    public static void main(String[] args) {
        Set<Integer> set = new TreeSet<>();
        set.add(5);
        set.add(3);
        set.add(7);

        for (Integer element : set) {
            System.out.println(element);
        }
    }
}

在这个例子中，TreeSet 会按照元素的自然顺序（从小到大）存储和遍历元素。

与 LinkedHashSet 的对比

LinkedHashSet 继承自 HashSet，它在 HashSet 的基础上增加了链表的维护，以保持元素的插入顺序。LinkedHashSet 同样使用哈希算法和链地址法来处理冲突，与 HashSet 在冲突处理机制上基本相同。

不同之处在于，LinkedHashSet 内部维护了一个双向链表，记录了元素的插入顺序。在遍历 LinkedHashSet 时，会按照插入顺序返回元素，而 HashSet 是无序的。

例如：

import java.util.LinkedHashSet;
import java.util.Set;

public class LinkedHashSetExample {
    public static void main(String[] args) {
        Set<String> set = new LinkedHashSet<>();
        set.add("apple");
        set.add("banana");
        set.add("cherry");

        for (String element : set) {
            System.out.println(element);
        }
    }
}

在这个例子中，LinkedHashSet 会按照 “apple”、“banana”、“cherry” 的插入顺序遍历元素。

总结

通过深入了解 HashSet 的哈希算法与冲突处理机制，我们能够更好地使用 HashSet 以及理解 Java 集合框架的底层实现原理。合理运用哈希算法、正确处理哈希冲突，以及优化相关性能，对于开发高效、稳定的 Java 应用程序具有重要意义。在实际编程中，根据具体需求选择合适的集合类，并且针对自定义类正确重写 hashCode 和 equals 方法，是编写高质量 Java 代码的关键步骤之一。同时，与其他集合类如 TreeSet、LinkedHashSet 的对比，也让我们更清楚地认识到不同集合类在存储和冲突处理机制上的差异，从而能够更精准地选择合适的集合来满足业务需求。