9
\$\begingroup\$

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 < SIZE_OF_TABLE; i++) {
            table[i] = null;
        }
    }

    public void put(int key, int value) {
        int index = hashCodeNew(key);
        System.out.println(index);
        HashEntry hashEntry = new HashEntry(key, value);
        if (table[index] == null) {
            table[index] = hashEntry;
        } else {
            HashEntry runner = table[index];
            while (runner.next != null) {
                if (runner.key == hashEntry.key) {
                    runner.value = hashEntry.value;
                    break;
                } else {
                    runner = runner.next;
                }
            }
            if (runner.next == null) {
                if (runner.key == hashEntry.key) {
                    runner.value = hashEntry.value;
                } else {
                    runner.next = hashEntry;
                }
            }
        }

    }

    public int get(int key) {
        int index = hashCodeNew(key);
        if (table[index] == null) {
            return -1;
        } else {
            HashEntry runner = table[index];
            if (runner.key == key) {
                return runner.value;
            }
            while (runner.next != null) {
                if (runner.key == key) {
                    return runner.value;
                }
            }
            return -1;
        }
    }

    public int hashCodeNew(int h) {
        h ^= (h >>> 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);

}
}
\$\endgroup\$
11
\$\begingroup\$

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<List<HashEntry>> 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<HashEntry> chain = table[index];
    if (chain == null) {
        chain = new ArrayList<>();
    }

    Iterator<HashEntry> 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)).

\$\endgroup\$
3
  • \$\begingroup\$ Thanks for the review, I liked your reasoning behind using list of list instead of linked list. Also I have read somewhere that multiplication is computationally expensive and should be avoided in a hash function, would you still suggest the same hash function. \$\endgroup\$ Sep 6 '14 at 17:19
  • \$\begingroup\$ On modern computers a multiplication takes about 3-5 instructions compare this to 8x bit manipulations in the original, which I think is executed in 4 cycles on a super scalar cpu. But that's not the point, the suggested function should provide a more even distribution of hash values reducing collisions in the table and improving your performance that way. So yes, I still recommend the proposed function. \$\endgroup\$
    – Emily L.
    Sep 7 '14 at 7:18
  • \$\begingroup\$ Also that advice applies mostly to string hash functions that have to process all characters in the string. This is different. If you really are worried about performance of the hash function then you should worry about misspredicted branches on the if statement. But that only becomes a problem if you ever use negative keys and can be addressed by removing the branch and replacing with something else. \$\endgroup\$
    – Emily L.
    Sep 7 '14 at 7:23
7
\$\begingroup\$

The HashEntry[] table is currently public in HashMap, which is dangerous, as anybody can mess with it. It should be private.

The same goes for the fields of HashEntry.


Something's wrong here in get:

while (runner.next != null) {
    if (runner.key == key) {
        return runner.value;
    }
}

runner.key will never be equal to key. And runner.next is always null when execution gets here. So the entire loop is unused, but I think you just forgot something there.


The implementation doesn't pass this unit test:

@Test
public void test_1000_28() {
    HashMap hashMap = new HashMap();
    for (int i = 0; i < 28; ++i) {
        hashMap.put(i + 1000, i);
        assertEquals(i, hashMap.get(i + 1000));
    }
}

Don't mix JUnit 3 and 4 like this:

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

Stick with one of them (JUnit 4):

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

Use all capital letters for constants only. So instead of this:

int SIZE_OF_TABLE = 128;

Use either of:

private static final int SIZE_OF_TABLE = 128;
//private final sizeOfTable = 128;
//private final tableSize = 128;

Arrays of objects are initialized with nulls. So instead of this:

HashEntry[] table;
HashMap() {
    table = new HashEntry[SIZE_OF_TABLE];
    for (int i = 0; i < SIZE_OF_TABLE; i++) {
        table[i] = null;
    }
}

You could simplify as:

HashEntry[] table;
HashMap() {
    table = new HashEntry[SIZE_OF_TABLE];
}

public void put(int key, int value) {
    int index = hashCodeNew(key);
    System.out.println(index);

Don't print to stdout. I guess you forgot to delete this debugging line before code review.

\$\endgroup\$
1
\$\begingroup\$
HashEntry[] table;
HashMap() {
    table = new HashEntry[SIZE_OF_TABLE];
    for (int i = 0; i < SIZE_OF_TABLE; i++) {
        table[i] = null;
    }
}

I'd call it proper obfuscation. Or did you mean something different from

HashEntry[] table = new HashEntry[SIZE_OF_TABLE];

? It's Java, everything gets initialized (or you get a compile-time error). Btw., make everything private.


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

This blows for negative values. The fastest way is to ensure that table.length is always a power of two and use

    return hashCode & (table.length-1);

I'm using table.length rather than SIZE_OF_TABLE here, as it should be able to grow.

\$\endgroup\$
0
\$\begingroup\$

I would use a prime number for the table size because then any spacing in the input will still use every table slot (unless the spacing is the table size). Also, your hash function doesn't work for negative inputs. I would multiply the input by another large prime before taking the remainder.

public int hashCodeNew(int h) {
    h = (h * (SIZE_OF_TABLE == 65537 ? 8191 : 65537)) % SIZE_OF_TABLE;
    if(h < 0)
        h += SIZE_OF_TABLE;
    return h;
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ thanks for comment, how does prime number help ? \$\endgroup\$ Sep 5 '14 at 16:07
  • \$\begingroup\$ You need to explain it a bit more \$\endgroup\$ Sep 5 '14 at 16:18

Not the answer you're looking for? Browse other questions tagged or ask your own question.