Search code examples
algorithmhashcollision-detectioncollisionhash-collision

What hash function produces the maximum number of collisions when hashing n keys?

My question has to do with collisions. What is the maximum number of collisions that may result from hashing n keys? I believe you would be able to find this by taking n-1. But I am unsure if this is correct. I'm specifically trying to figure out a hash function that would produce that many collisions. I'm just having a hard time understand the concept of the question. Any help on the subject would be appreciated!

Solution

  • The maximum number of collisions is equal to the number of items you hash.

    Example:

    hash function: h(x) = 3

    All items will be hashed to key 3.

    Notice that number of keys, n in your case, doesn't affect the answer, since no matter how many keys you have, your items are always going to be hashed in key 3, with the h(x) I provided above.

    Visualization:

    Usually, hashing looks like this:

    enter image description here

    but if I want to have the maximum number of collisions, then, by using the h(x) provided above I will get all my items (the names in the picture) all hashed to the vary same key, i.e. key 3.

    So in that case the maximum number of collisions is the number of names, 5.