分离链接法（separate chaining）是解决哈希冲突的一种简单方法，其做法是将散列到同一个值的所有元素保留在一个表中。为方便起见，这些表都有表头。如果空间很紧，则更可取的方法是避免使用这些表头。本文假设关键字是前 10 个完全平方数并设散列函数就是 。（表的大小不是素数，用在这里是为了简单起见）。
为执行 Find ，我们使用散列函数来确定究竟考察哪个表。此时我们以通常的方式遍历该表并返回所找到的被查找项所在位置。为执行 Insert，我们遍历一个相应的表以检查该元素是否已经处在适当的位置（如果要插入重复元，那么通常要留出一个额外的域，这个域当重复元出现时增 1）。如果这个元素是个新的元素，那么或者插入到表的前端，或者插入到表的末尾，哪个容易就执行哪个。当编写程序的时候这是最容易寻找的一种。有时将元素插入到表的前端不仅因为方便，而且还因为新近插入的元素最有可能最先被访问。
实现分离链接法所需要的类型如下：
#ifndef _HashSep_H
struct ListNode;
typedef struct ListNode *Position;
struct HashTbl;
typedef struct HashTbl *HashTable;
HashTable InitializaTable( int TableSize );
void DestroyTable( HashTable H );
Postion Find( ElementType Key, HashTable H);
void Insert( ELementType Key, HashTable H );
ElementType Retrieve( Position P );
/* Routines such as Delete and MakeEmpty are omitted */
#endif /* _HashSep_H */
/* Place in the implementation file */
struct ListNode
{
ElementType Element;
Position Next;
};
typedef Position List;
/* List *TheList will be an array of lists, allocated later */
/* The lists use headers (for simplicity), though this wastes space */
struct HashTbl
{
int TableSize;
List *TheLists;
};
上面程式码中的 ListNode 结构与链式表声明相同。程式码中散列表结构包含一个链表数组（以及数组中的链表的个数），它们在散列表结构初始化时动态分配空间。此处的 HashTable 类型就是指向该结构的指针类型。
注意，TheList 域实际上是一个指向指向 ListNode 结构的指针的指针。如果不使用这些 typedef，那可能会相当混乱。
初始化函数如下：
HashTale
InitializaTable( int TableSize )
{
HashTable H;
int i;
/* 1 */ if(TableSize < MinTableSize)
/* 2 */ {
/* 3 */ Error("Table size too small") ;
return NULL;
}
/* Allocate table */
/* 4 */ H = malloc( sizeof( struct HashTbl ));
/* 5 */ if( H == NULL)
/* 6 */ FatalError( "Out of space!!!");
/* 7 */ H->TableSize = NextPrime( TableSize );
/* Allocate array of lists */
/* 8 */ H->TheLists = malloc( sizeof(list)*H->TableSize);
/* 9 */ if(H->TheLists == NULL )
/* 10 */ FatalError("Out of space!!!");
/* Allocate list headers */
/* 11 */for( i=0; i < H->TableSize; i++ )
{
/* 12 */ H->TheLists[i] = malloc(sizeof( struct ListNode));
/* 13 */ if(H->TheLists[i] == NULL)
/* 14 */ FatalError("Out of space!!!");
else
/* 15 */ H->TheLists[i]->Next = NULL;
}
/* 16 */return H;
}
它用到与栈的数组实现中相同的想法。第 4～6 行给一个散列表分配空间。如果空间允许，则 H 将指向一个结构，该结构包含一个整数和指向一个表的指针。第 7 行设置表的大小为一素数，而第 8～10 行则试图指定 List 的一个数组。由于 List 被定义为一个指针，因此结果为指针的数组。
假如 List 的实现不用表头，那么我们就可以到此为止了。但是我们使用了表头，因此必须给每个表分配一个表头并设置它的 Next 域为 NULL。这由第 11～15 行实现。当然，第 12～15 行可以用语句
H->TheLists[i] = MakeEmpty();
代替。虽然我们没有选择使用这条语句，但是因为该例中它胜过使程序尽可能自包含，所以它当然值得考虑。这个程序的一个低效之处在于第 12 行上的 malloc 执行了 H→TableSize 次。这可以通过在循环出现之前调用一次 malloc 操作
H->TheLists=malloc(H->TableSize*sizeof(struct ListNode));
代替第 12 行来避免。第 16 行返回 H。
对 Find(Key, H) 的调用将返回一个指针，该指针指向包含 Key 的那个单元。实现它的程序如下：
Position
Find( ElementType Key, HashTable H)
{
Postion P;
List L;
/*1*/ L = H->TheLists[( Key, H->TableSize)];
/*2*/ P = L->Next;
/*3*/ while( P!= NULL && P->Element != key)
/* Probably need strcmp!!*/
/*4*/ P = P->Next;
/*5*/ return P;
}
注意，第 2～5 行等同于链表执行的 Find 程序。记住，如果 ElementType 是一个字符串，那比较和赋值必须相应地使用 strcpm 和 strcpy 来进行。
下面是一个插入例程：
viod
Insert( ElementType Key, HashTable H)
{
Position Pos, NewCell;
List L;
/*1*/ Pos = Find(key, H);
/*2*/ if(Pos == NULL) /* Key is not found*/
{
/*3*/ NewCell = malloc(sizeof(struct ListNode));
/*4*/ if(NewCell == NULL)
/*5*/ FatalError("Out of space!!!");
else
{
/*6*/ L = H->TheLists[Hash(Key, H->TableSize)];
/*7*/ NewCell->Next = L->Next;
/*8*/ NewCell->ELement = key; /* Probably need strcpy! */
/*9*/ L->Next = NewCell;
}
}
}
如果要插入的项已经存在，那么我们就什么也不做；否则我们把它放到表的前端。该元素可以放在表的任何地方，此处这样做是最方便的。注意，插入到表的前端的程序基本上等同于使用链表实现 Push 的程序。
上面的例程写得多少有些不好，因为它计算了两次散列函数。多余的计算总是不好的，因此，如果这些散列例程真的构成程序运行时间的重要部分，那么这个程序就应该重写。
删除例程是链表中的删除操作的直接实现，如果在散列的诸例程中不包括删除操作，那么最好不要使用表头，因为使用表头不仅不能简化问题而且还要浪费大量的空间。
除了链表外，任何的方案都有可能用来解决冲突现象 —— 一棵二叉查找树甚至另外一个散列表均可胜任，但是我们期望如果表大，同时散列函数好，那么所有的表就应该短，这样就不至于进行任何复杂的尝试了。
我们定义散列表的装载因子（load factor） 为散列表中元素个数与散列表大小的比值。在本文的例子中，
。表的平均长度为
。执行一次查找所需要的工作是计算散列函数值所需要的常数时间加上遍历表所用的时间。再一次不成功的查找中，遍历的链接数平均为
（不包括最后的 NULL 链接）。成功的查找则需要遍历大约
个链接；它保证必然会遍历一个链接（因为查找是成功的），而我们也期望沿着一个表中途就能找到匹配的元素。这就指出，表的大小实际上并不重要，而装载因子才是重要的。分离链接散列的一般法则是使得表的大小尽量与预料的元素个数差不多（换句话说，让
）。因此，使表的大小是素数以保证一个好的分布，这也是一个好的想法。
关于对素数取模的好处，我们首先要知道素数是什么？素数（质数）即只有两个因数，分别为 1 和其本身。如果对一个合数取模（有两个以上的因数），那么对其某个因数取模，结果可能仍然一致。例如 10 对 8 取模，结果为 2，对 4 取模，结果也为 2。而我们对一个素数取模，由于素数只有 1 和其本身两个素数，即不可能出现上述情形。
网友评论