Simple implementation of HashMap

I have implemented a HashMap which supports insertions of integer key value pairs. The approach uses an array for simplicity and uses a standard hash function. Please give a review on the coding approach used in the program.

import junit.framework.Assert;
import org.junit.Test;

public class HashMapImpl {
class HashMap {
    int SIZE_OF_TABLE = 128;
    HashEntry[] table;
    HashMap() {
        table = new HashEntry[SIZE_OF_TABLE];
        for (int i = 0; i >> 20) ^ (h >>> 12);
        int hashCode = h ^ (h >>> 7) ^ (h >>> 4);
        return hashCode % SIZE_OF_TABLE;
    }
}

class HashEntry {
    int key;
    int value;
    HashEntry next = null;

    HashEntry() {
    }

    public HashEntry(int key, int value) {
        this.key = key;
        this.value = value;
    }

    public int getKey() {
        return this.key;
    }

    public int getValue() {
        return this.value;
    }
}

@Test
public void testBasic() {
    HashMap hashMap = new HashMap();
    hashMap.put(10, 20);
    hashMap.put(20, 11);
    hashMap.put(21, 1);
    hashMap.put(20, 10);

    int value = hashMap.get(20);
    Assert.assertEquals(10, value);

}
}

Besides what has already been mentioned:

public class HashMapImpl {
class HashMap {

What's going on here? HashMapImpl is never used. This should be just simply

public class HashMap {

Don't have your unit tests inside of the class implementation, unit tests should be in a separate folder structure that mirrors your source structure. That way you don't have to ship the unit tests with your program when you release it.

Also this:

public int hashCodeNew(int h) {

should be private.

You're implementing the hash chaining as a linked list which has poor cache locality. You might just be better of having:

List> table = new ArrayList<>(SIZE_OF_TABLE);

and let HashEntry be like this:

private class HashEntry {
    int key;
    int value;

    public HashEntry(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

As HashEntry is a class only used inside of HashMap it should be private or protected. Because it is protected or private and it is pretty much just a POD structure, you can just drop the accessors (get/set methods) which you weren't using anyway. Rule of thumb, if you're not using some parts of the code, remove them. The less code you have the better (generally). But don't skimp on the white space :)

Your put method allows the use of -1 as a key, but your get method uses -1 to signal a 'no such element' condition. Either you need to throw a IllegalArgumentException from put or you need to use another way of signaling that there is no such entry. I would suggest throwing NoSuchElementException like this:

public int get(int key) {
    int index = hashCodeNew(key);
    if (table[index] == null || table[index].size() < 1) {
        throw new NoSuchElementException("The key: \"" + key + "\" was not found in the map!");
    } else {
        ...
        throw new NoSuchElementException("The key: \"" + key + "\" was not found in the map!");
    }
}

While we're at it, notice that we have two code paths that result in the same action if an error occurs, we can rearrange this as:

public int get(int key) {
    int index = hashCodeNew(key);
    if (table[index] != null) {
        for(HashEntry entry : table[index]){
            if(entry.key == key)
                return entry.value;
        }
    }
    throw new NoSuchElementException("The key: \"" + key + "\" was not found in the map!");
}

Lets take a look at the put() function too, adapting it to use a list of lists for chaining and cleaning it up a bit:

public void put(int key, int value) {
    int index = hashCodeNew(key);
    HashEntry hashEntry = new HashEntry(key, value);

    List chain = table[index];
    if (chain == null) {
        chain = new ArrayList<>();
    }

    Iterator it = chain.iterator();
    while(it.hasNext()){
        if(it.next().key == key){
            it.remove();
            break;
        }
    }
    chain.add(hashEntry);
    table[index] = chain;
}

Your hash function is terrible:

public int hashCodeNew(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    int hashCode = h ^ (h >>> 7) ^ (h >>> 4);
    return hashCode % SIZE_OF_TABLE;
}

It doesn't handle negative h. You're basically just changing the lower bits, the high bits are mostly unaffected. A better (and faster) way is to simply multiply by a sizeable prime number:

private final static long BIG_PRIME = 175365371; // The 9,786,124th prime number
public int hashCodeNew(int h) {
    if( h >= 0) // 0 always at index 0.
        return (int)(h*BIG_PRIME) % SIZE_OF_TABLE;
    else
        return (int)((Integer.MAX_VALUE-h)*BIG_PRIME) % SIZE_OF_TABLE;
}

Why big? So that more of the available bits in the hash code are used.

Edit I just looked up Integer.hashCode() and it returns the value of the integer. Which implies that that is good enough as a hash and why wouldn't it be? All hash values are unique and evenly distributed. So:

public int hashCodeNew(int h) {
    return (h & Integer.MAX_VALUE) % hash.size();
}

First use Integer.MAX_VALUE which is \$2^{31} -1\$ to mask out the sign bit and then just take modulo. Handles negative values without a branch and is as fast as it gets without assuming the hash table is a power of two size (in which case simply use h & (hash.size() - 1)).

StackExchange Code Review Q#62049, answer score: 11