Hash Table

Time complexity of Hash table: https://stackoverflow.com/questions/3949217/time-complexity-of-hash-table

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

More intuitive https://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm

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: O(1) or N/A?
  • Search: Hash Tables: O(1)
  • Insertion: Hash Tables: O(1)
  • Deletion: Hash Tables: O(1)

Implementation

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