PadhaikoAll subjects

Past exam question: 2079 Ashwin (Back), Q9(a)

Data Structure and Algorithms · 3 marks

Open in the Padhaiko app

Topic: Searching Algorithms

Question

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:

  1. 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).
  2. 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.
  3. 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:

All past exam questions for Data Structure and Algorithms