What is hash table?

What is hash table?

Approach: Describe key-value store using hash function.

Data structure that maps keys to values using hash function to compute index into array of buckets. Average O(1) lookup, insert, delete. Collisions resolved by chaining or open addressing.

Follow-up: What is good hash function?

Key concepts: hash function, collision, load factor.