Performance and Test, Fall 2007: Episode 3.2
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:
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
Solutions to the following problems should be handed in to the course pigeon hole, before Wednesday, Oct 10, 13:30 [expected time 3-5 hours]
Use online sources and your own knowledge about data structures for
dictionaries to write a short report (2-3 pages) characterizing
implementations of dictonaries in Java API. You should analyze
several classes implementing java.util.Map
and java.util.Set interfaces. For each of the classess
try to describe at least the following:
It is fine to hand in this exercise in 2-4 person groups, but more you are more classes you should analyze.
|
|
|
|
Last updated Sep 27, 2007 20:08Peter Tiedemann, Andrzej Wąsowski |