CSC2100B Tutorial 6

CSC2100BTutorial 6 HashingTom Chao ZhouYi LIUMar 4, 2004{zzz{zzHashing - overviewHash functionCollision resolutionSeparate Chaining (Open hashing)Open addressing (Closed Hashing)Linear probingQuadratic probingDouble hashingCSC2100B Tutorial 2z{Hashing - hash functionHash functionA mapping function that maps a key to a number in the range 0 to TableSize -1int hashfunc(int integer_key){return integer_key % HASHTABLESIZE;}CSC2100B Tutorial 3zHashing - separate chainingIf two keys map to same value, the elements are chained together.CSC2100B Tutorial 4zzHashing - exampleInsert the following four keys 22 84 35 62 into hash table of size 10 using separate chaining. The hash function is key % 10Initial hash tableCSC2100B Tutorial 5zzHashing - exampleInsert the following four keys 22 84 35 62 into hash table of size 10 using separate chaining. The hash function is key % 1022 % 10 = 2After insert 22CSC2100B Tutorial 6zzHashing - exampleInsert the following four keys 22 84 35 62 into hash table of size 10 using separate chaining. The hash function is key % 1084 % 10 = 4After insert 84CSC2100B Tutorial 7zzHashing - exampleInsert the following four keys 22 84 35 62 into hash table of size 10 using separate chaining. The hash function is key % 1035 % 10 = 5After insert 35CSC2100B Tutorial 8zzHashing - exampleInsert the following four keys 22 84 35 62 into hash table of size 10 using separate chaining. The ...