Upgrade to Pro — share decks privately, control downloads, hide ads and more …

hash table - Part of an article on https://dev....

gitSushi
October 15, 2020

hash table - Part of an article on https://dev.to/gitsushi/data-structures-5cpj

gitSushi

October 15, 2020
Tweet

More Decks by gitSushi

Other Decks in Programming

Transcript

  1. What does a hash table do ? A hash table

    is a data structure that uses hashing to implement mappings of key / value pairs.
  2. What does a hash table do ? A simplistic diagram

    1. Takes a key / value pair as input 2. Key goes through the hash function and returns an index 3. The pair is stored at that index hash function 1 { key: value }
  3. What makes the hash table great ? • A hash

    function is irreversible. One cannot take the index and find the key. It only works one way. • A hash table is deterministic system. One gets the same result from the same input every time. • A hash table is very efficient. The time complexity in big O notation is O(1).
  4. Notes • However it is possible for two different inputs

    to return the same result. This is called a collision. • Collisions are stored in a nested array. This method is called seperate chaining. • This is also why the time complexity worst case is O(n), n being the number of inputs.
  5. Before we get to the code • Hash tables are

    included in most programming languages. This article is for a better understanding on how they work than a tutorial on how to implement one yourself. • In the following code example, we will implement an simple hash function. There are multiple ways to write them.
  6. First comes the hash function. It takes a key of

    type string and an integer size as parameter.
  7. The size is the length of the array storing the

    key/value pairs. Thus hashedkey % size returns the index.
  8. The remove function will save the value of the element

    to be removed with the get method of the Map object.
  9. The search function returns the value with get method of

    Map with the appropriate index returned by the hash function.