Past exam question: 2079 Ashwin (Back), Q9(a)
Open in the Padhaiko appQuestion
What is Hashing? Why do we need Hashing?
Solution
Definition of Hashing: Hashing is an efficient data storage and retrieval technique in which an arbitrary-sized search key is transformed into a fixed-range integer index through a mathematical function known as a hash function:
Here, denotes the size of the array or Hash Table.
Instead of comparing keys sequentially or hierarchically, hashing directly computes the table address where the record resides, facilitating constant-time operations.
Why We Need Hashing:
- Constant-Time Search Efficiency ():
- In comparison-based search structures:
- Linear search takes time.
- Binary search on sorted arrays takes time, but insertions take .
- Balanced Binary Search Trees (AVL, Red-Black) take time for search, insert, and delete.
- Hashing achieves average-case constant-time complexity for all three core operations (Search, Insert, and Delete).
- In comparison-based search structures:
- Feasibility Over Direct Addressing (Memory Compression):
- If keys are drawn from a massive universe (e.g., 9-digit citizenship/student roll numbers, or alphanumeric usernames like
"arya123"), allocating a direct-address array of size is impossible due to physical RAM limitations. - Most applications store only a small subset of actual active keys (). Hashing maps this massive sparse key space into a compact table of size , eliminating astronomical memory waste.
- If keys are drawn from a massive universe (e.g., 9-digit citizenship/student roll numbers, or alphanumeric usernames like
- Widespread Industry Applications:
- Compiler symbol tables for identifier lookups.
- Database indexing (Hash indexes for equality queries).
- In-memory key-value caching (e.g., Redis, Memcached).
- Network routing lookups and cryptographic message authentication.
Answer:
- Hashing is a technique that maps large or variable keys to fixed indices in a hash table using a hash function to enable direct record addressing.
- Why it is needed:
- Provides expected constant-time performance for search, insert, and delete operations.
- Compresses vast key universes into practical, bounded memory sizes, avoiding the impossible memory footprints of direct-address arrays.