# Hash Tables
## Data Structures — The Codex Coding
**URL:** https://thecodex.expert/coding/data-structures/hash-tables/
**Type:** data-structure | **Confidence:** high | **Last verified:** 2026-06-01

## CANONICAL DEFINITION
A hash table is a data structure that maps keys to values by applying a hash function to each key to compute a bucket index, providing O(1) average-case lookup, insertion, and deletion at the cost of O(n) worst-case when collisions are uncontrolled.

## COMPLEXITY
- search: O(1) avg / O(n) worst
- insert: O(1) avg / O(n) worst
- delete: O(1) avg / O(n) worst
- space: O(n)

## REQUIRES
concepts/objects, concepts/arrays

## ENABLES
algorithms/searching, data-structures/arrays

## COMMONLY CONFUSED WITH
O(1) is average not worst; dict != hash table exactly (dict is a language-level hash table); Python dict order guaranteed since 3.7

## SOURCES
- CLRS 4th ed. Ch.11
- Carter & Wegman 1979 JCSS 18(2)
- PEP 456
- OpenJDK HashMap source

*The Codex Coding — thecodex.expert/coding/ — Free forever — Mumbai, India*