CHAPTER 8

HASHING

8.1 THE SYMBOL TABLE ABSTRACT DATA TYPE

We have all used a dictionary, and many of us have a word processor equipped with a
limited dictionary, that is, a spelling checker. In this chapter, we consider the dictionary,
as an ADT. Examples of dictionaries are found in many applications, including the spel­
ling checker, the thesaurus, the data dictionary found in database management applica­
tions, and the symbol tables generated by loaders, assemblers, and compilers.
In computer science, we generally use the term symbol table rather than diction­
ary, when referring to the ADT. Viewed from this perspective, we define the symbol
table as a set of name-attribute pairs. The characteristics of the name and attribute vary
according to the application. For example, in a thesaurus, the name is a word, and the
attribute is a list of synonyms for the word; in a symbol table for a compiler, the name is
an identifier, and the attributes might include an initial value and a list of lines that use
the identifier.
Generally we would want to perform the following operations on any symbol
table:

(1) determine if a particular name is in the table

(2) retrieve the attributes of that name
(3) modify the attributes of that name
(4) insert a new name and its attributes

395
396 Hashing

(5) delete a name and its attributes.

Structure 8.1 provides the complete specification of the symbol table ADT.

structure SymbolTable(SymTab) is
objects: a set of name-attribute pairs, where the names are unique.
functions:
for all name e Name, attr e Attribute, symtab g SymbolTable, max-size g integer.
SymTab QxQ3XQ{max-size} create the empty symbol table
whose maximum capacity is max-size.
Boolean lsln(symtab, name) if (name is in symtab)
return TRUE
else return FALSE.
Attribute Find(symtab, name) if {name is in symtab)
return the corresponding attribute
else return null attribute.
SymTab XnsQXt^symtab, name, attr) if (name is in symtab)
replace its existing attribute with attr
else insert the pair {name, attr)
into symtab.
SymTab TioiQtQ^symtab, name) if {name is not in symtab)
return
else delete {name, attr) from symtab.

Structure 8.1: Abstract data type SymbolTable

Although Structure 8.1 lists several operations, there are only three basic opera­
tions on symbol tables: searching, inserting, and deleting. Therefore, when choosing a
symbol table representation, we must make sure that we can implement these operations
efficiently. For example, we could use the binary search tree introduced in Section 5.7
to represent a symbol table. If our search tree contained n identifiers, the worst case
complexity for these operations would be 0{n). In Chapter 10 we introduce several
refinements of binary search tree that reduce the time per operation to O(log n). In this
chapter we examine a technique for search, insert, and delete operations that has very
good expected performance. The technique is referred to as hashing. Unlike search tree
methods which rely on identifier comparisons to perform a search, hashing relies on a
formula called the hash function. We divide our discussion of hashing into two parts:
static hashing and dynamic hashing.
 Static Hashing 397

8.2 STATIC HASHING

8.2.1 Hash Tables

In static hashing, we store the identifiers in a fixed size table called a hash table. We use
an arithmetic function, /, to determine the address, or location, of an identifier, x, in the
table. Thus,/(x) gives the hash, or home address, of x in the table. The hash table ht is
stored in sequential memory locations that are partitioned into b buckets,
/2r[0],... , ht [b - 1]. Each bucket has 5 slots. Usually 5 = 1, which means that each
bucket holds exactly one record. We use the hash function f(x) to transform the
identifier x into an address in the hash table. Thus, / (x) maps the set of possible
identifiers onto the integers 0 through b - 1. If we limit the length of identifiers to six
characters, where the first character must be a letter and the remaining characters can be
a letter or a decimal digit, then there are T = ^26 x 36' > 1.6 x 10^ distinct possible
(=0
values for x. However, any reasonable application would never have this many
identifiers. We use T, as well as b and 5, to determine the identifier and loading density
of a hash table. Later we will use these statistics to estimate the efficiency of hashing
operations.

Definition: The identifier density of a hash table is the ratio n/T, where n is the number
of identifiers in the table. The loading density or loading factor of a hash table is a =
n/{sb). □

Since the number of buckets b in a hash table is usually several orders of magni­
tude lower than the total number of possible identifiers T, the hash function / must map
several different identifiers into the same bucket. Two identifiers, i\ and i^, are
synonyms with respect to/if/(/i) =/(/2)- enter distinct synonyms into the same
bucket as long as the bucket has slots available. An overflow occurs when we hash a
new identifier, /, into a full bucket. A collision occurs when we hash two nonidentical
identifiers into the same bucket. When the bucket size is 1, collisions and overflows
occur simultaneously.

Example 8.1: Consider the hash table ht with b = 26 buckets and 5 = 2. We have n = 10
distinct identifiers, each representing a C library function. This table has a loading fac­
tor, a, of 10/52 = 0.19. The hash function must map each of the possible identifiers onto
one of the numbers, 0-25. We can construct a fairly simple hash function by associating
the letters, a ~z, with the numbers, 0-25, respectively, and then defining the hash func­
tion, /U), as the first character of x. Using this scheme, the library functions acos,
define, float, exp, char, atan, ceil, floor, clock, and ctime hash into buckets 0, 3, 5, 4, 2,
0, 2, 5, 2, and 2, respectively. Figure 8.1 shows the first 8 identifiers entered into the
hash table.
398 Hashing

SlotO Slot 1
0 acos atan
T
2 char ceil
3 define
4 exp
5 float floor
6

25

Figure 8.1: Hash table with 26 buckets and two slots per bucket

The identifiers acos and atan are synonyms, as are float and floor, and ceil and
char. The next identifier, clock, hashes into the bucket Since this bucket is full,
we have an overflow. Where in the table should we place clock so that we may retrieve it
when necessary? We consider various solutions to the overflow problem in Sections
8.2.3. and 8.2.4 □
Assume, for a moment, that no overflows occur. Then the time required to enter,
delete, or search for identifiers using hashing depends only on the time required to com­
pute the hash function and to search one bucket. Since the bucket size is usually small,
we may use a sequential search to look for an identifier within a bucket. Hence, the time
required to enter, delete, or search for identifiers does not depend on the number of
identifiers n in use; it is 0(1).
Our choice of a hash function in Example 8.1 is not well suited for most applica­
tions since a large number of collisions and overflows is likely. For example, we have
already seen that many C functions begin with the same letter; the same is true of vari­
able names. Ideally, we would like to choose a hash function that is both easy to com­
pute and produces few collisions. Unfortunately, since the ratio h/T is usually small, we
cannot avoid collisions altogether.

8.2.2 Hashing Functions

A hash function, f, transforms an identifier, x, into a bucket address in the hash table. As
mentioned above, we want a hash function that is easy to compute and that minimizes
the number of collisions. Although the hash function we used in Example 8.1 was easy
to compute, using only the first character in an identifier is bound to have disastrous
consequences. We know that identifiers, whether they represent variable names in a
 Static Hashing 399

program, words in a dictionary, or names in a telephone book, cluster around certain

letters of the alphabet. To avoid collisions, the hash function should depend on all the
characters in an identifier. It also should be unbiased. That is, if we randomly choose an
identifier, x, from the identifier space (the universe of all possible identifiers), the proba­
bility that f (x) = i is \/b for all buckets i. This means that a random x has an equal
chance of hashing into any of the b buckets. We call a hash function that satisfies this
property a uniform hash function.
There are several types of uniform hash functions, and we shall describe four of
them. We assume that the identifiers have been suitably transformed into a numerical
equivalent. (Later we will describe a simple transformation.)

Mid-square

The middle of square hash function is frequently used in symbol table applications. We
compute the function by squaring the identifier and then using an appropriate number
of bits from the middle of the square to obtain the bucket address. (We assume that the
identifier fits into one computer word.) Since the middle bits of the square usually
depend upon all the characters in an identifier, there is a high probability that different
identifiers will produce different hash addresses, even when some of the characters are
the same. The number of bits used to obtain the bucket address depends on the table size.
If we use r bits, the range of the values is 2''. Therefore, the size of the hash table should
be a power of 2 when we use this scheme.

Division

We obtain a second simple hash function by using the modulus (%) operator. In this
scheme, we divide the identifier x by some number M and use the remainder as the hash
address for x. The hash function is:

%M

This gives bucket addresses that range from 0 to M - 1, where M = the table size. The
choice of M is critical. Recall that when we use the middle of square function f„, the
table size should be a power of 2. In the division function, if M is a power of 2, then
/pfx) depends only on the least significant bits of x. Such a choice for M results in a
biased use of the hash table when several of the identifiers in use have the same suffix. If
M is divisible by 2, then odd keys are mapped to odd buckets, and even keys are mapped
to even buckets. Hence, an even M results in a biased use of the table when a majority of
identifiers are even or when a majority are odd.
Let X = X\X2 and Y = two identifiers each consisting of the characters x,
and X2. If the internal binary representation of xj has value C(X|) and that forx2 has
value C(x2) ^hen if each character is represented by six bits, the numeric value of X is
2^C(X]) + C(x2) while that for Y is 2^C(x2) + C(xi). If p is a prime number dividing
400 Hashing

M then

(/d(x) - A(y)) % p = (26 c (X,) % p + c (X2) % p

- 2^C (X2) % p - C {x 1)% p) % p

If p = 3, then

(/d(X) -foaft %P = (64 % 3 e(xi) % 3 -F C(%2) % 3

- 64 % 3 C(X2) %3- C(xi) % 3) % 3
= C(;ri) % 3 C(X2) C(_X2) %3- C(%i) % 3
= 0%3

i.e., permutations of the same set of characters are hashed at a distance a factor of 3
apart. So, when many identifiers are permutations of each other, a biased use of the table
results. This happens because 64 % 3 = 1. The same behavior can be expected when 7
divides M as 64 % 7 = 1.
These difficulties can be avoided by choosing M as a prime number. Then, the
only factors of M are M and 1. Knuth has shown that w’hen M divides r^ ± a where k and
a are small numbers and r is the radix of the character set (in the above example r = 64),
then X % M tends to be a simple superposition of the characters in X. Thus, a good
choice for M would be: M a prime number such that M does not divide ± a for small k
and a. Experience indicates that, in practice, it is sufficient to choose M such that it has
no prime divisors less than 20.

Folding

In this method, we partition the identifier x into several parts. All parts, except for the
last one have the same length. We then add the parts together to obtain the hash address
for X. There are two ways of carrying out this addition. In the first method, we shift all
parts except for the last one, so that the least significant bit of each part lines up with the
corresponding bit of the last part. We then add the parts together to obtain f (x). This
method is known as shift folding. For example, suppose that we have divided the
identifiers into the following parts; xj = 123, x^ - 203, S3 = 241, S4 = 112, and S5 = 20.
Using shift folding, we would align si through S4 with S5 and add. This gives us a hash
address of 699.
The second method, known as folding at the boundaries, reverses every other par­
tition before adding. For example, suppose the identifiers is divided into the same parti­
tions as in shift folding. Using the folding at the boundaries method, we would reverse
the second and fourth partitions, that is, S2 = 302 and S4 - 211, and add the partitions.
This gives us a hash address of 897.
 Static Hashing 401

Digit Analysis

The last method we will examine, digit analysis, is used with static files. A static file is
one in which all the identifiers are known in advance. Using this method, we first
transform the identifiers into numbers using some radix, r. We then examine the digits of
each identifier, deleting those digits that have the most skewed distributions. We con­
tinue deleting digits until the number of remaining digits is small enough to give an
address in the range of the hash table. The digits used to calculate the hash address must
be the same for all identifiers and must not have abnormally high peaks or valleys (the
standard deviation must be small).
In Section 8.2.4, we compare the various methods used to generate a hash address.
Of these methods, the one most suitable for general purpose applications is the division
method with a divisor, A/, such that M has no prime factors less than 20.

8.2.3 Overflow Handling

Linear Open Addressing

There are two methods for detecting collisions and overflows in a static hash table; each
method using a different data structure to represent the hash table. In this section we dis­
cuss the simplest method, referred to as linear open addressing or linear probing, and in
the next section we introduce chaining.
When we use linear open addressing, the hash table is represented as a one­
dimensional array with indices that range from 0 to the desired table size - 1. The com­
ponent type of the array is a struct that contains at least a key field. Since the keys are
usually words, we use a string to denote them. The C declarations creating the hash
table ht with one slot per bucket are:

#define MAX-CHAR 10 *
/
max number of characters in
an identifier
/
*
#define TABLE-SIZE 13 /
* max table size-prime number */
typedef struct {
char key[MAX—CHAR];
*
/ other fields */
} element;
element hash-table[TABLE-SIZE] ;

Before inserting any elements into this table, we must initialize the table to
represent the situation where all slots are empty. This allows us to detect overflows and
collisions when we insert elements into the table. The obvious choice for an empty slot
is the empty string since it will never be a valid key in any application, init-table (Pro­
gram 8.1) shows the initialization function.
402 Hashing

void init—table(element ht[])

{
int i;
for (i 0; i TABLE—SIZE; i++)
ht[i].key[0] = NULL;
}

Program 8.1: Initialization of a hash table

To insert a new element into the hash table we convert the key field into a natural
number, and then apply one of the hash functions discussed in Section 8.2.2. We can
transform a key into a number if we convert each character into a number and then add
these numbers together. (Apparently this is one of the most popular transformation tech­
niques, despite the fact that it does not produce a uniform hash function.) The function
transform (Program 8.2) uses this simplistic approach. (The exercises examine other
alternatives.) To find the hash adddress of the transformed key, hash (Program 8.2) uses
the division method.

int transform(char *
key)
{
*
/ simple additive approach to create a natural number
that is within the integer range
int number - 0;
while key)
*
(
number += *key++;
return number;
}

int hash(char *
key)
{
*
/ transform key to a natural number, and return this
result modulus the table size */
Q,
return(transform(key) 'O TABLE-SIZE);
}

Program 8.2: Creation of a hash function

We are now ready to insert elements into the hash table. If the slot at the hash
address is empty, we simply place the new element into this slot. However, if the new
element is hashed into a full bucket, we must find another bucket for it. The simplest
solution places the new element in the closest unfilled bucket. We refer to this method
 Static Hashing 403

of resolving overflows as linear probing or linear open addressing. Let us illustrate this
technique on a 13-bucket table with one slot per bucket. As our data we will use the
words for, do, while, if, else, and function. Figure 8.2 shows the hash value for each
word using the simplified scheme discussed above. Inserting the first five words into the
table poses no problem since they have different hash addresses. However, the last
identifier, function, hashes to the same bucket as if. Using a circular rotation, the next
available bucket is at ht [0], which is where we place function (Figure 8.3).

Identifier Additive X Hash

Transformation
for 102+111 + 114 327 2
do 100 + 111 211 3
while 119 + 104 + 105 + 108 + 101 537 4
if 105 + 102 207 12
else 101 + 108 + 115 + 101 425 9
function 102 + 117 + 110 + 99 + 116 + 105 + 111 + 110 870 12

Figure 8.2 : Additive transformation

[0] function
[1]
[2] for
[3] do
[4] while
[5]
[6]
[7]
18]
19] else
[10]
111]
112] if

Figure 8.3 : Hash table with linear probing (13 buckets, 1 slot/bucket)

To implement the linear probing strategy, we first compute /(x) for identifier x
and then examine the hash table buckets + j}%TABLE-SlZE\.
0 <7 < TABLE-SIZE in this order. Four outcomes can result from the examination of a
404 Hashing

hash table bucket:

(1) The bucket contains x. In this case, x is already in the table. Depending on the
application, we may either simply report a duplicate identifier, or we may update
information in the other fields of the element.
(2) The bucket contains the empty string. In this case, the bucket is empty, and we
may insert the new element into it.
(3) The bucket contains a nonempty string other than x. In this case we proceed to
examine the next bucket.
(4) We return to the home bucket ht [f (r)] (j = TABLE-SIZE}. In this case, the home
bucket is being examined for the second time and all remaining buckets have been
examined. The table is full and we report an error condition and exit.

The insertion strategy just discussed is implemented in linear-insert (Program 8.3).

void linear—insert{element item, element ht[])

{
*
/ insert the key into the table using the linear probing
technique, exit the function if the table is full */
int i, hash—value;
hash—value = hash{[Link]);
i = hash—value;
while (strlen(ht[i].key)) {
if (!strcmp{ht[i].key, [Link])) {
fprintf(stderr,"Duplicate entry\n");
exit{1);
}
i -- (i + 1)
(i+1) g,
•o TABLE—SIZE;
%
if {i == hash—value) {
fprintf(stderr,"The table is full\n");
exit{1);
}
}
ht [i] Item;
}

Program 8.3: Linear insert into a hash table

Our earlier example shows that when we use linear probing to resolve overflows,
identifiers tend to cluster together. In addition, adjacent clusters tend to coalesce, thus
increasing the search time. For example, suppose we enter the C built-in functions acos,
atoi, char, define, exp, ceil, cos, float, atol, floor, and ctime into a 26-bucket hash table
 Static Hashing 405

in that order. For illustrative purposes, we assume that the hash function uses the first
character in each function name. Figure 8.4 shows the bucket number, the identifier con­
tained in the bucket, and the number of comparisons required to insert the identifier.
Notice that before we can insert atol, we must examine ht [0], . . . Jit [8], a total of nine
comparisons. This is far worse than the worst case behavior of the search trees we will
study in Chapter 10. If we retrieved each of the identifiers in ht exactly once, the aver­
age number of buckets examined would be 35/11 =3.18 per identifier. Analyses of the
linear probing method show that the expected average number of identifier comparisons,
p, required to look up an identifier is approximately (2 - a)/(2 - 2a) where a is the load­
ing density. In the above example, a = 11/26 = .42 and p = 1.36. This indicates that the
average number of probes for a loading density of .42 is 1.36. Thus, although we know
that the average number of probes is small, the worst case can be large.

bucket X buckets searched

0 acos 1
1 atoi 2
2 char T
3 define T
4 exp T
5 ceil 4
6 cos 5
7 float 3
8 atol 9
9 floor 5
io ctime 9

25

Figure 8.4 : Hash table with linear probing (26 buckets, 1 slot per bucket)

We have just seen that linear open addressing creates clusters of identifiers. These
clusters tend to merge as we enter more identifiers into the table, thus leading to bigger
clusters. We can partially curtail the growth of these clusters and hence reduce the aver­
age number of probes by using quadratic probing. Whereas, linear probing searches
buckets (f (x) + i)% h, 0 < i < h - where b is the number of buckets in the table, in
quadratic probing we use a quadratic function of i as the increment. In particular, we
carry out the search by examining buckets / (x), (/“(x) 4- r) % Z?, and {J (x) - z ) % b for
!</<(/?- l)/2. When b is a prime number of the form 4/ -I- 3, where j is an integer, the
quadratic search described above examines every bucket in the table. (We refer the
406 Hashing

reader interested in the proof to the Radke article cited in the References and Selected
Readings section.) Figure 8.5 lists some primes of the form 47 + 3.

Prime 2 Prime J
3 0 43 10
7 1 59 14
11 2 127 31
19 4 251 62
23 5 503 125
31 7 1019 254

Figure 8.5 : Some primes of the form +3

We also can reduce the clustering that occurs with linear probing by applying a
series of hash functions/|,/2 5 ^fb- This method is known as rehashing. We examine
buckets TKx), !</</?. A third approach for handling bucket overflow, random probing,
is explored in the exercises.

Chaining

Linear probing and its variations perform poorly because inserting an identifier requires
the comparison of identifiers with different hash values. For example, in the hash table
of Figure 8.4, before we could insert atol we had to examine buckets ht [0] to ht [8], even
though only the first two identifiers collided with atol; the remainder could not possibly
be in the same bucket as atol. We could have eliminated most of these comparisons if
we had maintained a list of synonyms for each bucket. To insert a new element we
would only have to compute the hash address f (x) and examine the identifiers in the list
for/(x). Since we would not know the sizes of the lists in advance, we should maintain
them as linked chains. We now require additional space for a link field. Since we will
have M lists, where M is the desired table size, we employ a head node for each chain.
These head nodes only need a link field, so they are smaller than the other nodes. We
maintain the head nodes in ascending order, 0, • • • , A/ - 1 so that we may access the
lists at random. The C declarations required to create the chained hash table are:

#define MAX-CHAR 10 //
* maximum identifier size
/
*
ttdefine TABLE-SIZE 13 *
/ prime number */
#define IS-EULL(ptr) (!(ptr))
 Static Hashing 407

typedef struct {
char key[MAX—CHAR] ;
*
/ other fields /
*
} element;

★
typedef struct list list—pointer;
typedef struct list {
element item;
list—pointer link;
} ;
list—pointer hash—table[TABLE—SIZE];

The function chain-insert (Program 8.4) implements the chaining strategy. The
function first computes the hash address for the identifier. It then examines the
identifiers in the list for the selected bucket. If the identifier is found, we print an error
message and exit. If the identifier is not in the list, we insert it at the end of the list. If
the list was empty, we change the head node to point to the new entry.
Figure 8.6 shows the chained hash table corresponding to the linear table found in
Figure 8.4. The number of probes needed to search for any of the identifiers is now one
each for acos, char, define, exp and float; two each for atoi, ceil, and float; three each
for atol and cos; and four for ctime. The average number of comparisons is now 21/11 =
1.91. The expected number of identifier comparisons for a chained table is 1 + a/2,
where a is the loading density n/b (b = number of headnodes). For a = 0.42, the
expected number of probes is 1.21; for a = 1, it is about 1.5.
The results of this section and the last suggest that the performance of a hash table
depends only on the method used to handle overflows, that is, chaining or linear probing.
As long as a uniform hash function is used, the performance is independent of the hash
function. Although this is true if we randomly select identifiers from the identifier space,
it is not true in practice. In practice, our choice of identifiers is biased since we fre­
quently use identifiers that have a common suffix or prefix or are simple permutations of
other identifiers. Thus, in practice we would expect the choice of a hash function to
affect hash table performance. The table of Figure 8.7 presents the results of an empiri­
cal study conducted by Lum, Yuen, and Dodd. The values in each column give the aver­
age number of bucket accesses made in searching eight different tables with 33,575,
24,050, 4909, 3072, 2241, 930, 762, and 500 identifiers each. As expected, chaining per­
forms better than linear open addressing. Examining the performance of the various
hash functions, we can see that division is generally superior. Therefore, for a general
application, this is the preferred method. The divisor should be a prime number,
although it is sufficient to choose a divisor that has no prime factors less than 20. Notice
that the table also gives the theoretical expected number of bucket accesses based on
random keys.
408 Hashing

void chain—insert(element item, list—pointer ht[])

{
/■^ insert the key into the table using chaining
int hash—value = hash([Link]);
list—pointer ptr,trail-KULL,lead-hc[hash —value];
for (; lead; trail = lead, lead = lead->link)
if (!strcmp(lead->[Link],[Link])) {
fprintf(stderr, "The key is in the tableXn");
exit(1);
}
}
ptr (list—pointer)malloc(sizeof(list));
if (IS-FULL(ptr)) {
fprintf(stderr, "The memory is full\n");
exit(1);
}
ptr->item i t em ;
ptr—>link NULL;
if (trail)
trail->link = ptr;
else
ht[hash—value] = ptr;
}

Program 8.4: Chain insert into a hash table

[0] -> acos -> atoi -> atol

[1] -> NULL
[2] -> char -> ceil -> cos -> ctime
[3] -> define
[4] -> exp
[5] -> float -> floor
[6] -> NULL

[25] -> NULL

Figure 8.6: Hash chains corresponding to Figure 8.4

 Static Hashing 409

a= .50 .75 .90 .95

b
Hash Function Chain Open Chain Open Chain Open Chain Open

mid square 1.26 1.73 1.40 9.75 1.45 37.14 1.47 37.53
division 1,19 4.52 1.31 7.20 1.38 22,42 1.41 25.79
shift fold 1.33 21.75 1.48 65.10 1.40 77,01 1.51 118.57
bound fold 1.39 22.97 1.57 48.70 1.55 69,63 1.51 97.56
digit analysis 1.35 4.55 1.49 30.62 1.52 89.20 1.52 125.59
theoretical 1.25 1.50 1.37 2.50 1.45 5.50 1.48 10.50

(Adapted from V. Lum, P. Yuen, and M. Dodd, CACM, 1971, Vol. 14, No. 4)

Figure 8.7: Average number of bucket accesses per identifier retrieved.

8.2.4 Theoretical Evaluation of Overflow Techniques

The experimental evaluation of hashing techniques indicates that they generally perform
better than conventional techniques, such as binary search trees. However, the worst
case performance for hashing can be very bad. In the worst case, an insertion in a hash
table with n identifiers may take O(/i) time. In this section, we present a probabilistic
analysis for the expected performance of the chaining method and state, without proof,
the results of similar analyses for the other overflow handling methods. First, we formal­
ize what we mean by expected performance.
Let ht [ b ] be a hash table with b buckets, each bucket having one slot. Let / be a
uniform hash function with range fO, b - 1 ]. If we enter n identifiers x j, x^, • • • , into
the hash table, then there are b^ distinct hash sequences /(X|), f {x£}, • • • , /(x^).
Assume that each of these is equally likely to occur. Let denote the expected number
of identifier comparisons needed to locate a randomly chosen x,-, !</<«. Then, is
the average number of comparisons needed to find the yth key Xy, averaged over
1 < j < n, with each j equally likely and averaged over all hash sequences, assuming
each of these also to be equally likely. Let (/„ be the expected number of identifier
comparisons when a search is made for an identifier not in the hash table. This hash
table contains n identifiers. The quantity may be defined in a manner analogous to
that used for

Theorem 8.1 Let a = n/h be the loading density of a hash table using a uniform hash
function/. Then:

(1) for linear open addressing:

410 Hashing

1 ]
1+
2 (1-a) 2

i 1
Sn 1+
2 1-a

(2) for rehashing, random probing, and quadratic probing:

1/(1-a)

1
Sn - — loge(l-a)
a

(3) for chaining:

Un = a

= 1 + Qf/1

Proof: Exact derivations of Un and are fairly involved and can be found in Knuth’s
book The Art of Computer Programming: Sorting and Searching. Here, we present a
derivation of the approximate formulas for chaining. First, assume that we wish to insert
the identifier x, where f (x) = i and chain i has k nodes, excluding the headnode. If x is
not on the chain, k comparisons are made. If x is j nodes away from the head node,
1 < j < k, j comparisons are made. When the n identifiers distribute uniformly over the b
possible chains, the expected number in each chain is n/b = a. Since Un = expected
number of identifiers on a chain, [/„ = a. When we enter the /th identifier X/ into the
table, the expected number of identifiers on any chain is (/ - 1)//?. Hence, the expected
number of comparisons needed to insert X/ after all n identifiers have been entered is
1 + a - lyfc. (This assumes that new entries are added to the end of the chain.) There­
fore:

n n- 1 a
Sn = ^{{ + (i-iyb} = i +
n i=\ 2b 2

EXERCISES

1. Why does transform (Program 8.2) produce a biased hash function? What
transformation would you suggest?
 Static Hashing 411

2. Create a C function linear-search that returns -1 if an identifier, x, is not in the

hash table, and the bucket address of x if x is in the table.
3. Write a C function that deletes identifier x from a hash table that uses hash func­
tion /and linear open addressing to resolve collisions. Show that simply setting
the slot previously occupied by x to an empty string does not solve the problem.
How must you modify linear-search so that a correct search is made in the situa­
tion when deletions are permitted? Where can a new identifier be inserted?
4. (a) Show that if quadratic searching is carried out in the sequence (/(x) + q^\
(/(x)-I-(^ - 1/), , (/(x) + 1), /(x), (f(x)- 1), , (/(x)-<?2) with
q = {b - l)/2 then the address difference mod b between successive buckets being
examined is:

b — 2, b — 4, b — 6, • • •,5, 3, 1, 1, 3, 5, ,b — 6, b — b—2

(b) Write an algorithm to insert the identifier x into a hash table contain b buck­
ets. Use quadratic hashing to resolve overflows.
5. [Morris 1968] In random probing, the search for an identifier, x, in a hash table
with b buckets is carried out by examining buckets /(x), (/{x)-i-5(0) % b,
1 <i < Z?-l, where 5(0 is a pseudorandom number. The random number generator
must generate every number from 1 to b - 1 exactly once.
(a) Show that for a table of size 2'", the following sequence of computations
generates numbers with this property:

Initialize R to 1 each time the search routine is called.

On successive calls for a random number do the following:
R=R^ 5
R -.= low order r + 2 bits of R
S{i') — R/^
(b) Write an algorithm, incorporating the above random number generator, to
insert an identifier into a hash table using random probing and the middle of
square hash function
It can be shown that for this method, the expected value for the average number of
comparisons needed to search for x is -(1 /ex)Iog( 1 - a) where a is the loading fac­
tor.
6. Write an algorithm to list all the identifiers in a hash table in lexicographic order.
Assume the hash function /is/(x) = first character of x and linear probing is
used. How much time does your algorithm take?
7. Let the binary representation of identifier x be XiX2. Let |x | denote the number of
bits in X and let the first bit of X| be 1. Let |x|| = [ |x|/2 ] and | X2I = Ll-^l^ J ■
Consider the following hash function:
412 Hashing

f {x} = middle k bits of (xj XORX2)

where XOR is the exclusive or operator. Is this a uniform hash function if

identifiers are drawn at random from the space of allowable C identifiers? What
can you say about the behavior of this hash function in a real symbol table usage?
8. [T. Gonzalez] Design a symbol table representation which allows you to search,
insert, and delete an identifier x in 0(1) time. Assume that 0<x < m and that
m + n units of space are available where n is the number of insertions to be made.
(Hint: Use two arrays a [az] and b[m], where a[Z] will be the zth identifier
inserted into the table. If x is the zth identifier inserted, then b [x ] = z.) Write algo­
rithms to search, insert, and delete identifiers. Note that you cannot initialize
either a or b to zero as this would take O(az -I- m) time. Note that x is an integer.
9. [T. Gonzalez] Let S = [xj, X2,... , x„) and T = (y 1, ^2, • • ■ ^r) be two sets.
Assume 0 < x, < m, 1 < z < az and 0 < y,- < azz, 1 < z < r. Using the idea of Exercise
8, write an algorithm to determine if 5 c T. Your algorithm should work in
0(r + n) time. Since S = T iff 5 c T and T qS, this implies that one can deter­
mine in linear time if two sets are equivalent. How much space is needed by your
algorithm?
10. [T. Gonzalez] Using the idea of Exercise 9, write an O(az + m) time algorithm to
carry out the function of algorithm verify2 of Section 7.1. How much space does
your algorithm need?
11. Show that when linear open addressing is used:

1 n~\

Using this equation and the approximate equality:

1 1
1 + where a = —
2 (l-a)2 b

show that:

1
Sn
1 +
2 (1 - a)
12. [Guttag] The following set of operations defines a symbol table that handles a
language with block structure. Write a specification for this data type in the style
of Structure 8.1.
 Static Hashing 413

INIT creates an empty table

ENTERS indicates a new block has been entered
ADD places an identifier and its attributes in the table
LEAVES deletes all identifiers that are defined in the innermost block
RETRIEVE returns the attributes of the most recently defined identifier
ISINS returns true if the identifier is defined in the innermost block else false

13. § [Programming project] Create a menu-driven, user-friendly program that

manages the supply list of Widgets, Inc. Widgets, Inc., keeps the following infor­
mation on their supplies:
♦ 5-digit part number (the key)
• 10-character description of part
• reorder level
• size of current inventory

You must maintain the supply list using a chained hash table. In addition, Widg­
ets, Inc., employees must be able to perform the following operations:
(a) add a new part to the inventory
(b) delete a part from the inventory
(c) search for a part
(d) change the key field of a part
(e) change any of the remaining fields

8.3 DYNAMIC HASHING

One of the most important classes of software is the database management system or
DBMS. In a DBMS the user enters a query using some language (possibly SQL) and the
system translates it and retrieves the resulting data. Fast access time is essential since a
DBMS is typically used to hold large sets of information. Another key characteristic of
a DBMS is that the amount of information can vary a great deal over time. Various data
structures have been suggested for storing the data in a DBMS. In this section, we exam­
ine an extension of hashing that permits the technique to be used by a DBMS.
Traditional hashing schemes as described in the previous sections are not ideal
because we must statically allocate a portion of memory to hold the hash table. This
hash table is used to point to the buckets that hold identifiers, or it may actually contain
the identifiers. In either case, if we allocate a large portion of memory to hold the table,
we waste space. Yet, if we allocate a minimal amount of memory, we will have to res­
tructure the entire file when the data exceeds the capacity of the hash table. This is a very
time-consuming process. Dynamic hashing, also referred to as extendible hashing,
retains the fast retrieval time of conventional hashing, while extending the technique so
414 Hashing

that it can accommodate dynamically increasing and decreasing file size without penalty.
We assume that a file, F, is a collection of records, R. Each record has a key field,
K, by which it is identified. Records are stored in buckets, or pages as they are called in
dynamic hashing, whose capacity is p. The algorithms we develop must minimize page
accesses since pages are usually stored on disk and their retrieval into memory dom­
inates any operation. The measure of space utilization is the ratio of the number of
records, n, divided by the total space, mp, where m is the number of pages.

8.3.1 Dynamic Hashing Using Directories

Consider an example where an identifier consists of two characters and each character is
represented by 3 bits. Figure 8.8 gives a list of some of these identifiers.

Identifiers Binary representation

aO 100 000
al 100 001
bO 101 000
bl 101 001
cO 110 000
cl 110 001
c2 110010
c3 110011

Figure 8.8: Some identifiers requiring 3 bits per character

We would like to place these identifiers into a table that has four pages. Each page can
hold no more than two identifiers, and the pages are indexed by the 2 bit sequence 00,
01, 10, 11, respectively. We use the two low-order bits of each identifier to determine
the page address of the identifier. Figure 8.9(a) shows the placement of aO, bO, c2, al,
bl, and c3 into the table. Notice that we select the bits from least significant to most
significant. Branching at the root is determined by the least significant bit. If this bit is
zero, the upper branch is taken. Otherwise, the lower branch is taken. Branching at the
next level is determined by the second least significant bit, and so on. aO and bO are in
the first page since their two low-order bits are 0 and 0. The second page contains only
c2. To get to this page, we first branch on the least significant bit of c2 (i.e., 0) and then
on the next bit (i.e., 1). The third page contains al and bl. To get to this page, we first
branch on the least significant bit of al or bl. This bit is one for both al and bl. Next,
we branch on the next bit which is zero for both. The last page contains c3, with a bit
pattern of 11. We use the term trie to denote a binary tree in which we locate an
identifier by following its bit sequence. (We shall describe tries in greater detail in
Chapter 10.) Notice that this trie has nodes that always branch in two directions
 Dynamic Hashing 415

corresponding to 0 or 1. Only the leaf nodes of the trie contain a pointer to a page.

aO, bO
aO, bO

c2

c2

al, bl

al,bl
c5

c3
c3
(a) two level trie on four pages
(b) inserting c5 with overflow

aO, bO

c2

al,cl

bl

c5

c3

(c) inserting cl with overflow

Figure 8.9: A trie to hold identifiers

416 Hashing

Now suppose we try to insert a new identifier, say c5, into Figure 8.9(a). The two
low-order bits of c5 are 1 and 0, which means that we should place it in the third page.
However, since a page can hold only two identifiers, an overflow occurs. When this hap­
pens, we add a new page and increase the depth of the trie. This is shown in Figure
8.9(b). If we now insert the identifier cl, an overflow of the page containing al and bl
occurs. We obtain a new page and divide the identifiers among the two pages according
to their four low-order bits.
From this example one can see that two major problems exist. First, the access
time for a page depends on the number of bits needed to distinguish the identifiers.
Second, if the identifiers have a skewed distribution, the tree is also skewed. Both these
factors increase the retrieval time. Fagin et al. present a method, which they call exten­
dible hashing, for solving these problems. To avoid the skewed distribution of
identifiers, a hash function is used. This function takes the key and produces a random
set of binary digits. To avoid the long search down the trie, the trie is mapped to a direc­
tory.
A directory is a table of page pointers. In case k bits are needed to distinguish the
identifiers, the directory has 2^ entries indexed 0, • • •, 2^-1. To find the page for an
identifier, we use the integer with binary representation equal to the last k bits of the
identifier. The page pointed at by this directory entry is searched. Figure 8.10 shows the
three directories corresponding to the three tries in Figure 8.9. The first directory con­
tains four entries indexed from 0 to 3 (the binary representation of each index is shown
in Figure 8.10). Each entry contains a pointer to a page. This pointer is shown as an
arrow in the figure. The letter above each pointer is a page label. The page labels were
obtained by labeling the pages of Figure 8.9(a) top to bottom beginning with the label a.
The page contents are shown immediately after the page pointer. To see the correspon­
dence between the directory and the trie, notice that if the bits in the directory index are
used to follow a path in the trie (beginning with the least significant bit), we will reach
the page pointed at by the corresponding directory entry.
The second directory contains eight entries indexed from 0 to 7, and the third has
16 entries indexed from 0 to 15. Page a of the second directory (Figure 8.10(b)) has two
directory entries (000 and 100) pointing to it. The page contents are shown only once.
Page b has two pointers to it, page c has one pointer, page d has one pointer, and page e
has two pointers. In Figure 8.10(c) there are six pages with the following number of
pointers respectively: 4, 4, 1, 1,2, and 4.
Using a directory to represent a trie allows the table of identifiers to grow and
shrink dynamically. This, of course, assumes that the operating system can give us more
pages or return pages to available storage with little or no difficulty. In addition, access­
ing any page requires only two steps. In the first step, we use the hash function to find
the address of the directory entry, and in the second, we retrieve the page associated with
the address.
Unfortunately, if the keys are not uniformly divided among the pages, the direc­
tory can grow quite large. However, most of the entries point to the same pages. To
prevent this from happening, we cannot use the bit sequence of the keys themselves.
Instead we translate the bits into a random sequence. This is done using a uniform hash
 Dynamic Hashing 417

00 ^aO, bO 000 ^aO, bO 0000-4. aO, bO

c c
01 al, bl 001 ^al, bl 0001 al, cl
b b 0010-X- c2
10 c2 010 c2
d e f
11 c3 Oil c3 0011 c3
a a
100 0100
d 0101-^ c5
101 c5
b b
110 OHO
e f
111 0111
a
lOOQ
d
1001 bl

loia b
f
1011
a
1100
e
1101
b
1110
f
nil

(a) 2 bits (b) 3 bits (c) 4 bits

Figure 8.10 : Tries collapsed into directories

function as discussed in the previous section. But, in contrast to the previous section, we
need a family of hash functions, because, at any point, we may require a different number
of bits to distinguish the new key. One solution is the family:

hashi'. key {0...2‘-‘), i<i<d

where hashj is simply hashi_\ with either a zero or one appended as the new leading bit
of the result. Thus, hash (key, z) might be a function that produces a random number of
i bits from the identifier key.
There are some important twists associated with this approach. For example, sup­
pose a page identified by i bits overflows. We allocate a new page and rehash the
identifiers into those two pages. The identifiers in both pages have their low-order i bits
418 Hashing

in common. We refer to these pages as buddies. When the number of identifiers in two
buddy pages is no more than the capacity of a single page, then we coalesce the two
pages into one.
Suppose a page that can hold only p records now contains p records and a new
record is to be added. The operating system allocates a new page. All 4- 1 keys are
rehashed, using 1 more bit and divided among the two pages. If the number of bits used
is greater than the depth (the number of bits or log2 of the directory size) of the direc­
tory, the whole directory doubles in size and its depth increases by 1. If all p -I- 1 records
are hashed to one of the two pages the split operation has to be repeated. Fortunately,
this is a fairly rare occurrence. When this happens, the depth of the directory can be
reduced using a compressed trie as discussed in Chapter 10.
Program 8.5 contains a pseudo-C program that provides many of the details for
implementing the directory version of dynamic hashing.

#include stdio.h>
#include alloc.h>
#include stdlib.h
ttdefine WORD—SIZE 5 /* max number of directory bits */
#define PAGE-SIZE 10 *
/ max size of a page * /
#define DIRECTORY-SIZE 32 / * max size of directory */
typedef struct page *
paddr;
typedef struct page {
int local—depth; *
/ page level */
name[PAGE —SIZE];
char *
int num—idents; /
*
/ # of identifiers in page */
};

typedef struct {
char *
key; /
* pointer to string */
*
/ other fields */
} brecord;
int global—depth; /
* trie height /
*
paddr directory[DIRECTORY-SIZE]; *
/ pointers to pages */

paddr hash{char •k , short int);

paddr buddy{paddr) ;
short int pgsearch{ char * , paddr);
int convert{paddr);
void enter{brecord, paddr);
void pgdelete{char •k , paddr);
paddr find{brecord, char k ) ;
void insert{brecord, char *> ;
int size{paddr);
 Dynamic Hashing 419

void coalesce(paddr , paddr);

void delete(brecord, char ) ;

paddr hash(char *
key, short int precision)
{
/* * key is hashed using a uniform hash function, and the
low precision bits are returned as the page address */
}

paddr buddy(paddr index)

{
/
* Take an address of a page and returns the page's
buddy, i.e., the leading bit is complemented */
}

int size(paddr ptr)

{
*
/ return the number of identifiers in the page */
}

void coalesce(paddr ptr, paddr buddy)

{
/
* combine page ptr and its buddy into a single page */
}

short int pgsearch(char key,

* paddr index)
{
*
/ Search a page for a key. If found return 1
otherwise return 0 */
}

int convert(paddr ptr)

{
/
* Convert a pointer to a page to an equivalent
integer */
}

void enter(brecord r, paddr ptr)

{
*
/ Insert a new record into the page pointed
at by ptr */
}

void pgdelete{char *
key, paddr ptr)
420 Hashing

{
*
/ remove the record with key, key, from the page
pointed to by ptr */
)

short int find(char *

key, paddr *ptr)
{
*
/ return 0 if key is not found and 1 if it is. Also,
return a pointer (in ptr) to the page that was searched.
Assume that an empty directory has one page. */

paddr index;
int intindex;

index = hash(key, global—depth);

intindex = convert(index);
*ptr = directory[intindex] ;
return pgsearch(key, ptr);
}

void insert(brecord r, char *

key)
{
paddr ptr;
if find(key, &ptr) {
fprintf(stderr. "The key IS already in the
[Link]");
exit(1);
}
if (ptr->num—idents != PAGE-SIZE) {
enter(r,ptr);
ptr->num—idents++;
}
else {
/
* Split the page into two, insert the new key, and
update global—depth if necessary.
If this causes global—depth to exceed WORD—SIZE
then print an error and terminate. */
};
}

void delete(brecord r, key)

char *
{
*
/ find and delete the record r from the file */
paddr ptr;
 Dynamic Hashing 421

if (!find(key, &ptr)) {
fprintf(stderr,"Key is not in the table.\n");
return; / * non-fatal error */
}
pgdelete(key,ptr);
if (size(ptr) + size(buddy(ptr)) PAGE—SIZE)
coalesce(ptr,buddy(ptr));
}

void main(void)
{
}

Program 8.5: Dynamic hashing

8.3.2 Analysis of Directory Dynamic Hashing

The most important feature of the directory version of extendible hashing is the guaran­
tee that retrieving any page requires only two disk accesses. Thus, its performance is
very good. However, we pay for this performance in space usage. Recall that adding
identifiers that are not uniformly distributed can double the directory size. Since many
of the pointers could point to the same page, we have a lot of wasted storage.
A second criterion for judging hashing schemes is the space utilization. This is
defined as the ratio of the number of records stored in the table divided by the total
amount of space allocated. Several researchers (Fagin, Larson, and Mendelson) have
analyzed this measure for different variations of dynamic hashing. They have all
reached similar conclusions, namely, that without any special strategies for handling
overflows, the space utilization is approximately 69 percent. Each of their derivations is
quite complex and rely on assumptions about the distributions of the identifiers. Here we
will follow the derivation given by Mendelson.
Let L{k} stand for the expected number of leaf nodes needed to hold k records.
When the records all fit in a single page, L{k} = 1. The interesting case is when k
exceeds the page size. In this case, the number of records in the two subtrees of the root
have a symmetric binomial distribution. From this it follows that there will be j keys in
the left subtree and k - j in the right, each with a given probability, which is:

k
; (1/2)
j

This implies that the number of leaf pages in the left subtree is L(/) and the
number in the right subtree is L{k - j}. Thus, one can express L{k} by the formula:

it
1 ' {LG-) + L(/;-7)}=2'-'X k
2^' ./=o J
.i=(^
422 Flashing

Mendelson goes on to show that:

k
p\n2

It follows that the storage utilization is the number of records k divided by the pro­
duct of the page size p and the number of leaf nodes L (k) or that:

k
utilization = - In2 - 0.69
pL(k)

To see that Mendelson’s estimate is reasonable, suppose there is no overflow stra­

tegy other than doubling the directory size. We have a full page with p records and
attempt to insert ap -t-l’st record, which causes an overflow. With a uniform hash func­
tion we now have two pages each containing about p/2 identifiers, or a space utilization
of 50 percent. After the process of inserting and deleting continues for a while, we
would expect that a recently split page is at least half full. Thus, space utilization should
be at least 50 percent, but certainly less than 100 percent.
When a page overflows, it may double the directory size. To avoid this, we intro­
duce the concept of overflow pages. Instead of increasing the directory, an overflow
causes the allocation of a new page. The pointer to this page is stored in the main page.
Rather than storing new identifiers in the main page, we place them in the overflow page.
As we shall see, this increases storage utilization, but at the expense of increased
retrieval time.
Assume that an overflow page is the same size as a regular page and that both
pages are full with p records, a total of 2p records. Suppose an overflow now occurs.
We obtain a new page, and distribute the keys among the three pages. The utilization is
2p/3p or 66 percent. On the other hand, suppose that the overflow page has a capacity of
p/2 rather than p. If we redistribute the keys as before, then a total of 3p/2 records is
divided over a capacity of 2p. This produces a utilization of 3/4 = 75 percent. Thus, we
see that although overflow pages increase utilization, they also increase retrieval time.
Determining the ideal size for the overflow page has been investigated by Larson
and others. Larson concludes that if a space utilization below 80 percent is sufficient,
then the size of the overflow pages can vary widely, say, from p to p/2. However, higher
space utilizations require a successively narrow range of overflow page sizes, because
utilization begins to oscillate and access time increases significantly. To cope with this
problem, we could monitor the space utilization of the file, so that when it achieves some
predetermined amount, say the 80 percent ratio, the algorithm resumes splitting.
We can also analyze the size of the directory in terms of the number of records, n,
that are stored in the file. Fagin estimates this as:

n
2 [log
p\n2
1
 Dynamic Hashing 423

Figure 8.11 contains a table given by Flajolet which shows the expected directory
size for various numbers of records, n, and page size, p. For example, we would need a
directory of size 62,500 to store one million records using a page size of 50. This is sub­
stantial, and indicates that the directory may have to be stored using auxiliary storage.

P
n 5 10____ 20___ 50 100 200
H? 1.5K 0?3K [Link] [Link] [Link] [Link]
*10 25.6K 4.8K 1.7K 0.5K 0.2K [Link]
10’ 424. IK 68.2K 16.8K 4.1K 2.0K [Link]
10® 6.9M 1.02M 0,26M 62.5K 16.8K 8.1K
10’ [Link] 11.64M 2.25M 0.52M 0.26M 0.13M

Figure 8.11 : Directory size given n records and p page size

In the event that the hash function does not evenly distribute the identifiers across
the pages, more sophisticated techniques are required. Lomet suggests that, in the direc­
tory scheme, we do not view pages as of a fixed size, but allow them to grow. Thus, any
given page may be composed of several subpages. As more identifiers map to this page,
its storage is expanded. This leads to different strategies for maintaining the identifiers
within the page. The simplest strategy is to keep the identifiers in the order they were
entered into the table. However, sequential searching is time consuming, especially as
the identifier list gets long. An alternate strategy is to treat each subpage as a dynami­
cally hashed directoryless structure. We describe its maintenance in Section 8.3.3.

Simulation

One important way to measure the performance of any new data structure is to
carry out a series of experiments. Each experiment makes use of the algorithms that
implement the data structure. Various distributions of identifiers are given to the algo­
rithms and the resultant behavior is tabulated. In the case of dynamic hashing, we would
want to monitor (1) access time, (2) insertion time, and (3) total space utilization. The
factors influencing these attributes are (1) the number of records, (2) the page size, (3)
the directory size, (4) the size of main memory for holding the directory and identifiers,
and (5) the time required to process page faults.
Fagin et al. have done such a series of experiments. They found that in all cases
extendible hashing performed at least as well or better than B-trees, a popular competi­
tor. In the case of access time and insertion time, extendible hashing was clearly supe­
rior. For space utilization the two methods were about equal.
424 Hashing

8.3.3 Directoryless Dynamic Hashing

Section 8.3.2 assumed that a directory existed that pointed to pages. One criticism of
this approach is that it always requires at least one level of indirection. If we assume
that we have a contiguous address space which is large enough to hold all the records,
we can eliminate the directory. In effect, this leaves it to the operating system to break
the address space into pages, and to manage moving them into and out of memory. This
scheme is referred to as directoryless hashing or linear hashing.
Consider the trie in Figure 8.9(a) which has two levels and indexes four pages. In
the new method, the 2 bit addresses are the actual addresses of these pages (actually they
are an offset of some base address). Thus, the hash function delivers the actual address
of a page containing the key. Moreover, every value produced by the hash function must
point to an actual page. In contrast to the directory scheme where a single page might be
pointed at by several directory entries, in the directoryless scheme there must exist a
unique page for every possible address. Figure 8.12 shows a simple trie and its mapping
to contiguous memory without a directory.

aO,bO

00 aO
bO
c2
01 c2

10 al
bl
al, bl
11 c3

c3

Figure 8.12 : A trie mapped to a directoryless, contiguous storage

Now what happens when a page overflows? We could double the size of the
address space, but this is wasteful. Instead, whenever an overflow occurs we add a new
page to the end of the file, and divide the identifiers in one of the pages between its origi­
nal page and the new page. This complicates the handling of the family of hash func­
tions somewhat. However, if we had simply added one bit to the result of the hash func­
tion, the table would have to be doubled. By adding only a single page, the hash
 Dynamic Hashing 425

function must distinguish between pages addressed by r bits and those addressed by r +1.
We will show how this is done in a moment.
Figure 8.13 provides an example of directoryless hashing after two insertions. Ini­
tially, there are four pages each addressed by 2 bits (Figure 8.13(a)). Two of the pages
are full, and two have one identifier each. When c5 is inserted, it hashes to the page
whose address is 10 (Figure 8.13(b)). Since that page is full, an overflow node is allo­
cated to hold c5. At the same time, we add a new page at the end of the storage, rehash
the identifiers in the first page, and split them between the first and new page. Unfor­
tunately, none of the new identifiers go into the new page. The first page and the new
page are now addressed by 3 bits, not 2 as shown in Figure 8.13(b). In the next step, we
insert the identifier cl. Since it hashes to the same page as c5, we use another overflow
node to store it. We add another new page to the end of the file and rehash the identifiers
in the second page. Once again none go into the new page. (Note that this is largely a
result of not using a uniform hash function.) Now the first two pages and the two new
pages are all addressed using three bits. Eventually the number of pages will double,
thereby completing one phase. A new phase then begins.

00 aO 000 aO 000 aO
bO bO bO
01 c2 01 c2 001 c2
overflow
P4ge
10 al 10 al 10 al
bl bl c5 bl cl c5
11 c3 11 c3 11 c3

100 100
new page
new page
101

start of expansion 2 insert c5 insert c l

there are 4 pages page 10 overflows page 10 overflows
page 00 splits page 01 splits
(a) (b) (c)

Figure 8.13 : An example with two insertions

Consider Figure 8.14, which shows the state of file expansion during the rth phase
at some time q. At the beginning of the rth phase, there are 2'’ pages all addressed by r
426 Hashing

bits. In the figure, q new pages have been added. The pages to the left of the q line have
already been split. The pages between the q and r lines are waiting to be split, and the
pages to the right of the r line have been added during this phase of the process. Each
page in this section of the file is addressed by r + 1 bits. Notice that the q line indicates
which page gets split next. The actual modified hash function is given in Program 8.6.
All pages less than q require r + 1 bits. The function hash {key, r) is in the range
{0,2''”’) so, if the result is less than q, we rehash using r + 1 bits. This gives us either the
pages to the left of q or above 2''-!. The directoryless method always requires
overflows.

pages already split pages not yet split pages added so far

addressed by r +1 bits addressed by r bits addressed by r +1 bits

Q r

-------------------- 2'' pages at start --------------------

suppose we are at phase r; there are 2'" pages indexed by r bits

Figure 8.14 : During the rth phase of expansion of directoryless method

One sees that many retrievals require only one access, that is, those that have
identifiers that are in the page directly addressed by the hash function. However, other
retrievals might require substantially more than two accesses as one moves along the
overflow chain. When a new page is added and the identifiers split across the two pages,
all identifiers including the overflows are rehashed.
We should also point out that the space utilization for this method is not good. As
can be seen from Figure 8.13, some extra pages are empty and yet overflow pages are
being used. Litwin has shown that space utilization is approximately 60 percent. He
offers an alternate strategy pursued in the exercises. The term controlled splitting refers
to splitting the next page only when storage utilization exceeds a predefined amount.
Litwin suggests that until 80 percent utilization is reached, other pages continue to
overflow.
A natural way to handle overflows is to use one of the traditional hashing schemes
discussed earlier, such as open addressing. Recall that open addressing searches the file
linearly from the point where the identifier hashes, either looking for the identifier or for
an open spot.
 Dynamic Hashing 427

if (hash(key,r) q)
page = hash(key,r+1);
else
page = hash(key,r);
if needed, then follow overflow pointers;

Program 8.6: Modified hash function

From the example, one sees that the longest overflow chains occur for those pages
that are near the end of the expansion phase since they are the last to be split. In con­
trast, those pages that are split early are generally underfuli.

EXERCISES

1. The text points out that nonuniform distributions of keys result in a skewed direc­
tory and a waste of directory space. We can avoid this problem in the directory
scheme if we store the directory as a forest of tries rather than a table. A new key
is hashed to one of the tries and then its nodes are traversed until a leaf node is
reached. The leaf node points to the page containing the desired record. Splitting
is still required. The tries grow and contract with respect to the file. Write out the
algorithms for maintaining a trie as a directory.
2. In extendible hashing, given a directory of size d, suppose two pointers point to
the same page. How many low-order bits do all identifiers share in common? If
four pointers point to the same page, how many bits do the identifiers have in com­
mon?
3. We can handle overflows in directory dynamic hashing by permitting a page to be
divided into as many multiple pages as necessary to hold all identifiers that hash to
that page. We assign a limit on the size of the directory. Once this limit has been
reached, pages simply continue to grow. Modify the algorithms in Program 8.11
to implement this strategy.
4. Prove that in directory-based dynamic hashing a page can be pointed at by a
number of pointers that is a power of 2.
5. We have not talked much about how to organize the identifiers within a page for
fast retrieval. Consider an unordered list, an ordered list, and hashing and com­
pare their merits.
6. The function insert is almost complete except for a few lines of pseudocode.
Replace the pseudocode by actual C code that places all identifiers in page p into
the temp area and then rehashes those identifiers back into either page p or q.
428 Hashing

1. Program 8.5 contains a reference to a function coalesce that combines the

identifiers in two pages into a single page. Using the types and functions already
defined, write a C version of this function.
8. Take the formula given by Mendelson for the number of leaf pages required to
store k records in a directory-based dynamic hashing scheme and formally derive
the approximation that L (k} is about equal to k/{p In 2) where p is the page size.
9. Larson has suggested using open addressing in a directoryless dynamic hashing
method to handle overflows. The problem is that those pages that have yet to be
split have the most overflows, but these pages are stored contiguously. Instead,
Larson suggests that pages be alternately split, so next to an unsplit page is a split
page. Show how the hash function must be rewritten to handle this scheme.

8.4 REFERENCES AND SELECTED READINGS

Several interesting and enlightening works on hash tables exist. Some of these are: R.
Morris, "Scatter storage techniques," CACM, vol. 11, no. 1, 1968, pp. 38-44; V. Lum, P.
Yuen, and M. Dodd, "Key to address transform techniques: A fundamental performance
study on large existing formatted files," CACM, vol. 14, no. 4, 1971, pp. 228-239; J. Bell,
"The quadratic quotient method: A hash code eliminating secondary clustering," CACM,
vol. 13, no. 2, 1970, pp. 107-109; A. Day, "Full table quadratic searching for scatter
storage," CACM, vol. 13, no. 8, 1970, pp. 481-482; D. Severance, "Identifier search
mechanisms: A survey and generalized model," ACM Computing Surveys, vol. 6, no. 3,
1974, pp. 175-194; W. Mauer and T. Lewis, "Hash table methods," ACM Computing Sur­
veys, vol. 7, no. 1, 1975, pp. 5-20; D. Knuth, The Art of Computer Programmamming:
Sorting and Searching, Addison-Wesley, Reading, Massachusetts, 1973; R. Brent,
"Reducing the retrieval time of scatter storage techniques," CACM, vol. 16, no. 2, 1973,
pp. 105-109; V. Lum, "General performance analysis of key-to-address transformation
methods using an abstract file concept," CACM, vol. 16, no. 10, 1973, pp. 603-612; and
C. E. Radke, "The use of quadratic residue research, CACM, vol. 13, no. 2, 1970, pp.
103-105.
In the literature, Larson was the first to introduce a method he called dynamic
hashing. Litwin followed. Fagin et al. called their method extendible hashing. Fagin
uses a directory scheme that doubles in size on expansion. Larson used a linked tree
structure as the representation of the directory with pointers to pages in the leaves. The
references are: P. Larson, "Dynamic hashing," BIT, vol, 18, 1978, pp. 184-201; W.
Litwin, "Virtual hashing: a dynamically changing hashing," Proc. Int. conf, on very large
databases, Berlin, 1978, pp. 517-523; and R. Fagin, J. Nievergelt, N. Pippenger, and
H.R. Strong, "Extendible hashing - a fast access method for dynamic files," ACM Trans,
on Database Systems, vol. 4, no. 3, 1979, pp. 315-344.
An excellent overview of dynamic hashing techniques and variations can be found
in R.J. Enbody and H.C. Du, "Dynamic Hashing Schemes," ACM Computing Surveys,
vol. 20, no 2, 1988, pp. 85-113.
 References And Selected Readings 429

Some other papers on dynamic hashing are: P. Flajolet, "On the performance
evaluation of extendible hashing and trie searching," Acta Informatica, 20, 1983, pp.
345-369; D.B. Lomet, "Bounded index exponential hashing," ACM Trans, on Database
Systems, vol. 8, no. 1, 1983, pp. 136-165; H. Mendelson, "Analysis of extendible hash­
ing," IEEE Trans, on Soft\vare Engineering, vol. 8, no. 6, 1982, pp. 611-619; and K.
Ramamohanarao and J.W. Lloyd, "Dynamic hashing schemes," The Computer Journal,
vol. 25, no. 4, 1982, pp. 478-485.
Scholl introduces two methods to improve storage utilization by deferring the
splitting of pages and handling overflows internally. This gives a tradeoff between
storage utilization and access time. See M. Scholl, "New file organizations based on
dynamic hashing," ACM Trans, ofDatabase Systems, vol. 6, no. 1, 1981, pp. 194-211.
CHAPTER 9
HEAP STRUCTURES

9.1 MIN-MAX HEAPS

9.1.1 Definition

A double-ended priority queue is a data structure that supports the following operations:

(1) Insert an element with arbitrary key.

(2) Delete an element with the largest key.
(3) Delete an element with the smallest key.

When only insertion and one of the two deletion operations is supported, we may
use a min heap or a max heap (see Chapter 5). A min-max heap supports all of the
operations just described.

Definition: A min-max heap is a complete binary tree such that if it is not empty, each
element has a field called key. Alternating levels of this tree are min levels and max lev­
els, respectively. The root is on a min level. Let x be any node in a min-max heap. If x
is on a min level then the element in x has the minimum key from among all elements in
the subtree with root x. We call this node a min node. Similarly, if x is on a max level
then the element in x has the maximum key from among all elements in the subtree with

430
 Min-Max Heaps 431

root X. We call this node a max node. □

Figure 9.1 shows an example 12 element min-max heap. The value in each node is
the key of the element in that node. Notice that we are using the array representation
discussed in Section 5.2.

7 min

70 40 max

30 9 10 15 min

45 50 30 20 12 max

Figure 9.1 : A 12 element min-max-heap

9.1.2 Insertion Into A Min-Max Heap

Suppose we wish to insert the element with key 5 into this min-max heap. Following the
insertion, we will have a 13 element min-max-heap. This has the shape shown in Figure
9.2. As in the case of heaps, the insertion algorithm for min-max-heaps follows the path
from the new node j to the root. Comparing the new key 5 with the key 10 that is in the
parent of j, we see that since the node with key 10 is on a min level and 5 < 10, 5 is
guaranteed to be smaller than all keys in nodes that are both on max levels and on the
path from j to the root. Hence, the min-max-heap property is to be verified only with
respect to min nodes on the path from j to the root. First, the element with key 10 is
moved to node j. Then the element with key 7 is moved to the former position of 10.
Finally, the new element with key 5 is inserted into the root. The min-max-heap follow­
ing the insertion is shown in Figure 9.3(a).
Next, suppose we wish to insert an element with key 80 into the min-max-heap of
Figure 9.1. The resulting min-max-heap has 13 elements and has the shape shown in
Figure 9.2. Since 80 > 10 and 10 is on a min level, we are assured that 80 is larger than
all keys in nodes that are both on min levels and on the path from j to the root. Hence,
the min-max-heap property is to be verified only with respect to max nodes on the path
from j to the root. There is only one such node in the min-max-heap of Figure 9.1. This
432 Heap Structures

7 min

70 40 max

30 9 10 15 min

45 50 30 20 12 J max

Figure 9.2 : Min-max-heap of Figure 9.1 with new node j

node has key 40. The element with key 40 is moved to j and the new element inserted
into the node formerly occupied by this element. The resulting min-max-heap is shown
in Figure 9.3(b).
The preceding insertion examples lead to the insertion function min-max-insert
(Program 9.1). The C declarations necessary to create the min-max heap are:
#define MAX-SIZE 100 /
* maximum size of heap plus 1
*/
#define FALSE 0
ttdefine TRUE 1
#define SWAP(x,y,t) ((t) (x) , (X) (y) , (y) (t))
typedef struct {
int key;
other fields
} element;
element heap[MAX—SIZE];

Notice that we store a min-max heap in a one-dimensional array using the standard array
representation of a complete binary tree (see Section 5.3). The function
min-max-insert uses verify-max. verify-min. and level functions. The function level
determines whether a node is on a min or a max level of a min-max heap; it returns
FALSE for a min level and TRUE for a max level. The function verify-max (Program
9.2) begins at a max node i and follows the path of max nodes from i to the root of the
min-max heap. It searches for the correct node in which to insert item. This node has
the property that all max nodes above it and on the path to the root have key values at
least as large as [Link]. In addition, all max nodes below it and on the path from i to
 Min-Max Heaps 433

5 min

70 40 max

30 9 7 15 min

45 50 30 20 12 10 max

(a) min-max-heap of Figure 9.1 after inserting 5

7 min

70 80 max

30 9 10 15 min

45 50 30 20 12 40 max

(b) min-max-heap of Figure 9.1 after inserting 80

Figure 9.3 : Insertion into a min-max-heap

the root have key values smaller than [Link]. During the search, max nodes with keys
smaller than [Link] are moved one max level down.
The functions verify-min and verify-max are similar except that verify-min
begins at a min node i and follows the path of min nodes from i to the root. To preserve
the min-max heap property, item is inserted into one of these min nodes. We leave the
formal development of verify-min and level as an exercise.

Analysis of min-max-insert: We may easily establish the correctness of

min-max-insert. In addition, since a min-max heap with n elements has O(log n) levels,
the complexity of the min-max-insert function is O(log n). □
434 Heap Structures

void min—max—insert(element heap[], int *n, element item)

{
*
/ item into the min-max heap */
insert
int parent;
n)
*
( ++ 7
if {
n
* == MAX_SIZE) {
fprintf(stderr,"The heap is full\n");
exit(1);
}
parent *
(
n)/2;
if ( !parent)
/
* heap is empty, insert item into first position */
heap[1] item;
else switch(level(parent)) {
case FALSE: *
/ min level */
if ([Link] heap[parent].key) {
heap[
n]
* = heap[parent] ;
verify—min(heap,parent,item);
}
else
verify—max(heap,*
n,item) ;
break;
case TRUE: *
/ max level */
if ([Link] heap[parent].key) {
heap[
n]
* = heap[parent];
verify—max(heap,parent,item);
}
else
verify_min(heap,
n,item)
* ;
}
}

Program 9.1: Procedure to insert into a min-max heap

9.1.3 Deletion Of Min Element

Let us now take a look at deletion from a min-max-heap. If we wish to delete the ele­
ment with smallest key, then this element is in the root. In the case of the min-max-heap
of Figure 9.1, we are to delete the element with key 7. Following the deletion, we will
be left with a min-max-heap that has 11 elements. Its shape is shown in Figure 9.4. The
node with key 12 is deleted from the heap and the element with key 12 is reinserted into
 Min-Max Heaps 435

void verify-_rr>ax (element heap[], int i, element item)

{
*
/ follow the nodes from the max node i to the root and
insert item into its proper place */
int grandparent = i/4;
while (grandparent)
if ([Link] heap[grandparent].key) {
heap[i] = heap[grandparent] ;
i = grandparent;
grandparent /- 4;
}
else
break;
heap[i] 11 em ;
}

Program 9.2: verify-max: function

the heap. As in the case of deletion from a min or max-heap, the reinsertion is done by
examining the nodes of Figure 9.4 from the root down towards the leaves.

12 min

70 40 max

30 9 10 15 min

45 50 30 20 max

Figure 9.4 : Shape of Figure 9.1 following a delete min

In a general situation, we are to reinsert an element item into a min-max-heap,

heap, whose root is empty. We consider the two cases:
436 Heap Structures

(1) The root has no children. In this case item is to be inserted into the root.
(2) The root has at least one child. Now, the smallest key in the min-max-heap is in
one of the children or grandchildren of the root. We determine which of these
nodes has the smallest key. Let this be node k. The following possibilities need to
be considered:
(a) item, key < heap item may be inserted into the root as there is no
element in heap with key smaller than item. key.
(b) item, key > heap [/:]. key and A: is a child of the root. Since k is a max node,
it has no descendants with key larger than heap Hence, node k has
no descendants with key larger than item. key. So, the element heap [k ] may
be moved to the root and item inserted into node k.
(c) item, key > heap [k]. key and k is a grandchild of the root. In this case too,
heap [k ] may be moved to the root. Let parent be the parent of k. If
item, key > heap [parent}.key, then heap [parent} and item are to be inter­
changed. This ensures that the max node parent contains the largest key in
the sub-heap with root parent. At this point, we are faced with the problem
of inserting item into the sub-heap with root k. The root of this sub-min-max
heap is presently empty. This is quite similar to our initial situation where
we were to insert item into the min-max-heap heap with root 1 and node 1 is
initially empty. Therefore, we repeat the above process.

In our example, x. key =12 and the smallest key in the children and grandchildren
of the root node is 9. Let k denote the node that contains this key and let p be its parent.
Since, 9 < 12 and k is a grandchild of the root, we are in case 2 (c). The element with
key 9 (i.e., A [A:]) is moved to the root. Since x. key = 12 < 70 = h[p}.key, we do not
interchange x and h[p}. The current configuration is shown in Figure 9.5. We must
now reinsert x into the sub-min-max-heap with root k. The smallest key from among the
children and grandchildren of node k is 20. Since 12 < 20, we are in case 2 (a) and the
element x is inserted into /?[/:].
The function delete-min (Program 9.3) implements the deletion of the node with
the minimum key from a min-max heap. This function uses a min-child-grandchild(i)
function to determine the child or grandchild of the node i that has the smallest key. If
both a child and a grandchild of i have the smallest key, min-child-grandchild should
return the address of the child since this prevents further iterations of the for loop of
delete-min. Notice that although delete-min does not explicitly check for the case
when n = 1, this is handled correctly and an empty min-max heap results from the dele­
tion.

Analysis of delete-min'. In each iteration of the for loop of delete-min a constant

amount of work is done. Also, in each iteration (except possibly the last), i moves down
two levels. Since a min-max heap is a complete binary tree, heap has O(log «) levels.
Hence, the complexity of delete-min is O(log n). □
 Min-Max Heaps 437

9 min

70 40 max

30 12 10 15 min

45 50 30 20 max

Figure 9.5: Figure 9.4 following the move of the element with key 9

The function to delete the element with the maximum key is similar to delete-min.
We leave its development as an exercise.

EXERCISES

1. Write the verify-min function defined in connection with insertion into a min-max
heap.
2. Write the level (?) function that determines whether node i of a min-max heap is on
a min or a max level.
3. Write the mm-child-grandchild(i, n) function that returns the child or grandchild
of node i of a min-max heap that has the smallest key. You may assume that i has
at least one child, n is the current size of the min-max heap.
4. Write a delete-max function to delete the element with the maximum key in a
min-max heap. Your function should run in O(log «) time for a min-max heap
with n elements.
5. Write a function that initializes a min-max heap with n elements. Use a series of
adjusts as described in the initialization of a min (or max) heap (see Section 5.6).
Show that your function takes O(n) time rather than the O(n log n) time that would
be taken if initialization is done by performing n insertions into an initially empty
heap.
438 Heap Structures

element delete—min(element heap[], int *n)

{
/■^ delete the minimum element from the min-max heap ■^ /
int i, last, k, parent;
element temp, x;

if (!(
*
n) ) {
fprintf(stderr, "The heap is emptyXn");
heap[0].key - INT—MAX; / * error key in heap[0] ^1
return heap[0];
}
heap[0] = heap[1]; I* save the element */
y. = heap [ ( *
n) --] ;
/'^ find place to insert x '^ /
for (i = 1, last = n)
*
( /'I-, i : last;} {
k = min—child—grandchild(i, * n) ;
if ([Link] = heap[k].key) break;
/■^ case 2(b) or 2(c)
heap[i] = heap[k];
if (k i+l)
= 2
* { 2 (b) ■^ /
i - k;
break;
}
/
* case 2(c), k is a grandchild of i ■^ /
parent = k/2;
if ([Link] heap[parent].key)
SWAP(heap[parent], x, temp);
1 z k;
} /* for */
heap[i] x;
return heap[0];
}

Program 9.3: Function to delete the element with minimum key

 Deaps 439

9.2 DEAPS

9.2.1 Definition

A deap is a double-ended heap that supports the double-ended priority queue operations
of insert, delete min, and delete max. As in the case of the min-max heap, these opera­
tions take logarithmic time on a deap. However, the deap is faster by a constant factor
and the algorithms are simpler.

Definition: A deap is a complete binary tree that is either empty or satisfies the follow
ing properties:
(1) The root contains no element.
(2) The left subtree is a min-heap.
(3) The right subtree is a max-heap.
(4) If the right subtree is not empty, then let i be any node in the left subtree. Let j be
the corresponding node in the right subtree. If such a j does not exist, then let j be
the node in the right subtree that corresponds to the parent of i. The key in node i
is less than or equal to the key in j. □

An example of an 11-element deap is shown in Figure 9.6. The root of the min-
heap contains 5, while that of the max-heap contains 45. The min-heap node with key 10
corresponds to the max-heap node with key 25, while the min-heap node with key 15
corresponds to the max-heap node with key 20. For the node containing 9, the node j
defined in property (4) of the deap definition is the max-heap node that contains 40.

Figure 9.6: An 11 element deap

440 Heap Structures

From the definition of a deap, it is evident that in an n element deap, n > 1, the
min element is in the root of the min-heap while the max element is in the root of the
max-heap. If n = 1, then the min and max elements are the same and are in the root of
the min-heap. Since a deap is a complete binary tree, it may stored as an implicit data
structure in a one dimensional array much the same way as min-, max-, and min-max-
heaps are stored. In the case of a deap, position 1 of the array is not utilized (we may
simply begin the array indexing at 2 rather than at 1). Let n denote the last occupied
position in this array. Then the number of elements in the deap is n - 1. If i is a node in
Lloga/J—1
the min-heap, then its corresponding node in the max-heap is i Hence the j
defined in property (4) of the definition is given by:

if (j > n')j/= 2;

Notice that if property (4) of the deap definition is satisfied by all leaf nodes i of
the min-heap, then it is satisfied by all remaining nodes of the min-heap too.
The double-ended priority queue operations are particularly easy to implement on
a deap. The complexity of each operation is bounded by the height of the deap which is
logarithmic in the number of elements in the deap.

9.2.2 Insertion Into A Deap

Suppose we wish to insert an element with key 4 into the deap of Figure 9.6. Following
this insertion, the deap will have 12 elements in it and will thus have the shape shown in
Figure 9.7. j points to the new node in the deap.
The insertion process begins by comparing the key 4 to the key in y’s correspond­
ing node, i, in the min-heap. This node contains a 19. To satisfy property (4), we move
the 19 to node j. Now, if we use the min-heap insertion algorithm to insert 4 into posi­
tion i, we get the deap of Figure 9.8.
If instead of inserting a 4, we were to insert a 30 into the deap of Figure 9.6, then
the resulting deap has the same shape as in Figure 9.7. Comparing 30 with the key 19 in
the corresponding node i, we see that property (4) may be satisfied by using the max­
heap insertion algorithm to insert 30 into position j. This results in the deap of Figure
9.9.
The case when the new node, j, is a node of the min-heap is symmetric to the case
just discussed. The function deap-insert (Program 9.4) implements the insert operation.
The data type, deap, is defined as:

element deap [MAX—SIZE]

The position of the last element in the deap is n and n = 1 denotes an empty deap.
 Deaps 441

5 45

iO 8 25 40

15 19 9 30 20 7

Figure 9.7: Shape of a 12 element deap

Figure 9.8: Deap of Figure 9.6 following the insertion of 4

The function deap-insert uses the following functions whose implementation we

leave as exercises:
442 Heap Structures

5 45

10 8 30 40

15 19 9 30 20 25

Figure 9.9 : Deap of Figure 9.6 following the insertion of 30

(1) max-heap(n). This function returns TRUE iffn is a position in the max-heap of the
deap.
(2) miri-partner^n). This function computes the min-heap node that corresponds to
the max-heap position n. This is given by n - 2
(3) max-partnerin). This function computes the max-heap node that corresponds to
the parent of the min-heap position n. This is given by (n •+• 2 Uog2«J-l
'■’”^^"^"5/2.

(4) min-insert and max-insert. These functions insert an element into a specified
position of a min- and max-heap, respectively. This is done by following the path
from this position toward the root of the respective heap. Elements are moved
down as necessary until the correct place to insert the new element is found. This
process differs from that used in Chapter 5 to insert into a min- or max-heap only
in that the root is now at position 2 or 3 rather than at 1.

Analysis of deap-insert'. The correctness of this function is easily established. Its com­
plexity is O(log«) as the height of the deap is O(logn). □

9.2.3 Deletion Of Min Element

Now consider the delete min operation. A description of the deletion process is given in
Program 9.5. The strategy is to first transform the deletion of the element from the root
of the min-heap to the deletion of an element from a leaf position in the min-heap. This
is done by following a root to leaf path in the min-heap ensuring that the min-heap pro­
perties are satisfied on the preceding levels of the heap. This process has the effect of
shifting the empty position initially at the min-heap root to a leaf node p. This leaf node
 Deaps 443

void deap—insert(element deap[], int *

n, element x)
{
/■^ insert x into the deap
int i;
n)
*
( + +;
if (
n
* =- MAX-SIZE) {
fprintf(stderr, "The heap is full\n");
exit(1);
}
if (*
n 2)
deap[2] = x; //★★ insert into empty deap ★/
n) )
else switch(max —heap(* {
case FALSE: 1^
*
/ n
* is a position on min side */
i = max—partner(*
n) ;
if ([Link] deep[i].key) {
deap[
n]
* = deap[i];
max—insert(deap,i,x);
}
else
min—insert(deap,*
n ,x);
break;
case TRUE: *
/ *n is a position on max side ■^ /
i = min—partner(*
n) ;
if ([Link] deap[i].key) {
deap[
n]
* = deap[i];
min—insert(deap,i,x);
}
else
n,x)
*
max—insert(deap, ;
}
}

Program 9.4: Function to insert an item into a deap

is then filled by the element, r, initially in the last position of the deap. The insertion of t
into position p of the min-heap is done as in deap-insert except that the specification of
max-partner(i) is changed to:

Llog2ij-1 .
j =i
if (j > n) j /= 2;

and the insertion does not increase the size of the deap. Function modified-deap-insert
444 Heap Structures

does this insertion. We leave the writing of this function as an exercise.

element deap—delete—min(element deap[1, int *n)

{
/
* delete the minimum element from the heap /
*
int i, j;
element temp;
if (*
n 2) {
fprintf(stderr, "The deap is empty\n");
/
* return an error code to user */
deap[0].key - INT-MAX;
return deap[01;
}
deap[0] - deap[2]; *
/ save min element */
n) --];
temp - deap[(*
for (i - 2; i
2
* <-
<= *
*n; deap[i] = deap[j], i = j) {
*
/ find node with smaller key */
j 2;
*
i
if (j+1 <= n)
* {
if (deap[j].key > deap[j+[Link])
j++;
}
}
modified—deap—insert(deap,i,temp);
return deap[0];
}

Program 9.5: Delete min function

For example, suppose that we wish to remove the minimum element from the deap
of Figure 9.6. To do this, we first place the last element (the one with key 20) in the deap
into a temporary element, temp, since the deletion removes this node from the heap
structure. Next, we fill the vacancy created in the min-heap root (node 2) by the removal
of the minimum element. To fill this vacancy we move along the path from the root to a
leaf node. Prior to each move, we place the smaller of the elements in the current node’s
children into the current node. We then move to the node previously occupied by the
moved element. In this example, we first move 8 into node 2. Then we move 9 into the
node formerly occupied by 8. Now, we have an empty leaf and proceed to insert 20 into
this. We compare 20 with the key 40 in its max partner. Since 20 < 40, no exchange is
needed and we proceed to insert the 20 into the min-heap beginning at the empty posi­
tion. This operation results in the deap of Figure 9.10.
 Deaps 445

8 45

10 9 25 40

15 19 20 30

Figure 9.10 : Deap of Figure 9.6 following a delete min

Analysis of deap -delete -mint We may easily verify that deap-delete-min works
correctly regardless of whether the last position in the deap is in the min- or max-heap.
The complexity is O(logn) as the height of a deap is O(logn). □

The deap-delete-max operation is performed in a similar manner.

EXERCISES

1. Complete the deap-insert function (Program 9.4) by writing all the functions that
it uses. Test the insertion function by running it on a computer. Generate your
own test data.
2. Complete the deap-delete-min function (Program 9.5) by writing all the func­
tions that it uses. Test the correctness of your function by running it on a computer
using test data of your choice.
3. Write a function to initialize a deap with n elements. Your function must run in
O(n) time. Show that it actually has this running time. (Hint: Use a series of
adjusts as discussed in Section 5.6.)
4. Write the functions to perform all double-ended priority queue operations for a
min-max heap and for a deap.
(a) Use suitable test data to test the correctness of your functions.
CHAPTER 10
SEARCH STRUCTURES

10.1 OPTIMAL BINARY SEARCH TREES

We introduced binary search trees in Chapter 5, and in this section we look at the con­
struction of these search trees for a static set of identifiers. That is, we make no additions
to or deletions from the tree; we only perform searches.
We begin by examining the correspondence between a binary search tree and the
binary search function we studied in Chapter 7. In Chapter 7 we showed that we could
construct a binary search tree that corresponds to a binary search on a sorted list (see
Figure 7.1). For example, a binary search on the list (do, if, while) is equivalent to using
the function search 2 (Program 5.17) on the binary search tree of Figure 10.1. Although
this is a full binary tree, it may not be an optimal binary search tree for this list if the
identifiers are searched for with different frequency. That is, the probability that we will
search for one of the identifiers is higher than the probability that we will search for the
other identifiers.
To find an optimal binary search tree for a given static list, we must first decide on
a cost measure for search trees. Assume that we wish to search for an identifier at level k
of a binary search tree using the search 2 function. We know that search 2 makes k itera­
tions of the while loop. Generally, the number of iterations of this loop equals the level
number of the identifier we seek. Since the while loop determines the computing time of
the search, it is reasonable to use the level number of a node as its cost.

470
 Optimal Binary Search Trees 471

if

do while

Figure 10. 1: Binary search tree corresponding to a binary search on the list (do, if,
while)

Consider the two search trees of Figure 10.2. The second tree requires at most
three comparisons to decide whether the identifier we seek is in the tree. The first binary
tree may require four comparisons, since any identifier that alphabetically comes after
for but precedes void tests four nodes. Thus, the second binary tree has a better worst
case search time than the first tree. Searching for an identifier in the first tree requires
one comparison for for, two comparisons each for do and while, three comparisons for
void, and four comparisons for if. If we search for each with equal probability, the aver­
age number of comparisons for a successful search is 2.4. The average number of com­
parisons for the second tree is only 2.2. Thus, the second tree also has better average
behavior.

for for

do while do void

void if while

(b)
if

(a)

Figure 10. 2: Two possible binary search trees

472 Search Structures

In evaluating binary search trees, it is useful to add a special square node at every
place there is a null link. Doing this to the trees of Figure 10.2 yields the trees of Figure
10.3. Remember that every binary tree with n nodes has n + 1 null links and hence has
n + 1 square nodes. We call these nodes external nodes because they are not part of the
original tree. The remaining nodes are internal nodes. Each time we search for an
identifier that is not in a binary search tree, the search terminates at an external node.
Since all such searches represent unsuccessful searches, we also refer to external nodes
as failure nodes. A binary tree with external nodes added is an extended binary tree.
Figure 10.3 shows the extended binary trees corresponding to the search trees of Figure
10.2.

for for

do while do void

void if while

if

(b)

(a)

Figure 10. 3: Extended binary trees corresponding to search trees of Figure 10.2

We define the external path length of a binary tree as the sum over all external
nodes of the lengths of the paths from the root to those nodes. Analogously, the internal
path length is the sum over all internal nodes of the lengths of the paths from the root to
those nodes. For example, the internal path length, I, of the tree of Figure 10.3(a) is:

/ = 0+ 1 + 1+2 + 3 = 7

Its external path length, E, is:

£ = 2 + 2 + 4 + 4 + 3 + 2= 17
 Optimal Binary Search Trees 473

Exercise 1 shows that the internal and external path lengths of a binary tree with n
internal nodes are related by the formula E = I + 2n. Hence, binary trees with the max­
imum E also have maximum 1. What are the maximum and minimum possible values for
I over all binary trees with n internal nodes? Clearly, the worst case occurs when the
tree is skewed, that is, the tree has a depth of n. In this case,

n-1
f ~ n(n ~ V)/2
i=Q

To obtain trees with minimal /, we must have as many internal nodes as close to
the root as possible. We can have at most 2 nodes at distance 1,4 at distance 2, 8 at dis­
tance 3, and so on. In general, the smallest value for I is:

0+*
2
l+4 + 8
3+...+
*

One tree with minimal internal path length is the complete binary tree defined in
Section 5.2. If we number the nodes in a complete binary tree as in Section 5.2, then we
see that the distance of node i from the root is [ log2/ J • Hence, the smallest value for I
is:

Z Uogzd = O(niog2n)

Let us now return to our original problem of representing a static list of identifiers
as a binary search tree. If the binary search tree contains the identifiers a i ,a2> • • •,
with cfj < 6^2 < ■ ■ ■ the probability of searching for each a, is p,, then the total
cost of any binary search tree is:

n
leveKa,-)
Z=1

when only successful searches are made. Since unsuccessful searches, that is, searches
for identifiers not in the table, are also made, we should include the cost of these
searches in our cost measure. Unsuccessful searches terminate with NULL returned in
function search?. Every node with a null subtree defines a point at which such a termi­
nation can take place. If we replace every null subtree by a failure node, we may parti­
tion the identifiers that are not in the binary search tree into n 4- 1 classes 0 < Z < n.
Eq contains all identifiers x such that x <a\. £, contains all identifiers x such that
ai < X < a^+j, 1 < Z < n, and £„ contains all identifiers x, x > a„. It is easy to see that for
all identifiers in a particular class, £,, the search terminates at the same failure node; it
terminates at different failure nodes for identifiers in different classes. We may number
the failure nodes from 0 to n with Z being the failure node for class £,, 0 < Z < n. If q, is
474 Search Structures

the probability that the identifier we are searching for is in £,•, then the cost of the failure
nodes is:

^qp (level(failure node 0 - 1)

i=Q

Therefore, the total cost of a binary search tree is:

n n
YjPi ’ level(flj) + • (level (failure node Z)-l) (10.1)
i=l 1=0

An optimal binary search tree for the identifier set aj, • • • , a^ is one that minimizes
Eq.(10.1) over all possible binary search trees for this identifier set. Since all searches
must terminate either successfully or unsuccessfully, we have:

n n
ILPi + Qi =
i=l i=0

Example 10.1: Figure 10.4 shows the possible binary search trees for the identifier set
(a 1, 02, «3) = (do, if, while). If we search for the identifiers with equal probabilities,
Pl = Oj = 1/7 for all i and y, we have:

cost (tree a} = \5n\ cost (tree b) = \3n

cost (tree c) = XSH', cost (tree d) = \5n
cost (tree e) = \5n

As expected, tree b is optimal. However, with pi =.5, p2 = .l, P3 =.05, = .15,

q^ = ,\^q2 = .05, and q^ = .05, we have:

cost (tree a) = 2.65; cost (tree b) = 1.9

cost (tree c) = 1.5; cost (tree d) = 2.05
cost (tree e) = 1.6

Tree c is optimal with this assignment of p’s and q's. □

How do we determine the optimal tree from all the possible binary search trees for
a given set of identifiers? We could proceed as in Example 10.1 and explicitly generate
all possible binary search trees. Thus, we would compute the cost of each such tree and
determine the optimal tree. We can determine the cost of each of the binary search trees
in O(n) time for an n node tree. If A(n) is the total number of distinct binary search
trees with n identifiers, the complexity of the algorithm is O(n A(n)). From Section 5.10
we know that N(n) = 0(4Vn^'^), which makes this brute force algorithm impractical for
 optima] Binary Search Trees 475

while if

if do while

do

(b)

(a)

do while do

if do while

while if if

(c) (d) (e)

Figure 10. 4: Binary search trees with three identifiers

large values of n. However, we can find a fairly efficient algorithm by making some
observations about the properties of optimal binary search trees.
Let a I < 672 < .. . < be the n identifiers represented in a binary search tree. Let
Tij denote an optimal binary search tree for • , aj, i < j. Tii is an empty tree for
0 < i < n and TaV is not Jdefined ijfor i > /. Let c,; denote the cost of the ij search
J tree T,. By
definition c,-, is 0. Let rij denote the root of Tij and let

J
= IL + Pk)
k=i-¥\

denote the weight of T^j. By definition, = 0 and h’,/ = qj, (}<i <n. T^^n is an optimal
binary search tree for «i, • • • , 67„.
an. Its cost is c,,n its weight is and its root is
476 Search Structures

If Tij is an optimal binary search tree for , • • • , aj and = k, then k satisfies

the inequality i < k < j. Tij has two subtrees L and R. L is the left subtree and contains
the identifiers a7+1 ♦ • • • , and R is the right subtree and contains the identifiers
■ ■ ■ ,aj (Figure 10.5). The cost of Tij is

=Pk + cost (L) + cost (/?) + weight (L) + weight (7?) (10.2)

where weight (L) = weight (r,,^_i) = and weight (R) = weight (T^j) =

L R

Figure 10.5: An optimal binary search tree 7,^

From Eq. (10.2) it is clear that Cy is minimal only if cost(L)=Cj,^_i and cost(A) =
Cj^j. Otherwise we could replace either Lor R with a subtree of lower cost and thus obtain
a binary search tree for aj+i, . .., aj with a lower cost than C/y. This violates the assump­
tion that Tij is optimal. Hence, Eq. (10.2) becomes:

- p-t + C,+ Ckj + + Wj^j

= Wy + + Ckj (10.3)

Since is optimal, it follows from Eq. (10.3) that = k is such that

+ Ckj = min{Wy -I- Q/.j + C/y}

or

Q;:-! + Ckj = min{Q/_, + qJ (10.4)

Equation (10.4) shows us how to obtain and starting from the knowledge that
Th = 0 and c,-,- = 0.
 Optimal Binary Search Trees 477

Example 10.2: Let n = 4 and (a i, 6/2, ^3, <24) = (do, for, void, while). Let {pi, p2^
P4) = (3, 3, 1, 1) and q^, q2, q^, q^} = (2, 3, I, 1, 1). (We have multiplied the origi­
nal p’s and q's by 16 for convenience.) Initially, = q^, cu = 0, and ra = Q,0<i <4.
Using Eqs. (10.3) and (10.4) we get:

n^oi - Pi+^oo+>^ii -Pi+^i+vvoo = 8

coi = woi+min{coo+cii} = 8

^01 = 1
W12 = P2 + ^li+'^22 =P2+‘?2+^ll

12 = Wi2+min{c‘ii+C221 = 7

12 = 1
*^23 = P3+n/22+>V33 = P3+^3+'^22 = 3
^23 = W23+min{c'22+C33} =3

f'23 = 3
n^34 = P4+n’33+^'44 = P4 ■'”^4 "^n^33 = 3

C34 = W34-l-min{C33-|-C44 ) = 3
^■34 = 4

Knowing and 0<z < 4 we can again use Eqs. (10.3) and (10.4) to
compute w,/+2, ^f.i+2 0<?<3.
c,.i+2’’ ^i.i+2’ 0<i<3. repeat this process until we obtain
Wo4, Co4’ ^04- The table of Eigure 10.6 shows the results of this computation. From
the table, we see that cq^ = 32 is the minimal cost of a binary search tree for to ^4.
The root of tree Tq^ is a2- Hence, the left subtree is Tq] and the right subtree 724- Tgi
has root Oj and subtrees Too and Tn. T24 has root a^', its left subtree is therefore T22
and right subtree Thus, with the data in the table it is possible to reconstruct
(Figure 10.7). □
Example 10.2 illustrates how we use Eq.(10.4) to determine the c’s and r’s, and
how to reconstruct T^n knowing the r’s. Let us examine the complexity of the function
that evaluates the c’s and r’s. The evaluation function described in Example 10.2
requires us to compute c,y for (J - z) = 1, 2, • • • , n in that order. When j - i = m there
are n-m + 1 Cy’s to compute. To compute each of these C/y’s we must find the
minimum of m quantities (see Equation (10.4)). Hence, we can compute each such Cjj in
O(m) time. Therefore, the total time for all Cj/s with 7 - z = m is 0(nm - m^). The total
time to evaluate all the Cjj's and rjfs is:

n
y (nm — m^) = O(n^)
m=i

Actually we can do better than this by using a result attributed to D. E. Knuth. He

states that we can find the optimal / in Eq.(10.4) by limiting the search to the range
r,y_] </<r/^.i y. In this case, the computing time become.s O(n^) (Exercise 3). The
function ohst (Program 10.1) uses this result to obtain the values of W/y, r,y, and Cjj, 0 < i
< j < n in 0(^7^) time. We may construct the actual tree, Tq,,, from the values of rjj in
478 Search Structures

i! 00 2 3 1 1 W44 1
0 0 c 0 C 0 r44 0
R °° 0 R 0 0 R 23 0 0
00 22 33 44
U
” 01 8 U 7 “ 23 3 W 34 3
12
8 C 7 3 3
R 01 12 R 23
2 01 1 R 2 23 3 " 34 4
12
u 12 U 13 9 5
02
c 19 C 13 12 8
02 R 24
R 1 R 13 2 3
02 24
W 03 = 14 U 14 11
= 25 C 14 19
R 03 = 2 R 14 2

W 04 16
C 04 32
04 2

Computation is carried out row-wise from row 0 to row 4

Figure 10.6: Computation of C04 and ro4.

for

do void

while

Figure 10.7: Optimal search tree for Example 10.2

O(n) time. We leave this as an exercise. The data types used by obst are:

ttdefine MAX—SIZE 200 max

*
/ # of ids plus /
*
1
ttdefine MAX-CHAR 30 max
*
/ characters/id
/
*
*
/ set of identifiers ■^ /
char words[MAX-SIZE][MAX-CHAR] , ptr = words[0];
int q[MAX-SIZE] ;
int p[MAX-SIZE] ;
int cost[MAX-SIZE] [MAX-SIZE] ;
 optimal Binary Search Trees 479

int root[MAX-SIZE][MAX-SIZE] ;
int weight[MAX-SIZE][MAX-SIZE] ;
int n; /■^ number of identifiers

void obstdnt p[], int q[], int cost [] [MAX—SIZE] ,

int root[] [MAX—SIZE] , int weight[] [MAX—SIZE] , int n)
{
given n distinct identifiers a[l] ... a[n] and
probabilities p[l] ... p[n], and q[0] ... q[n] compute
the cost c[i][j] of the optimal binary search tree for
a [i] ... a[j], 1 < z < 7 < n. Also compute the weight
and root of the tree */
int i,j,k,m,min,minpos ;
/■^ initialize 0 and 1 node trees
for (i = 0; i < n; i++) {
weight[i][i] = q[i];
root[i] [i] 0;
cost [i] [i] 0;
cost[i] [i + 1] = weight[i] [i + 1]
q[i] + q[i+l] + p[i+l];
root[i] [ i + 1] = i + 1;
}
weight [n] [n] = q[n]
root[n][n] 0;
cost[n][n] 0;
*
/ compute remaining diagonals */
for (m = 2; m < n; m++)
for (i 0; . n-m; i + +} {
j = i + m;
weight[i] [j] = weight[i][j-l] + p[j] + q[j];
k = knuth—min{cost,root,i,j);
/★ knuth—min returns a value, k,
k. in the range
root[i][j-l] to root[i+1][j], that minimizes
cost[i][k-1] + cost[k][j] */
cost[i][j] = weight[i][j] + cost[i][k-1]
+ cost[k][j];
root[i][j] - k;
}
!

Program 10.1: Function to find an optimal binary search tree

480 Search Structures

EXERCISES

1. (a) Prove by induction that if T is a binary tree with n internal nodes, I its inter­
nal path length, and E its external path length, then E = 1 + 2n, n>Q.
(b) Using the result of (a), show that the average number of comparisons 5 in a
successful search is related to the average number of comparisons, u, in an
unsuccessful search by the formula:
5 = (1 + i/n}u ~ 1, n >1
2. Using function obst, compute Wy, rij, and Cq, 0 < i < y < 4 for the identifier set {a 1,
02, a^, 04} = (else, malloc, printf, scanf) with pi = 1/20, p2 = 1/5, p3 = 1/10,
P4 = 1/20, ^0 = 1/5, = 1/ZO, q2 = 1/5, ^3 = 1/2Q, q4 =■ 1/20. Using the rfs,
construct the optimal binary search tree.
3. (a) Complete function obst by providing the code for the knuth-min function.
(b) Show that the computing time of obst is 0{ri^}.
(c) Write an algorithm to construct the optimal binary search tree given the
roots rij, 0 < i < j < n. Show that this can be done in Q{n} time.
4. Since often only the approximate values of the p’s and q's are known, it is just as
meaningful to find a binary search tree that is nearly optimal; that is, its cost. Eq.
(10.1), is almost minimal for the given p’s and ^’s. This exercise explores an
O(n log n} algorithm that creates nearly optimal binary search trees. The search
tree heuristic we will study is:

Choose the root such that | ^0,^-1 - ^k,n\ small as possible. Repeat this
function to find the left and right subtrees of aj^.
Using this heuristic obtain the resulting binary search tree for the list of
Exercise 2. What is its cost?
(b) Write a C algorithm implementing the above heuristic. Your algorithm
should have time complexity O(ai log n).

An analysis of the performance of this heuristic may be found in the paper by

Melhorn.

10.2 AVL TREES

We also may maintain dynamic tables as binary search trees. In Chapter 5, we discussed
how to insert elements into and delete them from binary search trees. Figure 10.8 shows
the binary search tree obtained by entering the months January to December, in that
order, into an initially empty binary search tree. We used add~node (Program 5.18).
The maximum number of comparisons needed to search for any identifier in the
tree of Figure 10.8 is six (for November}. The average number of comparisons is (1 for
January + 2 each for February and March + 3 each for April, June, and May + • • • + 6
for November} = 42/12 = 3.5. If we enter the months into the tree in the order July,