Java开放地址哈希详解（小白也能学会的哈希冲突解决方法）

线性探测实现（Java代码示例）

下面我们用 Java 实现一个简单的基于线性探测的哈希表。我们将支持插入（put）、查找（get）和删除（remove）操作。

public class LinearProbingHashTable {    private static final int DEFAULT_SIZE = 10;    private String[] keys;    private Integer[] values;    private int size;    public LinearProbingHashTable() {        this(DEFAULT_SIZE);    }    public LinearProbingHashTable(int capacity) {        keys = new String[capacity];        values = new Integer[capacity];        size = 0;    }    private int hash(String key) {        return Math.abs(key.hashCode()) % keys.length;    }    public void put(String key, Integer value) {        if (size >= keys.length / 2) {            resize(2 * keys.length);        }        int i;        for (i = hash(key); keys[i] != null; i = (i + 1) % keys.length) {            if (keys[i].equals(key)) {                values[i] = value;                return;            }        }        keys[i] = key;        values[i] = value;        size++;    }    public Integer get(String key) {        for (int i = hash(key); keys[i] != null; i = (i + 1) % keys.length) {            if (keys[i].equals(key)) {                return values[i];            }        }        return null;    }    private void resize(int newSize) {        LinearProbingHashTable temp = new LinearProbingHashTable(newSize);        for (int i = 0; i < keys.length; i++) {            if (keys[i] != null) {                temp.put(keys[i], values[i]);            }        }        this.keys = temp.keys;        this.values = temp.values;        this.size = temp.size;    }}  

代码说明

上面的代码实现了基本的开放地址哈希表：

• hash() 方法计算键的初始索引；
• put() 方法在冲突时使用 线性探测（i+1）寻找下一个空位；
• 当负载因子超过 0.5 时自动扩容，避免性能下降；
• get() 同样使用线性探测查找键。

优缺点分析

优点：

• 不需要额外的指针或链表，内存更紧凑；
• 缓存友好，访问连续内存效率高。

缺点：

• 容易产生“聚集”（Clustering），影响性能；
• 删除操作复杂，通常需标记为“已删除”而非真正清空。

总结

通过本教程，你已经掌握了 Java开放地址哈希 的基本原理与实现方式。无论是准备面试还是深入学习数据结构，理解 哈希表冲突解决 和 线性探测哈希 都是关键一步。希望这篇 Java哈希教程 能为你打下坚实基础！

提示：实际项目中建议使用 Java 自带的 HashMap，但理解底层原理对提升编程能力至关重要。