how to fix java hashtable assertion error?

Question

I have to implement a Hashtable that passes set tests for coursework, i have managed to pass all the tests but two and cannot figure out why they are not passing. Both tests give an assertion error. They test the get and put methods.

bellow is the entirety of the hashtable code as i believe the error could be in another method.

Hashtable code:

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collection;

public class Hashtable<V> {

private Object[] arr; //an array of Pair objects, where each pair contains the key and value stored in the hashtable
private int max; //the size of arr. This should be a prime number
private int itemCount; //the number of items stored in arr
private final double maxLoad = 0.6; //the maximum load factor

public static enum PROBE_TYPE {
    LINEAR_PROBE, QUADRATIC_PROBE, DOUBLE_HASH;
}

PROBE_TYPE probeType; //the type of probe to use when dealing with collisions
private final BigInteger DBL_HASH_K = BigInteger.valueOf(8);

/**
 * Create a new Hashtable with a given initial capacity and using a given probe type
 * @param initialCapacity
 * @param pt
 */
public Hashtable(int initialCapacity, PROBE_TYPE pt) {
    max = nextPrime(initialCapacity);
    probeType = pt ;
    arr = new Object[max];
}

/**
 * Create a new Hashtable with a given initial capacity and using the default probe type
 * @param initialCapacity
 */
public Hashtable(int initialCapacity) {
    max = nextPrime(initialCapacity);
    probeType = PROBE_TYPE.LINEAR_PROBE;
    arr = new Object[max];
}

/**
 * Store the value against the given key. If the loadFactor exceeds maxLoad, call the resize 
 * method to resize the array. the If key already exists then its value should be overwritten.
 * Create a new Pair item containing the key and value, then use the findEmpty method to find an unoccupied 
 * position in the array to store the pair. Call findEmmpty with the hashed value of the key as the starting
 * position for the search, stepNum of zero and the original key.
 * containing   
 * @param key
 * @param value
 */

public void put(String key, V value) {  
    int i = hash(key);
    int finalPos = findEmpty(i,1, key);
    
    if (this.getLoadFactor() > this.maxLoad) {
        this.resize();
    }
    
    if (!hasKey(key)) {
        itemCount++;
    }
    
    arr[finalPos] = new Pair(key, value);   
}

/**
 * Get the value associated with key, or return null if key does not exists. Use the find method to search the
 * array, starting at the hashed value of the key, stepNum of zero and the original key.
 * @param key
 * @return
 */
public V get(String key) {
    int i = hash(key);
    
    if( arr[i] == null) {
        return null;
    } else {return find(hash(key),key,0);}
}

/**
 * Return true if the Hashtable contains this key, false otherwise 
 * @param key
 * @return
 */
public boolean hasKey(String key) {
    if (find(hash(key),key,0) == null) {
        return false;
    }else {
        return true;
    }
}

/**
 * Return all the keys in this Hashtable as a collection
 * @return
 */
public Collection<String> getKeys() {
    ArrayList<String> collection = new ArrayList<String>();
    for(int i =0;i<arr.length;i++) {
        if(arr[i] != null) {
            Pair p = (Pair) arr[i];
            collection.add(p.key);
        }
    }
    return collection;
}

/**
 * Return the load factor, which is the ratio of itemCount to max
 * @return
 */
public double getLoadFactor() {
    return itemCount / (double) max;
}

/**
 * return the maximum capacity of the Hashtable
 * @return
 */
public int getCapacity() {
    return this.max;
}

/**
 * Find the value stored for this key, starting the search at position startPos in the array. If
 * the item at position startPos is null, the Hashtable does not contain the value, so return null. 
 * If the key stored in the pair at position startPos matches the key we're looking for, return the associated 
 * value. If the key stored in the pair at position startPos does not match the key we're looking for, this
 * is a hash collision so use the getNextLocation method with an incremented value of stepNum to find 
 * the next location to search (the way that this is calculated will differ depending on the probe type 
 * being used). Then use the value of the next location in a recursive call to find.
 * @param startPos
 * @param key
 * @param stepNum
 * @return
 */
private V find(int startPos, String key, int stepNum) {
    Pair p = (Pair) arr[startPos];
    if(p == null) {
        return null;
        
    }else if (p.key.equals(key)) {
        return p.value;
        
    }else {
        stepNum++;
        int nextLocation = getNextLocation(startPos, stepNum, key);
        return find(nextLocation, key , stepNum);
    }
}

/**
 * Find the first unoccupied location where a value associated with key can be stored, starting the
 * search at position startPos. If startPos is unoccupied, return startPos. Otherwise use the getNextLocation
 * method with an incremented value of stepNum to find the appropriate next position to check 
 * (which will differ depending on the probe type being used) and use this in a recursive call to findEmpty.
 * @param startPos
 * @param stepNum
 * @param key
 * @return
 */
private int findEmpty(int startPos, int stepNum, String key) {
    if (arr[startPos] == null || ((Pair) arr[startPos]).key.equals(key)) {
        return startPos;
    }else {
        stepNum++;
        int nextPos = getNextLocation(startPos,stepNum,key);
        return findEmpty(nextPos,stepNum,key);
    }       
}

/**
 * Finds the next position in the Hashtable array starting at position startPos. If the linear
 * probe is being used, we just increment startPos. If the double hash probe type is being used, 
 * add the double hashed value of the key to startPos. If the quadratic probe is being used, add
 * the square of the step number to startPos.
 * @param i
 * @param stepNum
 * @param key
 * @return
 */
private int getNextLocation(int startPos, int stepNum, String key) {
    int step = startPos;
    switch (probeType) {
    case LINEAR_PROBE:
        step++;
        break;
    case DOUBLE_HASH:
        step += doubleHash(key);
        break;
    case QUADRATIC_PROBE:
        step += stepNum * stepNum;
        break;
    default:
        break;
    }
    return step % max;
}

/**
 * A secondary hash function which returns a small value (less than or equal to DBL_HASH_K)
 * to probe the next location if the double hash probe type is being used
 * @param key
 * @return
 */
private int doubleHash(String key) {
    BigInteger hashVal = BigInteger.valueOf(key.charAt(0) - 96);
    for (int i = 0; i < key.length(); i++) {
        BigInteger c = BigInteger.valueOf(key.charAt(i) - 96);
        hashVal = hashVal.multiply(BigInteger.valueOf(27)).add(c);
    }
    return DBL_HASH_K.subtract(hashVal.mod(DBL_HASH_K)).intValue();
}

/**
 * Return an int value calculated by hashing the key. See the lecture slides for information
 * on creating hash functions. The return value should be less than max, the maximum capacity 
 * of the array
 * @param key
 * @return
 */
private int hash(String key) {
    int hashVal = key.charAt(0);
    for(int i=0; i<key.length();i++) {
        int c = key.charAt(i);
        hashVal =(hashVal * 27 +c) % max;
    }
    return hashVal;
}

/**
 * Return true if n is prime
 * @param n
 * @return
 */
private boolean isPrime(int n) {
    if(n<=2) return true;
    if(n % 2 == 0) return false;
    for(int i=3; i*i<n; i+=2) {
        if(n % i == 0) return false;
    }
    return true;
}

/**
 * Get the smallest prime number which is larger than n
 * @param n
 * @return
 */
private int nextPrime(int n) {
    if(isPrime(n)) {
        return n;
    }else {
        n++;
        return nextPrime(n);
    }
}

/**
 * Resize the hashtable, to be used when the load factor exceeds maxLoad. The new size of
 * the underlying array should be the smallest prime number which is at least twice the size
 * of the old array.
 */
private void resize() {
        int tableSize = nextPrime(max*2);
        Object[] oldArr = arr;
        arr = new Object[tableSize];
        itemCount = 0;
        max = tableSize;
        for (int i=0;i<oldArr.length;i++) {
            if(oldArr[i] != null) {
                Pair p = (Pair) oldArr[i];
                put(p.key, p.value);
            }
            
        }
}


/**
 * Instances of Pair are stored in the underlying array. We can't just store
 * the value because we need to check the original key in the case of collisions.
 * @author jb259
 *
 */
private class Pair {
    private String key;
    private V value;

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

}

Tests:

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

    @Test
public void testGet() {
    Hashtable<String> h = new Hashtable<>(9);
    int c = 0;
    for(int i=0;i<10;i++) {
        for(int j=10;j>0;j--) {
            h.put(i+":"+j, j+":"+i);
            c++;
        }
    }
    for(int i=0;i<10;i++) {
        for(int j=10;j>0;j--) {
            assertEquals(h.get(i+":"+j), j+":"+i);
        }
    }
}

many thanks for your help!!

question from:https://stackoverflow.com/questions/65890411/how-to-fix-java-hashtable-assertion-error

Answer 1

Waitting for answers