1.
Using the hash table performance formulas given in the chapter, compute the average number of comparisons necessary when the table is
At what point do you think the hash table is too small? Explain.
Section 6.8 Maps and Sets via Hash Tables: Exercises
Exercises Exercises
2.
Modify the hash function for strings to use positional weightings.
3.
We used a hash function for strings that weighted the characters by position. Devise an alternative weighting scheme. What are the biases that exist with these functions?
4.
Research perfect hash functions. Using a list of names (classmates, family members, etc.), generate the hash values using the perfect hash algorithm
5.
Implement the
size method for the hash table Map ADT implementation.
6.
Implement the
containsKey method for the hash table Map ADT implementation.
7.
How can you delete items from a hash table that uses chaining for collision resolution? How about if open addressing is used? What are the special circumstances that must be handled? Implement the
removeKey method for the HashTableMap class.
8.
In the hash table map implementation, the hash table size was chosen to be 101. If the table gets full, this needs to be increased. Re-implement the
put method so that the table will automatically resize itself when the loading factor reaches a predetermined value (you can decide the value based on your assessment of load versus performance).
9.
Implement quadratic probing as a rehash technique.
You have attempted of activities on this page.
