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
- Hash Table
- Hash Function
- A strategy for dealing with Hash Collision
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:
- Define a mapping from your custom class to some unique key as an index
- the original key which map to some index buckets, which would store the actual values