Java 中的 Rehash 算法详解

简介

在 Java 中，Rehash 算法是哈希表（如 HashMap）在扩容时所采用的一种重要机制。当哈希表中的元素数量达到一定阈值时，为了保证哈希表的性能，需要对其进行扩容操作，而 Rehash 算法就是在扩容过程中重新计算元素的哈希值并将其重新放置到新的哈希表位置的过程。本文将详细介绍 Rehash 算法在 Java 中的基础概念、使用方法、常见实践以及最佳实践。

基础概念

哈希表与哈希冲突

哈希表是一种根据键（Key）直接访问内存存储位置的数据结构。它通过哈希函数将键映射到一个数组的索引位置，从而实现快速的查找、插入和删除操作。然而，由于哈希函数的输出范围通常是有限的，不同的键可能会被映射到相同的索引位置，这就是哈希冲突。

Rehash 算法的作用

当哈希表的负载因子（元素数量与数组容量的比值）达到一定阈值时，哈希冲突的概率会显著增加，导致哈希表的性能下降。为了避免这种情况，哈希表需要进行扩容操作，即增加数组的容量。Rehash 算法就是在扩容过程中重新计算每个元素的哈希值，并将其放置到新的数组位置上，以保证哈希表的性能。

使用方法

在 Java 中，HashMap 是最常用的哈希表实现，它会自动处理 Rehash 操作。下面是一个简单的示例，展示了 HashMap 的基本使用和扩容过程：

import java.util.HashMap;

public class RehashExample {
    public static void main(String[] args) {
        // 创建一个初始容量为 4 的 HashMap
        HashMap<Integer, String> map = new HashMap<>(4);

        // 插入元素
        map.put(1, "One");
        map.put(2, "Two");
        map.put(3, "Three");
        map.put(4, "Four");

        // 此时 HashMap 可能会进行扩容和 Rehash 操作
        map.put(5, "Five");

        // 打印 HashMap 中的元素
        for (Integer key : map.keySet()) {
            System.out.println("Key: " + key + ", Value: " + map.get(key));
        }
    }
}

在上述示例中，我们创建了一个初始容量为 4 的 HashMap，并插入了 5 个元素。当插入第 5 个元素时，HashMap 的负载因子超过了默认阈值（0.75），因此会进行扩容和 Rehash 操作。

常见实践

自定义哈希表的扩容和 Rehash

除了使用 Java 内置的 HashMap，我们还可以自定义哈希表，并实现自己的扩容和 Rehash 算法。下面是一个简单的自定义哈希表的示例：

import java.util.LinkedList;

class CustomHashMap<K, V> {
    private static final int INITIAL_CAPACITY = 4;
    private LinkedList<Entry<K, V>>[] table;
    private int size;

    static class Entry<K, V> {
        K key;
        V value;

        Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    @SuppressWarnings("unchecked")
    public CustomHashMap() {
        table = new LinkedList[INITIAL_CAPACITY];
        for (int i = 0; i < INITIAL_CAPACITY; i++) {
            table[i] = new LinkedList<>();
        }
        size = 0;
    }

    private int hash(K key) {
        return Math.abs(key.hashCode()) % table.length;
    }

    public void put(K key, V value) {
        int index = hash(key);
        for (Entry<K, V> entry : table[index]) {
            if (entry.key.equals(key)) {
                entry.value = value;
                return;
            }
        }
        table[index].add(new Entry<>(key, value));
        size++;

        // 检查是否需要扩容
        if ((double) size / table.length > 0.75) {
            rehash();
        }
    }

    @SuppressWarnings("unchecked")
    private void rehash() {
        LinkedList<Entry<K, V>>[] oldTable = table;
        int newCapacity = table.length * 2;
        table = new LinkedList[newCapacity];
        for (int i = 0; i < newCapacity; i++) {
            table[i] = new LinkedList<>();
        }
        size = 0;

        // 重新插入所有元素
        for (LinkedList<Entry<K, V>> bucket : oldTable) {
            for (Entry<K, V> entry : bucket) {
                put(entry.key, entry.value);
            }
        }
    }

    public V get(K key) {
        int index = hash(key);
        for (Entry<K, V> entry : table[index]) {
            if (entry.key.equals(key)) {
                return entry.value;
            }
        }
        return null;
    }
}

public class CustomHashMapExample {
    public static void main(String[] args) {
        CustomHashMap<Integer, String> map = new CustomHashMap<>();
        map.put(1, "One");
        map.put(2, "Two");
        map.put(3, "Three");
        map.put(4, "Four");
        map.put(5, "Five");

        System.out.println(map.get(3));
    }
}

在上述示例中，我们实现了一个简单的自定义哈希表 CustomHashMap，并在插入元素时检查是否需要扩容。如果需要扩容，则调用 rehash 方法进行 Rehash 操作。

最佳实践

选择合适的初始容量

在创建哈希表时，选择合适的初始容量可以减少扩容和 Rehash 的次数，从而提高性能。如果事先知道元素的大致数量，可以根据这个数量来选择初始容量。

使用高质量的哈希函数

哈希函数的质量直接影响哈希表的性能。在自定义哈希表时，应该选择一个分布均匀的哈希函数，以减少哈希冲突的概率。

避免频繁的扩容和 Rehash

频繁的扩容和 Rehash 操作会带来一定的性能开销。因此，在设计哈希表时，应该尽量避免频繁的扩容和 Rehash 操作。

小结

Rehash 算法是 Java 中哈希表扩容的关键机制，它通过重新计算元素的哈希值并将其重新放置到新的位置，保证了哈希表的性能。本文介绍了 Rehash 算法的基础概念、使用方法、常见实践以及最佳实践。通过合理使用 Rehash 算法，可以提高哈希表的性能和稳定性。

参考资料

《算法导论》
《Effective Java》