This article deals with the implementation and empirical testing of a method to achieve *practical perfect hashing*. The method was devised by G.V. Cormack, R.N.S. Horspool and M. Kaiserwerth, and was published in *The Computer Journal* (Vol. 28, No. 1, 1985, pp. 54-58). The paper can be downloaded from the web at http://comjnl.oxfordjournals.org. The code described in this article is a C# version of a Turbo Pascal program that I wrote in 1990 when I was teaching at the Computer Sciences Department of the University of Texas at Austin. The Pascal code is my solution to Programming Assignment 10.2 from my unpublished textbook *Applied Algorithms and Data Structures*.

The main goal of the implementation of the method was to determine in an empirical way to what extent its authors’ claims were justified. The following description highlights the major points of the paper and adds some practical information not provided by the authors, but the reader is urged to read the paper in order to be thoroughly familiar with the data structures, and the insertion and retrieval algorithms.

The algorithms described by Cormack, Horspool and Kaiserwerth use a *family* of hash functions denoted by

Where *i* is the index of a particular hash function, *k* is a numerical key, and *r* is a range (or interval) of consecutive elements in a data array. In mathematical terms, the *i*th hash function can be described as

,

That is, the hash function maps a tuple < *k*, *r* > into a unique number in the interval [ 0, *r* ). In the actual implementation, Cormack, Horspool and Kaiserwerth found that the general function

worked well if the *implicit* assumption *k* >> 2*i* + 100*r* +1 was satisfied. Observe that the index *i* of each hash function is an argument to the general function.

The elements of the Header Table (denoted by *H*) are triples < *i*, *r*, *p* >, where *i* is the index of a hash function, *r* is the size of a range of elements in the Data Table (denoted by *D*), and *p* is the index the first element of such a range in the Data Table. The size of the Header Table, *S*, must be a prime number. In general, the elements (or *records*) of the Data Table consist of a *key* field and additional data fields.

Both the insertion and retrieval algorithms depend on the *conversion* of a record’s *key* field into a numerical key *k*, which is used as the first argument to the hash functions. If the keys are alphanumeric strings, the first step in the implementation of these algorithms is to figure out a way to derive a *large* numerical value from the characters in a key. The simplest way to achieve this is to consider the characters as if they were “digits” in a positional number system (by using their ASCII codes as their numerical equivalents) and to multiply them by weights that yield reasonably-distributed “random” numbers having almost no common factors. For example, the weights could be prime numbers.

Assume that a function `Int64 KeyToK( string key )`

is available to compute the value of *k* that corresponds to an alphanumeric key, and that the family of hash functions is implemented by a function `int H( int i, Int64 k, int r )`

. Once the alphanumeric key has been converted to a numerical key *k*, the value of *k* is used to compute indices *x* and *y* into tables *H* and *D* respectively as follows:

*H*[ *x* ] contains a reference to a Header Table element and *D*[ *y* ] contains a reference to a Data Table element. The dots in the formula to compute *y* correspond to the C# field-access operator, or just the dot operator. (Observe that the hash function (H) and the Header Table *H* are not the same thing.) Given these definitions, the insertion and retrieval algorithms can be described in pseudo-code in a little more precise fashion than the one provided by Cormack, Horspool and Kaiserwerth.

## Insertion Algorithm

For the insertion of data records, it is assumed that each element of the Header Table *H*[ *j* ], for 0 ≤ *j* < *S*, was initialized with a reference to a triple < *i*, *r*, *p* >, where *i* = *r* = *p* = 0. In addition, each element of the Data Table must have been initialized as free, which is signaled by a `NULL`

reference.

To insert the record < *key*, *data* >:

k = KeyToK( key );
x = k % S;
< i, r, p > = H[ x ];
if ( r == 0 ) {
y = index of any free element in D;
H[ x ] = reference to < 0, 1, y >;
D[ y ] = reference to < key, data >;
}
else {
< kj, dj > = D[ p + j ];
Find an m such that the r + 1 values
h( m, kj, r+1 ), 0 <= j < r,
and h( m, k, r+1 )
are all distinct;
y = index of the first r + 1 consecutive free slots in D;
H[ x ] = < m, r+1, y >;
D[ y + h( m, k, r+1 ) ] = reference to < key, data >;
for ( j = 0; j < r; ++j )
move < kj, dj > to D[ y + h( m, kj, r+1 ) ];
Mark the r elements D[ p ] ... D[ p + r – 1 ] as free;
}

### Notes on the Insertion Algorithm

- The computation
`x = k % S`

determines a group of records in the Data Table *D*.
All records whose keys hash to the same value of `x`

are stored as a contiguous group in *D*.

The element referenced by `H[ x ]`

contains the starting index for the group (`p`

), the size of the group (`r`

), and a parameter (`i`

) to compute the second hash index.

A group may start at an arbitrary position in *D*.

- The hash function
`H( i, k, r )`

yields the offset of the desired record within the group.
As new records are inserted, groups grow in size.

When the size of a group increases, a new hash function `H<sub>m</sub>`

must be found, and new storage in *D* must be found for the group. The details of this storage management are omitted from the algorithm. Groups could be shifted down to make space where is needed, which is a *very expensive* operation. Alternatively, it would be possible to use another area of memory to move the groups and use first-fit or best-fit memory management to keep track of them.

## Retrieval Algorithm

k = KeyToK( akey );
x = k % S;
< i, r, p > = H[ x ];
if ( r == 0 )
there is no record with akey
else {
y = p + h( i, k, r );
< key, data > = D[ y ];
if ( key and akey are equal )
the record with akey has been found
else
there is no record with akey
}

## Implementation in C#

As mentioned before, the C# implementation of practical perfect hashing was based on a Turbo Pascal program written in 1990. The Pascal program was implemented by means of a powerful strategy of synthesis, namely *wishful thinking*. This strategy has been amply demonstrated by Harold Abelson and Gerald Jay Sussman in their masterpiece *Structure and Interpretation of Computer Programs* (The MIT Press, 1985, p. 75; Second Edition, 1996, p. 84), and is equivalent to the programming technique known as top-down design: to solve a problem, start with a top-level function and decompose it into auxiliary functions (wishing they were available), each of them solving a single sub-problem. To finish the implementation repeat the process on each of those functions. I will describe the C# implementation as a console application following this pattern.

## Constants and Fundamental Data Structures

To begin with, it is convenient to define some constants to be used throughout the code. They are defined as follows.

namespace PracticalPerfectHashing
{
public static class Constants
{
public static Int64
s = 1009,
n = 908;
public static Int16
thr = Int16.MaxValue;
public static int
maxL = 14,
avgL = 8,
fail = -1,
nPr = 6,
nPr_1 = 5;
}
}

The constants `maxL`

and `avgL`

are not strictly necessary because the C# code uses strings instead of the character arrays used in the Pascal code. I kept them to verify that both implementations produce the same results. The constants `nPr`

and `nPr_1`

are related to an array of prime numbers, which are used as weights when converting an alphanumeric key to a numerical value *k*.

Next, it is necessary to define the data structures for the elements of the Header Table and of the Data table.

namespace PracticalPerfectHashing
{
public class HeaderElement
{
private int i, r, p;
public HeaderElement( int _i, int _r, int _p )
{
i = _i; r = _r; p = _p;
}
public HeaderElement( HeaderElement hdrElem )
{
i = hdrElem.I; r = hdrElem.R; p = hdrElem.P;
}
public int I { get { return i; } set { i = value; } }
public int R { get { return r; } set { r = value; } }
public int P { get { return p; } set { p = value; } }
}
}
namespace PracticalPerfectHashing
{
public class DataElement
{
private Int64 k;
private string key;
public DataElement( Int64 _k, string _key )
{
k = _k;
key = String.Copy( _key );
}
public Int64 K { get { return k; } }
public string Key { get { return key; } }
}
}

Hereafter, the class `Program`

resides within the `PracticalPerfectHashing`

namespace, and all the functions are methods of the `Program`

class.

## Class Program and Main Function

The class `Program`

defines the global variables to be used: the Header Table, the Data Table, the array of prime numbers and some counters to report statistics. The top-level `Main`

function drives the whole computation.

class Program
{
public static HeaderElement[] header;
public static DataElement[] data;
public static int[] prime;
public static int mMax, mSum,
wordSum,
collSum,
failSum,
nomvSum;
public static void Main( string[] args )
{
Initialize();
LoadTable();
ShowDataTable();
ReportStatistics();
TestRetrieve();
}

Function `Initialize`

takes care of initializing the Header and Data tables, as described above, as well as the array of prime numbers and the counter variables.

private static void Initialize()
{
int i;
header = new HeaderElement[ Constants.s ];
for ( i = 0; i < Constants.s; ++i )
{
header[ i ] = new HeaderElement( 0, 0, 0 );
}
data = new DataElement[ Constants.n ];
for ( i = 0; i < Constants.n; ++i )
{
data[ i ] = null;
}
prime = new int[ Constants.nPr ];
prime[ 0 ] = 2; prime[ 1 ] = 3; prime[ 2 ] = 5;
prime[ 3 ] = 7; prime[ 4 ] = 11; prime[ 5 ] = 13;
mMax = mSum = wordSum = collSum = failSum = nomvSum = 0;
}

The definitions of functions `ShowDataTable`

, `ReportStatistics`

and `TestRetrieve`

will be given at the end of this section. Function `LoadTable`

reads words from a text file and, for each word, calls function `Store`

, which implements the insertion algorithm. The words in the text file are assumed to occur one per line without repetitions.

private static void LoadTable()
{
string fName, key;
FileStream fs;
StreamReader sr;
int p;
Console.Write( "Input file? " );
try
{
fName = Console.ReadLine();
Console.WriteLine( fName );
fs = new FileStream( fName, FileMode.Open );
sr = new StreamReader( fs );
while ( !sr.EndOfStream )
{
key = sr.ReadLine();
++wordSum;
p = Store( key );
if ( p == Constants.fail )
{
Console.WriteLine(
String.Format( " Failure to store '{0} '\n", key ) );
++failSum;
}
}
sr.Close();
fs.Close();
}
catch ( Exception exc )
{
Console.WriteLine();
Console.WriteLine( exc.Message );
Console.WriteLine();
Console.WriteLine( exc.StackTrace );
}
}

Observe that function `LoadTable`

uses a `try-catch`

clause in order to report possible exceptions. If an exception occurs its message is reported, followed by a printout of the stack trace for debugging purposes.

Aside from the reporting code (calls to `Console.WriteLine`

, and `ReportCollision`

) function `Store`

implements the insertion algorithm as described above. It relies on several auxiliary functions whose names reflect the description of the algorithm in pseudo-code: `KeyToK`

, `FindCfreeSlots`

, `FindRp1distinctValues`

, the general hash function `H`

, `Install`

, and `ResetDataPtr`

. The definition of function `ShowData`

is given with the description of the functions dealing with the retrieval algorithm.

private static int Store( string key )
{
int x, y, m, j, offset;
HeaderElement irp;
Int64 k, kj;
k = KeyToK( key );
x = (int)( k % Constants.s );
irp = new HeaderElement( header[ x ] );
if ( irp.R == 0 )
{
y = FindCfreeSlots( 1 );
if ( y != Constants.fail )
{
header[ x ].P = y;
header[ x ].I = 0;
header[ x ].R = 1;
Install( k, key, ref data[ y ] );
ShowData( y );
return y;
}
else return Constants.fail;
}
else
{
ReportCollision( irp, k, key );
m = FindRp1distinctValues( irp.P, irp.R, k );
if ( m != Constants.fail )
{
mSum += m;
if ( m > mMax )
mMax = m;
y = FindCfreeSlots( irp.R + 1 );
if ( y != Constants.fail )
{
header[ x ].P = y;
header[ x ].I = m;
header[ x ].R = irp.R + 1;
offset = H( m, k, irp.R + 1 );
Console.WriteLine( "\ty = {0}, offset = {1}", y, offset );
Console.WriteLine(
String.Format( "\tinstalling {0} at y + off = {1}\n",
key, y + offset ) );
Install( k, key, ref data[ y + offset ] );
ShowData( y + offset );
for ( j = 0; j < irp.R; ++j )
{
if ( data[ irp.P + j ] != null )
{
kj = data[ irp.P + j ].K;
int index = y + H( m, kj, irp.R + 1 );
Console.WriteLine(
String.Format(
"\tresetting data from irp.P + j = {0} to index = {1}",
irp.P + j, index ) );
ResetDataPtr( index, irp.P + j );
}
}
Console.WriteLine();
return y + offset;
}
else return Constants.fail;
}
else return Constants.fail;
}
}

Function `KeyToK`

implements the conversion of an alphanumeric key into a number (`num`

) which corresponds to the numeric key *k*. It uses in a circular fashion the elements from the array of prime numbers as weights to be multiplied by the ASCII codes of successive characters from the key. If the length of the key is less than `Constants.maxL`

, the function “pads” the sum using the ASCII code of a blank space as the weight. Finally, if the number calculated is less than `Constants.thr`

(i.e., the number is too small) that constant is added to it (cf. the shifting of the value of *k* on page 54 of the original paper).

private static Int64 KeyToK( string key )
{
int i, j, l, md;
Int64 num;
l = key.Length;
if ( l <= Constants.avgL )
{
md = Constants.nPr;
}
else
{
md = Constants.nPr / 2;
}
j = 0;
num = 0;
for ( i = 0; i < l; ++i )
{
num = prime[ j ] * num + (int)( key[ i ] );
j = ( j + 1 ) % md;
}
for ( i = l; i < Constants.maxL; ++i )
{
num += prime[ j ] * ( (int)' ' );
j = ( j + 1 ) % md;
}
if ( num < Constants.thr )
{
num += Constants.thr;
}
return num;
}

The original pseudo-code description of the retrieval algorithm contains the line (broken into four lines above) “Find an` m `

such that the` r + 1 `

values `h( m, k<sub>j</sub>, r+1 ), 0 <= j < r`

, and` h( m, k, r+1 ) `

are all distinct”. Function `FindRp1distinctValues`

is the implementation of such a line! This function relies on the implementation of singly-linked lists where insertions occur at the end. Instead of using the standard generic `List`

class from C#, I used my own implementation of generic singly-linked lists (plus a couple of utility functions) because it offers some interesting operations. The generic singly-linked list class (`Glist`

) is implemented in file *Glist.cs* and the utility functions are in file *Util.cs*. For brevity’s sake, I will not describe them.

private static int FindRp1distinctValues( int p, int r, Int64 k )
{
int c, j, v, rp1, m;
Int64 kj;
Glist<int> list;
bool eqKeys;
Console.WriteLine( String.Format( "\tFindRp1distinctValues == {0}", r + 1 ) );
eqKeys = false;
j = 0;
while ( j < r && !eqKeys )
{
if ( data[ p + j ] != null )
{
eqKeys = k == data[ p + j ].K;
}
++j;
}
if ( eqKeys )
{
Console.Write( "\n###" );
return Constants.fail;
}
else
{
c = 0;
m = 1;
list = new Glist<int>();
list.ToStringNodeItem = Util.IntToString;
list.EqualItems = Util.EqualInts;
rp1 = r + 1;
while ( m < Int16.MaxValue && c < rp1 )
{
for ( j = 0; j <= r - 1; ++j )
{
if ( data[ p + j ] != null )
{
kj = data[ p + j ].K;
v = H( m, kj, rp1 );
if ( list.InsertUnique( v ) )
{
++c;
}
else
{
c = 0;
}
}
}
if ( c == r )
{
v = H( m, k, rp1 );
if ( list.InsertUnique( v ) )
{
++c;
}
}
if ( c < rp1 )
{
c = 0;
++m;
list.Empty();
}
}
Console.WriteLine( String.Format( "\tm == {0}", m ) );
if ( c == rp1 )
{
list = null;
return m;
}
else
{
return Constants.fail;
}
}
}

Function `FindCfreeSlots`

attempts to find `c`

consecutive free (i.e., `NULL`

) elements in the Data Table. If it finds them, it returns the starting index of the range; otherwise it returns failure.

private static int FindCfreeSlots( int c )
{
int i = 1, cc = 0;
while ( i <= Constants.n && cc < c )
{
if ( data[ i ] == null )
{
++cc;
}
else
{
cc = 0;
}
++i;
}
if ( cc == c )
{
return i - cc;
}
else
{
return Constants.fail;
}
}

Function `H`

implements the general hash function as described in the original paper by Cormack, Horspool and Kaiserwerth.

private static int H( int i, Int64 k, int r )
{
Int64 a = 2 * i + 100 * r + 1;
return (int)( ( k % a ) ) % r;
}

Function `Install`

simply creates a new `DataElement`

instance somewhere in the Data Table. Observe that the element in the Data Table is passed by reference. (See the calls to this function.)

private static void Install( Int64 kVal, string iKey, ref DataElement dp )
{
dp = new DataElement( kVal, String.Copy( iKey ) );
}

Function `ResetDataPtr`

“moves” an element of the Data Table from one index (`source`

) to another (`dest`

) and sets the source element to `NULL`

. The movement is accomplished by changing a reference to a `DataElement`

at the `dest`

index. The function will not “move” to a non-`NULL`

`dest`

element nor from an element to itself.

private static void ResetDataPtr( int dest, int source )
{
if ( dest != source )
{
if ( data[ dest ] != null )
{
Console.WriteLine(
String.Format( "\tcannot move data[ {0} ] ({1}) to data[ {2} ] ({3})",
source, data[ source ].Key, dest, data[ dest ].Key ) );
++nomvSum;
}
else
{
Console.WriteLine( String.Format( "\t{0,14} moved from {1,3} to {2,3}",
data[ source ].Key, source, dest ) );
data[ dest ] = data[ source ];
data[ source ] = null;
}
}
else
{
Console.WriteLine(
String.Format( "\tmoving data[ {0} ] ({1}) into itself would make it null",
source, data[ source ].Key ) );
}
}

Function `ReportCollision`

simply displays information about a collision. When a collision occurs, the insertion algorithm attempts to resolve it (see function `Store`

above).

private static void ReportCollision( HeaderElement irp, Int64 k, string key )
{
Console.WriteLine( "collision:" );
Console.WriteLine(
String.Format( "\t<i, r, p> = <{0,3}, {1,3}, {2,3}> : {3,10} == {4}",
irp.I, irp.R, irp.P, k, key ) );
++collSum;
}

Functions `ShowDataTable`

and `ReportStatistics`

display, respectively, the non-`NULL`

elements of the Data Table, and the values of the global counter variables.

private static void ShowDataTable()
{
int wCount = 0;
Console.WriteLine( "\n\nData Table:\n(entries not listed are null)\n\n" );
for ( int i = 0; i < Constants.n; ++i )
{
if ( data[ i ] != null )
{
Console.WriteLine( String.Format( "{0,4}: {1,20}", i, data[ i ].Key ) );
++wCount;
}
}
Console.WriteLine( String.Format( "\n{0} data items stored\n\n", wCount ) );
}
private static void ReportStatistics()
{
float avgM;
if ( collSum > 0 )
{
Console.WriteLine( String.Format( "\n{0} words read", wordSum ) );
Console.WriteLine( String.Format( "{0} collisions", collSum ) );
if ( failSum > 0 )
{
Console.WriteLine( String.Format( "{0} failures", failSum ) );
}
if ( nomvSum > 0 )
{
Console.WriteLine( String.Format( "{0} failed moves\n\n", nomvSum ) );
}
Console.WriteLine( String.Format( "\nMaximum 'm' == {0}", mMax ) );
avgM = ( (float)mSum ) / ( (float)collSum );
Console.WriteLine( String.Format( "Average 'm' == {0:######.###}\n", avgM ) );
}
}

After all the words from the input file have been processed, function `TestRetrieve`

continuously prompts the user for search keys. For each key, this function calls function `Retrieve`

, which is a straightforward implementation of the retrieval algorithm. If the key is found, function `ShowData`

is called to display it.

private static void TestRetrieve()
{
string key;
int p;
bool go;
Console.WriteLine();
do
{
Console.Write( "Search key? " );
key = Console.ReadLine();
if ( ( go = !String.IsNullOrWhiteSpace( key ) ) )
{
p = Retrieve( key );
if ( p == Constants.fail )
{
Console.WriteLine(
String.Format( "\tThe key '{0}' does not exist", key ) );
}
else
{
Console.Write( "\t" ); ShowData( p );
}
}
} while ( go );
}
private static void ShowData( int i )
{
if ( data[ i ] == null )
{
Console.WriteLine( String.Format( "data[ {0,5} ] == null", i ) );
}
else
{
Console.WriteLine( String.Format( "data[ {0,4} ]:{1,10} == {2}",
i, data[ i ].K, data[ i ].Key ) );
}
}
private static int Retrieve( string key )
{
int x, y;
Int64 k;
k = KeyToK( key );
x = (int)( k % Constants.s );
if ( header[ x ].R == 0 )
{
return Constants.fail;
}
else
{
y = header[ x ].P + H( header[ x ].I, k, header[ x ].R );
if ( String.Equals( key, data[ y ].Key ) )
{
return y;
}
else
{
return Constants.fail;
}
}
}

## Testing of the Insertion and Retrieval Algorithms

To test the insertion and retrieval algorithms I used two text files, `maya0.wr`

and `maya1.wr`

, which contain Chontal Maya words (one word per line without repetitions). These are the files I used to test the original Turbo Pascal code. When tested with these files, the C# code produced exactly the same results that the Pascal code produced. The files are in the *bin\Debug* subdirectory of the C# project in *PPH_C#.zip*, and they should remain there when the C# program is run as a console application. The program must be built and run under Visual Studio 2010.

As can be verified by running the C# program either from the Visual Studio 2010 IDE or from a stand-alone command prompt in the *bin\debug* subdirectory, the output is rather long, and I will not show it here in its entirety. The following are excerpts from the output at interesting points.

### Output up to the point of the second collision

Input file? maya0.wr
data[ 1 ]: 2384129 == tichel
data[ 2 ]: 13818855 == paxbolon
data[ 3 ]: 4272418 == chontal
data[ 4 ]: 51719 == uhal
data[ 5 ]: 14418088 == xachilci
data[ 6 ]: 50167 == hain
data[ 7 ]: 49563 == bane
data[ 8 ]: 35851 == ya
data[ 9 ]: 2458317 == uthani
data[ 10 ]: 163489 == ahlec
data[ 11 ]: 52065 == tuba
data[ 12 ]: 49622 == caha
data[ 13 ]: 2408818 == ukatan
data[ 14 ]: 4466689 == hochlec
data[ 15 ]: 35836 == ta
data[ 16 ]: 37486 == hun
data[ 17 ]: 4746122 == uchelen
data[ 18 ]: 190713 == tupam
data[ 19 ]: 2373215 == uchame
data[ 20 ]: 2466159 == utohal
data[ 21 ]: 51616 == than
data[ 22 ]: 165325 == cheix
data[ 23 ]: 185781 == uhahi
data[ 24 ]: 2257706 == nadzon
data[ 25 ]: 35847 == ui
data[ 26 ]: 35844 == ti
data[ 27 ]: 37305 == cah
data[ 28 ]: 4807506 == tixchel
data[ 29 ]: 51799 == xach
data[ 30 ]: 12394491 == acahoche
data[ 31 ]: 2234174 == dzibil
data[ 32 ]: 2280145 == mexico
data[ 33 ]: 3924939 == chamionihi
data[ 34 ]: 4452888 == unacahibal
data[ 35 ]: 52362 == ynay
data[ 36 ]: 35850 == vi
data[ 37 ]: 187071 == ukaua
data[ 38 ]: 14601319 == upayolel
data[ 39 ]: 2406242 == ukabal
data[ 40 ]: 4815944 == uillayl
data[ 41 ]: 5035468 == yucatan
data[ 42 ]: 35856 == tu
data[ 43 ]: 13378615 == lahunpel
data[ 44 ]: 2416070 == ukinil
data[ 45 ]: 35604 == u
data[ 46 ]: 2170893 == hainob
data[ 47 ]: 2476342 == yithoc
data[ 48 ]: 37333 == cha
data[ 49 ]: 14850963 == yithocob
data[ 50 ]: 50868 == naua
data[ 51 ]: 2407069 == quiuit
data[ 52 ]: 52198 == tuua
data[ 53 ]: 195706 == yucul
data[ 54 ]: 3884049 == canoahaula
data[ 55 ]: 2345182 == tacpam
data[ 56 ]: 49588 == cabi
data[ 57 ]: 162758 == cahai
data[ 58 ]: 50216 == ayan
data[ 59 ]: 37281 == abi
data[ 60 ]: 14588767 == upakibal
data[ 61 ]: 2207683 == uhatantel
data[ 62 ]: 65267358 == nucxibilbaob
data[ 63 ]: 51824 == ukal
data[ 64 ]: 37709 == yol
data[ 65 ]: 195499 == yubin
data[ 66 ]: 5073584 == yuuilan
data[ 67 ]: 2421484 == ybache
data[ 68 ]: 49630 == cahi
data[ 69 ]: 51443 == tali
data[ 70 ]: 2417997 == umamob
data[ 71 ]: 2433441 == upapob
data[ 72 ]: 11638355 == ahauonihobi
data[ 73 ]: 2512145 == uchecte?i
data[ 74 ]: 14742813 == uthaniob
data[ 75 ]: 186862 == ukaba
data[ 76 ]: 1956654 == chacbalam
data[ 77 ]: 2463834 == tutzin
data[ 78 ]: 2122400 == analay
data[ 79 ]: 4356814 == auxaual
data[ 80 ]: 135379228 == cu?umil
data[ 81 ]: 2375949 == uchuci
data[ 82 ]: 162387 == cabil
data[ 83 ]: 162443 == cabob
data[ 84 ]: 37632 == vij
data[ 85 ]: 50729 == hoti
data[ 86 ]: 188824 == umole
data[ 87 ]: 14129506 == tanodzic
data[ 88 ]: 14641431 == unucalob
collision:
<i, r, p> = < 0, 1, 19> : 2274333 == huncha
FindRp1distinctValues == 2
m == 1
y = 89, offset = 0
installing huncha at y + off = 89
data[ 89 ]: 2274333 == huncha
resetting data from irp.P + j = 19 to index = 90
uchame moved from 19 to 90
data[ 19 ]: 179153 == paxoc
data[ 91 ]: 4369774 == uchantulib
collision:
<i, r, p> = < 0, 1, 37> : 4610527 == paxmulu
FindRp1distinctValues == 2
m == 6
y = 92, offset = 0
installing paxmulu at y + off = 92
data[ 92 ]: 4610527 == paxmulu
resetting data from irp.P + j = 37 to index = 93
ukaua moved from 37 to 93
data[ 37 ]: 2170837 == hainix
data[ 94 ]: 2466903 == utolob
data[ 95 ]: 14461822 == ulachuci
data[ 96 ]: 37636 == yai
data[ 97 ]: 2248884 == tuchadzic
data[ 98 ]: 49628 == ahau

### Output at the point where the program fails to insert a word

data[ 241 ]: 14760019 == uthuntel
data[ 252 ]: 2270713 == uuincilel
collision:
<i, r, p> = < 0, 1, 36> : 35850 == to
FindRp1distinctValues == 2
### Failure to store 'to'
data[ 253 ]: 35815 == ma
data[ 254 ]: 37641 == yan
collision:
<i, r, p> = < 0, 1, 108> : 2264290 == tuthanobi
FindRp1distinctValues == 2
m == 3
y = 255, offset = 0
installing tuthanobi at y + off = 255

### Output at the end of the execution

868: paxhochacchan
869: tamal
870: hum
868 data items stored
871 words read
287 collisions
3 failures
Maximum 'm' == 38
Average 'm' == 2.895

As can be seen, of the 287 collisions that occurred 3 could not be resolved, yielding a failure rate of 3/287 = 0.0104 or 1%. Thus, the empirical test suggests that the practical perfect hashing algorithm of Cormack, Horspool and Kaiserwerth is very effective.

### A few tests of the retrieval algorithm

Search key? data[ 32 ]: 2280145 == mexico
Search key? data[ 172 ]: 13818855 == paxbolon
Search key? The key 'foo' does not exist
Search key? The key 'bar' does not exist
Search key? data[ 41 ]: 5035468 == yucatan
Search key?

## C# Project Files

The project files for the C# implementation of practical perfect hashing are in *PPH_C#.zip*. Extract it to a suitable subdirectory of the Visual Studio 2010 `Projects`

directory and run the program as a console application.

## Original Pascal Code

For historical reasons, and for the interested reader, I have included the original Pascal code that I wrote in 1990. The code and the sample test files are in *PPH_PAS.zip*. The code can be built into an executable using Free Pascal (FPC), a free Pascal compiler that can be obtained from the web (the installation program is *fpc-2.6.4.i386-win32.exe*). With the default installation, the source code `PPH.PAS`

and the test files must be placed in the *C:\FPC\2.6.4\i386-win32* directory. Upon building, *PPH.exe* will be in the same directory, and can be run from a command prompt.