Hash tables | Notion

References

Concept

Hash tables are very similar to direct address tables. Actually, it's an optimization of it.

A hash table is an unordered collection of key-value pairs (which means that it stores data in an associative manner), where each key is unique, implemented through an array (exactly like a direct address table). And that's why hash tables offers a combination of efficient lookup, insert and delete operations. The main difference, here, between the direct address table and the hash table is that the hash table uses a hash technique to generate an index (that it's going to be our data position into our array). We call it the hash function. The hash function is responsible for overcoming one of the biggest problems in direct address tables: scenarios with a large number of key-value pairs.

Hash Function

The hash function (h) is a special function that converts a range of key values into a range of indexes of an array. To do so, it uses the modulo operator.

<aside> 💡 The modulo operator returns the remainder of a division, after one number is divided by another (called the modulus of the operation). For example, the expression "5 % 2" would evaluate to 1, because 5 divided by 2 has a quotient of 2 and a remainder of 1, while "9 % 3" would evaluate to 0, because the division of 9 by 3 has a quotient of 3 and a remainder of 0.

</aside>

So, the formula for the hash function is: h(k) = k % m

Where:

h is the hash function
k is the key of which the hash value should be determined
m is the size of the hash table (number of slots available)

Example:

Key: 1 | Hash: 1 % 20 = 1 | Index: 1
Key: 2 | Hash: 2 % 20 = 2 | Index: 2
Key: 42 | Hash: 42 % 20 = 2 | Index: 2