数据结构与算法分析 —— C 语言描述：再散列

对于使用平方探测的定址散列法，如果表的元素填的太满，那么操作的运行时间将开始消耗过长，且 Insert 操作可能失败。这可能发生在有太多的移动和插入混合的场合。此时，一种解决办法是建立另外一个大约两倍大的表（而且使用一个相关的新散列函数），扫描整个元素散列表，计算每个（未删除）的元素的新散列值并将其插入到新表中。

例如，设将元素 13、15、24 和 6 插入到大小为 7 的开放定址散列表中。散列函数是 。此时散列表的元素已经超过一半，此时，如果再插入元素 23，表将有超过 的单元是满的。因为表填得过满，所以我们建立一个新的表。该表大小为 17，之所以为 17 是因为 17 是原表大小两倍后的第一个素数。新的散列函数为 。扫面原来的表，并将元素 6、15、23、24 以及 13 插入到新表中。

整个操作过程就叫做再散列（rehashing）。显然这是一种非常昂贵的操作，其运行时间为 ，因为有 N 个元素要再散列而表的大小约为 2N，不过，由于不是经常发生，因此实际效果根本没有这么差。特别是，在最后的再散列之前必然已经存在 N/2 次 Insert，当然添加到每个插入上的花费基本上是一个常数开销。如果这种数据结构是程序的一部分，那么其效果是不显著的。另一方面，如果再散列作为交互系统的一部分，那么其插入引起再散列的不幸的用户将会感到速度减慢。

再散列可以用平方探测以多种方法实现。一种做法是只要表填满一半就再散列。另一种极端的方法是只有当插入失败时才再散列。第三种方法是途中（middle-of-the-road）策略：当表到达某一个装填因子时进行再散列。由于随着装填因子的增加，表的性能的确有下降，因此，以好的截止手段实现第三种策略，可能最好的策略。

HashTable
Rehash( HashTable H)
{
        int i, OldSize;
        Cell *OldCells;

/*1*/   OldCells = H->TheCells;
/*2*/   OldSize = H->TableSize;
        /* Get a new, empty table */
/*3*/   H = InitializeTable(2 * OldSize);
        /* Scan throught old table, reinseting into new */
/*4*/   for( i=0; i< OldSize; i++ )
/*5*/       if( OldCells[i].Info == Legitimate )
/*6*/           Insert( OldCells[i].Element, H);

/*7*/   free( OldCells );

/*8*/   return H;
}

再散列使程序员再也不用担心表的大小，这一点很重要，因此在复杂的程序中散列表不能做得任意大。再散列还可以用在其他数据结构中。例如，队列数据结构变满时，我们可以声明一个双倍大小的数组，并将每一个成员拷贝过来，同时释放原来的队列。