Hash Table

Hash table data structure allows to realize an associative array (dictionary), with an average capacity of O (1) to insert, delete, search.

Below is an example of a simple implementation of a hash mapy on nodeJS:

How it works? Watching the hands:

  • Inside is an array of hash mapy
  • Inside the element of the array is a pointer to the first node of a linked list
  • Partitioning the memory to an array of pointers (e.g. 65,535 cells)
  • Implement the hash function, the input dictionary is the key, and at the outlet it can do just about anything, but in the end returns the array index

How does the record:

  • At the entrance there is a pair of key – value
  • The hash function returns the index on
  • Get node linked list from an array by index
  • Check whether it matches the key
  • If it matches, then replace the value
  • If it does not, then move on to the next node, until we find or do not find the node with the correct key.
  • If the node has not found, we create it at the end of a linked list

How does the search key:

  • At the entrance there is a pair of key – value
  • The hash function returns the index on
  • Get node linked list from an array by index
  • Check whether it matches the key
  • If it matches, the return value
  • If it does not, then move on to the next node, until we find or do not find the node with the correct key.

Why do we need a linked list in the array? Because of possible conflicts in the calculation of the hash function. In such a case several different key-value pairs will be located on the same index in the array, in such a case is carried out by extending the linked list with the search key necessary.

References

https://en.wikipedia.org/wiki/Hash_table
https://www.youtube.com/watch?v=wg8hZxMRwcw

Source Code

https://gitlab.com/demensdeum/datastructures