Exercises 11.2

11.2-1 Suppose we use a hash function h to hash n distinct keys into an array T of length m. Assuming simple uniform hashing, what is the expected number of collisions? More precisely, what is the expected cardinality of k and l where k is not equal to l and h(k) = h(l)}

Solution:

α = Expected Number of Collisions = n/m . This is also called the load factor, which means how many keys hashed to 1 slot of the table.

11.2-2 Demonstrate what happens when we insert the keys 5; 28; 19; 15; 20; 33; 12; 17; 10 into a hash table with collisions resolved by chaining. Let the table have 9 slots, and let the hash function be h(k) = k mod 9

Solution:

The hash table with collisions resolved by chaining looks like below:

| 1 | ->10->19->28 | 2 |->20 | 3 |->12 | 4 | | 5 | -> 5 | 6 |->33->15 | 7 | | 8 |->17 | 9 |

11.2-3 Professor Marley hypothesizes that he can obtain substantial performance gains by modifying the chaining scheme to keep each list in sorted order. How does the professor's modification affect the running time for successful searches, unsuccessful searches, insertions, and deletions?

Solution:

The running time will be affected as follows: Both Successful and Unsuccessful Searches take time O(l) where l = length of the list. As long as load factor is constant, it should not affect the average time complexity of O(1).

Insertions: The insertion operation earlier took O(1) because ecah time a new key was added to the head of the list. But now it would take O(l) where l = length of the list.

Deletions: As long as list is doubly linked list, it should still take O(1) time to delete an element from the table. But if it is singly linked list then it would take O(l) whether or not the list is sorted.

11.2-4 Suggest how to allocate and deallocate storage for elements within the hash table itself by linking all unused slots into a free list. Assume that one slot can store a flag and either one element plus a pointer or two pointers. All dictionary and free-list operations should run in O(1) expected time. Does the free list need to be doubly linked, or does a singly linked free list suffice?

11.2-5 Suppose that we are storing a set of n keys into a hash table of size m. Show that if the keys are drawn from a universe U with |U| > nm, then U has a subset of size n consisting of keys that all hash to the same slot, so that the worst-case searching time for hashing with chaining is ѳ(n).

Solution:

Since there are m slots available and the size of Universe(U) > nm The number of keys in Universe per slot > n

=> U > nm

=> U/m > n

Assume that:

Number of keys (n) = 100

Number of slots in hash table (m) = 10

Number of keys in U that hash to 1 slot = U/m = n = 100

From the given information, we know that U/m > n which means that at least n keys hash to the same slot of the table.

Since this implementation is achieved via Chaining, so searching in a list of size n will cost ѳ(n) running time.

11.2-6 Suppose we have stored n keys in a hash table of size m, with collisions resolved by chaining, and that we know the length of each chain, including the length L of the longest chain. Describe a procedure that selects a key uniformly at random from among the keys in the hash table and returns it in expected time O(L.(1+1/α)).