The current hashing function will return a very large integer, approximately 19 digits long. The hash value is not within the bounds of the hash table array, which was defined at
5 in the last exercise. This is a problem because you cannot store a value at index 1,234,567,890,123 if there are only 5 indices. To fix this, we need to use compression.
Compression means taking some input and returning an output that is within a specific range.
In our hash table implementation, we’re going to have our
index(for:) function handle hash value calculation as well as compression.
To do this, we’ll use modular arithmetic. Because modular arithmetic prevents a value from growing larger than some limit, it’s a common solution when we want a value to “wrap around”.
The modulo operator,
%, returns the remainder when dividing two numbers, discarding the result of the division. This means that the returning value can never be bigger than the divisor.
Take the following division problem for example:
11 % 2 = 1
The remainder of any number modulus
2 will never be greater than
1. This is because any value divided by
2 will either have a remainder of
1. We’ll apply the same modular arithmetic to our array size so the hash value never surpasses the size of our array.
Add a modulo operator after calculating the positive hash value to ensure it does not go outside of the array’s size.