Hashing

DSA, Database System & Operating System — Sorting, Searching, and Graphs, NEC licence examination syllabus (Nepal Engineering Council).

Hashing: near-instant lookup, if you handle collisions

Compute where a key belongs instead of searching for it — and then deal with the fact that two keys will eventually compute the same answer.

The idea

A hash function turns a key into an array index. Instead of searching a structure, you calculate the position directly and go there — one step, whatever the table's size. That is the O(1) average lookup that makes hash tables the default choice for dictionaries and sets.

h(key) = key mod 7 (table size 7) Insert 15, 22, 9, 3: h(15) = 15 mod 7 = 1 → slot 1 h(22) = 22 mod 7 = 1 → slot 1 is taken. COLLISION. h(9) = 9 mod 7 = 2 → slot 2 h(3) = 3 mod 7 = 3 → slot 3

Collisions are not a flaw in the hash function; they are unavoidable. A hash maps a large key space onto a small table, so by counting alone some keys must share a slot. The interesting question is never how to avoid collisions but what to do when one happens — and that choice is what the exam asks about.

Resolving collisions

🔗 Separate chaining

HowEach slot holds a linked list. Colliding keys are appended to it.

CostLookup is one hash plus a short list walk.

BehaviourDegrades gracefully — the table can hold more entries than it has slots.

📍 Open addressing

HowOn collision, probe for another empty slot — linear probing tries the next slot, quadratic probing steps further each time, double hashing uses a second hash to decide the step.

CostNo extra structures; everything lives in the array.

BehaviourDegrades sharply as the table fills, and cannot exceed its own size.

Load factor: the number that decides performance

load factor α = entries stored / slots available Chaining average chain length is α → lookup stays O(1 + α), workable above α = 1 Open addressing probes rise sharply as α approaches 1 → a nearly full table degrades towards O(n), so it is resized well before then Resizing means allocating a bigger table and REHASHING every key, because h(key) depends on the table size.

💡 Linear probing has a specific weakness worth naming: primary clustering. When a collision fills the next slot, it makes the following slot more likely to be probed too, so occupied runs grow and lengthen every future probe that lands in them. Quadratic probing and double hashing exist to break up those runs.

What makes a good hash function

Uniform — spreads keys evenly, so no slot attracts more than its share. Fast — it runs on every operation, so an expensive hash cancels the benefit. Deterministic — the same key must always hash to the same slot, or nothing can ever be found again.

A prime table size helps with the simple modulo hash, because a composite size shares factors with patterned keys and collapses them onto a few slots — keys that are all multiples of 4 in a table of size 8 use only half the slots.

Commonly confused

O(1) as a guarantee. It is the average. Worst case is O(n), when every key collides.

Chaining and probing. Chaining stores collisions outside the array; probing finds another slot inside it.

Hashing and encryption. A hash is one-way and not reversible by design; it is not a way to hide data.

Rapid revision

Compute the position instead of searching — O(1) average, O(n) worst.

Collisions are unavoidable, so the resolution strategy is the design decision.

Chaining tolerates α > 1; open addressing degrades sharply as α approaches 1.

Linear probing causes primary clustering.

Resizing requires rehashing every key, because the hash depends on the table size.

Syllabus points

Hash function, hash table
Collision resolution: chaining, open addressing

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.