How to Create Own HashMap in Java?

Question

I know about hashing algorithm and hashCode() to convert "key" into an equivalent integer (using some mathematically random expression) that is then compressed and stored into buckets.

But can someone point me to an implementation or at least data structure that should be used as baseline?

I haven't found it anywhere on the web.

Solution 1

Just use eclipse and use latest JDK. Source code of Java core packages come attached with the JDK. Open HashMap class and you are good to go. Some of the method implementations may come from AbstractMap, AbstractCollection etc. This is because of proper OO design. You can navigate to all the classes of JDK in your eclipse.

UPDATE: Why Eclipe ( or an IDE) instead of just opening the zip file? An IDE can be used to move back and forth between classes and in general is good for "reading" code. Note not all method implementations are in one file like HashMap.java and so simple text editors like notepad++, or textpad may not be enough. A full blown IDE like eclipse/IDEA can make it much easier. Atleast it worked for me :)

Solution 2

Create a class that implements the java.util.Map interface and fill in the given methods

Solution 3

Create own HashMap

http://javaexplorer03.blogspot.com/2015/10/create-own-hashmap.html

1. Data Structure need to store the Store the key-value pair. Make an Entry class to store the HashMap Entries. Variable: key, value and next next variable is used to avoid the collision of hashmap using chaining (linked list).

2. put() method to put new entries in hashmap. Identify the bucket using hash (hashcode%SIZE)

a. If no element exists in that bucket: put it as new Entry.

b. If element already exists: If element is duplicate, replace old one, otherwise find the last element in the chain and add new entry to next pointer of last element.

3. get() method : return the element in the hashmap a. Identify the element bucket by calculate the hash (hashcode%SIZE) of the key, and return the element using equals method.

Solution 4

If you want a fast and memory efficient implementation you are going to want to use an array to back your map. Use the hashing algorithms that you want to index into the array and store the object in that slot of the array.

There are a lot of little details that you will want to pay attention to. When to resize the array, how to detect and resolve a hash collision, etc.

I'd recommend making your class implement java.util.Map as it will give you a good idea of what methods will be necessary and useful.

View more solutions

Comments

[MAK]

The source for Java packages comes with the JDK. I don't see what using Eclipse has to do anything with it.

[Mike B]

This is probably the best way to go. Just pull the source at the moment and maybe rewrite it as pseudocode to understand what it does, then implement your own and make any necessary changes.