Hash Table
noun
say it: “HASH TAY-bul” /hæʃ ˈteɪbəl/
A structure that stores values under keys and turns each key into a bucket number with a hash function, so a value is found without searching.
What is a hash table?
A hash table stores values under keys, like a coat check where your name is the ticket. A hash function turns the key into a bucket number, so putting, getting and removing a value takes one trip to one bucket: O(1) on average, however many values it holds. Every language's dictionary and set is one.
In a sentence
- “The login page finds your account in a hash table, so it takes the same time with a thousand users or a million.”
Level: Apprentice · More Data Structures terms at this level
Updated