java写一个线性探测方法的哈希表

以下是一个Java实现的线性探测哈希表：

public class LinearProbingHashTable<K, V> {
    private int capacity;
    private int size;
    private K[] keys;
    private V[] values;
    
    public LinearProbingHashTable(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.keys = (K[]) new Object[capacity];
        this.values = (V[]) new Object[capacity];
    }
    
    public int size() {
        return size;
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public boolean containsKey(K key) {
        int index = hash(key);
        while (keys[index] != null) {
            if (keys[index].equals(key)) {
                return true;
            }
            index = (index + 1) % capacity;
        }
        return false;
    }
    
    public V get(K key) {
        int index = hash(key);
        while (keys[index] != null) {
            if (keys[index].equals(key)) {
                return values[index];
            }
            index = (index + 1) % capacity;
        }
        return null;
    }
    
    public void put(K key, V value) {
        if (size >= capacity * 0.75) {
            resize(capacity * 2);
        }
        int index = hash(key);
        while (keys[index] != null) {
            if (keys[index].equals(key)) {
                values[index] = value;
                return;
            }
            index = (index + 1) % capacity;
        }
        keys[index] = key;
        values[index] = value;
        size++;
    }
    
    public V remove(K key) {
        if (!containsKey(key)) {
            return null;
        }
        int index = hash(key);
        V removedValue = null;
        while (keys[index] != null) {
            if (keys[index].equals(key)) {
                removedValue = values[index];
                keys[index] = null;
                values[index] = null;
                size--;
                break;
            }
            index = (index + 1) % capacity;
        }
        index = (index + 1) % capacity;
        while (keys[index] != null) {
            K keyToRedo = keys[index];
            V valueToRedo = values[index];
            keys[index] = null;
            values[index] = null;
            size--;
            put(keyToRedo, valueToRedo);
            index = (index + 1) % capacity;
        }
        if (size <= capacity * 0.25) {
            resize(capacity / 2);
        }
        return removedValue;
    }
    
    private int hash(K key) {
        return (key.hashCode() & 0x7fffffff) % capacity;
    }
    
    private void resize(int newCapacity) {
        LinearProbingHashTable<K, V> newTable = new LinearProbingHashTable<>(newCapacity);
        for (int i = 0; i < capacity; i++) {
            if (keys[i] != null) {
                newTable.put(keys[i], values[i]);
            }
        }
        keys = newTable.keys;
        values = newTable.values;
        capacity = newTable.capacity;
    }
}

这个哈希表使用了线性探测法解决冲突。如果某个键的哈希值和已经被占用的槽位相同，就顺序往后找到下一个空槽位，直到找到一个空槽位或者找遍整个哈希表。这种方法的优点是实现简单，缺点是当哈希表的负载因子较高时，会导致查找效率降低，甚至退化为O(n)的线性查找。

在这个实现中，我们使用了两个数组来存储键值对。当一个新的键值对被插入哈希表时，如果哈希表的负载因子超过了0.75，就把哈希表的容量扩大为原来的两倍。当一个键被删除时，如果哈希表的负载因子低于0.25，就把哈希表的容量缩小为原来的一半。这样可以保证哈希表的负载因子始终在0.25和0.75之间，从而保证了查找效率的稳定性。