When working with collections of elements, like a list of strings, or a list of tuples, it becomes computationally very expensive to search for elements in the collection or answer queries like “Is item X present in our collection?”. Yet, comparing numbers is very fast, and our computers are specialized in comparing numbers very efficiently (unlike strings, or tuples). So, if we can map the data at hand to a numeric value, it would make some operations like finding it, or checking if it’s present in the collection quicker.
The technique of mapping data of arbitrary size to fixed-size data is called hashing. The resulting number (hash) serves as a unique identifier for the original data. We are usually given a
hashfunction that can map the initial data to fixed-sized data (like a number).
Python, for instance, has a built-in
hashfunction that can map any immutable object to a number, which is usually in the range
. Note that it can only map immutable objects. So, trying to hash a list or a dictionary (which are mutable and can be changed by adding or removing elements) would result in an error:
print(hash(123)) # 123 print(hash('Anna')) # 2573300035916889866 print(hash('Bob')) # -2781086332262035333 print(hash((2, 'Simon'))) # -6551767300073204554 print(hash([1, 2])) # TypeError: unhashable type: 'list'
Challenge: Hash a pair of integers
Let’s implement a custom hash function
h. It will receive a pair of integers and should return the hashed value. The function
his defined as:
This would ensure that the hash value is always in the range [0; 5077).
The only line of the input contains two numbers
b( ≤ a, b ≤ ).
The program should print the hash of the pair (a, b).
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB