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:

Hash tables¶

Hashtables¶

Question 1

How is a key used in a hash table?

The default status of a hash table is that it is locked, in other words no records in the hash table can be accessed. With a key, we can unlock the hash table.

A hash table is essentially just an array, where each location (or index) stores a record. A key is just a pompous synonym for a vector index.

Typically a hash table contains several keys, each of which is repeated. Hence there are two locations in the hash table containing the same key. To use the hash table we must search for the two locations containing the same key.

A unique key is associated with each record that is stored somewhere in the hash table. Using the key we can find the location of the record and hence access the contents of the record.

Question 2

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?

Each bucket has associated with it a data structure, typically a linked list. The keys \(k1\) and \(k2\) and their accompanying records will be both stored somewhere in this data structure.

When key \(k2\) and its accompanying record are to be stored, an entirely new empty hash table is created in which only key \(k2\) is stored. Key \(k1\) remains stored in the old hash table.

The hash-function used in open-hashing will repeatedly change key \(k2\) to a new value until it finds an empty bucket. It then stores the new \(k2\) and its record and returns the new \(k2\) to the user.

Since the bucket to which \(k2\) points will not be empty, a search is conducted in the hash table for an empty bucket in which \(k2\) can be stored.

Question 3

Each bucket has associated with it a data structure, typically a linked list. The keys \(k1\) and \(k2\) and their accompanying records will be both stored somewhere in this data structure.

When key \(k2\) and its accompanying record are to be stored, an entirely new empty hash table is created in which key \(k2\) is stored.

The hash-function used in closed hashing will repeatedly change key \(k2\) to a new value until it finds an empty bucket. It then stores the new \(k2\) and its record and returns the new \(k2\) to the user.

Since the bucket to which \(k2\) points will not be empty, a search is conducted in the hash table for an empty bucket in which \(k2\) and its accompanying record can be stored.

Question 4

Which of the following are properties of a good hash function? (More than 1 property may be correct.)

It maps the keys uniformly amongst all the buckets.

It provides exactly two different bucket candidates for each key

It uses all data provided in a key.

It always maps all keys having the same length to the same bucket.

It always results in at least one bucket being empty.

It can be computed quickly, hence it should have a constant (\(O(1)\)) runtime efficiency.

Question 5

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?

When the keys we want to use are all of the std:string type.

When the number of buckets we wish to use is odd.

When the keys we want to use are all of some struct type, which we we have defined ourselves.

When we are sure that rehashing will have to be done at some point.

Question 6

Rehashing is necessary when …

at least half of the buckets are empty.

the load factor becomes larger than some acceptable limit.

the key sizes become too large.

at least one bucket starts leaking

Question 7

Suppose we are using a hash table with open-hashing. What is the load factor of such a hash table?

the number of records being stored divided by the total number of buckets available

the total number of buckets available divided by the number of records being stored

the largest number of records stored in any one bucket

the number of empty buckets divided by the total number of buckets available

Question 8

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?

The bucket to which the hash function maps key \(k\) is empty.

All the keys currently stored in the hash table have been mapped to the same bucket and the hash function also maps \(k\) to this same bucket.

We have to search all the buckets in the hash table to find where the hash function has been stored.

There are no keys currently stored in the hash table and hence we have to go through all the buckets to confirm they are all empty.

Question 9

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?

how frequently rehashing must be done and the runtime efficiency of the hash function

the average time for performing one search operation and the average time for performing one delete operation

the total amount of memory needed for the buckets and the average time for performing one search or delete operation

how much new memory is needed when rehashing and how frequently rehashing must be done

Question 10

Which of the following statements is the most accurate regarding the runtime efficiency of one search operation in a hash table?

When the hash function effectively distributes the keys uniformly amongst the buckets, the search operation has a big-O efficiency that is constant.

Regardless of how well the hash function distributes the keys amongst the buckets, the search operation has a has a big-O efficiency that is constant.

When the hash function effectively distributes the keys uniformly amongst the buckets, the search operation has an amortized big-O efficiency that is constant.

Regardless of how well the hash function distributes the keys amongst the buckets, the search operation has a big-O efficiency efficiency that is linear in the number of buckets.

Extra links on the topic:

Week12 - Glossary

Course week 12¶

Self-study¶

Hash tables¶

Hashtables¶

Submit weekly exercises¶