A hash table allows you to implement an associative array (dictionary) data structure, with an average performance of O(1) for insert, delete, and search operations.
Below is an example of the simplest implementation of a hash map on nodeJS:
How does it work? Let’s watch the hands:
- There is an array inside the hash map
- Inside the array element is a pointer to the first node of the linked list
- Memory is allocated for an array of pointers (for example 65535 elements)
- Implement a hash function, the input is a dictionary key, and the output can do anything, but in the end it returns the index of the array element
How does the recording work:
- The input is a key – value pair
- The hash function returns an index by key
- Get a linked list node from an array by index
- We check if it matches the key
- If it matches, then replace the value
- If it doesn’t match, then we move on to the next node until we either find a node with the required key.
- If the node is not found, then we create it at the end of the linked list
How does keyword search work:
- The input is a key – value pair
- The hash function returns an index by key
- Get a linked list node from an array by index
- We check if it matches the key
- If it matches, then return the value
- If it doesn’t match, then we move on to the next node until we either find a node with the required key.
Why do we need a linked list inside an array? Because of possible collisions when calculating the hash function. In this case, several different key-value pairs will be located at the same index in the array, in which case the linked list is traversed to find the required key.
Sources
https://ru.wikipedia.org/wiki/Hash table
https://www.youtube.com/watch?v=wg8hZxMRwcw
Source code
https://gitlab.com/demensdeum/datastructures