Under certain assumptions, the expected cost of an insertion into a hash table

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).

Show the result of rehashing the hash tables in Exercise 5.1.

Write a program to compute the number of collisions required in a long random sequence of insertions using linear probing, quadratic probing, and double hashing.

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?

Reimplement separate chaining hash tables using singly linked lists instead of using java.util.LinkedList.

The isEmpty routine for quadratic probing has not been written. Can you implement it by returning the expression currentSize==0?

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 findPos maintain, with an additional variable, the location of the first inactive cell it encounters. b. Explain the circumstances under which the revised algorithm is faster than the original algorithm. Can it be slower?

Suppose instead of quadratic probing, we use cubic probing; here the ith probe is at hash(x) + i 3. Does cubic probing improve on quadratic probing?

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?

What are the advantages and disadvantages of the various collision resolution strategies?

Suppose that to mitigate the effects of secondary clustering we use as the collision resolution function f(i) = i r(hash(x)), where hash(x) is the 32-bit hash value (not yet scaled to a suitable array index), and r(y) = |48271y( mod (231 1))| mod TableSize. (Section 10.4.1 describes a method of performing this calculation without overflows, but it is unlikely that overflow matters in this case.) Explain why this strategy tends to avoid secondary clustering, and compare this strategy with both double hashing and quadratic probing

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.

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?

Describe a procedure that avoids initializing a hash table (at the expense of memory).

Suppose we want to find the first occurrence of a string P1P2 Pk in a long input string A1A2 AN. We can solve this problem by hashing the pattern string, obtaining a hash value HP, and comparing this value with the hash value formed from A1A2 Ak, A2A3 Ak+1, A3A4 Ak+2, and so on until ANk+1ANk+2 AN. If we have a match of hash values, we compare the strings character by character to verify the match. We return the position (in A) if the strings actually do match, and we continue in the unlikely event that the match is false. a. Show that if the hash value of AiAi+1 Ai+k1 is known, then the hash value of Ai+1Ai+2 Ai+k can be computed in constant time. b. Show that the running time is O(k + N) plus the time spent refuting false matches. c. Show that the expected number of false matches is negligible. d. Write a program to implement this algorithm. e. Describe an algorithm that runs in O(k + N) worst-case time. f. Describe an algorithm that runs in O(N/k) average time.

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.

An (old style) BASIC program consists of a series of statements numbered in ascending order. Control is passed by use of a goto or gosub and a statement number. Write a program that reads in a legal BASIC program and renumbers the statements so that the first starts at number F and each statement has a number D higher than the previous statement. You may assume an upper limit of N statements, but the statement numbers in the input might be as large as a 32-bit integer. Your program must run in linear time.

a. Implement the word puzzle program using the algorithm described at the end of the chapter. b. We can get a big speed increase by storing, in addition to each word W, all of Ws prefixes. (If one of Ws prefixes is another word in the dictionary, it is stored as a real word.) Although this may seem to increase the size of the hash table drastically, it does not, because many words have the same prefixes. When a scan is performed in a particular direction, if the word that is looked up is not even in the hash table as a prefix, then the scan in that direction can be terminated early. Use this idea to write an improved program to solve the word puzzle. c. If we are willing to sacrifice the sanctity of the hash table ADT, we can speed up the program in part (b) by noting that if, for example, we have just computed the hash function for excel, we do not need to compute the hash function for excels from scratch. Adjust your hash function so that it can take advantage of its previous calculation. d. In Chapter 2, we suggested using binary search. Incorporate the idea of using prefixes into your binary search algorithm. The modification should be simple. Which algorithm is faster? class Map<KeyType,ValueType> 2 { 3 public Map( ) 4 5 public void put( KeyType key, ValueType val ) 6 public ValueType get( KeyType key ) 7 public boolean isEmpty( ) 8 public void makeEmpty( ) 9 10 private QuadraticProbingHashTable<Entry<KeyType,ValueType>> items; 11 12 private static class Entry<KeyType,ValueType> 13 { 14 KeyType key; 15 ValueType value; 16 // Appropriate Constructors, etc. 17 } 18 }

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.

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).

Implement a spelling checker by using a hash table. Assume that the dictionary comes from two sources: an existing large dictionary and a second file containing a personal dictionary. Output all misspelled words and the line numbers in which they occur. Also, for each misspelled word, list any words in the dictionary that are obtainable by applying any of the following rules: a. Add one character. b. Remove one character. c. Exchange adjacent characters.

Prove Markovs Inequality: If X is any random variable and a > 0, then Pr( |X| a) E( |X| )/a. Show how this inequality can be applied to Theorems 5.2 and 5.3.

If a hopscotch table with parameter MAX_DIST has load factor 0.5, what is the approximate probability that an insertion requires a rehash?

Implement a hopscotch hash table and compare its performance with linear probing, separate chaining, and cuckoo hashing.

Implement the classic cuckoo hash table in which two separate tables are maintained. The simplest way to do this is to use a single array and modify the hash function to access either the top half or the bottom half.

Extend the classic cuckoo hash table to use d hash functions.

Show the result of inserting the keys 10111101, 00000010, 10011011, 10111110, 01111111, 01010001, 10010110, 00001011, 11001111, 10011110, 11011011, 00101011, 01100001, 11110000, 01101111 into an initially empty extendible hashing data structure with M = 4.

Write a program to implement extendible hashing. If the table is small enough to fit in main memory, how does its performance compare with separate chaining and open addressing hashing?