Hashing is a technique of mapping a large set of arbitrary data to tabular indexes using a hash function. It is a method for representing dictionaries for large datasets.

It allows lookups, updating and retrieval operation to occur in a constant time i.e. O(1).

Why Hashing is Needed?

After storing a large amount of data, we need to perform various operations on these data. Lookups are inevitable for the datasets. Linear search and binary search perform lookups/search with time complexity of O(n) and O(log n) respectively. As the size of the dataset increases, these complexities also become significantly high which is not acceptable.

We need a technique that does not depend on the size of data. Hashing allows lookups to occur in constant time i.e. O(1).

Hash Function

A hash function is used for mapping each element of a dataset to indexes in the table.

For more information on hash table, collision resolution techniques and hash functions, please visit Hash Table.

Did you find this article helpful?