Page 309 - Discrete Mathematics and Its Applications

288 4 / Number Theory and Cryptography

EXAMPLE 1 Find the memory locations assigned by the hashing function h(k) = k mod 111 to the records
of customers with Social Security numbers 064212848 and 037149212.

Solution: The record of the customer with Social Security number 064212848 is assigned to
memory location 14, because

h(064212848) = 064212848 mod 111 = 14.
Similarly, because

h(037149212) = 037149212 mod 111 = 65,

the record of the customer with Social Security number 037149212 is assigned to memory
location 65. ▲
Because a hashing function is not one-to-one (because there are more possible keys than
memorylocations),morethanonefilemaybeassignedtoamemorylocation.Whenthishappens,
we say that a collision occurs. One way to resolve a collision is to assign the first free location
following the occupied memory location assigned by the hashing function.
EXAMPLE 2 After making the assignments of records to memory locations in Example 1, assign a memory
location to the record of the customer with Social Security number 107405723.

Solution: First note that the hashing function h(k) = k mod 111 maps the Social Security
number 107405723 to location 14, because

h(107405723) = 107405723 mod 111 = 14.

However, this location is already occupied (by the file of the customer with Social Security
number 064212848). But, because memory location 15, the first location following memory
location 14, is free, we assign the record of the customer with Social Security number 107405723
to this location. ▲
In Example 1 we used a linear probing function, namely h(k, i) = h(k) + i mod m,to
look for the first free memory location, where i runs from 0 to m − 1. There are many other
ways to resolve collisions that are discussed in the references on hashing functions given at the
end of the book.

Pseudorandom Numbers

Randomly chosen numbers are often needed for computer simulations. Different methods have
been devised for generating numbers that have properties of randomly chosen numbers. Because
numbers generated by systematic methods are not truly random, they are called pseudorandom
numbers.
The most commonly used procedure for generating pseudorandom numbers is the
linear congruential method. We choose four integers: the modulus m, multiplier a,
increment c, and seed x 0 , with 2 ≤ a< m,0 ≤ c< m, and 0 ≤ x 0 <m. We generate a se-
quence of pseudorandom numbers {x n }, with 0 ≤ x n <m for all n, by successively using the
recursively defined function

x n+1 = (ax n + c) mod m.
(This is an example of a recursive definition, discussed in Section 5.3. In that section we will
show that such sequences are well defined.)