A hash table stores key-value pairs so that any pair can be found quickly without scanning the whole collection. It keeps an array of slots, called buckets, and uses a hash function to turn each key into an index into that array. To insert, look up, or delete a key, the table computes the key’s hash, jumps directly to the corresponding bucket, and works only with the few entries stored there. When the hash function spreads keys evenly, these operations take constant time on average, written O(1).
The MIT 6.006 lecture on hashing explains why this matters: a search that only compares keys cannot beat logarithmic time, but hashing sidesteps comparison entirely by computing an address from the key itself. That is how a hash table turns the natural cost of search from log n down to expected constant time, at the price of giving up any sorted ordering of the keys.
Because two different keys can land in the same bucket, every real hash table needs a collision-handling scheme. The common approach taught in the lecture notes is chaining, where each bucket holds a small list of all keys that hashed to it; the alternative is open addressing, where colliding keys are placed in other empty slots. Either way, performance stays close to O(1) only as long as the table is not too full, so implementations resize and rehash as they grow.
Hash tables are among the most heavily used structures in computing. They are the engine behind dictionaries and maps, sets, symbol tables in compilers, and many database indexes. Donald Knuth covers hashing as one of the major searching techniques in Chapter 6 of Volume 3 of The Art of Computer Programming, placing it alongside sequential and comparison-based search.