Beyond HashMap - Part 1

Simply, A HashMap is a data structure that allows us to store key-value pairs, where keys should be unique, and if you try to insert with duplicate key, it will replace the element of the corresponding key.

Example in java:

HashMap<String, Integer> userAgeMap = new HashMap<>();
userAgeMap.put("Mark",25);
userAgeMap.put("Silvana",32);        

One of main advantages of HashMap is fast retrieval of values based on their corresponding keys, HashMap provide us random access, insert and search operations on average with a time complexity O(1).

We just say "on average" , so there is a worst case ?

Actually there is a worst case that can makes operations take O(n), so we need to find out when we may reach this case and the important part why this case is even exist and how can we avoid it.

Many people may be familiar with HashMap, HashSet and HashTable data structures, not everyone may understand the idea beyond them .. it’s about the principle of hashing.

Hashing:

Process of converting a given key into another value. A hash function is used to generate the new value according to a mathematical algorithm. The result of a hash function is known as a hash value.

A hash function is a function that often takes a string and returns an output, which is typically a string of characters or a number, And the same input always produces the same output.

A hash function with an array provides us with a HashMap!

• Array to hold the elements of the HashMap "values"
• Hash function to map each key to a unique index in an the array, This index is used to store the associated value
• Insertion : A hash function takes a key as input, hashes it, and outputs an index. This index is then used to add the value associated with that key into the array at that specific location.
• Searching - Retrieving : Both are the same in HashMap. We just pass the key that we want to get to its corresponding value to the same hash function and it will give us an index. using this index within the array we get the value.

The size of this array is typically larger than the number of elements in the HashMap, to reduce the likelihood of collisions and ensure that the hash function produces a unique index for each key.

To be continued.

The next part will go deeply in the internals of HashMap. Most languages have built-in HashMap regardless the equivalent in each language like dictionary in python and so on, so you don’t have to implement a new HashMap but this explanation it’s just to understand the performance of HashMaps.

References:

• Wikipedia
• educative.io