Hashtable Open 8-16 using Linear Addressing

Question

I'm writing Hashtable implementation using Open Linear Addressing. I was able to make it go through on some of the tests, but it goes into infinite loop on one of them and doesn't go through others. Here are the requirements/hints I got: It should return a HashtableOpen8to16 instance.

There are several specifics of this hashtable implementation.

• Hashtable implementation must support open linear addressing.
• Initial capacity is 8.
• Maximum capacity is 16. The insertion of more elements must raise an IllegalStateException.
• The capacity should be doubled each time a new element arrives and all the buckets are already occupied. For example, if there are 8 buckets that are already filled, and a new key is about to be added, the capacity must be increased.
• The capacity should be halved each time an element is removed and size is not zero and size to capacity ratio reaches reaches 1/4 after the removal. For exmaple, if there are 8 buckets and 3 elements, then after removing of one of them, capacity must be
  shrunk to 4. Another example: if there are 4 buckets and 2 elements, the removal of one of them leads to fact that capacity shrinks to 2.
• Note, that in case of 2 buckets and 1 element removal of that element leads to zero size and in this case there is no shrinking, so minimum capacity of the implementation is effectively 2.
• If you add new key in the array that already exists, it should just update the value
• Also, you must implement additional keys() method. It should return an int array representing distribution of keys in hashtable bucket array.

Here's my implementation code:

    public interface
    HashtableOpen8to16 {
        void insert(int key, Object value);
        Object search(int key);
        void remove (int key);
        int size();
        int[] keys();
    
        static HashtableOpen8to16 getInstance(){
            return new HashtableImpl();
        }
    }
public class HashtableImpl implements HashtableOpen8to16{
    private static final int INIT_CAPACITY = 8;
    private static final int MAX_CAPACITY = 16;
    private static final double LOAD_FACTOR = 0.25;

    private int[] keys;
    private Object[] values;
    private int size;
    private int capacity;


    public HashtableImpl() {
        this.keys = new int[INIT_CAPACITY];
        this.values = new Object[INIT_CAPACITY];
        this.size = 0;
        this.capacity = INIT_CAPACITY;
    }
    @Override
    public void insert(int key, Object value) {

        if (size == capacity && ! containsKey(keys, key)) {
            if(capacity == MAX_CAPACITY ) throw new IllegalStateException();
            resizeAndRehash(2 * capacity);
        }
        int index = findIndex(key, capacity, keys);
        keys[index] = key;
        values[index] = value;
        size++;
    }

    private boolean containsKey(int[] keys, int key) {
        for (int tempKey: keys) {
            if(tempKey == key) return true;
        }
        return false;
    }

    private void resizeAndRehash(int resizeFactor) {
        int newCapacity = Math.min(resizeFactor, MAX_CAPACITY);
        int[] newKeys = new int[newCapacity];
        Object[] newValues = new Object[newCapacity];

        for (int i = 0; i < capacity; i++) {
            if (keys[i] != 0) {
                int newIndex = findIndex(keys[i], newCapacity, newKeys);
                newKeys[newIndex] = keys[i];
                newValues[newIndex] = values[i];
            }
        }

        keys = newKeys;
        values = newValues;
        capacity = newCapacity;
    }
    private int findIndex(int key, int capacity, int[] array) {
        int index = Math.abs(key) % capacity;
        while (array[index] != key && array[index] != 0) {
            index = (index + 1) % capacity;
        }
        return index;
    }
    @Override
    public Object search(int key) {
        int index = findIndex(key, capacity, keys);
        return values[index];
    }

    @Override
    public void remove(int key) {
        int index = findIndex(key, capacity, keys);
        if (keys[index] == key) {
            keys[index] = 0;
            values[index] = null;
            size--;
            if (size > 0 && size <= capacity * LOAD_FACTOR) {
                resizeAndRehash(capacity / 2);
            }
        }
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public int[] keys() {
        return keys;
    }
}

Here's the test case that goes into infinite loop: [0, 79, -62, -3, 49, 5, -70, 0, 88, -9, 25, 0, 0, 45, -14, 95]

Another test case that was failed:

    Expected:
    [-80, -17, -94, -7, -76, 53, 70, -46]
    [-80, -17, -94, -7, -76, 53, 0, -46]
    [-80, 0, -94, -7, -76, 53, 0, -46]
    [-80, 0, -94, -7, -76, 53, 0, 0]
    [0, 0, -94, -7, -76, 53, 0, 0]
    [0, 0, -94, -7, -76, 0, 0, 0]
    [-76, 0, 0, -7]
    [0, -7]
    Actual:
    [-80, -17, -94, -7, -76, 53, 70, -46]
    [-80, -17, -94, -7, -76, 53, 0, -46]
    [-80, 0, -94, -7, -76, 53, 0, -46]
    [-80, 0, -94, -7, -76, 53, 0, -46]
    [0, 0, -94, -7, -76, 53, 0, -46]
    [0, 0, -94, -7, -76, 0, 0, -46]
    [0, 0, -94, -7, -76, 0, 0, -46]
    [0, 0, -94, -7, 0, 0, 0, -46]
    [0, 0, -94, -7, 0, 0, 0, -46]
    [0, 0]

Sorry for the formatting, I'm new and still getting used to it.