2. Eight numbers come in the sequence as: 22, 33, 18, 88, 77, 61, 36, 82, and th

Question

2. Eight numbers come in the sequence as: 22, 33, 18, 88, 77, 61, 36, 82, and the hash
function is defined as: HashValue = number % (size of the table).
If the numbers are stored in linear hashing with the array defined as H[15], and the
rehash function for collision resolution being: (HashValue+1) % (size of the table), draw
the hash table. To search a number in the table, how many comparisons will be made
on average? Except 1, what numbers can also be used for rehash function to solve
collisions.
3. Using C++, define a hash table of 60 numbers using class, insert 30 random
numbers within [0, 99], then interact with user to search 10 numbers and count the
total and average comparison times.

Explanation / Answer

answer to question 2

0 ->

1 -> 61

2 ->77

3 ->33

4 ->18

5 ->

6->36

7 ->22

8 ->82

9->

10->

11->

12->

13->88

14->

on avg search takes 1 comparisons and in worst case it takes 15 comparisons

for collision resolution we are using (HashValue+step) % (size of the table)

here step = 1..............but in quadratic probing step size is c1xi^2+c2xi.............

and in double hashing step size is variable wcich is deter mined by another hash function

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.