Hash tables
Data structures using hash functions to map keys to storage indices, enabling O(1) average-case lookup time. Hash tables organize data as key-value pairs stored in arrays. Hash collisions occur when different keys hash to the same index, requiring resolution strategies. Hash tables trade space for speed, providing fast insertion, deletion, and lookup.
Formula
index = hash(key) MOD table_size
Real World
Python dictionaries use hash tables internally — when Instagram stores millions of usernames mapped to profile data, hash tables let it find any user in near-constant time.
Exam Focus
Always explain a collision resolution method (chaining or linear probing) — questions on hashing almost always require this for full marks.
How well did you know this?