s
Section 5.6 The Mighty Mod Function
427
Two goals should be kept in mind in designing a hash function:
1. Given an argument value x, h(x) can be computed quickly.
2. The number of collisions will be reduced because h(x) does a good job of
distributing values throughout the hash table.
Use of a modulo function as the hash function accomplishes the first goal. The
second goal is harder to achieve because data can always be found that produce a
large number of collisions, but distribution seems to work better on the average if
the table size (the modulo value) is a prime number.
The average number of comparisons required to search for an element using hashing depends not on the total number n of elements in the hash table, but
rather on the ratio of n to the total table size t. If this ratio is low, then (using linear
probing) there are lots of empty slots, so you won’t have to look very far to find
a place to insert a new element into the table or, correspondingly, to search for a
target element that is in the hash table. Similarly, if this ratio is low and chaining
is used, the average length of any linked list you may have to (sequentially) search
for a target element should be short. This ratio n/t is called the load factor of the
hash table. In sequential search or binary search, more elements in the set to be
searched increases the work (number of comparisons) required. But using hashing, more elements can be searched just as efficiently as fewer provided the hash
table size grows accordingly so that the load factor stays low.
computer Security
Computer security (or the more general term information assurance) is a topic
of critical interest when our economy, defense, and indeed our entire way of life
depend so much on computers and information. The mod function plays a part in
many aspects of security.
Cryptography
Children often delight in sending “secret messages” using some encoding/
decoding scheme that they know and that (they believe) their parents don’t know!
■
PRaCtiCe 44 Show the resulting hash tables if 28 is the next value stored in the hash tables of Figure
5.29(a) and (b).
example 51
Voting records for the citizens of a certain precinct are stored in a hash table of
size 197 using the voter’s Social Security number as a key value (the value that is
hashed). Using a hash function modulo the hash table size, the index to search first
for data on a voter with Social Security number
328356770
is
328356770 mod 197 = 125
Section 5.6 The Mighty Mod Function
427
Two goals should be kept in mind in designing a hash function:
1. Given an argument value x, h(x) can be computed quickly.
2. The number of collisions will be reduced because h(x) does a good job of
distributing values throughout the hash table.
Use of a modulo function as the hash function accomplishes the first goal. The
second goal is harder to achieve because data can always be found that produce a
large number of collisions, but distribution seems to work better on the average if
the table size (the modulo value) is a prime number.
The average number of comparisons required to search for an element using hashing depends not on the total number n of elements in the hash table, but
rather on the ratio of n to the total table size t. If this ratio is low, then (using linear
probing) there are lots of empty slots, so you won’t have to look very far to find
a place to insert a new element into the table or, correspondingly, to search for a
target element that is in the hash table. Similarly, if this ratio is low and chaining
is used, the average length of any linked list you may have to (sequentially) search
for a target element should be short. This ratio n/t is called the load factor of the
hash table. In sequential search or binary search, more elements in the set to be
searched increases the work (number of comparisons) required. But using hashing, more elements can be searched just as efficiently as fewer provided the hash
table size grows accordingly so that the load factor stays low.
computer Security
Computer security (or the more general term information assurance) is a topic
of critical interest when our economy, defense, and indeed our entire way of life
depend so much on computers and information. The mod function plays a part in
many aspects of security.
Cryptography
Children often delight in sending “secret messages” using some encoding/
decoding scheme that they know and that (they believe) their parents don’t know!
■
PRaCtiCe 44 Show the resulting hash tables if 28 is the next value stored in the hash tables of Figure
5.29(a) and (b).
example 51
Voting records for the citizens of a certain precinct are stored in a hash table of
size 197 using the voter’s Social Security number as a key value (the value that is
hashed). Using a hash function modulo the hash table size, the index to search first
for data on a voter with Social Security number
328356770
is
328356770 mod 197 = 125