Hash Map Collision Count

Problem

Count hash collisions when inserting keys into a table with chaining.

The bucket index of a key is key % capacity. A collision occurs whenever an insertion lands in a bucket that already holds at least one key; inserting a duplicate key also collides. Assume capacity is positive.

Return the number of collisions.

Hint

Track which bucket indices have been used; every repeat is a collision.

Test cases

case 1

in: [5,[0,1,5,6,10]]

expected: 3

case 2

in: [3,[1,2,3,4,5,6]]

expected: 3

case 3

in: [4,[7,11,15]]

expected: 2

case 4

in: [5,[1,2,3]]

expected: 0

Starter codePython

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

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