More ADT
- java.util.Hashtable
- "To successfully store and retrieve objects from a hashtable, the objects used as keys must implement the hashCode method and the equals method."
- in Java, every Object has a method, called hashCode()
- what is hashing?
- let's search your homepage using your student ID
- Students' Home Pages
- it takes, on average, (1 + 336)/2 comparisons to find a particular student
- even if we sort the students' ID and use binary search, it still requires (1 + log2336)/2 comparisons
- is it possible to improve the performance
- hash table
- with a good hashing function, each key address can be stored in a unique location
- allow very fast (constant time) insertion and retrieval
- Search Key -> Hash Function -> Hashtable Index
- Computing Hash Functions
- Using the Search Key as the Index (50123456)
- Selecting Digits (6)
- Folding (5+0+1+2+3+4+5+6 or 50 + 12 + 34 +56)
- let's use a very simple hashing function h(id) = id%10
| 50385364
| 50386926
| 50390478
| 50390940
| 50390337
| 50382165
| 50418049
| 50394152
|
|
|
\/
id%10
|
|
\/
- what if a location have already been occupied by another key
- we have a collision
- either we have a perfect hashing function which guarentees that no collision will occur
- or rehashing is required
- Examples
JavaHashDemo1 (demo with no collision resolution)
JavaHashDemo2 (demo with very naive collision resolution; does not always work!)
which make use of the Person class:
Person