Erik's answers to the 331 Review questions
76.
For the hash function h(k) = k%53, what is the range of hash addresses
keys can be sent to?
The range will be 0 to 52 inclusive.
77.
What do we call it when two non-identical keys are sent to the same
address?
When two keys has to the same address, its a collision
78.
Give two methods for resolving collisions in a hash table and state the
advantages and disadvantages of both?
- Chaining: Each bucket is really a linked list that we attach items
to.
Advantages: deletions made easy. simple implementation. We don't need
as many buckets as words.
Disadvantages: if everything hashes to the same index, we're back to a
O(n) worst case search.
- Probing: From index, we start looking forward for an empty bucket to
put the item in.
Advantages: less code (no need for linked list implementation
Disadcantages: if an item is deleted, any items that were inserted by
probing will not be located. There has to be more buckets that elements in
the table
79.
What's the difference between linear probing and incremental collision
resolution methods?
Linear probing advances one bucket at a time to look for an empty
bucket. Incremental probing advances by more than one item at a time.
80.
Why is it important to choose a uniform hash function?
So that the input is spread out throughout the whole table. This ensures
that the maximum chain length is very close to the ideal average.
81.
The running time of a search in a hash table is mostly dependent on
what measure?
The uniformity of the hashing function. If the hash function tends to
group items together, then the chains will tend to be long, increasing the
number of items to look over.