Final answer:
To find '90, Michael' in the hash table using h(key) = key mod 3, we check slot 0, which requires 4 operations as there are 4 names to check and 'Michael' is not there. The worst case for hash tables occurs when all keys collide into the same slot, leading to O(n) complexity, which happens if the hash function isn't chosen properly.
Step-by-step explanation:
To build the hash table with hash function h(key) = key mod m where m=3, we insert each entity as follows:
- h(213) = 213 mod 3 = 0 → Insert 'John' in slot 0
- h(122) = 122 mod 3 = 2 → Insert 'Mark' in slot 2
- h(345) = 345 mod 3 = 0 → Insert 'Jane' following 'John'
- h(234) = 234 mod 3 = 0 → Insert 'Steph' following 'Jane'
- h(340) = 340 mod 3 = 1 → Insert 'Hong' in slot 1
- h(423) = 423 mod 3 = 0 → Insert 'Linda' following 'Steph'
- h(143) = 143 mod 3 = 2 → Insert 'Mary' following 'Mark'
- h(467) = 467 mod 3 = 2 → Insert 'Tonia' following 'Mary'
- h(388) = 388 mod 3 = 1 → Insert 'Jim' following 'Hong'
- h(229) = 229 mod 3 = 2 → Insert 'Hey' following 'Tonia'
To find the entity 90, Michael, we compute h(90) = 90 mod 3 = 0. You would check the entries in slot 0 of the hash table. Since 'Michael' is not in the list of names associated with slot 0, you conclude that the entity is not in the table. This would require checking each entry in slot 0, which results in 4 operations in this case.The worst case scenario for hash tables is when all entities hash to the same slot, which is known as collision. This results in a performance degradation from O(1) to O(n) as every insert operation requires traversing the list of entries in the slot, and each lookup might need to go through all the elements if the key is not present or is the last one. An example of such a case is when using a hash function that returns the same value for all keys or if the keys themselves have some uniformity that causes them to hash to the same value under a specific hash function.