Implementation of hashmap data structure in java [closed]

Question

I am having one technical test , problem statement is given below, i am not getting what exactly i have to do, please help me for the same by providing some sample code.

Implement a hash-map data structure from scratch , where both key and value are of string data type.
The details of how a hash works can be found in Chapter 11 of the book "Introduction to
Algorithms" by Cormen, Leiserson, Rivest. You should also refer to Section 3.7 of "The
Algorithm Design Manual" by Steven Skiena. For the required hash-map implementation,
the following conditions hold true:
1. The key is made up of lower-case english alphabets only (a,b,c...z). It can be of any
length.
2. Values are of string data type.
3. The hash function to be used is the one given in Section 3.7 of Skiena.
4. Choose a suitable size of the hash-map, that is, the number of buckets. It should be
greater than 100.
4. Collisions will be resolved using Chaining. Doubly linked lists will be used to store
colliding entries.
You will have to implement the following operations on the hash-map:
a. Create an empty hash-map.
b. Insert a (key, value) pair into the hash-map.
c. Delete a (key) from the hash-map (if present).
d. Search for a (key) in the hash-map, and if present return its value. Else return null.

Thanks in advance.

Answer 1

I believe that it's going to be more helpful if I explain HashMaps in English.

What is a HashMap?

A HashMap is a data structure that is able to map certain keys to certain values. The keys and values could be anything. For example, if I were making a game, I might link every username to a friends list, represented by a List of Strings.

Why use a HashMap?

HashMaps are much faster for retreiving data than arrays and linked lists. A sorted array could find a particular value in O(log n) with binary search. However, a HashMap can check if it contains a particular key in O(1). All keys must be unique.

How do HashMaps work?

HashMaps use an array in the background. Each element in the array is another data structure (usually a linked list or binary search tree). The HashMap uses a function on the key to determine where to place the key's value in the array. For example, if my HashMap accepts Strings...possible hash functions can be:

A. Return the ASCII value of the first letter.
B. Return the sum of the ASCII values of every character in the String.
C. Return the ASCII value of the last character in the String.

The value returned will determine the index in which the value goes into the array.

But Wait! There's a Problem!

It is possible that the returned value will be outside of the array's bounds. Therefore, we are supposed to mod the returned value by the arrays length.

return Math.abs(number%hashMapArray.length);

Collisions:

Isn't it possible that multiple keys will make the hash function generate the same index? Yes. For example, if we used the first hash function shown above in a hash map of strings...any two Strings that start with the same letter will be given the same array index.

This is called a collision.

How do we handle collisions?

One collision handling technique is called Chaining. Since every element in the array is a linked list (or similar data structure), multiple keys that have the same hash value will be placed in the same linked list or "bucket". Afterwards, the hash map is able to retrieve values by calculating the hash code with the hash function, and searching the particular linked list to see if it contains a value with the same key.

A good hash function must be written to avoid collisions.

Advantages to Chaining:

-Array cannot overflow

-Data can be easily removed

Disadvantages to Chaining:

-May suffer a performance hit if buckets contain very long linked lists.

The total number of entries to the number of buckets is called the load factor. If the load factor is too low, a lot of space is wasted. If the load factor is too high, the advantage of hashing is lost. A good compromise on load factor is .75