Performance and Test, Spring 2007

Lecture Friday, February 16, 10-12pm, Room 2A14

Subject : Hashing.

Text : RS 14.0, 14.1, 14.2, 14.5, this note, pages 1—5 of this article [30pp, 4h].

Some of the following exercises will be discussed at the exercise session (Sep 21):

Discuss with your group partner what is the advantage of cuckoo hashing over hashing with chaining? (hint: summarize complexities of operations and compare them)
Professor Marley hypothesizes that substantial performance gains can be obtained if we modify the chaining scheme so that each list is kept in sorted order. How does professor's modification affect the running time for successful searches, unsuccessful searches, insertions, and deletions? [CLRS 11.2-3]
Let m be the size of a hash table. Show that if |U| > nm, there is asubset of U 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 linear. [CLRS 11.2-5 p. 229]
Suppose we wish to search a linked list of length n, where each element contains a key k along with a hash value h(k). Each key is a long character string. How might we take advantage of the hash values when searching the list for an element with a given key? [CLRS 11.3-1 p. 236]
RS 14.42, 14.43, p. 629