Module 0109: Basic hash tables
Tak Auyeung, Ph.D.
December 6, 2006
1
About this module
2
Θ(1) look up time!
3
Hash function
4
Basic hash table
4.1
Creation/Initialization
4.2
Insert
4.3
Remove
4.4
Lookup
5
Primitive hash table in action
6
A better hash function
6.1
Shift-add
6.2
Multiply by a large prime number
6.3
The perfect hash function
6.4
Conclusion?
7
Collision resolution
7.1
Chaining
7.2
Open addressing
7.2.1
Lookup
7.2.2
Insertion
7.2.3
Deletion
[
next
]