Why is my HashMap implementation 10 times slower than the JDK's?

Question

I would like to know what makes the difference, what should i aware of when im writing code.

• Used the same parameters and methods put(), get() when testing without printing
• Used System.NanoTime() to test runtime
• I tried it with 1-10 int keys with 10 values, so every single hash returns unique index, which is the most optimal scenario
• My HashSet implementation which is based on this is almost as fast as the JDK's

Here's my simple implementation:

---

public MyHashMap(int s) {

    this.TABLE_SIZE=s;
    table = new HashEntry[s];

}

class HashEntry {

    int key;
    String value;

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

    public int getKey() {
        return key;
    }

}



int TABLE_SIZE;

HashEntry[] table;

public void put(int key, String value) {

    int hash = key % TABLE_SIZE;

    while(table[hash] != null && table[hash].getKey() != key)
        hash = (hash +1) % TABLE_SIZE;

        table[hash] = new HashEntry(key, value);
}


public String get(int key) {

    int hash = key % TABLE_SIZE;

        while(table[hash] != null && table[hash].key != key)
            hash = (hash+1) % TABLE_SIZE;

            if(table[hash] == null)
                return null;
            else
                return table[hash].value;

}

---

Here's the benchmark:

public static void main(String[] args) {


    long start = System.nanoTime();

    MyHashMap map = new MyHashMap(11);

    map.put(1,"A");
    map.put(2,"B");
    map.put(3,"C");
    map.put(4,"D");
    map.put(5,"E");
    map.put(6,"F");
    map.put(7,"G");
    map.put(8,"H");
    map.put(9,"I");
    map.put(10,"J");


    map.get(1);
    map.get(2);
    map.get(3);
    map.get(4);
    map.get(5);
    map.get(6);
    map.get(7);
    map.get(8);
    map.get(9);
    map.get(10);

    long end = System.nanoTime();

    System.out.println(end-start+" ns");


}

Answer 1

If you read the documentation of the HashMap class, you see that it implements a hash table implementation based on the hashCode of the keys. This is dramatically more efficient than a brute-force search if the map contains a non-trivial number of entries, assuming reasonable key distribution amongst the "buckets" that it sorts the entries into.

That said, benchmarking the JVM is non-trivial and easy to get wrong, if you're seeing big differences with small numbers of entries, it could easily be a benchmarking error rather than the code.

Answer 2

When it is up to performance, never assume something.

Your assumption was "My HashSet implementation which is based on this is almost as fast as the JDK's". No, obviously it is not.

That is the tricky part when doing performance work: doubt everything unless you have measured with great accuracy. Worse, you even measured, and the measurement told you that your implementation is slower; and instead of checking your source, and the source of the thing you are measuring against; you decided that the measuring process must be wrong ...