In this problem you are required to design a hash function named Bailando on textual words composed of 5 characters (characters from a – z and A – Z).
Provide an algorithm (set of operations) to generate the output of your hash function. Try to come up with a hash design that has seemingly no collisions.
What is Bailando(“hello”), Bailando(“three”), and Bailando(“olleh”) based on your design.
Can you find any two 5-character words that generate a collision in your hash design?
How can you improve your function to reduce the number of collisions?
To design the hash function named Bailando, we can follow these steps:
Step 1: Calculate the ASCII values for each character in the word.
Step 2: Sum up these ASCII values.
Step 3: Take the modulo of the sum with a prime number larger than the number of possible outputs desired.
Here is the algorithm to generate the output of the Bailando hash function:
1. Start with the input word.
2. Convert all characters to lowercase if any are uppercase.
3. Convert each character to its ASCII value and sum them up.
4. Take the modulo of the sum with a suitable prime number.
Now let's calculate the output of Bailando("hello"), Bailando("three"), and Bailando("olleh") based on this design:
1. Bailando("hello"):
- The ASCII values of 'h', 'e', 'l', 'l', 'o' are 104, 101, 108, 108, 111.
- Sum = 104 + 101 + 108 + 108 + 111 = 532.
- If we select a prime number larger than the number of possible outputs desired, let's say 541, the output would be 532 % 541 = 532.
2. Bailando("three"):
- The ASCII values of 't', 'h', 'r', 'e', 'e' are 116, 104, 114, 101, 101.
- Sum = 116 + 104 + 114 + 101 + 101 = 536.
- Using the same prime number, the output would be 536 % 541 = 536.
3. Bailando("olleh") (the reverse of "hello"):
- The ASCII values of 'o', 'l', 'l', 'e', 'h' are 111, 108, 108, 101, 104.
- Sum = 111 + 108 + 108 + 101 + 104 = 532.
- Using the same prime number, the output would be 532 % 541 = 532.
We can see that "hello" and "olleh" produce the same hash value, resulting in a collision.
To reduce the number of collisions, we can make some improvements to the hash function design:
1. Increase the output range: If we want to reduce the chance of collisions, using a larger prime number as the modulo value would increase the output range, providing more possible outputs and reducing the likelihood of collisions.
2. Consider the position of characters: Instead of simply summing up the ASCII values, we can also include the position of each character in the word. For example, the ASCII value of 'h' at position 1 could be different from 'h' at position 3. This incorporation of position can help to spread the hash values more evenly.
3. Use other algorithms: There are various established hash functions, such as SHA family (e.g., SHA-256), that provide better distribution and lower collision probability. You can explore those algorithms to further reduce collisions.
It is essential to note that achieving a hash design with absolutely no collisions is practically impossible. The goal is to reduce the probability of collisions as much as possible.