Suppose that each entry in a hash table occupies 16 bytes of storage (exclusive

Question

Suppose that each entry in a hash table occupies 16 bytes of storage (exclusive of the pointer member needed if chaining is used), where we take 4 bytes as the amount of space needed for a pointer. Also suppose that there are 100 occupied entries in the hash table, and the hash table has a total of 1000 possible positions (1000 is the same as hash_size), including occupied and empty positions.

(a) If open addressing is used, determine how many bytes of storage will be required for the hash table. (10 pts)

(b) If chaining is used, what is the total storage requirement in bytes (including the 100 records/entries) for chaining? (10 pts)

Explanation / Answer

Ans1 number of keys<=size in open addressing so memory required is 16000 bytes
Ans2 In chaining we also have pointer to avoid collision so size is >=16400 bytes

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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