1.3. THINGS USEFUL TO KNOW
11
preferred that we choose B to be a prime. That choice reduces the chance of
nonrandom behavior, although we still have to consider the possibility that all
hash-keys have B as a factor. Of course there are many other types of hash
functions not based on modular arithmetic. We shall not try to summarize
the options here, but some sources of information will be mentioned in the
bibliographic notes.
What if hash-keys are not integers? In a sense, all data types have values
that are composed of bits, and sequences of bits can always be interpreted as in-
tegers. However, there are some simple rules that enable us to convert common
types to integers. For example, if hash-keys are strings, convert each character
to its ASCII or Unicode equivalent, which can be interpreted as a small inte-
ger. Sum the integers before dividing by B. As long as B is smaller than the
typical sum of character codes for the population of strings, the distribution
into buckets will be relatively uniform. If B is larger, then we can partition the
characters of a string into groups of several characters each. Treat the concate-
nation of the codes for the characters of a group as a single integer. Sum the
integers associated with all the groups of a string, and divide by B as before.
For instance, if B is around a billion, or 230, then grouping characters four at
a time will give us 32-bit integers. The sum of several of these will distribute
fairly evenly into a billion buckets.
For more complex data types, we can extend the idea used for converting
strings to integers, recursively.
• For a type that is a record, each of whose components has its own type,
recursively convert the value of each component to an integer, using the
algorithm appropriate for the type of that component. Sum the integers
for the components, and convert the integer sum to buckets by dividing
by B.
• For a type that is an array, set, or bag of elements of some one type,
convert the values of the elements’ type to integers, sum the integers, and
divide by B.
1.3.3
Indexes
An index is a data structure that makes it eﬃcient to retrieve objects given the
value of one or more elements of those objects. The most common situation
is one where the objects are records, and the index is on one of the ﬁelds of
that record. Given a value v for that ﬁeld, the index lets us retrieve all the
records with value v in that ﬁeld, without having to retrieve all the records in
the ﬁle. For example, we could have a ﬁle of (name, address, phone) triples,
and an index on the phone ﬁeld. Given a phone number, the index allows us
to ﬁnd quickly the record or records with that phone number.
There are many ways to implement indexes, and we shall not attempt to
survey the matter here. The bibliographic notes give suggestions for further
reading. However, a hash table is one simple way to build an index. The ﬁeld
