chapter
    Hashing and Collision Resolution Practice Questions for GATE CS

    Solve 0+ Hashing and Collision Resolution practice questions for GATE CS with answers and detailed solutions. Free sample questions below.

    Free preview ends here

    Login to view the complete practice questions and solutions

    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 Practice Questions for GATE CS

    Solve 0+ Hashing and Collision Resolution practice questions for GATE CS with answers and detailed solutions. Free sample questions below.

    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.

    More practice questions in this unit