If you are using simple chaining to handle collisions, and there are 4 buckets in your hash table
computer science
Description
Question 1
a) If
you are using simple chaining to handle collisions, and there are 4 buckets in
your hash table, what happens when inserting the following key values
[17,9,37,29,69,1649,2405,89,265,165,789].
How does this show problems with the
chaining approach?
b) If
you switch to using linear probing collision resolution and a larger number of
buckets i.e. 16 buckets, where each contains one value, what will the resulting
structure look like for the same key values from part a?
Will this improve search performance for those
values when compared to the chaining approach?
Tip
for Question 1:
You
should provide a hash function. The hash functions in these
cases can be simplified to using k% Number_of_buckets,
where % is the modulus/remainder operator, to split the input key
values among the buckets. (This is the same approach as is used in the
example in the slides this week for both chaining and linear
probing).
Sketch
out the resulting data structure with the key values inserted into the
appropriate buckets.
Question 2
a)
Linear hashing is one approach to hashing values to a dynamically
changing file. Briefly outline this approach and
illustrate the approach using the following record key values
[5,56,13,41,18,20,11,23,43,57,94].
Note: You
may assume that each block can contain two records, that the initial file
contains two blocks (M = 2), and that splits will occur whenever an insert
causes an insert into an overflow bucket.
b)
Change your approach to instead split when, after inserting, the load factor
> 0.75. Will this result in the same hash table? Illustrate your answer.
(load factor = number of all keys currently in table / number of (regular
non-overflow) buckets currently in table*max items per bucket)
Question 3
a)
What is the "Birthday paradox/Birthday problem"
and how is it relevant to hash tables?
b)
What is a "Random Oracle"
and why is it not a hashing algorithm?
