CSE Roadmap

Common tier · about 2 hours · 5 parts

Part 2 of 5 · 1 min read

How a hash index locates a value

A hash function maps a key directly to a bucket, skipping any tree traversal.

Think of a coat-check counter. It assigns every coat a numbered hook using a fixed rule based on the ticket number, so finding a coat later means computing that same rule once, not searching hook by hook.

In plain words: a hash index runs each key through a hash function, which maps the key to a specific bucket in a fixed-size table. Looking up a value means computing its hash once and going directly to that bucket, rather than walking down several levels of a search tree the way a B+-tree lookup does. A bucket may hold more than one entry if different keys happen to hash to the same bucket, called a collision, but in a well-sized hash index that list stays short.

A worked example. Looking up customer_id = 42 in a hash index computes the hash of 42 once, lands directly on its bucket, and checks the short list of entries there for a match.

The key lines.

CREATE INDEX idx_orders_customer_hash ON orders USING HASH (customer_id);
SELECT * FROM orders WHERE customer_id = 42;
-- the hash of 42 is computed once, landing directly on its bucket

Hash index

A hash index maps each key to a bucket using a hash function, allowing an exact-match lookup to reach the right bucket directly, without traversing a search tree.

Example: a coat-check counter's numbered-hook rule, computed once per ticket, is a hash index over coat tickets.