Double Hashing Probe Count

Problem

Count the total number of probes used to insert keys with double hashing.

The primary hash is key % capacity and the step is 1 + (key % (capacity - 1)). Probing visits (h1 + i * h2) % capacity for i = 0, 1, 2, ... Each visited slot counts as one probe; stop after the first empty slot. Assume keys are distinct and capacity is at least 2.

Return the total number of probes over all insertions.

Hint

The step is never zero, so the probe sequence eventually visits slots spread across the table.

Test cases

case 1

in: [7,[10,20,30]]

expected: 3

case 2

in: [5,[0,5]]

expected: 3

case 3

in: [3,[0,3,6]]

expected: 5

case 4

in: [2,[]]

expected: 0

Starter codePython

def double_hashing_probes(capacity, keys):
    # Your code here
    pass

4 test cases · run your code against them in the editor