Data Structure, Hashing

Hash Table

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

I think this is the most intuitive https://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm

A Hash table consists of a

• Hash Table
• Hash Function
• A strategy for dealing with Hash Collisions

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