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