Question about Hash Table : a) (7 points) In the hash table below, two items are

Question

Question about Hash Table:

a) (7 points) In the hash table below, two items are originally hashed to the same slot. The slots examined for inserting one of them are shown by a star and the slots examined for inserting the other are shown by a plus. You can assume that the table size is very big (e.g. more than 1000) and the slots shown did not require a mod (%) operation (that is we did not have to wrap around). 1) What type of open addressing was used? Justify. 2) Give the next slots to be checked for each item (show where the next star and where the next plus wil be Index 12 13 14 17

Explanation / Answer

1) Let us first see the types of open addressing:

a) Linear probing - In this type of open addressing, if the cell to which a number is mapped is found occupied, a number is added to the element and new position is found out.

b) Quadratic probing - In this type of open addressing, we add the square of the number to the element to find out the next position where ir can be kept

c) double hashing - In this type of open addressing, two hash functions are used to find out the next position for the element.

In the given question, first * maps to the 5, second to 9, third to 14 and so on with a gap of 4. There is difference of 4 in the next position of the same element, which is the case of LINEAR PROBING.

Similarly in case of +, first * maps to the 5, second to 8, third to 11 and so on with a gap of 3. There is difference of 3 in the next position of the same element, which is also the case of LINEAR PROBING

2) As we have seen above, linear probing is used, difference value is 4 for * and 3 for +,

So, next slot to be checked for * are 21, 25, 29, 33..... so on

next slot to be checked for + are 17, 20, 23, 26, 29.....so on

3) A bad hash function for the string can be the value of last character of the string.

Since there are limited characters, there are high chances of collision.

Some of the strings that maps to the same cell are:

Queue

are

square

trouble

the list can go on and on and on. .

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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