Hashing is a technique which can be used to know the presence of a key in a list in just one step. The idea is if we already know the value at every index position in a list, it would require only a single comparison to check the presence or absence of a key in that list. Hashing makes searching operations very efficient. A formula called hash function is used to calculate the value at an index in the list.
Thus, a hash function takes elements of a list one by one and generates an index value for every element. This will generate a new list called the hash table. Each index of the hash table can hold only one item and the positions are indexed by integer values starting from 0. Note that the size of the hash table can be larger than the size of the list.
A simple hash function that works with numeric values is known as the remainder method. It takes an element from a list and divides it by the size of the hash table. The remainder so generated is called the hash value.
h(element) = element % size(hash table)
We can easily implement a hash table using a Python’s List.
Let us consider an empty hash table having 10 positions as shown in Table :
An Empty hash table with 10 positions
Let us consider a list of numbers (34, 16, 2, 93, 80, 77, 51). We can use the hash function remainder method explained earlier to create a hash table as shown in Table.
Hash function element % 10 applied on the elements of list
After computing the hash values, each element is inserted at its designated position in the hash table shown in Table.
Hash table generated for elements given in Table
Now, to search for a key, we can calculate its index using the hashing function and compare the element at that index with the key to declare whether the element is present in the list or not. This search operation involves just one comparison and hence the same amount of time is always required to search a key irrespective of the size of the list.
