数据结构与算法分析 —— C 语言描述：开放定址法

2022-04-17 本文已影响0人 Sun东辉

分离链接散列算法的缺点是需要指针，由于给新单元分配地址需要时间，因此这就导致算法的速度多少有些缓慢，同时算法实际上还要求实现另一种数据结构。除使用链表解决冲突外，开放定址散列法（open addressing hashing）是另外一种用链表解决冲突的方法。在开放定址散列算法系统中，如果有冲突发生，那么就要尝试选择另外的单元，直到找出空的单元为止。更一般地，单元 $h_0(X),h1_(X),h_2(X),...,$ 相继试选，其中 $h_i(X)=(Hash(X)+F(i))mod \space\space TableSize$ ，且 $F(0)=0$ 。函数 F 是冲突解决方法，因为所有的数据都要置入表内，所以开放定址散列法所需要的表要比分离链接散列用的表大。一般说来，对开放定址散列算法来说，装填因子应该低于 $\lambda = 0.5$ 。开放定址散列法有三种常用的冲突解决办法：

线性探测法

在线性探测法中，函数 F 是 $i$ 的线性函数，典型的情形是 $F(i)=i$ 。这相当于逐个探测每个单元（必要时可以绕回）以查找出一个空空单元。即插入一个第一个冲突关键字，它将被放入下一个空闲地址，即地址 0，该地址是开放的。之后插入的冲突关键字，会对表进行试选，只要表足够大，总能够找到一个自由单元，但是如此花费的时间是相当多的。更糟的是，即使表相对较空，这样占据的单元也会开始形成一些区块，其结果称为一次聚集（primary clustering），于是，散列到区块中的任何关键字都需要多次试选单元才能解决冲突，然后该关键字被添加到相应的区块中。

可以证明，使用线性探测的预期探测次数对于插入和不成功的查找来说大约为 $\frac{1}{2}(1+1/(1-\lambda)^2)$ ，而对于成功的查找来说则是 $\frac{1}{2}(1+1/(1-\lambda))$ 。略加思考不难得出，成功查找应该比不成功查找平均花费较少的时间。

如果聚算不算是问题，那么对应的公式就不难得到。我们假设有一个很大的表，并设每次探测都与前面的探测无关。对于随机冲突解决办法而言，这些假设是成立的，并且当 $\lambda$ 不是非常接近 1 时也是合理的。首先，我们导出在一次不成功查找中探测的期望次数，而这正是直到我们找到一个空单元的探测次数。由于空单元所占的份额为 $1-\lambda$ ，因此我们预计要探测的单元数是 $1/(1-\lambda)$ 。一次成功查找的探测次数等于该特定元素插入时所需要的探测次数。当一个元素被插入时，可以看成是一次不成功查找的结果。因此，我们可以使用一次不成功查找的开销来计算一次成功查找的平均开销。

需要指出， $\lambda$ 在 0 到当前值之间的变化，因此早期的插入操作开销较少，从而降低平均开销。我可以通过使用积分计算插入时间平均值的方法来估计平均值，如此得到

$I(\lambda)\;=\;\frac1\lambda\int_0^\lambda\frac1{1-x}dx=\frac1\lambda\ln\left(\frac1{1-\lambda}\right)$

这些公式显然优于线性探测相应的公式，聚集不仅是理论上的问题，而且实际上也发生在具体的实现中。线性探测的预计探测次数与 $\lambda$ 呈正比，即 $\lambda$ 越小，插入操作平均次数越少。

平方探测法

平方探测是消除线性探测中一次聚集问题的冲突解决办法。平方探测就是冲突函数为二次函数的探测方法。流行的选择是 $F(i)=i^2$ 。

对于线性探测，让元素几乎填满散列表并不是个好主意，因为此时表的性能会降低。对于平方探测情况甚至更糟：一旦表被填满超过一半，当表的大小不是素数时甚至在表被填满超过一半之前，就不能保证一次找到一个空单元了。这是因为最多有一半的表可以用作解决冲突的备选位置。

定理：如果使用平方探测，且表的大小是素数，那么当表至少有一半是空的时候，总能够插入一个新的元素。

哪怕表有比一半多一个的位置被填满，那么插入都有可能失败（虽然这是非常难以见到的，但是把它记住很重要。）。另外，表的大小是素数也非常重要，如果表的大小不是素数，则备选单元的个数可能会锐减。

在开放定址散列表中，标准的删除操作不能施行，因为相应的单元可能已经引起过冲突，元素绕过它存在了别处。例如，如果我们删除一个冲突的中间元素，那么实际上所有其他的 Find 例程都将不能正确运行。因此，开放定址散列表需要懒惰删除，虽然在这种情况下并不存在真正意义上的懒惰。

开放定址散列表的类型声明如下，这里，我们不用链表数组，而是使用散列表项单元的数组，与在分离链接散列中一样，这些单元也是动态分配地址的。

#ifndef _HashQuad_H

typedef unsigned int Index;
typedef Index Position;

struct HashTbl;
typedef struct HashTbl *HashTable;

HashTable InitializeTable( int TableSize );
void DestroyTable( HashTable H );
Position Find( ElementType key, HashTable H);
void Insert( ELementType Key, HashTable H);
ElementType Retrieve( Position P; HashTable H);
HashTable Redash( HashTable H);
/* Routines such as Delete and MakeEmpty are omitted */

#endif // _HashQuad_H

/* Place int the implementation file */
enum KindOfEntry { Legitimate, Empty, Deleted };

struct HashEntry
{
    ElementType Element;
    enum KindOfEntry Info;
};

typedef struct HashEntry Cell;

/* Cell *TheCells will be an array of */
/* HashEntry cells, allocated later */
struct HashTbl
{
    int TableSize;
    Cell *TheCells;
};

初始化开放定址散列表的例程如下，由分配空间（第1～10行）及其后将每个单元的 Info 域设置为 Empty 组成。

HashTable
InitializeTable( int TableSize )
{
        HashTable H;
        int i;

/*1*/   if( TableSize < MinTableSize )
        {
/*2*/       Error(" Table size too small");
/*3*/       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 Cells */    
/*8*/   H->TheCells = malloc( sizeof( Cell) * H->TableSize );
/*9*/   if( H->TheCells == NULL )
/*10*/      FatalError("Out of space!!!");

/*11*/  for ( i=0;i<H->TableSize;i++ )  
/*12*/      H->TheCells[i].Info = Empty;

/*13*/   return H;
}

使用平方探测散列法的 Find 例程如下。如果分裂链接散列法一样， $Find(Key, H)$ 将返回 Key 在散列表中的位置。如果 Key 不出现，那么 Find 将返回最后的单元。该单元就是当需要时，Key 将被插入的地方。此外，因为被标记了 Empty，所以表达 Find 失败很容易。为了方便起见，我们假设散列表的大小至少为表中元素个数的两倍，因此平方探测方法总能够实现。否则，我们就要在第 4 行前测试 $i(CollisionNum)$ 。在下面的例程中，标记为删除的那些元素被认为还在表内，这可能引起一些问题，因为该表可能提前过满。

第 4～6 行为进行平方探测的快速方法。由平方解决函数的定义可知， $F(i)=F(i-1)+2i-1$ ，因此，下一个要探测的单元可以用乘以 2（实际上就是进行一位二进制移位）并减 1 来确定。如果新的定位越过数组，那么可以通过减去 TableSize 把它拉回到数组范围内。这比通常的方法要快，因为它避免了看似需要的乘法和除法。注意一条重要的警告：第 3 行的测试顺序很重要，切勿改变它。

Position
Find( ElementType Key, HashTable H)
{
         Position CurrentPos;
         int CellisionNum;

/*1*/    CollisionNum = 0; 
/*2*/    CurrentPos = Hash( Key, H->TableSize );
/*3*/    While(H->TheCells[CurrentPos ].Info != Empty && H->TheCells[ CurrentPos].Element != Key)
            /* Probably need strcpm!! */
         {
/*4*/       CurrentPos += 2 * ++CollisionNum -1;
/*5*/       if(CurrentPos >= H->TableSize)
/*6*/       Currentpos -= H->TableSize;
         }    
/*7*/    return CurrentPos;
}

下面的例程是插入。正如分离链接散列方法那样，若 Key 已经存在，则我们就什么也不做。其他工作只是简单的修改。否则，我们就把要插入的元素放在 Find 例程指出的地方。

void
Insert( ElementType Key, HashTable H)
{
    Position Pos;

    Pos = Find(Key, H);
    if( H->TheCells[ Pos ].Info != Legitimate )
    {
        /* OK to insert here */
        H->TheCells[ Pos ].Info = Legitimate;
        H->TheCells[ Pos ].Element = Key;
            /* Probably need strcpy! */
    }
}

虽然平方探测排除了一次聚集，但是散列到同一位置上的那些元素将探测相同的备选单元。这叫做二次聚集（secondary clustering）。二次聚集是理论上的一个小缺憾，模拟结果指出，对每次查找，它一般要引起另外的少于一半的探测。

双散列

双散列（double hashing）能够解决平方探测中的二次聚集问题，不过也需要花费另外的一些乘法和除法形销。对于双散列，一种流行的选择是 $F(i)=i*hash_2(X)$ 。这个公式是说，我们将第二个散列函数应用到 X 并在距离 $hash_2(X)$ , $2hash_2(X)$ 等处探测。 $hash_2(X)$ 选择的不好将会是灾难性的。

在双散列时，保证表的带下为素数是非常重要的。假设我们在插入一个关键字的时候，发现它已经引发冲突，就会选择备选位置，如果表的大小不是素数，那么备选单元就很有可能提前用完。然后，如果双散列正确实现，则模拟表明，预期的探测次数几乎和随机冲突解决方法的情形相同。这使得双散列理论上很有吸引力，不过，平方探测不需要使用第二个散列函数，从而在实践中可能更简单并且更快。

数据结构与算法分析 —— C 语言描述：开放定址法

线性探测法

平方探测法

双散列

猜你喜欢

热点阅读