Hash Tables
Overview
Hash tables are also data structures that can be used to implement finite sets and mappings. Their worst-case performance is not very good, and their analysis is complicated — but they work extremely well in practice (especially when used to represent a set or mapping that does not change very much) and they can be proved to have very good “expected” performance under certain assumptions.
Two kinds of hash tables — “hash tables with chaining” and “hash tables with open addressing” — will be presented and discussed. A few other kinds of hash tables will be more briefly described.
Lecture #12: Hash Tables — Part One
Required Reading
- Lecture Notes: [ PDF ] [ Video ]
- Supplemental Material: Average-Case Analysis for Hash Tables with Chaining: [ PDF ]
Lecture Presentation
Code Supplied with This Lecture
Hash Functions for Hash Tables with Chaining
- ChainHashFunction.java (Interface): [ Source ] [ Documentation ]
- SimpleChainHashFunction.java (Implementation): [ Source ] [ Documentation ]
A Hash Table with Chaining
- ChainHashTable.java: [ Source ] [ Documentation ]
Implementation of a Set Using a Hash Table with Chaining
- ChainHashSet.java: [ Source ] [ Documentation ]
- TestChainHashSet.java (Code for Testing): [ Source ]
Implementation of a Mapping Using a Hash Table with Chaining
- ChainHashMap.java: [ Source ] [ Documentation ]
- TestChainHashMap.java (Code for Testing): [ Source ]
Reading Exercise #3: Hash Functions
Lecture #13: Hash Tables — Part Two
Required Reading
- Lecture Notes: [ PDF ] [ Video ]
- Supplemental Material: Average-Case Analysis of Hashing with Open Addressing: [ PDF ]
Lecture Presentation
Code Supplied with This Lecture
Hash Functions for Hash Tables with Open Addressing
- OpenHashFunction.java (Interface): [ Source ] [ Documentation ]
- OpenHashFunctionDouble.java (Implementation): [ Source ] [ Documentation ]
Implementation of a Hash Table with Open Addressing
- KeyValuePair.java (Class Providing a Key-Value Pair): [ Source ] [ Documentation ]
- TableFullException.java (Exception to Report that a Table is Full): [ Source ] [ Documentation ]
- OpenHashTableDouble.java (Hash Table Implementation): [ Source ] [ Documentation ]
- TestOpenHashTableDouble.java (Code for Testing): [ Source ]
Reading Exercise #4: Randomization and Hashing
Tutorial #12: Hash Tables
Test Results
- testChainResults.txt (Test Results for Hash Tables with Chaining)
- testOpenResults.txt (Test Results for Hash Tables with Open Addressing)
Code To Be Completed
- NewOpenHashTableDouble.java (Expandable Hash Table wiht Open Addressing): [ Source ] [ Documentation ]
Implementation of a Set (Use After Completing the Above)
- OpenHashSet.java (Implementation): [ Source ] [ Documentation ]
- TestOpenHashSet.java (Code for Testing): [ Source ]
Implementation of a Mapping (Use After Completing the Above
- OpenHashMap.java (Implementation): [ Source ] [ Documentation ]
- TestOpenHashMap.java (Code for Testing): [ Source ]
