Take quiz & check grades
Collision with open addressing:
 | No pointers, no lists | ||||||
| Saves the memory otherwise used by pointers. | ||||||
| Once a collision occurs, you probe the table for an empty slot. Consider using different
permutations in the order you visit the table.
| ||||||
| Very difficult to remove entries from this kind of table, you may have to mark: DELETED |
Analysis:
Function of the load factor alfa < 1 .. since n/m must be <1
Theorem 12.5
number of probes in an unsuccessful search is at most 1 / (1-alfa)
Theorem 12.7
expected number of probes in a successful search is at most:
(1/alfa) ln ( 1 / (1-alfa)) + 1 / alfa