Overwrite the hash value (java)

Question

Can anyone give some help over here? :)

I am failing to pass this JUnit test:

@Test
public void testInsert() {
    Hashtable <Boolean> h = new Hashtable <Boolean> (1000, PROBE_TYPE.DOUBLE_HASH);
    for (int i = 0; i < 2000; i++) {
        for (int j = 2000; j > 0; j--) {
            h.put(i + ":" + j, true);
        }
    }
}

Here is my put method:

For the put method the value against the given key must be stored. If loadFactor>maxLoad, resize() (method to resize the array). If there is a key already, overwrite the value. New Pair item including (key, value) findEmpty (to find the next empty position in the array to store the pair). Call findEmpty with the hashed value of the key as the start pos for the search, stepNum of zero, and the original key.

public void put(String key, V value) {
    boolean isTrue = false;
    int size = 0;
    Pair aPair = new Pair(key, value);
    if (getLoadFactor() > maxLoad) { //if the maxLoad value is exceeded.
        resize(); //call the resize method.
    }
    if (hasKey(key)) { //if there is a key(position occupied).
        while (!isTrue) {
            if (size < max) { //if the size is less than the maximum size.
                if (arr[hash(key)].equals(key)) { //if the key already exists
                    aPair.value = value; //overwrite the value
                    isTrue = false;
                }
                size++;
            }
        }
    } else { //if the position is not occupied.
        int empty = findEmpty(hash(key), 0, key); //find the next empty position.
        arr[empty] = aPair; // stored in the empty position.
    }
    itemCount++;
}

Pair instances are stored (in an array). Check original key in case of collisions. Here is the Pair class:

private class Pair {
    private String key;
    private V value;

    public Pair(String key, V value) {
        this.key = key;
        this.value = value;
    }
}

getLoadFactor(): returns a double for the size
maxLoad: is a double = 0.6
itemCount: the number of items stored in the array
hasKey(): returns a boolean true/false if there is a key or not
private V find(int startingPosition, String key, int stepNumber)
private int findEmpty(int startingPosition, int stepNumber, String key)
This is a hashtable Hashtable<V> I'm using an array private Object[] arr

Answer 1

import java.util.Hashtable;


public class Main <V>{

    private Integer max;
    private Object[] arr;
    private long itemCount = 0;
    private double maxLoad;

    public Main(int i) {
        this.max = i;
        maxLoad = 0.75;
        arr = new Object[i];
    }

    public static void main(String[] args) {
        Main<Boolean> h = new Main<Boolean>(1000);
        int counter = 0;
        for(int i=0;i<1000;i++) {
            for(int j=1000;j>0;j--) {
                h.put(i+":"+j, true);
                System.out.println(counter);
                counter++;
            }
        }
    }



    private void resize() {
        Object[] oldArray = arr;
        max = max * 2;
        arr = new Object[max];
        itemCount = oldArray.length;

        for (int i = 0; i < oldArray.length; i++) {
            if (oldArray[i] != null) {
                Pair arPair = (Pair) oldArray[i];
                arr[i] = arPair;
            }
        }
    }

    public void put(String key, V value) {
        boolean isTrue = false;
        int size = 0;
        Pair aPair = new Pair(key, value);
        if (getLoadFactor() > maxLoad) { // if the maxLoad value is exceeded.
            resize(); // call the resize method.
        }
        int index = hasKey(key);
        if (index != -1) { // if there is a key(position occupied).
            ((Pair<V>)arr[index]).value = value;
        } else { // if the position is not occupied.
            int empty = findEmpty(hash(key), 0, key); // find the next empty
                                                        // position.
            arr[empty] = aPair; // stored in the empty position.
        }
        itemCount++;
    }

    private int findKey(String key) {
        int index = 0;
        for (Object obj  : arr) {
            Pair pair = (Pair) obj;
            if(pair!= null && pair.key.equals(key))
                return index;

            index++;
        }
        return 0;
    }

    private double getLoadFactor() {

        return (double)itemCount / max;
    }

    private int findEmpty(int hash, int i, String key) {
        int j = 0 ;
        for (Object obj  : arr) {
            Pair pair = (Pair) obj;
            if(pair != null){
                j++;    
            }else{
                return j;
            }

        }
        return j;
    }

    private int hash(String key) {
        return key.hashCode();
    }

    private int hasKey(String key) {
        int counter = 0 ;
        for (Object obj  : arr) {
            Pair pair = (Pair) obj;
            if(pair != null && pair.key.equals(key)){
                return counter;
            }
            counter++;
        }
        return -1;
    }



    private class Pair<V> {
        private String key;
        private V value;

        public Pair(String key, V value) {
            this.key = key;
            this.value = value;
        }
    }

}

Answer 2

I suspect your problem is an infinite while loop in your put method. First, the loop will only terminate if you set isTrue to true, which you never do. Changing the assignment inside if to isTrue = true; may help, but only if you get in there. If size is greater than or equal to max, you never will no matter how many times through the loop, so it will still be infinite. Next, if understand correctly that arr contains Pair objects, arr[hash(key)].equals(key) will never be true, also keeping your loop from terminating.

There may be yet more bugs in there. Hope this gets you a step further.