08-01-2013, 04:50 PM
Hash Tables
Hash Tables.ppt (Size: 330 KB / Downloads: 68)
Recall the Map ADT
Map ADT methods:
get(k): if the map M has an entry with key k, return its assoiciated value; else, return null
put(k, v): insert entry (k, v) into the map M; if key k is not already in M, then return null; else, return old value associated with k
remove(k): if the map M has an entry with key k, remove it from M and return its associated value; else, return null
size(), isEmpty()
keys(): return an iterator of the keys in M
values(): return an iterator of the values in M
Example
We design a hash table for a map storing entries as (SSN, Name), where SSN (social security number) is a nine-digit positive integer
Our hash table uses an array of size N = 10,000 and the hash functionh(x) = last four digits of x
Hash Functions
A hash function is usually specified as the composition of two functions
The hash code is applied first, and the compression function is applied next on the result, i.e.,
Memory address:
We reinterpret the memory address of the key object as an integer.
Default hash code of all Java objects.
Doesn’t work for numeric and string keys.
Also bad if objects can move!