12
CHAPTER 1. DATA MINING
or ﬁelds on which the index is based form the hash-key for a hash function.
We apply the hash function applied to value of the hash-key for each record,
and the record itself is placed in the bucket whose number is determined by the
hash function. The bucket could be a list of records in main-memory, or a disk
block, for example.
Then, given a hash-key value, we can hash it, ﬁnd the bucket, and need to
search only that bucket to ﬁnd the records with that value for the hash-key. If
we choose the number of buckets B to be comparable to the number of records
in the ﬁle, then there will be relatively few records in any bucket, and we will
ﬁnd few, if any, records in the bucket with a hash key that is not the one we are
looking for. Thus, the search for the desired records is quite eﬃcient, compared
with searching the entire ﬁle for records with the desired hash key.
−1
B
17
0
h (800−555−1212)
Records with h(phone) = 17
Array of
bucket
headers
.
.
.
.
.
.
Sally Jones   Maple St   800−555−1212
Figure 1.2: A hash table used as an index; phone numbers are hashed to buckets,
and the entire record is placed in the bucket whose number is the hash value of
the phone
Example 1.6 : Figure 1.2 suggests what a main-memory index of records with
name, address, and phone ﬁelds might look like. Here, the index is on the phone
ﬁeld, and buckets are linked lists. We show the phone 800-555-1212 hashed to
bucket number 17. There is an array of bucket headers, whose ith element is
the head of a linked list for the bucket numbered i. We show, in expanded
form, one of the elements of the linked list. It contains a record with name,
address, and phone ﬁelds. This record is in fact one with the phone number
800-555-1212. Other records in that bucket may or may not have this phone
number. We only know that whatever phone number they have is a phone that
hashes to 17.
✷
