How to implement a HashMap data structure in Java?

Question

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.

Map does not necessarily need hash and array. Explain what you need. — mentallurg
– mentallurg, Commented Jun 24, 2018 at 14:42
No it isn't, I was trying to implement my own versions of data structures, and some algorithms. My current DS was Map/Dictionary. I don't want to use HashMap, I want to implement one — Mansur
– Mansur, Commented Jun 24, 2018 at 14:42
Learn from the masters: hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/… — M. le Rutte
– M. le Rutte, Commented Jun 24, 2018 at 14:45

Brendon Boldt · Accepted Answer · 2018-06-24 14:55:56Z

1

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.

edited Jun 24, 2018 at 14:55

answered Jun 24, 2018 at 14:54

Brendon Boldt

2352 silver badges11 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

mentallurg Over a year ago

He does not want to use HashMap, does not want to copy & paste it. He wants to implement his own structure.

Thijs Steel · Accepted Answer · 2018-06-24 14:52:19Z

0

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 Jun 24, 2018 at 14:52

Thijs Steel

1,2729 silver badges20 bronze badges

5 Comments

mentallurg Over a year ago

This is how HashMap works. But said he does not want to use HashMap, does not want to copy & paste it. He wants to implement his own structure.

Thijs Steel Over a year ago

"I want to implement a HashMap data structure", he just wants to do it himself, probably because he wants to learn how it works

mentallurg Over a year ago

"I don't want to use HashMap" - means he does not want to use the code, the approach in this class. He wants to implement his own solution.

Mansur Over a year ago

@mentallurg, no, Thijs Steel is correct, just to learn how it works.

mentallurg Over a year ago

OK. Then why don't you go through each method in debugger and just ask "why" to each line of the code?

Collectives™ on Stack Overflow

How to implement a HashMap data structure in Java?

2 Answers 2

1 Comment

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related