Hash Tables

A hash function turns a key into an index. Two keys landing on the same index is a collision, handled by chaining (a list per slot) or open addressing (probe the next free slot).

Average insert/lookup/delete: $O(1)$; worst case $O(n)$ if many keys collide. When the table fills up past its load factor, it is resized and every key is rehashed. Python dict, Java HashMap and C++ unordered_map are hash tables.