How to implement a HashMap data structure in Java?

Mensur Qulami Source

I want to implement a HashMap data structure, but I can't quite figure out what to do with underlying array structure.

If I'm not mistaken, in HashMap each key is hashed and converted into an integer which is used to refer to the array index. Search time is O(1) because of direct referring.

Let's say K is key and V is value. We can create an array of size n of V type and it will reside in the index produced by hash(K) function. However, hash(K) doesn't produce consecutive indices and Java's arrays aren't sparse and to solve this we can create a very large array to hold elements, but it won't be efficient, it will hold a lot of NULL elements.

One solution is to store elements in consecutive order, and for finding an element we have to search the entire array and check elements' keys but it will be linear time. I want to achieve direct access.

Thanks, beforehand.



answered 3 months ago Thijs Steel #1

You can look at the source code for all your problems.

For the sake of not going through a pretty large code. The solution to your problem is to use modulo. You can choose n=64, then store an element x with h(x) mod 64 = 2 in the second position of the array, ...

If two elements have the same hash modulo n, then you store them next to each other (usually done in a tree map). Another solution would be to increase n.

answered 3 months ago Brendon Boldt #2

Borrowed from the Wikipedia article on hash tables, you can use a smaller array for underlying storage by taking the hash modulo the array size like so:

hash = hashfunc(key)
index = hash % array_size

This is a good solution because you can keep the underlying array relatively dense, you don't have to modify the hash funciton, and it does not affect the time complexity.

comments powered by Disqus