3. [4] For our running hash table, you\'11 need to decide if you need to rehash.

Question

3. [4] For our running hash table, you'11 need to decide if you need to rehash. You just inserted a new item into the table, bringing your data count up to 53491 entries. The table's vector is currently sized at 106963 buckets. Calculate the load factor (A): Given a linear probing collision function should we rehash? Why? * Given a separate chaining collision function should we rehash? Why? 4. [4] What is the Big-o of these actions for a well designed and properly loaded hash table with N elements? Big-o complexity Function Insert(x) Rehash() Remove(x) Contains(x)

Explanation / Answer

3

a) load factor is 53491/106963 = 0.5, as load factor is 0.5 we need to do rehash

rehashing is techqniue to avoid collision and is done when load factor becomes greater than equal to 0.5, irrespective of collision resolution strategy

4)

insert O(1)

contains O(1)

remove O( 1)

rehash() O(n)

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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