JAVA:实现HashMap线性探测算法（附带源码）

m0_61840987

1156人浏览 · 2025-08-26 00:15:00

m0_61840987 · 2025-08-26 00:15:00 发布

一、项目背景详细介绍

在计算机科学中，哈希表（Hash Table） 是一种非常高效的数据结构。它通过哈希函数将键（Key）映射到存储位置，从而实现 平均时间复杂度为 O(1) 的插入、删除和查找操作。

但是，哈希表有一个非常核心的问题 —— 哈希冲突（Hash Collision）。

哈希冲突是指：
当两个不同的键通过哈希函数计算后，映射到相同的存储位置时，就会发生冲突。

解决哈希冲突的常见方法有：

拉链法（Separate Chaining）：每个桶存储一个链表/红黑树；
开放寻址法（Open Addressing）：冲突时寻找下一个可用槽位存储元素。

而 线性探测（Linear Probing） 就是开放寻址法的一种具体实现。

线性探测的思想

当哈希表中的某个位置已经被占用时：

就沿着数组顺序（即 index+1, index+2, …）继续寻找，直到找到一个空槽存放元素。
查找时同样按照该规则查找。

例如：
哈希表大小 = 5
哈希函数：hash(key) = key % 5

插入 key=1, key=6 时：

1 % 5 = 1 → 存在 index=1；
6 % 5 = 1 → 冲突！那么尝试 index=2，如果空则存储。

这样就避免了覆盖问题。

在本文中，我们将基于 Java 实现一个简化版的 HashMap，并使用 线性探测法 来解决哈希冲突。

二、项目需求详细介绍

实现一个支持泛型的 HashMap
- 键类型 K
- 值类型 V
主要功能
- put(K key, V value)：插入/更新键值对
- get(K key)：根据键查找值
- remove(K key)：删除键值对
- containsKey(K key)：判断键是否存在
- size()：获取元素数量
冲突处理方式
使用 线性探测（Linear Probing），即在哈希冲突时向后顺序查找空槽。
自动扩容
当负载因子（Load Factor）超过阈值（如 0.75）时，扩展数组并重新哈希（rehash）。
测试用例
- 插入多个键值对
- 触发冲突并测试查找是否正确
- 删除后是否还能继续插入
- 自动扩容是否生效

三、相关技术详细介绍

1. 哈希函数

Java 的哈希表通常调用对象的 hashCode() 方法，再对数组长度取模：

index = key.hashCode() % capacity;

2. 开放寻址与线性探测

开放寻址：元素直接存在数组中，不使用链表；
线性探测：当冲突时，依次向后查找下一个空槽；
查找和删除时，也必须按相同的探测路径进行。

3. 删除处理

删除元素时，不能简单设为 null，否则可能破坏查找链。
解决办法：引入一个特殊的 删除标记（TOMBSTONE），表示“曾经有数据，但现在被删除”。

4. 扩容

当负载因子超过阈值时，需要将数组大小扩展为原来的两倍，并重新插入所有元素。

四、实现思路详细介绍

定义 内部类 Entry<K,V> 表示一个键值对；
使用一个数组 table 存储 Entry；
插入操作：
- 计算哈希位置；
- 如果冲突，顺序查找下一个空位；
- 插入新元素；
查找操作：
- 按相同规则查找；
- 如果遇到空位但没找到目标，说明不存在；
删除操作：
- 查找到目标时，将该位置设为 TOMBSTONE；
- 保持查找链不断裂；
扩容：
- 当元素数量超过 capacity * loadFactor 时，扩展容量并重新插入。

五、完整实现代码

// 文件：LinearProbingHashMap.java

import java.util.Arrays;

public class LinearProbingHashMap<K, V> {
    private static final int DEFAULT_CAPACITY = 8; // 初始容量
    private static final double LOAD_FACTOR = 0.75; // 负载因子

    private Entry<K, V>[] table; // 存储数据的数组
    private int size; // 元素个数
    private int capacity; // 当前容量

    // 删除标记
    private final Entry<K, V> TOMBSTONE = new Entry<>(null, null);

    // 内部类 Entry，表示键值对
    private static class Entry<K, V> {
        K key;
        V value;

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

    // 构造函数
    public LinearProbingHashMap() {
        this.capacity = DEFAULT_CAPACITY;
        this.table = new Entry[capacity];
        this.size = 0;
    }

    // 哈希函数
    private int hash(Object key) {
        return (key.hashCode() & 0x7fffffff) % capacity;
    }

    // 插入/更新
    public void put(K key, V value) {
        if (key == null) throw new IllegalArgumentException("Key cannot be null");

        if (size >= capacity * LOAD_FACTOR) {
            resize(capacity * 2);
        }

        int index = hash(key);

        while (table[index] != null && table[index] != TOMBSTONE) {
            if (table[index].key.equals(key)) {
                table[index].value = value; // 更新
                return;
            }
            index = (index + 1) % capacity; // 线性探测
        }

        table[index] = new Entry<>(key, value);
        size++;
    }

    // 查找
    public V get(K key) {
        if (key == null) return null;

        int index = hash(key);

        while (table[index] != null) {
            if (table[index] != TOMBSTONE && table[index].key.equals(key)) {
                return table[index].value;
            }
            index = (index + 1) % capacity;
        }

        return null;
    }

    // 删除
    public void remove(K key) {
        if (key == null) return;

        int index = hash(key);

        while (table[index] != null) {
            if (table[index] != TOMBSTONE && table[index].key.equals(key)) {
                table[index] = TOMBSTONE; // 设置为删除标记
                size--;
                return;
            }
            index = (index + 1) % capacity;
        }
    }

    // 是否包含某个键
    public boolean containsKey(K key) {
        return get(key) != null;
    }

    // 返回大小
    public int size() {
        return size;
    }

    // 扩容
    private void resize(int newCapacity) {
        Entry<K, V>[] oldTable = table;
        table = new Entry[newCapacity];
        capacity = newCapacity;
        size = 0;

        for (Entry<K, V> entry : oldTable) {
            if (entry != null && entry != TOMBSTONE) {
                put(entry.key, entry.value);
            }
        }
    }

    // 打印哈希表（调试用）
    @Override
    public String toString() {
        return Arrays.toString(table);
    }

    // 测试
    public static void main(String[] args) {
        LinearProbingHashMap<Integer, String> map = new LinearProbingHashMap<>();

        map.put(1, "A");
        map.put(9, "B"); // 冲突测试（假设容量8，1和9会冲突）
        map.put(17, "C");

        System.out.println("Map大小: " + map.size());
        System.out.println("取key=9: " + map.get(9));
        System.out.println("取key=17: " + map.get(17));

        map.remove(9);
        System.out.println("删除key=9后，containsKey(9): " + map.containsKey(9));

        map.put(9, "BB"); // 再次插入
        System.out.println("重新插入key=9后，get(9): " + map.get(9));

        // 自动扩容测试
        for (int i = 0; i < 20; i++) {
            map.put(i, "Val" + i);
        }
        System.out.println("扩容后Map大小: " + map.size());
    }
}