Exercises

The following exercises provide you with the opportunity to practice with hash functions, randomized hashing, and hash function families. The solutions to these exercises are found in the section .

1. Imagine that you’re the nefarious hacker I described in the chapter. You’ve found an app to exploit, and you obtained its source code. (Bwah hah hah hah!) When reading the code, you discover that it stores its data in a hash table, and the hash function being used is the Division Method. However, it’s not randomizing the hash function in any way. Instead, the app always uses the following hash function, with K representing the key being hashed:

   ​

   K % 997

   What data can you feed the app so that all the data ends up in the same slot within the hash table?

2. Exploration: In this chapter, we only hashed numbers, but what if we want to hash strings? Let’s extend our division hashing method so that it can hash strings as well. To do this, we’ll rely on ASCII standards to map each alphabet character to an integer. In Python, we can use the ord method to convert a character to an integer. For example:

   ​	ord(​'a'​)
   ​	>>> 97
   ​
   ​	ord(​'z'​)
   ​	>>> 122

   Modify the hash function from our DivisionHasher class so that it can hash strings as well as integers.

3. Exploration: Once you’ve completed Exercise #2, here’s another thing to think about. Does your hash function place anagrams in the same slot? For example, does your hash function assign the same hash code to both "listen" and "silent"? Can you make it so that your function doesn’t necessarily assign the same hash code to anagrams?