Conceptual
Browse Instruct Curate
Login

Hash Table Lookup in Constant Time

A hash table stores entries in buckets chosen by hashing the key, so a lookup costs one hash computation and a short probe instead of a scan of every entry. Its speed is bought with memory, it holds no ordering among keys, and it depends on the table living where random access is cheap. After this Concept a student can explain why a hash-map lookup is constant time regardless of table size, and can name the two things it gives up: range queries and a small memory footprint.