home page - news - syllabus - schedule - assignments - tutorials - tests - java - references - Mike Jacobson |
Tutorial 1 - Tutorial 2 - Tutorial 3 - Tutorial 4 - Tutorial 5 - Tutorial 6 - Tutorial 7 - Tutorial 8 - Tutorial 9 - Tutorial 10 - Tutorial 11 - Tutorial 12 - Tutorial 13 - Tutorial 14 - Tutorial 15 - Tutorial 16 - Tutorial 17 - Tutorial 18 - Tutorial 19 - Tutorial 20 - Tutorial 21 - Tutorial 22 - Tutorial 23 |
Hash Tables |
The objectives of this exercise are
Students should read through and try to solve the problems on this exercise before attending the tutorial.
This exercise is based on material presented during the lectures on hash tables. It is expected that students have attended these lectures or carefully reviewed the notes for these classes that are now available online.
The exercise also makes use of material in the lecture supplement on hash functions and additional hashing strategies Students should review this supplemental material before spending time on this exercise as well.
It is to be expected that all of the questions in this first section can be answered by any student who has successfully completed the prerequisites for this course, attended the lectures in which hash tables ere discussed (reviewing the lecture notes, as needed, too), and completed the assigned reading mentioned above.
Students who do have difficulty with these questions, after completing the above, should contact the course instructor to get extra help.
Give a brief description of each of the following.
Suppose that you inserted the following values into a hash table of size m=59 (using “the division method”):
473, 418, 356, 312, 119, 237, 605, 307
You should assume that the “universe” U is the set of integers between 0 and 999 and that the hash table is empty before 473 is inserted into it.
Show the hash tables that would result from this sequence of insertions when each of the following kinds of hash tables are used.
When using double hashing, please use
h0(x) = x mod 59
as suggested above, and use
h1(x) = (x mod 58) + 1.
Consider the following hash table (with size m=8).
Confirm that this table could be produced from an empty table by inserting the keys
25, 2, 12, 14, 22
using the hash function
h(k, i) = k+i mod 8.
Draw the tables produced and mention the results you would obtain if the following sequence of operations was performed, starting with the table given above and using the above hash function.
Describe how the algorithm to insert a key into a hash table with open addressing could be modified in order to allow deleted to be overwritten with the key you wish to insert.
What could go wrong if you simply replaced the first copy of deleted with the key to be inserted, as soon as one such copy was found?
The worst-case performance of an operation on any of the (reasonably simple) kinds of hash tables, that have been described in lectures, is significantly worse than the worst-case performance of the corresponding operation on a balanced binary search tree. Yet, there are situations in which hash tables are considered to be preferable. Why?
Describe three (necessary or) desirable properties that hash functions should have.
Describe the hashCode method that is provided by every Object in Java.
Notice that this should not be used, all by itself, as the “hash function” that maps values to locations in a hash table. Why is that? Why is this function useful (when implementing hash tables) anyway?
Last updated:
http://www.cpsc.ucalgary.ca/~jacobs/Courses/cpsc331/W12/tutorials/tutorial13.html |