Question

A hash function from strings to numbers derives a numerical hash value h(s) from a text string s; for example, by adding up the numerical codes for the characters in s, dividing by a prime number p, and keeping just the remainder. The point of a hash function is to yield a reproducible result (calculating h(s) twice for the same string s yields the same numerical value) and tomake it likely that the hash values for different strings will be spread out evenly across the possible hash values (from 0 to p−1). If the hash function has identical hash values for two different strings, then these two strings are said to collide on that Please do not circulate. hash value.We count the number of collisions on a hash value as 1 less than the number of strings that have that hash value, so if 2 strings have the same hash value there is 1 collision on that hash value. If there are m strings and p possible hash values, what is the minimum number of collisions that must occur on the hash value with the most collisions? The maximum number of collisions that might occur on some hash value?

Answer 1

Answer:

The minimum number of collisions that must occur on the hash value with the most collisions = 0 or 1 or m - p depending on the scenario.

The maximum number of collisions that might occur on some hash value = m - 1

Explanation:

1) Suppose a scenario where the value of m is less than any kind of possible hash values:  

• Then, you can have a zero minimum number of collisions.
• As there will be the same value for all m strings and the hash value might have m -1 maximum number of collisions so this is possible.  

2) Suppose another scenario where the value of m is greater than any kind of possible hash values:  

• Then, you can have at least one minimum number of collisions and it may also be m - p minimum number of collisions in some other cases.  
• As there will be the same value for all m strings and the hash value might have m -1 maximum number of collisions so this is possible.