Course week 12

Self-study

The topic for this week is Hash tables.

The following links will take you to the video-lectures and the accompanying slides:

Hashtables

How is a key used in a hash table?
Suppose in a hash table we want to store two keys \(k1\) and \(k2\) and their accompanying records. Assume \(k1\) is stored before \(k2\). If \(k1\) and \(k2\) point to the same bucket, how is this situation handled in open hashing?
Suppose in a hash table we want to store two keys \(k1\) and \(k2\) and their accompanying records. Assume \(k1\) is stored before \(k2\). If \(k1\) and \(k2\) point to the same bucket, how is this handled in closed hashing?
Which of the following are properties of a good hash function? (More than 1 property may be correct.)
Suppose we are using the std:unordered_map container from STL. For which of the following situations will it be necessary for us to provide our own hash function?
Rehashing is necessary when …
Suppose we are using a hash table with open-hashing. What is the load factor of such a hash table?
Suppose we are using a hash table with open-hashing. Suppose we want to search for key \(k\) in the hash table. From an runtime efficiency viewpoint, what is the worst possible situation for this search operation?
Suppose we are using a hash table with open-hashing and that our hash function does a good job at uniformly distributing the keys amongst the buckets. To determine when rehashing is done, an upper limit on the load factor must be set. The value of this upper limit is a compromise between what two things?
Which of the following statements is the most accurate regarding the runtime efficiency of one search operation in a hash table?
What is a central question, related to this course, whose answer can be found in this week’s videos?
Of the following topics, which do you think deserves further discussion/explanation during the weekly consultation session?
Were there any parts of the video lectures that were particularly difficult? Particularly interesting? Something about which you wish to learn more?

Extra links on the topic:

Week12 - Glossary

Submit weekly exercises

Questions to be submitted this week