Hash Table
A data structure that maps keys to values using a hashing function for fast lookup.
A hash table (or hash map) is a structure that can map keys to values. A hash table uses a hash [function](/en/terms/hash-function) to compute an index into an array of buckets or slots, from which the desired value can be found. In an ideal case, the hash function will assign each key to a unique bucket, but most hash table designs employ some form of collision resolution.
graph LR
Center["Hash Table"]:::main
Rel_index_database["index-database"]:::related -.-> Center
click Rel_index_database "/terms/index-database"
Rel_relational_database["relational-database"]:::related -.-> Center
click Rel_relational_database "/terms/relational-database"
Rel_object["object"]:::related -.-> Center
click Rel_object "/terms/object"
classDef main fill:#7c3aed,stroke:#8b5cf6,stroke-width:2px,color:white,font-weight:bold,rx:5,ry:5;
classDef pre fill:#0f172a,stroke:#3b82f6,color:#94a3b8,rx:5,ry:5;
classDef child fill:#0f172a,stroke:#10b981,color:#94a3b8,rx:5,ry:5;
classDef related fill:#0f172a,stroke:#8b5cf6,stroke-dasharray: 5 5,color:#94a3b8,rx:5,ry:5;
linkStyle default stroke:#4b5563,stroke-width:2px;
🧠 Knowledge Check
🧒 Explain Like I'm 5
A [hash](/en/terms/hash) table is like a giant library where a magician (the [hash [function](/en/terms/function)](/en/terms/hash-function)) takes the title of a book and instantly tells you exactly which shelf and position it's on. You don't have to walk through every aisle; you just go straight to the book you want.
🤓 Expert Deep Dive
Hash tables rely on uniform distribution to achieve average O(1) complexity. Collision resolution strategies include Separate Chaining (linked lists in buckets) and Open Addressing (Linear Probing, Quadratic Probing). Load factor management (rehashing) is critical for preventing performance degradation during table growth.