Hash Tables
Search = O(1)
![](hash.gif)
![](hash_address.gif)
SSN or UM-D barcode
10^9 vs 10^4
used needed
Library Example
- 1000 books
- 100 students (75% actually visit the library)
Collision Resolution
![](chaining_pic.gif)
O(N) can result if we are not careful
![](hash_formulas.gif)
Quadratic Probing
key + IČ
I = 0, 1, 2, 3, 4, ...
IČ = 0, 1, 4, 9, 16, ...
![](hash_functions2.gif)
Heuristic Rule for Table Sizes = 4 * J + 1
Return to CIS 350 Index Page