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 %

Answer 2

Integer.hashCode(key) just returns key as result. You could write:

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

This way, you don't use Integer.hashCode(key).

Without seeing your class ListNode, you could have a problem with your MyHashMap structure since you are setting many elements to the same array element. For instance the key 3 and 1003 will be saved in the same node element. You must design MyHashMap to be a list of list (or an array of list or something similar).

Answer 3

Well, first of all the hash is something that is unique or a very rarely repeating value.

Assuming that your values will be evenly distributed you can use the remainder of division as a hash value for your key.

public int get(int key) {
    return (-1 ^ key) % nodes.length;
}