CODEWITHSUNDEEP
javaperformancehashmapruntime
freestar
freestar

Reputation: 448

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

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

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");


}

Upvotes: 1

Views: 1370

Answers (2)

GhostCat
GhostCat

Reputation: 140407

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 ...

Upvotes: 0

T.J. Crowder
T.J. Crowder

Reputation: 1073968

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.

Upvotes: 4

Related Questions