Hashing

Overview

Explains hash functions, collisions and why load factor governs performance.

A hash table maps a key to an array index using a hash function. When two keys map to the same index, the table resolves the collision by chaining entries in a list or by probing for another slot.

Performance stays close to constant time only while the load factor, the ratio of entries to slots, is kept low; tables resize to maintain it.