s
Section 5.6 The Mighty Mod Function
425
where t is some relatively small positive integer. If the domain S consists of text
strings, we can imagine them encoded in some way into integer values, perhaps
by an algorithm as simple as converting each individual letter of a text string into
its position in the alphabet (a = 1, b = 2, and so on) and adding up the resulting
list of integers to get one integer value. Therefore we can assume that S consists of
integer values to begin with.
The function h therefore maps a potentially large set of integer values S into
a relatively small window of integer values T. Consequently h isn’t likely to be a
one-to-one function because there may be many values x 1 , x 2 , x 3 , … from S such
that h(x 1 ) = h(x 2 ) = h(x 3 ), in which case we say that x 1 , x 2 , and x 3 all “hashed” to
the same value. The term “hash function” came about because the domain value
x is often chopped up into pieces in the process of computing h(x). Whatever the
function h(x) does to x, the last step is almost always to apply the mod t function
so the final value of h(x) falls in the codomain 50, 1, … , t − 16.
example 49
S is a set of positive integers, T is the set of integers 50, … , t − 16 and the hash
function h(x) is given by
h(x) = x mod t
If t = 10, for example, then values are computed modulo 10:
h(7) = 7 mod 10 = 7
h(23) = 23 mod 10 = 3
h(59) = 59 mod 10 = 9
h(158) = 158 mod 10 = 8
h(48) = 48 mod 10 = 8
Here 158 and 48 hash to the same value.
A hash function is often used as part of a search algorithm. We have already
discussed two search algorithms. In sequential search, n elements are stored in an
unordered (random) list and a given target value is compared one-by-one with the
list elements. In binary search, n elements are stored in a sorted list. The given
target value is compared with the midpoint of the list, the midpoint of half the list,
and so on. In a search using a hash function, n elements are stored in an array (a
one-dimensional table) called a hash table, where the array is indexed from 0
through t − 1; the table is of size t. The element x is passed as the argument to
the hash function and the resulting h(x) value gives the array index at which the
element is then stored. Later, when a search is carried out, the target value is run
through the same hash function, giving an index location in the hash table, which
is where to look for the matching stored element.
However, because the hash function is not one-to-one, things are not quite
that simple. As the search list is loaded into the hash table, different values may
hash to the same array index, producing a collision. There are several collision
resolution algorithms available. One is called linear probing—just keep going in
Section 5.6 The Mighty Mod Function
425
where t is some relatively small positive integer. If the domain S consists of text
strings, we can imagine them encoded in some way into integer values, perhaps
by an algorithm as simple as converting each individual letter of a text string into
its position in the alphabet (a = 1, b = 2, and so on) and adding up the resulting
list of integers to get one integer value. Therefore we can assume that S consists of
integer values to begin with.
The function h therefore maps a potentially large set of integer values S into
a relatively small window of integer values T. Consequently h isn’t likely to be a
one-to-one function because there may be many values x 1 , x 2 , x 3 , … from S such
that h(x 1 ) = h(x 2 ) = h(x 3 ), in which case we say that x 1 , x 2 , and x 3 all “hashed” to
the same value. The term “hash function” came about because the domain value
x is often chopped up into pieces in the process of computing h(x). Whatever the
function h(x) does to x, the last step is almost always to apply the mod t function
so the final value of h(x) falls in the codomain 50, 1, … , t − 16.
example 49
S is a set of positive integers, T is the set of integers 50, … , t − 16 and the hash
function h(x) is given by
h(x) = x mod t
If t = 10, for example, then values are computed modulo 10:
h(7) = 7 mod 10 = 7
h(23) = 23 mod 10 = 3
h(59) = 59 mod 10 = 9
h(158) = 158 mod 10 = 8
h(48) = 48 mod 10 = 8
Here 158 and 48 hash to the same value.
A hash function is often used as part of a search algorithm. We have already
discussed two search algorithms. In sequential search, n elements are stored in an
unordered (random) list and a given target value is compared one-by-one with the
list elements. In binary search, n elements are stored in a sorted list. The given
target value is compared with the midpoint of the list, the midpoint of half the list,
and so on. In a search using a hash function, n elements are stored in an array (a
one-dimensional table) called a hash table, where the array is indexed from 0
through t − 1; the table is of size t. The element x is passed as the argument to
the hash function and the resulting h(x) value gives the array index at which the
element is then stored. Later, when a search is carried out, the target value is run
through the same hash function, giving an index location in the hash table, which
is where to look for the matching stored element.
However, because the hash function is not one-to-one, things are not quite
that simple. As the search list is loaded into the hash table, different values may
hash to the same array index, producing a collision. There are several collision
resolution algorithms available. One is called linear probing—just keep going in