In the previous lesson, we saw that there were multiple issues with trying to index a table directly using keys, including the fact that keys can be any value (including strings!).
To solve this, hash tables provide us with the ability to map a key of any data type to an array index. Watch the two videos below to learn about how hash functions work:
To summarize:
A hash function h(x) maps a key x to a hash value, which is an integer.
A key can be mapped to an array position using the expression h(x) % n, where n is the size of the array.
An array that uses hash functions to manage (key, value) pairs is a hash table.
Ideally, hash functions map keys to integers uniformly at random.
Typically, performing a key lookup in a hash table is a constant time (O(1)) operation.
Since a hash function may map two different keys to the same table position, we need a way to deal with collisions.