数据结构-哈希表.ppt

Chapter 10Hashing
ADT of Dictionary
const int DefaultSize = 26;
template<class Name, Attribute>class Dictionary{
public:
Dictionary ( int size = DefaultSize );
int IsIn ( Name name );
Attribute *Find ( Name name );
void Insert ( Name name, Attribute attr );
void Remove ( Name name );
}
Hash table
Support the following operations
Find
Insert
Delete. (deletions may be unnecessary in some applications)
Unlike binary search tree, AVL tree and B+-tree, the following functions cannot be done:
Minimum and maximum
Successor and predecessor
Report data within a given range
List out the data in order
Unrealistic solution
Each position (slot) corresponds to a key in the universe of keys
T[k] corresponds to an element with key k
If the set contains no element with key k, then T[k]=NULL
Unrealistic solution
insert, delete and find all take O(1) (worst-case) time
Problem:
The scheme wastes too much space if the universe is too large compared with the actual number of elements to be stored.
. student IDs are 8-digit integers, so the universe size is 108, but we only have about 4000 students in Software College.
Hashing
Usually, m << N.
h(Ki) = an integer in [0, …, m-1]
called the hash value of Ki
Example applications
Compilers use hash tables (symbol table) to keep track of declared variables.
On-line spell checkers. After prehashing the entire dictionary, one can check each word in constant time and print out the misspelled word in order of their appearance in the document.
Useful in applications when the input keys come in sorted order. This is a bad case for binary search tree. AVL tree and B+-tree are harder to implement and they are not necessarily more efficient.
Hashing
With hashing, an element of key k is stored in T[h(k)]
Hashing
h: hash function
maps the universe U of keys into the slots of a hash table T[0,1,...,m-1]
an element of key k hashes to slot h(k)
h(k) is the hash value of key k