Suppose you insert 125 integer keys into a hash table with an initial capacity o

Question

Suppose you insert 125 integer keys into a hash table with an initial capacity of 25 and load factor threshold of 2.THe hash code is the key itself,and the function key mod table_capacity is used to map a key into a table position.Derive the total units of time that will be used to insert all keys,ONLY counting one unit of time each to do the mapping,insert an entry into a linked list,andd check load factor against threshold.Assume a rehash doubles the table capacity,and the load factor is checked AFTER an entry is mapped and inserted into a chain.

Explanation / Answer

Load factor of hash table is = N / M

N = number of elements in hash table

M = no. of slots in hash table

In this case, M = 25

Problem is to calculate the time units consumed to insert 125 keys if one time unit is consumed each to

And load factor threshold is checked after inserting key into table.

So for 1st 51 keys, each key will consume 3 time units. So total units consumed are 153.

Load factor threshold will exceed 2 after 51st key is inserted so rehashing will happen. Size of new hash table is 50 (doubled as mentioned in problem). Again 51 keys of previous hash table are inserted into new hash table with three steps listed above so again 153 time units will be consumed.

For 52 to 101 keys, 50 * 3 = 150 time units will be consumed.

For 101st key, load threshold will exceed 2 (101/50 > 2) so rehashing will happen.150 time units will be consumed again to move the entries from previous hash table into new hash table.

For 102th – 125th key, 24 * 3 = 72 time units will be consumed.

So total units consumed are = 153 + 153 + 150 + 150 + 72 = 678

Please let me know in case of any doubt.

Thanks

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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