Internal implementation of HashMap in Java

Question

I am trying to create the data structure of a HashMap() in Java. The HashMap has to work for a maximum of N = 1000 operations and the keys are only positive integers. What I did is the following:

class MyHashMap {
        final ListNode[] nodes = new ListNode[1000];
        // "put", "get" and "remove" methods which take
        // collisions into account using "chaining".
}

to decide the placement of my new key - value pair in nodes I always need to compute an index. I use the function:

 public int getIndex(int key) { return Integer.hashCode(key) % nodes.length;}

which returns an integer between 0 and nodes.length. But how can I write a Hashfunction in Java on my own that maps integers to some index without using Integer.hashMap(key)? Also the procedure is fine, I don't really need a code.

Answer 1

A simple strategy for hashing an int value is to multiply by a large constant. If you don't use a constant, you can get very poor collision rates depending on your key distribution. It's is still possible to get poor key distribution, however it is less likely for real data.

NOTE: Unless you know the key cannot be negative, you should use Math.abs to ensure it is non-negative.

static final int K = 0x7A646E4D; // some large prime.

public int getIndex(int key) { 
    return Math.abs(key * K % nodes.length);
}

A faster solution is to drop the use of % use a multiplication and shift. e.g.

public int getIndex(int key) { 
    return (int) ((key * K & 0xFFFF_FFFFL) * nodes.length >>> 32);
}

What this does is turn key * K into a fraction and is faster than using %