CMPT 225 Lecture Notes - Hash Table, Open Addressing, Double Hashing

• School: Simon Fraser University
• Department: Computing Science
• Course: CMPT 225
• Professor: John Edgar

Document Summary

Occurs when 2 different keys are mapped to the same index. When insertion results in collision, look for somewhere else to put the value. Start at index to which hash function mapped the inserted item. Look for free space in array following a search patten (probing) Each time probed for free location, add one to index. Just look for next empty space in array. Table contains groups of consecutively occupied locations, clusters get larger as time goes on, reduces efficiency. Search for 59, 59 mod 23 = 13, index 13 does not contain 59, but it contains something else. Cannot yet conclude that table does not contain 59. Cannot conclude until you get to a free space. Probe, check, add one to index, continue until hit 59 or free space. Don"t just add one to index, add p^2. p is number of times you"ve had to do this probing.