Hash Tables

A hash table is a key/value store, where each key points to a different value. This provides easy and fast access to the elements by the key. The advantage to hash tables is that inserting, removing, and accessing values are constant time operations, or O(1).

Under the hood, hash tables are built with a dynamic array of linked lists. The keys are transformed into an index of the array using a hashing function. These hashing functions will always return the same output with a given input. Each index of the hash table is actually a linked list, where the values are stored as nodes. If two keys equate to the same index when run through the hashing function, then the linked list will store multiple values. These values then point back to the key via another pointer, so we know which key is associated to which value.

Theoretically, if every key links to the same index, then the time complexity of operations is O(n). Most modern hashing functions are designed to minimize collisions, so we can assume O(1) complexity on average. Similar to a dynamic array, the hash table can resize itself once it starts to fill up, rehash the keys, and replace the values in their new spots.

[
    0: (value1, key1) -> null
    1: null
    2: (value2, key2) -> (value3, key3) -> (value4, key4) -> null
]