java - 100000 + 条目后无效的哈希条目

Question

我已经实现了一个带有线性探测的 HashMap，用于哈希冲突。

import java.util.Optional;

@SuppressWarnings("unchecked")
public abstract class HashMap<T, R> {

    private static final int MIN_CAPACITY = 2;
    private Entry<T, R>[] table;
    private int internalSize, size;
    private float fillRatio;

    public HashMap() {
        this(MIN_CAPACITY);
    }

    public HashMap(int initialCapacity) {
        this(initialCapacity, .75f);
    }

    public HashMap(int initialCapacity, float fillRatio) {
        this.table = new Entry[Math.max(MIN_CAPACITY, initialCapacity)];
        this.fillRatio = fillRatio;
    }

    public Optional<R> put(T key, R value) {
        int index = getIndex(key);
        Entry<T, R> current = table[index];
        table[index] = new Entry<>(key, value);

        if(value == null && current != null && current.getValue() != null) {
            size--;
        } else if(value != null && (current == null || current.getValue() == null)){
            size++;
        }

        if(current == null && ++internalSize >= (table.length * fillRatio)) {
            resizeTable();
        }

        if(current != null) {
            return Optional.ofNullable(current.getValue());
        }
        return Optional.empty();
    }

    public Optional<R> get(T key) {
        int index = getIndex(key);
        Entry<T, R> entry = table[index];
        if(entry != null)
            return Optional.ofNullable(entry.getValue());
        return Optional.empty();
    }

    public boolean has(T key) {
        return get(key).isPresent();
    }

    public int getSize() {
        return size;
    }

    protected void resizeTable() {
        internalSize = size = 0;
        Entry<T, R>[] tmp = table;
        table = new Entry[(int) ((table.length /fillRatio)* 2)];
        for(Entry<T, R> entry : tmp){
            if(entry != null) {
                put(entry.getKey(), entry.getValue());
            }
        }
    }

    private int getIndex(T key) {
        int hash = key.hashCode();
        int index = (((hash % table.length) + table.length) % table.length);
        while(table[index] != null && table[index].getKey().hashCode() != hash) {
            if(++index == table.length) {
                index = 0;
            }
        }
        return index;
    }

    public static final class Entry <T, R> {
        private final T key;
        private final R value;

        public Entry(T key, R value) {
            this.key = key;
            this.value = value;
        }

        public T getKey() {
            return key;
        }

        public R getValue() {
            return value;
        }
    }

}

它似乎完全按照预期工作，除了每 100,000 个条目左右会返回错误的哈希值。我可以通过这个测试相当可靠地重现它

        java.util.HashMap<UUID, UUID> javaMap = new java.util.HashMap<>();
        HashMap<UUID, UUID> map = new HashMap<>();

        for (int i = 0; i < 200000; i++) {
            UUID key = UUID.randomUUID(), value = UUID.randomUUID();
            javaMap.put(key, value);
            map.put(key, value);
        }

        for (java.util.HashMap.Entry<UUID, UUID> entry : javaMap.entrySet()) {
            Optional<UUID> value = map.get(entry.getKey());
            assertTrue(value.isPresent());
            assertEquals(value.get(), entry.getValue());
        }

我没有看到我的问题是什么，我也没有想到一个好的方法来调试这种罕见的情况。关于我可能做错了什么或者如何调试它而不花太多时间的想法？

Answer 1

How does a Java HashMap handle different objects with the same hash code?回答了我的问题。我的 HashMap 实现不处理具有相同哈希码的不同对象。仅当哈希码对于相等的对象是唯一的时，它才能正确工作。