Hash functions are imperfect; sometimes, totally different data points can result in the same hash result. This violates the one-to-one mapping between the inputs and the hash value. That can result in different strings getting the same hash value, or a pair of numbers having the same hash. Hash collisions can lead to security problems as well as performance issues, depending on the context in which they occur. For example, a simple hash function that maps a pair of integers to a hash value can map many (a, b) pairs to the same hash value:
Here are several examples of
(a, b)pairs resulting in the same hash value:
- h(1, 1) = (1997 + 1) mod 5077 = 1998
- h(1, 5078) = (1997 + 5078) mod 5077 = 1998
- h(5078, 1) = (10140766 + 1) mod 5077 = 1998
So, if we had a list of pairs that were specifically designed to have the same hash, we would have a lot of collisions, and therefore searching for a value or checking if a pair
(a, b)is present in a list would be very inefficient or even wrong (depending on the implementation).
Hash collisions can be a source of security vulnerabilities. User passwords are usually stored as hashes for security reasons (to avoid leaking the passwords even if the database is hacked). If the hash function is not a good one and causes many collisions, the hackers can crack an account without even guessing the right password. If a random password’s hash coincides with the original password’s hash, the system thinks it’s the same person.
A good hash function can ensure as few collisions as possible. Usually, the built-in functions for hashing perform pretty well for random inputs. Yet, if the input data is of a specific type, or the problem has some specific requirements, you will need to implement a custom hashing function.
Challenge: Check for Collisions
Given a hash function
hthat maps a pair of integers
(a, b)to an integer, you are asked to find out if the
hfunction is good enough. The program should check for collisions, and should output
Yesif there are no collisions, and
Nootherwise. The hash function is defined as:
The first line of the input contains a single integer
n(1 ≤ n ≤ 10 000) the number of pairs.
nlines contain space-separated pairs of integers (0 ≤ ≤ ). It’s guaranteed that the given pairs are unique.
The program should print
h(a, b)is a good hash function for the given input and it managed to avoid collisions, and
3 0 4 1 5 2 9
2 0 0 0 1 542313474 3
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB