236 CHAPTER 4 Functions
storage location 18. Carry out this hashing procedure for Smith, Jones, Brown, Zento, and
Ruster.Solution.Steps 1 through 3 Step 4 Hash ValueSmith -- 19.2+ 13.22+9.23+20.24+8.25=738 =11.63+45-- 45
Jones • 10.2+15.22+14.23+5.24+19.25=880 =13.63+61-- 61
Brown-2- 22 + 18.2^2 + 15.2^3 + 23.2^4 + 14.2^5 = 1012 =16.63+4 --+ 4
Zento --+26.2+5-22+14-23+20-24+15.25 =984 =15.63+39-* 39
Ruster- 18.2+21.22+ 19.23+20.24+5.25 + 18.26 = 1904=30.63+ 14-- 14Each of these names can be located among a set of 63 storage locations, numbered 0, 1,
2 ... , 62, by using their hash value as the location to access. 0If any two names give rise to the same hash value, then an auxiliary rule, called a
collision resolution strategy, is used to make sure that each piece of information has its
own storage location that can be determined from the information alone and the given
collision resolution strategy.
How many students in your class can have their names hashed this way without gen-
erating a collision? (If your class has more than 63 students, simply change the function to
find the remainder when you divide by some number at least as large as the size of your
class.)Application: Encryption and Decryption
In this age of electronic messaging, it is often important that only the intended receiver
of an electronic message can read it. If the security of a transmission is a problem, the
message can still be made secure if the original message has been encoded or encrypted
so that the symbols seen make no sense unless you know how to decrypt the message, that
is, return the encrypted message back to its original form. Here, we present an example of
the process of encoding and decoding a message. The method used is very simple and not
as powerful or secure as modern methods, but the example points out how an encryption
scheme interacts with a message, a user, and a receiver. The difficult problem today is
to find an encoding scheme that cannot be compromised through a brute force search by
a computer. More complex ideas from number theory lie at the heart of the best current
encryption methods. The encoding scheme presented uses a bijection from the symbol set
used in writing the message to the same symbol set. The sender of the message must use
the bijection to transform the message into a form that is not recognizable, and the receiver
must use the inverse of the coding function to decrypt the message received to return it into
plain text.
A very simple encoding scheme is to associate each letter of the alphabet (we
will only deal with uppercase letters) with two digits as follows: A -- 00, B
01, C ->. 02 ... ,X --+ 23, Y -+ 24, and Z --* 25. Define a function F(lettervalue) -
a(lettervalue) + b (mod 26), where a and b are integers and a has no factor in common