Date: Mon, 26 Nov 2001 23:03:19 -0600 (CST) From: Mark Jacobson To: 810-080-01@uni.edu, 810-080-02@uni.edu Subject: hash table review exercise... Hi 080 students, The hash function is h(x) = x mod 17 The codomain of the function h is: {0, 1, 2, 3, ..., 15, 16} The data to be stored in the hash table is: 23, then 14, then 52, then 40, then 24, then 18, followed by 33, 58 and finally 50 gets stored. The collision resolution method is linear probe, as shown in class. Treat the hash table as a circular array, with location 16 being followed by location 0. 1. Draw the hash table with the stored data items. 2. Calculate the average successful search performance value. 3. Calculate the average unsuccessful search number of probes. 4. Describe the search for item 58 and how it proceeds, probe by probe. 5. What is the cardinality of the range of the function h? Do this exercise before Wednesday's class. If you want to read more about hash tables, see pages 649-650 of the textbook, Example 14.14 material only one those two pages. Also see http://www.cns.uni.edu/~jacobson/hashingOct2000.txt which is easily linked from http://www.cns.uni.edu/~jacobson and http://www.cns.uni.edu/~jacobson/c080.html The http://www.cns.uni.edu/~jacobson/hashingOct2000.txt material is also good review and preview for the Friday Nov 30th hands-on class. Mark