chapter
    Hashing and Collision Resolution Notes for GATE CS

    Hashing and Collision Resolution notes for GATE CS: 50 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

    hashing and collision resolution notes

    Open Addressing Mechanics and Probe Sequences

    Open Addressing Mechanics and Probe Sequences

    Table with 11 slots. A key hashes to slot 3, but it is occupied.

    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    Linear probe: 3 → 4 → 5 → 6 → 7

    primary clustering consecutive slots fill into a block

    secondary clustering two keys hashing to 3 follow the identical path

    Consider a hash table with eleven slots, indexed from zero to ten. If we insert a key that hashes to slot three, but slot three is already occupied, we must check another slot. In open addressing, we check slots according to a fixed probe sequence. If the sequence checks slots three, four, five, and six in order, we are using linear probing. This creates primary clustering, where consecutive slots fill up, forming traffic jams. If two different keys both hash to slot three and follow the exact same sequence, they suffer from secondary clustering. In linear and quadratic probing, the probe sequence depends only on the initial hash value, not the key itself. Double hashing avoids this by making the step size a function of the key.

    Explain this more simply
    Imagine a parking lot where every car has an assigned spot. If your spot is taken, you do not leave the lot. You drive to the next available spot. Primary clustering is what happens when everyone assigned to the front row ends up parking in the back row because the front is full. Secondary clustering is when two different people, assigned to the same spot, follow the exact same driving path to find a new space.
    Go one level deeper
    The mathematical distinction between these clusterings dictates performance. Primary clustering degrades the expected probe length because the probability of hitting a filled block increases with the block size. Secondary clustering is less severe but still present in linear and quadratic probing because the probe sequence is a deterministic function of the initial hash value. Double hashing eliminates secondary clustering by making the step size a function of the key itself.

    Linear Probing Formula and Wrap-around

    Table size 11. Key hashes to slot 8. Slots 8, 9, 10 are full.

    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10

    Probe 0: slot 8 (full) → Probe 1: slot 9 (full) → Probe 2: slot 10 (full) → Probe 3: slot 0 (wrap-around)

    h(k, i) = (h(k) + i) mod m

    For h(k)=8, m=11: i=0 → 8, i=1 → 9, i=2 → 10, i=3 → 0

    Suppose a table has size eleven. A key hashes to slot eight. If slot eight is full, linear probing checks slot nine, then ten, then wraps around to zero, then one. The general formula for the i-th probe is the initial hash plus i, all modulo the table size. For our key, the zero-th probe is eight. The first probe is nine. The second probe is ten. The third probe wraps around to zero. The step size is always exactly one. This constant step is what causes primary clustering, as any key hashing near a filled block will join that block.

    Explain this more simply
    Think of a circular track with eleven lanes. You start in your assigned lane. If it is blocked, you move to the very next lane. If you reach lane ten and it is blocked, your next step takes you back to lane zero. You never skip a lane.
    Go one level deeper
    Three-second check: Substitute zero into your formula. If the result is not exactly the initial hash value, your index offset is wrong. The most common error is starting the probe index at one instead of zero. If you start at one, your first check is the initial hash plus one, completely skipping the initial hash slot.

    Quadratic Probing and the Half-Load Limit

    Key hashes to slot 2. Linear probe checks consecutive slots.

    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10

    Probe path: 2 → 3 → 4 → 5 → … (step = 1 each time)

    h(k, i) = (h(k) + i) mod m

    Same key hashes to slot 2. Quadratic probe uses squared offsets.

    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10

    Probe path: 2 → 3 → 6 → 0 → … (steps: +1, +4, +9)

    h(k, i) = (h(k) + i²) mod m
    Precondition: Table must be prime-sized and less than half full to guarantee an empty slot is found.

    Consider a table of size eleven. A key hashes to slot two. Instead of checking three, four, five, quadratic probing checks slot two, then two plus one squared, which is three. The next check is two plus two squared, which is six. The next is two plus three squared, which is zero. The formula uses the square of the probe index. This avoids primary clustering because keys that collide do not follow the same subsequent path. However, it introduces a strict precondition. If the table is more than half full, or if the table size is not prime, the probe sequence might loop without ever finding an empty slot, even if empty slots exist.

    Explain this more simply
    Imagine searching for a seat in a theater. Linear probing is checking the seat to your left, then the next left. Quadratic probing is checking your seat, then skipping one seat to check the next, then skipping three seats, then skipping five. You cover the theater much faster, but you might skip over the only empty seats if the theater is too crowded.
    Go one level deeper
    Candidates often assume quadratic probing will always find an empty slot as long as the table is not completely full. This is false. The standard method breaks if the load factor exceeds half, or if the table size shares factors with the step increments. The check is to verify the table size is prime and the load factor is strictly less than zero point five before assuming guaranteed insertion.

    47 more cards in this chapter

    Free preview ends here

    Login to view the complete notes

    Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

    Login to continueSee plans
    Why MastersUp

    Personalised first. High quality throughout.

    Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

    Built around you, not around a syllabus PDF

    Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

    Revision that hits your weak spots

    We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

    Questions calibrated to the real exam

    Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

    Notes written for recall, not for volume

    Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

    One place for everything

    Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

    Honest progress

    No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

    Unlock the whole course

    Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

    View all plansStart free

    Hashing and Collision Resolution Notes for GATE CS

    Hashing and Collision Resolution notes for GATE CS: 50 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

    Open Addressing Mechanics and Probe Sequences

    Open Addressing Mechanics and Probe Sequences

    Table with 11 slots. A key hashes to slot 3, but it is occupied.

    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    Linear probe: 3 → 4 → 5 → 6 → 7

    primary clustering consecutive slots fill into a block

    secondary clustering two keys hashing to 3 follow the identical path

    Consider a hash table with eleven slots, indexed from zero to ten. If we insert a key that hashes to slot three, but slot three is already occupied, we must check another slot. In open addressing, we check slots according to a fixed probe sequence. If the sequence checks slots three, four, five, and six in order, we are using linear probing. This creates primary clustering, where consecutive slots fill up, forming traffic jams. If two different keys both hash to slot three and follow the exact same sequence, they suffer from secondary clustering. In linear and quadratic probing, the probe sequence depends only on the initial hash value, not the key itself. Double hashing avoids this by making the step size a function of the key.

    Explain this more simply
    Imagine a parking lot where every car has an assigned spot. If your spot is taken, you do not leave the lot. You drive to the next available spot. Primary clustering is what happens when everyone assigned to the front row ends up parking in the back row because the front is full. Secondary clustering is when two different people, assigned to the same spot, follow the exact same driving path to find a new space.
    Go one level deeper
    The mathematical distinction between these clusterings dictates performance. Primary clustering degrades the expected probe length because the probability of hitting a filled block increases with the block size. Secondary clustering is less severe but still present in linear and quadratic probing because the probe sequence is a deterministic function of the initial hash value. Double hashing eliminates secondary clustering by making the step size a function of the key itself.

    Linear Probing Formula and Wrap-around

    Table size 11. Key hashes to slot 8. Slots 8, 9, 10 are full.

    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10

    Probe 0: slot 8 (full) → Probe 1: slot 9 (full) → Probe 2: slot 10 (full) → Probe 3: slot 0 (wrap-around)

    h(k, i) = (h(k) + i) mod m

    For h(k)=8, m=11: i=0 → 8, i=1 → 9, i=2 → 10, i=3 → 0

    Suppose a table has size eleven. A key hashes to slot eight. If slot eight is full, linear probing checks slot nine, then ten, then wraps around to zero, then one. The general formula for the i-th probe is the initial hash plus i, all modulo the table size. For our key, the zero-th probe is eight. The first probe is nine. The second probe is ten. The third probe wraps around to zero. The step size is always exactly one. This constant step is what causes primary clustering, as any key hashing near a filled block will join that block.

    Explain this more simply
    Think of a circular track with eleven lanes. You start in your assigned lane. If it is blocked, you move to the very next lane. If you reach lane ten and it is blocked, your next step takes you back to lane zero. You never skip a lane.
    Go one level deeper
    Three-second check: Substitute zero into your formula. If the result is not exactly the initial hash value, your index offset is wrong. The most common error is starting the probe index at one instead of zero. If you start at one, your first check is the initial hash plus one, completely skipping the initial hash slot.

    Quadratic Probing and the Half-Load Limit

    Key hashes to slot 2. Linear probe checks consecutive slots.

    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10

    Probe path: 2 → 3 → 4 → 5 → … (step = 1 each time)

    h(k, i) = (h(k) + i) mod m

    Same key hashes to slot 2. Quadratic probe uses squared offsets.

    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10

    Probe path: 2 → 3 → 6 → 0 → … (steps: +1, +4, +9)

    h(k, i) = (h(k) + i²) mod m
    Precondition: Table must be prime-sized and less than half full to guarantee an empty slot is found.

    Consider a table of size eleven. A key hashes to slot two. Instead of checking three, four, five, quadratic probing checks slot two, then two plus one squared, which is three. The next check is two plus two squared, which is six. The next is two plus three squared, which is zero. The formula uses the square of the probe index. This avoids primary clustering because keys that collide do not follow the same subsequent path. However, it introduces a strict precondition. If the table is more than half full, or if the table size is not prime, the probe sequence might loop without ever finding an empty slot, even if empty slots exist.

    Explain this more simply
    Imagine searching for a seat in a theater. Linear probing is checking the seat to your left, then the next left. Quadratic probing is checking your seat, then skipping one seat to check the next, then skipping three seats, then skipping five. You cover the theater much faster, but you might skip over the only empty seats if the theater is too crowded.
    Go one level deeper
    Candidates often assume quadratic probing will always find an empty slot as long as the table is not completely full. This is false. The standard method breaks if the load factor exceeds half, or if the table size shares factors with the step increments. The check is to verify the table size is prime and the load factor is strictly less than zero point five before assuming guaranteed insertion.

    Double Hashing: Two Functions and Step Sizes

    Table size 11. Key hashes to slot 4 (full). Second hash returns step size 3.

    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10

    Probe 0: 4 (full) → Probe 1: 4+3=7 (full) → Probe 2: 4+6=10

    h(k, i) = (h₁(k) + i · h₂(k)) mod m

    In a table of size eleven, a key hashes to slot four using the first function. If slot four is full, we evaluate a second hash function for the same key, which returns a step size of three. We add three to get slot seven. If seven is full, we add three again to get slot ten. The formula is the first hash plus the probe index times the second hash, all modulo the table size. The step size is constant for a given key but varies across different keys. This prevents both primary and secondary clustering.

    Explain this more simply
    Your assigned parking spot is taken. Instead of just checking the next spot, you use a personal rule based on your license plate to decide how many spots to skip. That skip distance is fixed for you, but different drivers will skip different numbers of spots, spreading everyone out evenly.
    Go one level deeper
    Three-second check: Verify the second hash function is strictly greater than zero for all keys, and that the step size shares no common factors with the table size. The critical trap is selecting a second hash function that can evaluate to zero, or one that is not coprime to the table size. If the second function returns zero, you will check the same full slot indefinitely.

    More notes in this unit