data structures

Hashtables, Pigeonholes, and Birthdays

One of the most beloved of all data structures in computer science is the hash table. A hash table is a data structure that associates keys with values. The primary operation it supports efficiently is a lookup: given a key (e.g. a person’s name), find the corresponding value