Glossary

Hash Table

A hash table is a data structure providing O(1) average-case access by key. A key is passed through a hash function; the result points to a "bucket" storing the value. Associative arrays in PHP and dicts in Python are hash tables.

Collisions

Different keys can produce the same hash — a collision. Resolved two ways:

Chaining — each bucket holds a list of elements with the same hash
Open addressing — on collision, probe for the next free bucket

Load factor

The ratio of elements to buckets. When a threshold is exceeded (usually 0.75), rehashing occurs (table grows, elements redistributed). Expensive, but rare.

Vs search tree

Hash table: O(1) access, but no ordering. BST: O(log n) access, but elements are sorted. Choose based on whether sorted order matters.