Skip to content
Know.itKnow.it
Create an animated lesson
On request

This article is free to read. Creating a lesson uses your daily or stored credits; review the language and settings before starting.

What is a hash table?

TechnologyLesson on requestFree to read

Quick answer

A hash table is a data structure that stores items by key for near-instant lookup. It runs each key through a 'hash' function to compute where to put the value, so finding it later takes roughly constant time, no matter how much data you store.

Key things to understand

  1. A hash function turns each key into an index in an array.
  2. The value is stored at that index, so lookups jump straight to it.
  3. Average lookup, insert, and delete take roughly constant time.
  4. Two keys landing on the same slot ('collision') are handled by a backup scheme.
  5. It powers dictionaries, database indexes, and caches.

People also ask

Why are hash tables so fast?
The hash function computes an item's location directly, so the program jumps to it instead of searching — usually in constant time.
What is a hash collision?
When two different keys hash to the same slot. Hash tables resolve it by chaining items together or probing for the next free slot.
Where are hash tables used?
Behind the dictionaries and maps in most programming languages, plus database indexes, caches, and deduplication.