C# 中的实用完美哈希
5.00/5 (26投票s)
本文讨论了实现和实证测试一种实现实用完美散列的方法。
本文讨论了实现和实证测试一种实现实用完美散列的方法。该方法由 G.V. Cormack、R.N.S. Horspool 和 M. Kaiserwerth 设计，并发表在The Computer Journal (Vol. 28, No. 1, 1985, pp. 54-58) 上。可以在网上下载该论文，网址为 http://comjnl.oxfordjournals.org。本文介绍的代码是 Turbo Pascal 程序的 C# 版本，我于 1990 年在德克萨斯大学奥斯汀分校计算机科学系任教时编写。Pascal 代码是我未出版的教科书《应用算法与数据结构》的编程作业 10.2 的解决方案。
实现该方法的主要目标是以实证方式确定其作者的声明在多大程度上是合理的。以下描述强调了论文的主要观点，并补充了一些作者未提供但实用的信息，但仍建议读者阅读论文，以便全面了解数据结构以及插入和检索算法。
Cormack、Horspool 和 Kaiserwerth 描述的算法使用了一个散列函数族，表示为
其中 i 是特定散列函数的索引，k 是数值键，r 是数据数组中连续元素的范围（或区间）。用数学术语来说，第 i 个散列函数可以描述为
,
也就是说，散列函数将一个元组 < k, r > 映射到区间 [ 0, r ) 中的唯一数字。在实际实现中，Cormack、Horspool 和 Kaiserwerth 发现，当满足隐式假设 k >> 2i + 100r +1 时，通用函数
效果很好。请注意，每个散列函数的索引 i 都是通用函数的参数。
头表（表示为 H）的元素是三元组 < i, r, p >，其中 i 是散列函数的索引，r 是数据表（表示为 D）中元素范围的大小，p 是数据表中此类范围的第一个元素的索引。头表的大小 S 必须是一个素数。通常，数据表中的元素（或记录）包含一个键字段和其他数据字段。
插入和检索算法都依赖于将记录的键字段转换为数值键 k，该键用作散列函数的第一个参数。如果键是字母数字字符串，则在实现这些算法时，第一步是找出一种方法从键中的字符派生出一个大数值。实现此目的的最简单方法是将字符视为带权重的“数字”，在一个位置数字系统中（通过使用它们的 ASCII 码作为数值等效项），并乘以可以产生分布合理且几乎没有公因数的“随机”数字的权重。例如，权重可以是素数。
假设有一个函数 Int64 KeyToK( string key ) 用于计算与字母数字键对应的 k 值，并且散列函数族由函数 int H( int i, Int64 k, int r ) 实现。一旦字母数字键转换为数值键 k，k 的值将用于计算指向表 H 和 D 的索引 x 和 y，如下所示：
H[ x ] 包含对头表元素的引用，而 D[ y ] 包含对数据表元素的引用。计算 y 的公式中的点对应于 C# 的字段访问运算符，或者只是点运算符。（请注意，散列函数 (H) 和头表 H 是不同的。）有了这些定义，就可以比 Cormack、Horspool 和 Kaiserwerth 提供的更精确地用伪代码描述插入和检索算法。
插入算法
对于数据记录的插入，假设头表 H[ j ] 的每个元素（对于 0 ≤ j < S）都已初始化为指向一个三元组 < i, r, p >，其中 i = r = p = 0。此外，数据表的每个元素都必须初始化为空闲状态，这由 NULL 引用表示。
要插入记录 < 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 { // r != 0
< kj, dj > = D[ p + j ]; // for some j such that 0 <= j < r
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;
}
关于插入算法的说明
- 计算
x = k % S确定了数据表 D 中的一组记录。所有键散列到相同
x值的记录都存储在 D 中的连续组中。H[ x ]引用的元素包含该组的起始索引（p）、组的大小（r）以及用于计算第二个散列索引的参数（i）。组可以从 D 中的任意位置开始。
- 散列函数
H( i, k, r )生成所需记录在组内的偏移量。随着新记录的插入，组的大小会增加。
当组的大小增加时，必须找到一个新的散列函数 H<sub>m</sub>，并且必须为该组在 D 中找到新的存储空间。此存储管理的详细信息已从算法中省略。可以向下移动组以在需要的位置腾出空间，这是一个非常昂贵的操作。或者，可以使用另一个内存区域来移动组，并使用首次适应或最佳适应内存管理来跟踪它们。
检索算法
k = KeyToK( akey );
x = k % S;
< i, r, p > = H[ x ];
if ( r == 0 )
there is no record with akey
else { // r != 0
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
}
C# 实现
如前所述，C# 实现实用完美散列是基于 1990 年编写的 Turbo Pascal 程序。Pascal 程序是通过一种强大的综合策略实现的，即一厢情愿。Harold Abelson 和 Gerald Jay Sussman 在他们的杰作《结构与解释计算机程序》（MIT Press，1985 年，第 75 页；第二版，1996 年，第 84 页）中充分展示了这一策略，该策略等同于所谓的自顶向下设计编程技术：要解决问题，请从顶层函数开始，将其分解为辅助函数（假设它们可用），每个函数解决一个子问题。要完成实现，请对这些函数中的每一个重复此过程。我将以控制台应用程序的形式描述 C# 实现，遵循此模式。
常量和基本数据结构
首先，方便定义一些在代码中将使用的常量。它们定义如下。
namespace PracticalPerfectHashing
{
public static class Constants
{
public static Int64
s = 1009, // size of header table
n = 908; // maximum number of data items stored = 0.9 * s
public static Int16
thr = Int16.MaxValue; // threshold for small values of k
public static int
maxL = 14, // maximum length of alphanumeric data keys
avgL = 8, // average length of alphanumeric data keys
fail = -1, // value to signal failure to store data
nPr = 6, // size of array of prime numbers
nPr_1 = 5; // maximum index into array of prime numbers
}
}
常量 maxL 和 avgL 不是严格必需的，因为 C# 代码使用字符串而不是 Pascal 代码中使用的字符数组。我保留它们是为了验证两种实现是否产生相同的结果。常量 nPr 和 nPr_1 与素数数组相关，这些素数用作将字母数字键转换为数值 k 值时的权重。
接下来，有必要为头表和数据表的元素定义数据结构。
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; } }
}
}
此后，Program 类位于 PracticalPerfectHashing 命名空间内，并且所有函数都是 Program 类的成员函数。
Program 类和 Main 函数
Program 类定义了要使用的全局变量：头表、数据表、素数数组以及用于报告统计信息的几个计数器。顶层 Main 函数驱动整个计算。
class Program
{
public static HeaderElement[] header;
public static DataElement[] data;
public static int[] prime;
public static int mMax, mSum,
wordSum, // Total words read from source file
collSum, // Total number of collisions
failSum, // Total number of failures to store words
nomvSum; // Total number of failures to move words
// (to avoid overwriting)
public static void Main( string[] args )
{
Initialize();
LoadTable();
ShowDataTable();
ReportStatistics();
TestRetrieve();
}
Initialize 函数负责初始化头表和数据表（如上所述），以及素数数组和计数器变量。
private static void Initialize()
{
int i;
// Initialize header table
header = new HeaderElement[ Constants.s ];
for ( i = 0; i < Constants.s; ++i )
{
header[ i ] = new HeaderElement( 0, 0, 0 );
}
// Mark all cells in data table as free
data = new DataElement[ Constants.n ];
for ( i = 0; i < Constants.n; ++i )
{
data[ i ] = null;
}
// Initialize array of prime numbers
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;
}// Initialize
ShowDataTable、ReportStatistics 和 TestRetrieve 函数的定义将在本节末尾给出。LoadTable 函数从文本文件中读取单词，并为每个单词调用 Store 函数，该函数实现插入算法。文本文件中的单词假定每行一个，不重复。
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 );
}
}// LoadTable
请注意，LoadTable 函数使用 try-catch 子句来报告可能的异常。如果发生异常，将报告其消息，后跟堆栈跟踪的输出以供调试。
除了报告代码（对 Console.WriteLine 和 ReportCollision 的调用）外，Store 函数实现了上述插入算法。它依赖于几个辅助函数，这些函数的名称反映了算法在伪代码中的描述：KeyToK、FindCfreeSlots、FindRp1distinctValues、通用散列函数 H、Install 和 ResetDataPtr。ShowData 函数的定义随检索算法相关函数的描述一起给出。
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 // irp.R > 0
{
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 /* y == Constants.fail */ return Constants.fail;
}
else /* m == Constants.fail */ return Constants.fail;
}
}// Store
KeyToK 函数实现了将字母数字键转换为数字（num），该数字对应于数值键 k。它以循环方式使用素数数组的元素作为权重，乘以键的连续字符的 ASCII 码。如果键的长度小于 Constants.maxL，则该函数使用空格的 ASCII 码作为权重来“填充”总和。最后，如果计算出的数字小于 Constants.thr（即数字太小），则将其加上该常量（参见原始论文第 54 页的 k 值移位）。
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;
}// KeyToK
检索算法的原始伪代码描述包含一行（在上面分解为四行）“找到一个 m ，使得 r + 1 个值 h( m, k<sub>j</sub>, r+1 ), 0 <= j < r，以及 h( m, k, r+1 ) 都不同”。FindRp1distinctValues 函数就是这个功能的实现！该函数依赖于单链表的实现，其中插入发生在末尾。我使用了自己实现的泛型单链表（加上一些实用函数），而不是使用 C# 标准的泛型 List 类，因为它提供了一些有趣的操作。泛型单链表类（Glist）实现在文件 Glist.cs 中，实用函数实现在文件 Util.cs 中。为简洁起见，我将不作介绍。
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 // !eqKeys
{
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 // !list.InsertUnique( v )
{
c = 0;
}
}
}
if ( c == r )
{
v = H( m, k, rp1 );
if ( list.InsertUnique( v ) )
{
++c;
}
}
if ( c < rp1 )
{
c = 0;
++m;
list.Empty(); // list = null;
}
}
// m == Int16.MaxValue || c == rp1 // m == Int32.MaxValue || c == rp1
Console.WriteLine( String.Format( "\tm == {0}", m ) );
if ( c == rp1 )
{
// ShowList( p, 0, k, list );
list = null;
return m;
}
else // c < rP1
{
return Constants.fail;
}
}
}// FindRp1distinctValues
FindCfreeSlots 函数尝试在数据表中查找 c 个连续的空（即 NULL）元素。如果找到，它将返回该范围的起始索引；否则，它返回失败。
private static int FindCfreeSlots( int c )
{
int i = 1, cc = 0;
while ( i <= Constants.n && cc < c )
{
if ( data[ i ] == null )
{
++cc;
}
else // data[ i ] != null
{
cc = 0;
}
++i;
}
// i > Constants.n || cc == c
if ( cc == c )
{
return i - cc;
}
else // cc < c && i > Constants.n
{
return Constants.fail;
}
}// FindCfreeSlots
H 函数实现了 Cormack、Horspool 和 Kaiserwerth 原始论文中所述的通用散列函数。
private static int H( int i, Int64 k, int r )
{
Int64 a = 2 * i + 100 * r + 1;
return (int)( ( k % a ) ) % r;
}// H
Install 函数仅在数据表的某处创建一个新的 DataElement 实例。请注意，数据表中的元素是按引用传递的。（参见对该函数的调用。）
private static void Install( Int64 kVal, string iKey, ref DataElement dp )
{
dp = new DataElement( kVal, String.Copy( iKey ) );
}// Install
ResetDataPtr 函数将数据表的一个元素从一个索引（source）“移动”到另一个索引（dest），并将源元素设置为 NULL。移动是通过更改 dest 索引处的 DataElement 引用来实现的。该函数不会“移动”到非 NULL 的 dest 元素，也不会从一个元素移动到自身。
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 ) );
}
}// ResetDataPtr
ReportCollision 函数仅显示有关冲突的信息。发生冲突时，插入算法会尝试解决它（参见上面的 Store 函数）。
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;
}// ReportCollision
ShowDataTable 和 ReportStatistics 函数分别显示数据表的非 NULL 元素以及全局计数器的值。
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 ) );
}// ShowDataTable
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 ) );
}
}// ReportStatistics
处理完输入文件中的所有单词后，TestRetrieve 函数会持续提示用户输入搜索键。对于每个键，该函数会调用 Retrieve 函数，该函数是对检索算法的直接实现。如果找到键，则调用 ShowData 函数来显示它。
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 // p != Constants.fail
{
Console.Write( "\t" ); ShowData( p );
}
}
} while ( go );
}// TestRetrieve
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 ) );
}
}// ShowData
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 // header[ x ].R > 0
{
y = header[ x ].P + H( header[ x ].I, k, header[ x ].R );
if ( String.Equals( key, data[ y ].Key ) )
{
return y;
}
else // !String.Equals( key, data[ y ].Key )
{
return Constants.fail;
}
}
}// Retrieve
插入和检索算法的测试
为了测试插入和检索算法，我使用了两个文本文件 maya0.wr 和 maya1.wr，其中包含 Chontal Maya 单词（每行一个单词，不重复）。这些文件是我用来测试原始 Turbo Pascal 代码的文件。使用这些文件进行测试时，C# 代码产生的与 Pascal 代码完全相同的结果。这些文件位于 PPH_C#.zip 中 C# 项目的 bin\Debug 子目录中，并且在 C# 程序作为控制台应用程序运行时应保留在那里。程序必须在 Visual Studio 2010 下构建和运行。
通过从 Visual Studio 2010 IDE 或从 bin\debug 子目录中的独立命令提示符运行 C# 程序，可以验证输出相当长，我将在此不全部显示。以下是从输出中的有趣点的摘录。
第二次冲突前的输出
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
程序无法插入单词时的输出
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
执行结束时的输出
868: paxhochacchan 869: tamal 870: hum 868 data items stored 871 words read 287 collisions 3 failures Maximum 'm' == 38 Average 'm' == 2.895
可以看出，在发生的 287 次冲突中，有 3 次未能解决，失败率为 3/287 = 0.0104 或 1%。因此，实证测试表明 Cormack、Horspool 和 Kaiserwerth 的实用完美散列算法非常有效。
对检索算法的一些测试
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# 项目文件
实用完美散列 C# 实现的项目文件在 PPH_C#.zip 中。将其解压缩到 Visual Studio 2010 Projects 目录的合适子目录中，然后作为控制台应用程序运行程序。
原始 Pascal 代码
出于历史原因和为感兴趣的读者，我包含了 1990 年编写的原始 Pascal 代码。代码和示例测试文件在 PPH_PAS.zip 中。可以使用 Free Pascal (FPC) 构建代码以生成可执行文件，FPC 是一个免费的 Pascal 编译器，可以从网上获得（安装程序是 fpc-2.6.4.i386-win32.exe）。使用默认安装，源文件 PPH.PAS 和测试文件必须放在 C:\FPC\2.6.4\i386-win32 目录中。构建后，PPH.exe 将位于同一目录中，并且可以从命令提示符运行。