Question

1.Consider hashing with a table size of 100 and a hash function of key%tablesize. Insert 25 keys. Do you expect to see any collisions? Why or why not?

Yes, because random values likely will land on same locations.

No becase there are four times as many slots as needed.

2. Secondary clustering means that elements that hash to the same position will probe to the same alternate cells.
Simple hashing uses key%tablesize as the hash function.

Which of the following sequence of insertions would demonstrate secondary clustering of quadratic probing if the tablesize is 100?

1,3,5,7,9

Secondary clustering is unlikely with quadratic probing.

1,2,3,4,5,6

259,359,459,559

0,1,4,9,16,25,36,49

3.Using double hashing (as the Collision Resolution technique), consider inserting multiple copies of the same value Is there clustering?

The table is large enough there is little chance for collision.

Because neighbors are not used for overflow, clustering does not occur.

Each key has a unique step function.

There is clustering. It is impossible to prevent.

4. Consider the following collision resolution scheme: You use linear probing, but always increment by 3 (rather than 1) in the event of a collision.

Which is true of this method?

secondary clustering

non-clustering

primary clustering

Answer 1

1).yes,because random values likely will land on dame locations.

for example suppose two among the 25 keys are 1 and 101

Then 1 % 100 = 1,101%100 = 1

Both will land on same slot so,collision may occur.

2).right option is d).259,359,459,559

Secondary clustering happens with Quadratic probing.it happens when two or more keys directs to same slot in hash table.

259 % 100 = 59

359 % 100 = 59

459 % 100 = 59

559 % 100 = 59

Since,these keys are directed to same slot it causes secondary clustering.

3).Right option is a).The Table is large enough there is little chance for clustering.

Infact double hashing is used to overcome the primary and secondary clustering.it eliminates 99% secondary clustering.1 or 2 keys may cause secondary clustering.

4).Right option is c).Primary clustering

Here,instead of 1 step increment 3 step increments occurs.but the path of slots followed will be still the same when two or more keys are directed to same slot.