项目背景详细介绍
在哈希表的开放寻址（Open Addressing）实现中，探测（probing）策略决定在发生冲突时如何寻找下一个可用槽位。常见策略包括线性探测（Linear Probing）、二次探测（Quadratic Probing）、双哈希（Double Hashing）等。为了增强可维护性和可扩展性，我们可以抽象出一个开放寻址哈希表基类，将探测策略作为可扩展的部分，通过子类来实现不同的探测函数。

项目需求详细介绍

1. 基类 OpenAddressingHashMapBase<K,V>

   • 定义通用字段：Entry<K,V>[] table、int capacity、int size、float loadFactor、int deletedCount（墓碑计数）。

   • 定义通用方法：put、get、remove、containsKey、size、isEmpty、clear、resize。

   • 声明抽象方法：

/** 计算第 i 次探测时的槽位 */
protected abstract int probe(int hash, int i);

• 节点类 Entry<K,V>

  • 字段：K key; V value; boolean deleted;。

• 子类示例：LinearProbingHashMap<K,V>

  • 实现 probe(hash, i) = (hash + i) % capacity;。

• 冲突与删除

  • 插入时优先复用第一个遇到的墓碑槽位；

  • 删除时打墓碑 deleted = true，并维护 size、deletedCount；

  • 扩容条件：(size + deletedCount) / capacity ≥ loadFactor，扩容时容量翻倍并重哈希。

• 健壮性

  • null 键抛 IllegalArgumentException；

  • get/remove 未命中返回 null；

// 文件：OpenAddressingHashMapBase.java
import java.util.NoSuchElementException;

public abstract class OpenAddressingHashMapBase<K, V> {
    /** 存储槽位的内部节点 */
    protected static class Entry<K, V> {
        final K key;
        V value;
        boolean deleted;
        Entry(K k, V v) { key = k; value = v; deleted = false; }
    }

    protected Entry<K, V>[] table;
    protected int capacity;
    protected int size;
    protected int deletedCount;
    protected final float loadFactor;

    @SuppressWarnings("unchecked")
    public OpenAddressingHashMapBase(int initialCapacity, float loadFactor) {
        if (initialCapacity <= 0 || loadFactor <= 0 || loadFactor >= 1)
            throw new IllegalArgumentException("Invalid capacity or loadFactor");
        this.capacity = initialCapacity;
        this.loadFactor = loadFactor;
        this.table = (Entry<K, V>[]) new Entry[capacity];
        this.size = 0;
        this.deletedCount = 0;
    }

    /** 子类实现：第 i 次探测时，给定初始 hash，应返回槽位索引 */
    protected abstract int probe(int hash, int i);

    /** 计算非负哈希 */
    protected 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 + deletedCount) >= capacity * loadFactor) resize();

        int h = hash(key), firstDeletedIdx = -1;
        for (int i = 0; i < capacity; i++) {
            int idx = probe(h, i);
            Entry<K, V> e = table[idx];
            if (e == null) {
                int target = (firstDeletedIdx >= 0 ? firstDeletedIdx : idx);
                table[target] = new Entry<>(key, value);
                if (firstDeletedIdx >= 0) deletedCount--;
                size++;
                return;
            }
            if (e.deleted) {
                if (firstDeletedIdx < 0) firstDeletedIdx = idx;
                continue;
            }
            if (e.key.equals(key)) {
                e.value = value;
                return;
            }
        }
        throw new IllegalStateException("HashMap is full");
    }

    /** 根据键查找，未命中返回 null */
    public V get(K key) {
        if (key == null) throw new IllegalArgumentException("Key cannot be null");
        int h = hash(key);
        for (int i = 0; i < capacity; i++) {
            int idx = probe(h, i);
            Entry<K, V> e = table[idx];
            if (e == null) break;
            if (!e.deleted && e.key.equals(key)) return e.value;
        }
        return null;
    }

    /** 删除键并返回旧值，未命中返回 null */
    public V remove(K key) {
        if (key == null) throw new IllegalArgumentException("Key cannot be null");
        int h = hash(key);
        for (int i = 0; i < capacity; i++) {
            int idx = probe(h, i);
            Entry<K, V> e = table[idx];
            if (e == null) break;
            if (!e.deleted && e.key.equals(key)) {
                e.deleted = true;
                size--;
                deletedCount++;
                return e.value;
            }
        }
        return null;
    }

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

    /** 当前元素数量（不含已删除） */
    public int size() {
        return size;
    }

    /** 是否为空 */
    public boolean isEmpty() {
        return size == 0;
    }

    /** 清空所有数据 */
    @SuppressWarnings("unchecked")
    public void clear() {
        table = (Entry<K, V>[]) new Entry[capacity];
        size = 0;
        deletedCount = 0;
    }

    /** 扩容并重哈希 */
    @SuppressWarnings("unchecked")
    protected void resize() {
        Entry<K, V>[] old = table;
        capacity <<= 1;
        table = (Entry<K, V>[]) new Entry[capacity];
        size = 0;
        deletedCount = 0;
        for (Entry<K, V> e : old) {
            if (e != null && !e.deleted) put(e.key, e.value);
        }
    }
}

// 文件：LinearProbingHashMap.java
/**
 * 线性探测（Linear Probing）实现
 */
public class LinearProbingHashMap<K, V> extends OpenAddressingHashMapBase<K, V> {
    public LinearProbingHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
    }
    @Override
    protected int probe(int hash, int i) {
        // 线性探测：hash + i
        return (hash + i) % capacity;
    }
}

// 文件：Main.java
public class Main {
    public static void main(String[] args) {
        LinearProbingHashMap<String, Integer> map =
            new LinearProbingHashMap<>(16, 0.5f);

        map.put("apple", 3);
        map.put("banana", 2);
        map.put("orange", 5);
        System.out.println("banana -> " + map.get("banana")); // 2

        map.put("banana", 7);
        System.out.println("banana -> " + map.get("banana")); // 7

        System.out.println("contains grape? " + map.containsKey("grape")); // false
        System.out.println("remove apple: " + map.remove("apple"));        // 3
        System.out.println("size: " + map.size());                        // 2
    }
}

代码详细解读

1. 基类 OpenAddressingHashMapBase

   • 抽象出通用的槽位管理、扩容、插入/查找/删除逻辑；

   • 通过 protected abstract int probe(int hash, int i) 让子类定义具体探测函数；

2. 线性探测子类 LinearProbingHashMap

   • 实现 probe(hash, i) = (hash + i) % capacity;；

3. 墓碑处理

   • 删除时标记 deleted = true，保留槽位以维护探测链；

   • 插入时优先重用第一个墓碑槽位；

4. 动态扩容

   • 当已用槽位（包含墓碑）超过负载因子阈值，容量翻倍并重哈希所有有效元素；