Hash Tables (part 2): Resolving Collisions
This is the second part of a two-part series on hash tables. In this part we discuss how to resolve collisions:
0:00 Chaining
3:33 Analysis of Chaining
9:19 Open Addressing
13:30 Dictionary operations
19:33 Linear probing
21:22 Quadratic probing
22:47 Double hashing
25:38 Analysis of open addressing
27:25 Proof for unsuccessful search
32:32 Implementation of dict in Python
Note: In the last quiz (31:52) I am assuming a constant load factor.
Notebook with exercises:
https://github.com/kbuchin/algonotebo...
solutions: https://github.com/kbuchin/algonotebo...