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.
Create a class that implements the java.util.Map interface and fill in the given methods
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 :)
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.
Id recommend making your class implement java.util.Map as it will give you a good idea of what methods will be necessary and useful.