Base.cs Podcast S4:E1 - "Gotta hash 'em all"
Oct 31, 2018
Dive into the world of hash tables! Explore how hash functions determine data placement and speed up retrieval. Discover the difference between naive array insertion and efficient hashing, and learn about searching arrays with Big O time complexity. The hosts use fun metaphors like fridge shelving to explain buckets and indexing. Plus, get insights on collision handling and why even distribution is crucial for performance. This engaging conversation makes complex concepts accessible while adding a touch of humor!
AI Snips
Chapters
Books
Transcript
Episode notes
Two Parts That Make Hash Tables
- A hash table combines an array with a hash function to store and locate data efficiently.
- The hash function decides where each item lives inside the array so retrieval can be fast.
Linear Search Limits Arrays
- Without a hash function you must linearly search an array when you don't know an index.
- That linear search is O(N) in the worst case and doesn't scale to large datasets.
Use Hash Functions To Map And Retrieve
- Use a hash function to map inputs to array buckets so items distribute across the table.
- Rely on the hash function both to place items and to locate them later for fast access.
