5.1 Given input {4371, 1323, 6173, 4199, 4344, 9679, 1989} and a hash function
h(x) = x mod 10, show the resulting:
a. Separate chaining hash table.
b. Hash table using linear probing.
c. Hash table using quadratic probing.
d. Hash table with second hash function h2(x) = 7 − (x mod 7). Get solution
5.2 Show the result of rehashing the hash tables in Exercise 5.1. Get solution
5.4 A large number of deletions in a separate chaining hash table can cause the table to be fairly empty, which wastes space. In this case, we can rehash to a table half as large. Assume that we rehash to a larger table when there are twice as many elements as the table size. How empty should the table be before we rehash to a smaller table? Get solution
5.5 Reimplement separate chaining hash tables using singly linked lists instead of using
java.util.LinkedList. Get solution
5.6 The isEmpty routine for quadratic probing has not been written. Can you implement
it by returning the expression currentSize==0?
Sol: No; this does not take deletions into account.
5.7 In the quadratic probing hash table, suppose that instead of inserting a new item into the location suggested by findPos, we insert it into the first inactive cell on the search path (thus, it is possible to reclaim a cell that is marked “deleted,” potentially saving space).
a. Rewrite the insertion algorithm to use this observation. Do this by having find-
Pos maintain, with an additional variable, the location of the first inactive cell it
encounters. (Solution Not available)
b. Explain the circumstances under which the revised algorithm is faster than the
original algorithm. Can it be slower?
Sol: If the number of deleted cells is small, then we spend extra time looking for inactive cells that are not likely to be found. If the number of deleted cells is large, then we may get improvement.
5.8 Suppose instead of quadratic probing, we use “cubic probing”; here the ith probe
is at hash(x) + i3. Does cubic probing improve on quadratic probing? Get solution
5.9 The hash function in Figure 5.4 makes repeated calls to key.length( ) in the for
loop. Is it worth computing this once prior to entering the loop?
Sol: In a good library implementation, the length method should be inlined.
5.10 What are the advantages and disadvantages of the various collision resolution
strategies? Get solution
5.12 Rehashing requires recomputing the hash function for all items in the hash table.
Since computing the hash function is expensive, suppose objects provide a hash member function of their own, and each object stores the result in an additional data member the first time the hash function is computed for it. Show how such a scheme would apply for the Employee class in Figure 5.8, and explain under what circumstances the remembered hash value remains valid in each Employee.
Sol: The old values would remain valid if the hashed values were less than the old table size.
5.13 Write a program to implement the following strategy for multiplying two sparse polynomials P1, P2 of size M and N, respectively. Each polynomial is represented as a linked list of objects consisting of a coefficient and an exponent (Exercise 3.12).
We multiply each term in P1 by a term in P2 for a total of MN operations. One method is to sort these terms and combine like terms, but this requires sorting MN records, which could be expensive, especially in small-memory environments.
Alternatively, we could merge terms as they are computed and then sort the result.
a. Write a program to implement the alternative strategy.
b. If the output polynomial has about O(M + N) terms, what is the running time
of both methods? Get solution
5.14 Describe a procedure that avoids initializing a hash table (at the expense of
memory). Get solution
5.16 Java 7 adds syntax that allows a switch statement to work with the String type
(instead of the primitive integer types). Explain how hash tables can be used by the
compiler to implement this language addition. Get solution
5.19 Under certain assumptions, the expected cost of an insertion into a hash table with
secondary clustering is given by 1/(1−λ)−λ−ln(1−λ). Unfortunately, this formula
is not accurate for quadratic probing. However, assuming that it is, determine the
following:
a. The expected cost of an unsuccessful search.
b. The expected cost of a successful search. Get solution
5.20 Implement a generic Map that supports the put and get operations. The implementation
will store a hash table of pairs (key, definition). Figure 5.55 provides the Map
specification (minus some details). Get solution
5.23 If a hopscotch table with parameter MAX_DIST has load factor 0.5, what is the
approximate probability that an insertion requires a rehash? Get solution
