Exercises B#

Note

You must complete these exercises by Wednesday of W8.

Exercise 4.2.1 (Hash of Long and Double)#

Here is the formula used by Java to calculate the hash code of a double (where bits is a 64-bit value represented as a long):

return (int) bits ^ (bits >>> 32);

  • Why not simply use (int) bits (casting from long to int)? Hint: The textbook suggests that a good hash function should use all bits in its calculation. Why?

  • A double in Java is represented in 64 bits as \((-1)^s \times m \times 2^{(e - 1023)}\). The first bit \(s\) is the sign bit, the next 11 bits represent the exponent in binary, and the last 52 bits represent the mantissa (significand). Do a positive floating-point number and its opposite receive different hash codes?

Exercise 4.2.2 (Hash and casting of integers)#

  • Is the hash code of a 32-bit integer the same as the hash code of the same integer cast to a double?

  • Is the hash code of a 32-bit integer the same as the hash code of the same integer cast to a long? Hint: Long.toBinaryString(Double.doubleToRawLongBits(a)) displays the bits used to represent a double.

Exercise 4.2.3 (String Hashing: Choice of M and R Constants)#

The hash function for a given string as presented on page 460 of the book is as follows:

int hash = 0;
for (int i = 0; i < s.length(); i++)
    hash = (R * hash + s.charAt(i)) % M;

In the book’s implementation, \(M\) (the size of the hash table) is a power of two. The suggested value for \(R\) is a small prime such as 31 so that the bits of all characters play a role.

  • Suppose that \(R\) is a multiple of \(M\). What would happen in the calculation?

  • Suppose that \(R\) is an even number. What would happen?

In both cases, how many characters in the string will actually determine the hash code? What are the risks in terms of collisions? Can controlling the load factor solve this problem? Explain why using 31 is a good choice for array sizes that are powers of two. Would it also be a good choice for an array size that starts at 31 and is multiplied by two each time it is resized?

  • In the book’s implementation, \(M\) (the size of the hash table) is a power of two, initialized to 16. Suppose that at some point \(M\) is \(2^8 = 256\). Then two integer keys are added to a hash table implemented with separate chaining: \(2560\) and \(3072\) respectively (assume that these additions do not cause a resize). As you know, the hash code of an integer key (int) in Java is the integer itself. Will adding these two values cause a collision between them in the table? If so, why?

    If so, can you suggest a third value that will also collide?

    If there is a collision, can it disappear the next time the table is resized using the book’s resizing strategy?

  • What do you suggest to avoid this problem? What is the initialization and resizing policy for \(M\) used in java.util.Hashtable / java.util.HashMap? Does this solve the problem in our example?

Exercise 4.2.4 (Design of a Hash Function for Vehicles)#

  • What would you suggest as a hash function for vehicle identifiers that are strings of numbers and letters of the form: "9X9XX99X9XX999999", where each 9 represents a digit (0–9) and each X represents an uppercase letter (A–Z)?

  • Does your hash function have the property that for a hypothetical array size \(N\) of \(10^{11} \cdot 26^6\) there will never be any collision?

Exercise 4.2.5 (Design of a Hash Function: Citizens)#

Suppose we want to build a directory of Belgian citizens where each citizen can be accessed by their 12-digit national identity card number. We can consider this number as the unique key identifying each citizen and use it directly as an index in a Java array. Each array index would hold a reference to an instance of a class whose fields contain the citizen’s personal information.

What is the time complexity of the following operations?

  • Searching for a citizen’s information using their identity card number.

  • Adding a new citizen.

Is this implementation of a dictionary not even better than a hash table? Can a collision occur in this design? Justify your answer.

Exercise 4.2.6 (Rabin-Karp Revisited)#

Check that you have obtained a solution in \(\mathcal{O}(n)\) and not \(\mathcal{O}(kn)\) (not counting the initial hashing of the keywords to be searched, which is in \(\mathcal{O}(km)\)) for last week’s Exercise 4.1.11.

Exercise 4.2.7 (INGInious: Linear Probing)#

Implement a linear probing hash table.

Exercise 4.2.8 (INGInious: Tries and Autocompletion)#

Implement an efficient auto-completion algorithm using a trie data structure: AutoCompleter

Exercise 4.2.9 (INGInious: A Fun Exercise Using Hash Tables)#

This is problem 21 of the Advent of Code 2022. It can be efficiently solved using a hash table in combination with a linked tree data structure: Monkeys

Exercise 4.2.10 (INGInious: Bitset)#

Implement an efficient alternative to a HashSet when you need to store a dense set of integers: Bitset