Could any one please send solution for followingquestion. 1.) Suppose that the s

Question

Could any one please send solution for followingquestion. 1.) Suppose that the size of hash table is 17, and insert tothe hash table with the key 15, 3, 7, 32, 49, 66. i.) using the quadrtic probing method to show how the indicesfor each of entry. ii.) Instead of using quadratinc probing, using doublehashing, to arrange the entries, you can assume your second hashfunction. Please mention detail step. Please explain every thing. Please send it as soon as possible Thank you Could any one please send solution for followingquestion. 1.) Suppose that the size of hash table is 17, and insert tothe hash table with the key 15, 3, 7, 32, 49, 66. i.) using the quadrtic probing method to show how the indicesfor each of entry. ii.) Instead of using quadratinc probing, using doublehashing, to arrange the entries, you can assume your second hashfunction. Please mention detail step. Please explain every thing. Please send it as soon as possible Thank you

Explanation / Answer

1.) Suppose that the size of hash table is 17, and insert tothe hash table with the key 15, 3, 7, 32, 49, 66. i.) using the quadrtic probing method to show how the indicesfor each of entry.
Let h(k) = k be the hash function
Quadratic probing calculates index to be ( h(k) + i*i) mod M
here M is 17...since size of hash table is 17
1) for 15....
set i=0..the index will be calculated as (15 + 0*0)mod 15 =15
therefore it is stored at index 15

2) for 3...
set i=0;
(3 + 0*0) mod 17 =3...therefore it will be stored at index 3

3) 7 will be stored at (7 + 0*0) mod 17 =7
7 will be stored at index 7

4) (32 +0*0) mod 17 = 15
index 15 is occupied by 15
set i=1....now (32 +1*1)mod 17 = 33 mod 17 = 16
therefore 32 occupies index 16

5) (49 + 0* 0)mod 17 = 15...
now index 15 is occupied by 15
set i=1....now (49 + 1*1)mod 17 = 50 mod 17 = 16
index 16 is occupied by 32
set i=2;
now (49 + 2*2) mod 17 = 53 mod 17 = 2
therefore49 occupies index 2

6) (66 + 0*0) mod 17 = 15
index 15 is occupied by 32
set i=1;
now (66 + 1*1)mod 17 = 16
index 16 is occupied by 49
set i=2;
now (66 + 2*2) mod 17 = 70 mod 17 = 2
index 2 is occupied by 49
set i=3
(66 + 3*3)mod 17 = 74 mod 17 = 4
therefore 66 occupies index 4

Now the has table has
15 at index 15
3 at index 3
7 at index 7
32 at index 16
49 at index 2
66 at index 4



ii.) Instead of using quadratic probing, using double hashing,to arrange the entries, you can assume your second hashfunction.

Assume that the first hash function h(k) = k mod 17
and second hash function to be h2(k)= k mod 10;

now 15 occupied index 15
3 occupied index 3
7 occupies index 7
32 occupies index 2...as in second hash function 32mod10 = 2
49 occupies index 9...as in second hash function 49mod10 = 9
66 occupies index 6...as in second hash function66mod10 = 6

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---