Search a sorted list by checking every entry one by one, and a bigger list takes proportionally longer to search — ten times the entries, roughly ten times the work. A hash table is built to avoid that trade-off almost entirely: looking something up takes, on average, roughly the same amount of time whether the table holds ten entries or ten million.
Turning a key into an address instead of searching for it
A hash table works by running each item's key — a word, a username, an ID — through a hash function, a calculation that converts that key into a number, which is then used directly as an index into an array. Looking up a key later means running it through the same hash function again, landing on the same index, and checking what's stored there — no scanning through other entries required, because the key told you exactly where to look before you ever started searching.
What happens when two keys land on the same address
Different keys can, occasionally, hash to the same index — a collision — and how a hash table handles that determines how well it holds up under heavy use. Common strategies include chaining, where each index holds a small list of every key that's landed there, checked one by one only within that short list, or open addressing, where a colliding key gets placed at the next available nearby slot according to a fixed rule. A well-designed hash function spreads keys evenly enough that collisions stay rare, and the lookups — checking a short list, or trying a few nearby slots — stay close to instant on average, which is how the whole structure keeps its near-constant lookup speed even as it grows.
What we're still unsure about
The near-constant lookup time is an average, not a guarantee. A badly chosen hash function, or a malicious user who can predict it, can force many keys to collide on purpose, degrading a hash table's performance toward the slow, one-by-one search it was designed to avoid — an attack real systems have to defend against explicitly. Designing hash functions that are both fast to compute and provably resistant to this kind of deliberate collision attack, for every kind of data a system might realistically see, remains an active area of research in both computer science and applied security, not a fully settled problem.
This sits inside Hash Tables & Hash Functions, one of eight topics in Data Structures, one of seven domains in Computer Science, one of seventeen subjects the app can quiz you on.