COMP 251 Study Guide - Midterm Guide: Hash Table, Open Addressing, Linear Probing
19 Nov 2018
School
Department
Course
Professor
Document Summary
Hashing: suppose that you use a hash table and a hash function implementing the division method. The following keys are inserted: 5, 28, 19, 15, 20, 33, 12, 17, 10 and m = 9 (for simplicity, here we do not distinguish a key from its hashcode, so we assume h(key)=key). Solution: the keys 5, 28, 19, 15, 20, 33, 12, 17, 10 map to slots 5, 1, 1, 6, 2, 6, 3, 8, 1. Collisions are shown in bolded fonts: now suppose you use open addressing with linear probing and the same keys as above are inserted. More collisions occur than in the previous question. Solution: the key 19 collides with key 28 at slot 1 and 19 goes into slot 2. Key 20 collides with key 19 at slot 2 and needs to go to slot 3. Key 33 collides with key 15 at slot 6 and needs to go to slot 7.
