invalid hash entry after 100000 + entries

Question

I've implemented a HashMap with Linear Probing for hash collisions.

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;
        }
    }

}

it seems to work exactly as expected except for every 100,000 entries or so will return the wrong value for a hash. I can reproduce it fairly reliably with this test

        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());
        }

I'm not seeing what my problem is and I'm not thinking of a good way to debug such a rare occurrence. Any thoughts on what I might be doing wrong or how to debug this without spending forever on it?

Answer 1

How does a Java HashMap handle different objects with the same hash code? answered my question. My HashMap implementation does not handle different objects with the same hash code. It only works correctly if hashcodes are unique to equal objects.