To improve the speed of operations, we may wish to replace an open hash table wi

Question

To improve the speed of operations, we may wish to replace an open hash table with B1 buckets holding many more than B1 elements by another hash table with B2 buckets. Write a procedure to construct the new hash table from the old, using the list ADT operations to process each bucket. In Section 4.8 we discussed ''random'' hash functions, where hi(x), the bucket to be tried after i collisions, is (h (x) + di) mod B for some sequence d1, d2,. .. ,dB-1. We also suggested that one way to compute a suitable sequence d1 , d2,. .. , dB-1 was to pick a constant k, an arbitrary d1 > 0, and let where i > 1, B is a power of 2, and stands for the bitwise modulo 2 sum. If B = 16, find those values of k for which the sequence d1, d2,. . . , d15 includes all the integers 1, 2, . . ., 15.

Explanation / Answer

4.10)

Ans:

We can do this by dynamic hashing.

In this whenever a collision occurs lets say in Bucket number i , Then the data is stored in that Bucket only using linked list concept.

The new data is inserted in the current Linked list present in the bucket by simply Linked list insertion of a structure node q after node p method.

i.e.

Nodeptr *q; // new node to be added;

char data;

p-> next = q;

q-> info = data;

q -> next = NULL;

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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