Data Structure, Hashing

Hash Table

A Hash Table stores data with key value pairs without sortedness.

I think this is the most intuitive

A Hash table consists of a

What you need to know

  • Designed to optimize searching, insertion, and deletion.
  • Hash collisions are when a hash function returns the same output for two distinct inputs.
    • All hash functions have this problem.
    • This is often accommodated for by having the hash tables be very large.
  • Hashes are important for associative arrays and database indexing.

Time Complexity

  • Indexing: Hash Tables: or N/A?
  • Search: Hash Tables:
  • Insertion: Hash Tables:
  • Deletion: Hash Tables:


Basically, when you explain it in a coding interview, you need to:

  1. Define a mapping from your custom class to some unique key as an index
  2. the original key which map to some index buckets, which would store the actual values