深入理解 Java 中的线性探测（Linear Probing）

简介

在数据结构和算法领域，哈希表是一种非常重要的数据结构，用于实现快速的数据查找和插入操作。线性探测是解决哈希冲突的一种常用方法。本文将详细介绍线性探测在 Java 中的基础概念、使用方法、常见实践以及最佳实践，帮助读者更好地理解和运用这一技术。

线性探测基础概念

哈希表通过哈希函数将键（key）映射到一个哈希值，这个哈希值作为数组的索引来存储对应的值（value）。然而，不同的键可能会产生相同的哈希值，这就是所谓的哈希冲突。线性探测是解决哈希冲突的一种简单而直观的方法。

当发生哈希冲突时，线性探测会在哈希表数组中按顺序向后查找下一个空的位置来存储新的元素。也就是说，如果键 k1 和 k2 产生了相同的哈希值 h，那么 k1 会存储在位置 h，而 k2 会存储在位置 h + 1（如果 h + 1 为空），如果 h + 1 也被占用，则继续查找 h + 2，以此类推，直到找到一个空的位置。

线性探测在 Java 中的使用方法

下面通过一个简单的 Java 代码示例来展示如何使用线性探测实现一个基本的哈希表。

public class LinearProbingHashTable {
    private static final int DEFAULT_CAPACITY = 16;
    private int size;
    private int capacity;
    private Object[] keys;
    private Object[] values;

    public LinearProbingHashTable() {
        this.capacity = DEFAULT_CAPACITY;
        this.keys = new Object[capacity];
        this.values = new Object[capacity];
        this.size = 0;
    }

    private int hashFunction(Object key) {
        return Math.abs(key.hashCode()) % capacity;
    }

    public void put(Object key, Object value) {
        if (size >= capacity * 0.75) {
            resize();
        }
        int index = hashFunction(key);
        while (keys[index] != null &&!keys[index].equals(key)) {
            index = (index + 1) % capacity;
        }
        if (keys[index] == null) {
            size++;
        }
        keys[index] = key;
        values[index] = value;
    }

    public Object get(Object key) {
        int index = hashFunction(key);
        while (keys[index] != null &&!keys[index].equals(key)) {
            index = (index + 1) % capacity;
        }
        if (keys[index] == null) {
            return null;
        }
        return values[index];
    }

    private void resize() {
        capacity *= 2;
        Object[] newKeys = new Object[capacity];
        Object[] newValues = new Object[capacity];
        for (int i = 0; i < keys.length; i++) {
            if (keys[i] != null) {
                int newIndex = hashFunction(keys[i]);
                while (newKeys[newIndex] != null) {
                    newIndex = (newIndex + 1) % capacity;
                }
                newKeys[newIndex] = keys[i];
                newValues[newIndex] = values[i];
            }
        }
        keys = newKeys;
        values = newValues;
    }

    public static void main(String[] args) {
        LinearProbingHashTable hashTable = new LinearProbingHashTable();
        hashTable.put("one", 1);
        hashTable.put("two", 2);
        hashTable.put("three", 3);

        System.out.println(hashTable.get("one"));
        System.out.println(hashTable.get("two"));
        System.out.println(hashTable.get("three"));
    }
}

代码解释

构造函数：初始化哈希表的容量、键数组和值数组。
哈希函数：使用 key.hashCode() 并取绝对值后对容量取模，得到哈希值。
put 方法：首先检查负载因子，如果超过 0.75 则进行扩容。然后通过哈希函数找到初始位置，若该位置被占用且键不相等，则线性探测下一个位置，直到找到空位置或键相等的位置，然后插入键值对。
get 方法：通过哈希函数找到初始位置，线性探测直到找到键相等的位置或空位置，若找到则返回对应的值，否则返回 null。
resize 方法：将容量翻倍，重新计算所有键的哈希值并插入到新的数组中。

常见实践

负载因子控制：如上述代码所示，通常在负载因子达到一定阈值（如 0.75）时进行扩容，以保证哈希表的性能。负载因子过高会导致哈希冲突增加，从而降低查找和插入的效率。
处理删除操作：在删除元素时，不能简单地将对应位置设为空，因为这可能会影响后续查找。可以使用一个特殊的标记（如 DELETED）来表示该位置曾经被占用过，这样在查找时遇到该标记可以继续探测。

private static final Object DELETED = new Object();

public void remove(Object key) {
    int index = hashFunction(key);
    while (keys[index] != null &&!keys[index].equals(key)) {
        index = (index + 1) % capacity;
    }
    if (keys[index] == key) {
        keys[index] = DELETED;
        values[index] = null;
        size--;
    }
}

最佳实践

选择合适的哈希函数：一个好的哈希函数应该能够均匀地分布键值，减少哈希冲突的发生。对于自定义对象，需要重写 hashCode 方法，确保不同对象的哈希值尽可能分散。
避免线性探测聚集：线性探测可能会导致聚集现象，即连续的位置被占用，使得后续查找效率降低。可以采用二次探测（Quadratic Probing）或双重哈希（Double Hashing）等方法来缓解聚集问题。
动态扩容与缩容：除了在负载因子过高时进行扩容，也可以在负载因子过低时进行缩容，以节省内存空间。

小结

线性探测是解决哈希冲突的一种简单有效的方法，在 Java 中实现线性探测哈希表需要注意哈希函数的设计、负载因子的控制以及删除操作的处理等方面。通过遵循最佳实践，可以提高哈希表的性能和效率，使其在各种应用场景中发挥更大的作用。

参考资料

《算法导论》（Introduction to Algorithms）
Java 官方文档中关于哈希表和哈希函数的部分
Wikipedia - Linear Probing