数据结构（超详细讲解！！）第二十七节 查找

1.查找的基本概念

1、查找表——由同一类型的数据元素（或记录）构成的集合称为查找表。

2、对查找表进行的操作：

查找某个特定的数据元素是否存在；

检索某个特定数据元素的属性；

在查找表中插入一个数据元素；

在查找表中删除一个数据元素。

3、静态查找（Static Search Table）——在查找过程中仅查找某个特定元素是否存在或它的属性的，称为静态查找。

4、动态查找（Dynamic Search Table）——在查找过程中对查找表进行插入元素或删除元素操作的，称为动态查找。

5、关键字（Key）——数据元素（或记录）中某个数据项的值，用它可以标识数据元素（或记录）。

6、主关键字（Primary Key）——可以唯一地标识一个记录的关键字称为主关键字。如上图中的“学号”。

7、次关键字（Secondary Key）——可以标识若干个记录的关键字称为次关键字。如上图中的“姓名”，其中张三就有两位。

8、查找（Searching）——在查找表中确定是否存在一个数据元素的关键字等于给定值的操作，称为查找（也称为检索）。若表中存在这样一个数据元素（或记录），则查找成功；否则，查找失败。

9、内查找和外查找 ——若整个查找过程全部在内存进行，则称为内查找；若在查找过程中还需要访问外存，则称为外查找。

10、平均查找长度ASL 查找算法的效率，主要是看要查找的值与关键字的比较次数，通常用平均查找长度来衡量。

平均查找长度：为确定数据元素在列表中的位置， 需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。对于长度为n的列表， 查找成功时的平均查找长度为：

其中Pi为查找列表中第i个数据元素的概率，Ci为找到列表中第i个数据元素时，已经进行过的关键字比较次数。不同的查找方法有不同的Ci。由于查找算法的基本运算是关键字之间的比较操作，所以可用平均查找长度来衡量查找算法的性能。

?11、查找的基本方法：可以分为两大类，即比较式查找法和计算式查找法。其中比较式查找法又可以分为基于线性表的查找法和基于树的查找法，而计算式查找法也称为HASH（哈希）查找法。

2.基于线性表的查找法

1 ?顺序查找法 ? ? ? ? ?

顺序查找又称线性查找，是最基本的查找方法之一。顺序查找法的特点是，用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败。存储结构通常为顺序结构，也可为链式结构。 下面给出顺序结构有关数据类型的定义：

＃define  LIST-SIZE 20
 typedef struct {
       KeyType  key; 
        OtherType  other-data; 
       } RecordType; 
typedef struct {
       RecordType  r［LIST-SIZE+1］;   /* r［0］为工作单元 */
       int length; 
    } RecordList; 

1．顺序查找的基本思想 ? ?

从表的一端开始，顺序扫描线性表，依次按给定值k与关键字（Key）进行比较，若相等，则查找成功，并给出数据元素在表中的位置；若整个表查找完毕，仍未找到与k相同的关键字，则查找失败，给出失败信息。

2．算法的实现 ? ?

现以顺序存储为例，数据元素从下标为1的数组单元开始存放，0号单元留作为监测哨，用来存放待找的值k。

//设置监视哨的顺序查找法
typedef struct {
       RecordType  r［LIST-SIZE+1］;  
       int length; 
    } RecordList; 
int SeqSearch（RecordList l,   KeyType k）
/*在顺序表l中顺序查找其关键字等于k的元素， 若找到， 则函数值为该元素在表中的位置，否则为0*/
{ 
     l.r［0］.key=k;   i=l.length; 
     while (l.r［i］.key!=k)   i--; 
     return（i）; 
}

其中1.r［0］称为监视哨，可以起到防止越界的作用。

//不用监视哨的算法 
int SeqSearch（RecordList l,   KeyType k）
/*不用监视哨法， 在顺序表中查找关键字等于k的元素*/
{
     l.r［0］.key=k;   i=l.length; 
     while (i>=1&&l.r［i］.key!=k)  i--; 
     if (i>=1) return（i）
     else return (0); 
} 

监测哨的作用： （1）省去判定循环中下标越界的条件，从而节约比较时间；

（2）保存查找值的副本，查找时若遇到它，则表示查找不成功。这样在从后向前查找失败时，不必判查找表是否检测完，从而达到算法统一。

3．顺序查找性能分析 ? ? ? ?

下面用平均查找长度来分析一下顺序查找算法的性能。假设列表长度为n，那么查找第i个数据元素时需进行n-i+1次比较，即Ci=n-i+1。又假设查找每个数据元素的概率相等，即Pi=1/n， 则顺序查找算法的平均查找长度为：?

查找不成功时，关键字的比较次数总是n+1次。 ? ? ? ?

算法中的基本工作就是关键字的比较，因此，查找长度的量级就是查找算法的时间复杂度为O(n)。

4.顺序查找的优缺点 ? ? ? ? ?

顺序查找技术的优点是算法简单且适应面广，且对表结构没有任何要求，无论是顺序表还是链表，无论记录是否按关键字有序，均可应用。缺点是平均查找长度较大，当查找规模很大时，查找效率较低。另外，对于线性链表，只能进行顺序查找。

2.折半查找法

二分查找也叫折半查找，是一种效率较高的查找方法，但前提是表中元素必须按关键字有序（按关键字递增或递减）排列。 ?

1．二分查找的基本思路 ? ?

在有序表中，取中间元素作为比较对象，若给定值与中间元素的关键字相等，则查找成功；若给定值小于中间元素的关键字，则在中间元素的左半区继续查找；若给定值大于中间元素的关键字，则在中间元素的右半区继续查找。不断重复上述查找过程，直到查找成功，或所查找的区域无数据元素，查找失败。

注意：

1、由于关键字有序，所以查找时每次和中间位置的元素比较，可快速确定被查找元素在且只可能在哪半个区间内，从而省去与另一半区间内元素的比较，因此提高了效率。 ? ? ? ?

2、查找时，每次都和M下标处的元素比较，若相同则查找成功。M的计算规则为M=(H+L)/2。? ? ? ?

3、此算法的关键是下标的变化，初始时：L=0，H=元素数量-1，M=(H+L)/2，当确定元素在左半区间内时，对下标的更新规则为：L不变，H=M-1；同理，若确定元素在右半区间，则H不变，L=M+1。 ? ? ? ?

4、下标经过变化后，若发现H<L，则表示关键字不在序列中，查找失败。

int BinarySearch(int a[], int n, int key)
{   	int l = 0;  int h = n-1;  int m;	/* 根据结论3 */
	while (l<=h)                          	/* 根据结论4 */
        	{ m = (l+h)/2;  			/* 根据结论3 */
	  if( key == a[m])  return m; 
	  if( key < a[m]) 
 		h = m-1;
	  else
		l= m+1; 
	}
	  return -1; 		/*查找不成功，返回-1 */
}

下面用平均查找长度来分析折半查找算法的性能。 折半查找过程可用一个称为判定树的二叉树描述， 判定树中每一结点对应表中一个记录， 但结点值不是记录的关键字， 而是记录 在表中的位置序号。 根结点对应当前区间的中间记录， 左子树对应前一子表， 右子树对应后一子表。 例如对含11个记录的有序表， 其折半查找过程可如下图所示的二叉判定树表示。 二叉树结点内的数值表示有序表中记录的序号， 如二叉树的根结点表示第一次折半时找到的第6个记录。

图中的虚线表示查找关键字等于13的记录的过程， 需要的比较次数为4， 因为关键字等于13的记录在判定树上位于第4层。 因此， 记录在判定树上的“层次”恰为找到此记录时所需进行的比较次数。 假设每个记录的查找概率相同， 则从图所示判定树可知， 对任意长度为11的有序表进行折半查找的平均查找长度为ASL=(1+2+2+3+3+3+3+4+4+4+4)/11=33/11=3。

折半查找成功时， 关键字比较次数最多不超过判定树的深度。 由于判定树的叶子结点所在层次之差最多为1， 故n个结点的判定树的深度与n个结点的完全二叉树的深度相等，均为［log2n］+1。 这样，折半查找成功时，关键字比较次数最多不超过［log2n］+1。 相应地， 折半查找失败时的过程对应判定树中从根结点到某个含空指针的结点的路径， 因此， 折半查找失败时， 关键字比较次数最多也不超过判定树的深度［log2n］+1。 为便于讨论， 假定表的长度n=2h-1， 则相应判定树必为深度是h的满二叉树，h=log2(n+1)。 又假设每个记录的查找概率相等， 则折半查找成功时的平均查找长度为

所以，二分查找的时间复杂度为：O (log2n) 。

二分查找的优点是：效率高。 ? ? ? ?

二分查找的缺点是： ? ?

（1）必须按关键字排序，有时排序也很费时；? ?

（2）只适用顺序存储结构，所以进行插入、删除操作必须移动大量的结点。 ? ? ? ?

二分查找适用于那种一经建立就很少改动，而又经常需要查找的线性表。对于那些经常需要改动的线性表，可以采用链表存储结构，进行顺序查找。

3.分块查找法

?分块查找法要求将列表组织成以下索引顺序结构： ?

首先将列表分成若干个块（子表）。一般情况下，块的长度均匀， 最后一块可以不满。每块中元素任意排列，即块内无序，但块与块之间有序。

构造一个索引表。其中每个索引项对应一个块并记录每块的起始位置，以及每块中的最大关键字（或最小关键字）。索引表按关键字有序排列。

实现算法： ? ? ? ? ?

索引表是有序的，所以在索引表上既可以采用顺序查找，也可以采用折半查找，而每个块中的记录排列是任意的，所以在块内只能采用顺序查找。

注意：

1.算法引入索引表的辅助结构，可以首先通过索引表确定被查找关键字所在的区间，再从相应区间内查找，从而有效的减少比较的次数。

2.在构建索引表时，索引表存储相应块中的最大值，这些最大值按有序排放，在确定区间时可以使用折半查找的方法。

3.为了保证索引表有效，原始序列中的元素必须“部分有序”，所谓“部分有序”指的是对于第i个区间中的所有数据都应比前一个区间，即第i-1个区间内所有关键字大，否则会导致索引失效。

4.由于每个区间的关键字是无序的，因此在区间内的查找只能使用顺序查找。

5.算法需要在一开始构建索引表，并且保证原始序列“部分有序”，这本身会耗费一定的时间，如果原始序列中的元素不再发生变化，则索引表的结构是稳定的，一旦原始序列发生变化，则仍需重新构造索引表并使得新序列重新“部分有序”。

#define MaxIndex <索引表的最大长度>
  typedef struct
 {     elemtype key;
        int link;
 }IdxType;

在这种结构下，查找过程要分为两步：首先查找索引表。因为索引表是有序表，所以可采用二分查找或顺序查找，以确定给定值所在的块。因为块中的记录可以是任意排列的，所以再在已确定的块中进行顺序查找。

//分块查找
int IdxSerch(SeqList A[], IdxType index[], int b, KeyType k, int n)
{ //分块查找关键字为k的记录，索引表为index[0..b-1] 
  int low=0, high=b-1, mid, i;      int s=n/b; //每块记录个数
  while(low<=high) {   mid=(low+high)/2;
      if(index[mid].key < k) low = mid+1
      else high=mid-1;       }
  if(low<b) {           //在顺序表中顺序查找
     for(i=index[low].link;i<=index[low].link+s-1 && i<n; i++)
         if(A[i].key==k) return i;
	}
   return -1;
}

索引顺序查找的平均查找长度 = ?查找“索引”的平均查找长度 ? + ?查找“顺序表”的平均查找长度

?分块查找的平均查找长度由两部分构成， 即查找索引表时的平均查找长度为LB，以及在相应块内进行顺序查找的平均查找长度为LW。

? ? ? ??

假定将长度为n的表分成b块，且每块含s个元素，则b=n/s。又假定表中每个元素的查找概率相等，则每个索引项的查找概率为1/b，块中每个元素的查找概率为1/s。若用顺序查找法确定待查元素所在的块，则有

3.动态查找

动态查找表特点：表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在关键字等于key的记录，则查找成功；否则插入关键字为key的元素。

1.二叉排序树

二叉排序树(二叉搜索树、二叉查找树) ： 或者是一棵空树，或是一棵有如下特性的非空二叉树：

若它的左子树非空，则左子树上所有结点的关键字均小于根结点的关键字；若它的右子树非空，则右子树上所有结点的关键字均大于等于根结点的关键字。

左、右子树本身又各是一棵二叉排序树。

结论：二叉排序树中序遍历得到的必是一个有序序列。 ?

#define  NULL   0   
typedef struct Node  	/* 树中结点定义*/
{  int key;  			/* 关键字*/
   struct Node * pLeft;  	/* 指向左子树的指针 */
   struct Node * pRight; 	/* 指向右子树的指针 */
}Node;

二叉排序树的搜索：

若二叉排序树为空，则查找不成功；否则，

1）若给定值等于根结点的关键字，则查找成功；

2）若给定值小于根结点的关键字，则继续在左子树上进行查找；

3）若给定值大于根结点的关键字，则继续在右子树上进行查找。

/*查找成功返回值为1，查找失败返回0*/
int SearchBST(Node * pRoot,int key)
{ /* 结点为空，则表示搜索到叶子结点仍没找到，返回0 */
 if(pRoot == NULL) return 0;
 if(key == pRoot->key)return 1;	/*查找成功，返回1*/
        	/*若key小于当前结点的关键字，则继续在左子树中搜索*/
 else if(key < pRoot->key) 
       SearchBST(pRoot->pLeft, key);  
 else 	/*否则继续在右子树中查找*/
     SearchBST(pRoot->pRight,key)；
} 

二叉排序树的插入及创建：

根据动态查找表的定义，“插入”操作在查找不成功时才进行；

若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。

输入：4、2、3、5、8、0、1

//改进二叉排序树搜索算法
int SearchBST(Node * pRoot, int key, Node** pKeyNode, Node ** pParentNode)
{  *pKeyNode = pRoot;
     while(*pKeyNode)
    { if(key >(* pKeyNode)->key){       *pParentNode = *pKeyNode;
	*pKeyNode = (*pKeyNode)->pRight;            }
       else if(key <(*pKeyNode)->key)
      {       *pParentNode = *pKeyNode;   *pKeyNode = (*pKeyNode)->pLeft;       }
      else { return 1;}
     }	
    *pKeyNode= *pParentNode;					
     return 0;
}

pParentNode：pRoot的父结点，初始时pRoot指向根结点，其父结点为NULL;

?pKeyNode : 查找成功时返回关键字所在结点的指针，不成功时，返回查找路径上不为空的最后一个结点，当pKeyNode返回NULL时，表示此时二叉排序树为一颗空树; ? ?查找成功返回1，查找失败返回0

 //二叉排序树插入算法
int InsertBST(Node ** pRoot, int key)
{   Node * pNewNode; 	      	/*定义存放新的关键字的结点*/
     Node* pKeyNode， * pParentNode=NULL；
   				/*如果该关键字已在树中，则插入失败*/
if(SearchBST(*pRoot, key, &pKeyNode, &pParentNode)) return 0;
   				/*若不在树中，则首先为新结点分配空间*/
   Node * pNewNode = (Node*)malloc(sizeof(Node));
   pNewNode->key = key;				/*为新结点赋初值*/
   pNewNode->pLeft = pNewNode->pRight = NULL;
  				 /*若树为空树，则新结点为插入后的根结点*/
   if(pKeyNode == NULL) (*pRoot) = pNewNode;
  				 /*比结点关键字小，插入到左孩子*/
   else if(key < pKeyNode->key) pKeyNode->pLeft = pNewNode;
   else pKeyNode->pRight = pNewNode;
   return 1;
}

key：被插入关键字; ?

pRoot：插入后新的二叉排序树的根结点指针; ? ?插入成功返回1，插入失败返回0。

二叉排序树的删除算法：

和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。

（1）被删除的结点是叶子；

其双亲结点中相应指针域的值改为“空”

（2）被删除的结点只有左子树或者只有右子树；

其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树”。

（3）被删除的结点既有左子树，也有右子树。

以其前驱替代之，然后再删除该前驱结点

?方法1: ?首先找到p结点在中序序列中的直接前驱s结点，然后将p的左子树改为f的左子树，而将p的右子树改为s的右子树：f->lchild=p->lchild；s->rchild= p->rchild； free(p)；

方法2: ? 首先找到p结点在中序序列中的直接前驱s结点，然后用s结点的值替代p结点的值，再将s结点删除，原s结点的左子树改为s的双亲结点q的右子树：p->data=s->data；q->rchild= s->lchild；free(s)；

int DeleteBST(Node * pRoot,int key)
{     Node * pParentNode = NULL;
       Node * pNode = pRoot;
       Node * pKeyNode;
       Node ** pTempNode;
      if(SearchBST(pRoot,key,&pKeyNode,&pParentNode))
    {	if(pParentNode == NULL) pTempNode = &pRoot;
 	else if(pKeyNode == pParentNode->pLeft) 
                   pTempNode = &pParentNode->pLeft;
	else pTempNode = &pParentNode->pRight;
                   if (pKeyNode->pLeft ==NULL)
                  {	*pTempNode = pKeyNode->pRight;
		free(pKeyNode);
                   }
           
 else if(pKeyNode->pRight == NULL)
     {   *pTempNode = pKeyNode->pLeft;   free(pKeyNode);      }
      else
      {      pNode = pKeyNode->pLeft; 
              pTempNode = &pKeyNode->pLeft;
              while (pNode->pRight != NULL) 
             {    pTempNode = &pNode->pRight;
	        pNode = pNode->pRight;
              }
	   pKeyNode->key = pNode->key;
	  *pTempNode = pNode->pLeft;     	    free(pNode);
       }
        return 1;
    }
   return 0;
}

查找性能的分析：

对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的 ASL 值，显然，由值相同的 n 个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长度的值不同，甚至可能差别很大。

时间复杂度： ? ? ?

分析：在二叉排序树上进行查找的过程中，根结点为待查结点时，给定值同树中结点的比较次数仅为一次，待查结点位于最后一层时，比较的次数为树的深度。 ? ?

普通情况下，对二叉排序树进行查找的时间复杂度为O(?log2n ) ? ? 最差情况下(二叉排序树为一棵单支树)，其时间复杂度为O(n)。

为使得由任何初始序列构成的二叉排序树的平均查找长度是对数级的，所以可使得构造的二叉排序树是一个平衡二叉树。

2.平衡二叉排序树

平衡二叉排序树又称为AV树。一棵平衡二叉排序树或者是空树，或者是具有下列性质的二叉排序树：

① 左子树与右子树的高度之差的绝对值小于等于1；

② 左子树和右子树也是平衡二叉排序树。引入平衡二叉排序树的目的是为了提高查找效率， 其平均查找长度为O(log2n)。

在下面的描述中，需要用到结点的平衡因子（balance factor）这一概念，其定义为结点的左子树深度与右子树深度之差。

显然，对一棵平衡二叉排序树而言， 其所有结点的平衡因子只能是-1、 0，或1。当我们在一个平衡二叉排序树上插入一个结点时，有可能导致失衡，即出现绝对值大于1的平衡因子，如2、-2。图中给出了一棵平衡二叉排序树和一棵失去平衡的二叉排序树。

失衡调整

4.哈希法

哈希法又称散列法、杂凑法或关键字地址计算法等，相应的表称为哈希表。 这种方法的基本思想是：首先在元素的关键字k和元素的存储位置p之间建立一个对应关系H，使得p=H(k)，H称为哈希函数。创建哈希表时，把关键字为k的元素直接存入地址为H(k)的单元；以后当查找关键字为k的元素时，再利用哈希函数计算出该元素的存储位置p=H(k)，从而达到按关键字直接存取元素的目的。?

当关键字集合很大时，关键字值不同的元素可能会映象到哈希表的同一地址上，即 k1≠k2，但 H（k1）=H（k2），这种现象称为冲突，此时称k1和k2为同义词。实际中，冲突是不可避免的， 只能通过改进哈希函数的性能来减少冲突。

1.构造方法

1. 数字分析法 ? ?

例如，有80个记录，关键字为8位十进制整数d1d2d3…d7d8，如哈希表长取100，则哈希表的地址空间为： 00~99。假设经过分析，各关键字中d4和d7的取值分布较均匀， 则哈希函数为：H(key)=H(d1d2d3…d7d8)=d4d7。例如， H(81346532)=43，H(81301367)=06。 相反， 假设经过分析， 各关键字中 d1和d8的取值分布极不均匀，d1 都等于5，d8 都等于2，此时，如果哈希函数为：H(key)=H(d1d2d3…d7d8)=d1d8， 则所有关键字的地址码都是52，显然不可取。

? 2. 平方取中法 ? ? ?

?当无法确定关键字中哪几位分布较均匀时， 可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。

3. 分段叠加法

这种方法是按哈希表地址位数将关键字分成位数相等的几部分（最后一部分可以较短）， 然后将这几部分相加， 舍弃最高进位后的结果就是该关键字的哈希地址。 具体 方法有折叠法与移位法。 移位法是将分割后的每部分低位对齐相加， 折叠法是从一端向另一端沿分割界来回折叠（奇数段为正序， 偶数段为倒序）， 然后将各段相加。 例如： key=12360324711202065, 哈希表长度为1000， 则应把关键字分成3位一段， 在此舍去最低的两位65， 分别进行移位叠加和折叠叠加， 求得哈希地址为105和907。

4. 除留余数法

?假设哈希表长为m， p为小于等于m的最大素数， 则哈希函数为H（k）=k%p， 其中%为模p取余运算。 ? ? ?

例如，已知待散列元素为（18，75，60，43，54，90，46），表长m=10， p=7， 则有

H(18)=18 % 7=4 ? ? ?H(75)=75 % 7=5 ? ? ?H(60)=60 % 7=4 ?

H(43)=43 % 7=1 ? ? ?H(54)=54 % 7=5 ? ? ?H(90)=90 % 7=6 ? ? H(46)=46 % 7=4

此时冲突较多。 为减少冲突， 可取较大的m值和p值， 如m=p=13， 结果如下：

H(18)=18 % 13=5 ? ?H(75)=75 % 13=10 ? ?H(60)=60 % 13=8 ? ?

H(43)=43 % 13=4 ? ?H(54)=54 % 13=2 ? ? ?H(90)=90 % 13=12 ? ? H(46)=46 % 13=7

?5. 伪随机数法 ? ? ? ?

采用一个伪随机函数作哈希函数，即H(key)=random(key)。 ? ? ? ?

在实际应用中， 应根据具体情况， 灵活采用不同的方法， 并用实际数据测试它的性能，以便做出正确判定。 通常应考虑以下五个因素：

计算哈希函数所需的时间（简单）。

关键字的长度。

哈希表的大小。

关键字的分布情况。

记录查找的频率。

2.处理冲突的方法

? 1. 开放定址法 ? ? ? ?

这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p= H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2……直到找出一个不冲突的哈希地址pi，将相应元素存入其中。这种方法有一个通用的再散列函数形式：?

其中H（key）为哈希函数， m 为表长， di称为增量序列。 增量序列的取值方式不同，相应的再散列方式也不同。主要有以下三种： ? ? ? ?

线性探测再散列：di=1，2，3，…:， m-1 ? ? ? ?

这种方法的特点是： 冲突发生时，顺序查看表中下一单元， 直到找出一个空单元或查遍全表。? ? ?

二次探测再散列 ：di=12，-12， 22，-22，…，k2，-k2 ? ?(k≤m/2) ? ? ? ?

这种方法的特点是：冲突发生时，在表的左右进行跳跃式探测， 比较灵活。 ? ? ? ?

伪随机探测再散列：di=伪随机数序列。 ? ? ? ?

具体实现时，应建立一个伪随机数发生器，并给定一个随机数做起点。

?2. 再哈希法 ? ? ? ?

这种方法是同时构造多个不同的哈希函数： Hi=RH1（key）， i=1，2， …， k ? ? ? ?

当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

?3. 链地址法 ? ? ? ?

这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中， 因而查找、插入和删除主要在同义词链中进行。 链地址法适用于经常进行插入和删除的情况。

?4. 建立公共溢出区 ?

这种方法的基本思想是将哈希表分为基本表和溢出表两部分，凡是与基本表发生冲突的元素一律填入溢出表。

3.哈希表的查找过程

哈希表的查找过程与哈希表的创建过程是一致的。 当查找关键字为K的元素时， 首先计算p0=hash（K）。如果单元p0为空， 则所查元素不存在； 如果单元p0中元素的关键字为K，则找到所查元素；否则重复下述解决冲突的过程： 按解决冲突的方法，找出下一个哈希地址pi， 如果单元pi为空，则所查元素不存在；如果单元pi中元素的关键字为K，则找到所查元素。

//以线性探测再散列为例
＃define  m   <哈希表长度>
＃define  NULLKEY  <代表空记录的关键字值>
typedef  int   KeyType; 
typedef  struct
          {
            KeyType  key; 
          } RecordType ; 
typedef  RecordType  HashTable［m］ ; 

int  HashSearch( HashTable  ht,   KeyType  K)
{
 p0=hash(K); 
  if  (ht［p0］.key==NULLKEY)  return (-1);  
  else  if  (ht［p0］.key==K)  return (p0);  
  else    /* 用线性探测再散列解决冲突 */
    {  
         for (i=1;  i<=m-1;   i++)  
           {   
             pi=(p0+i) % m;    
             if  (ht［pi ］.key==NULLKEY)  return (-1);    
             else if  (ht［pi］.key==K)  return (pi);   
            } 
       return (-1); 
     }
} 

4.哈希法性能分析?

由于冲突的存在，哈希法仍需进行关键字比较， 因此仍需用平均查找长度来评价哈希法的查找性能。哈希法中影响关键字比较次数的因素有三个：哈希函数、 处理冲突的方法以及哈希表的装填因子。

哈希表的装填因子α的定义如下：

α可描述哈希表的装满程度。 显然，α越小， 发生冲突的可能性越小， 而α越大， 发生冲突的可能性也越大。 假定哈希函数是均匀的， 则影响平均查找长度的因素只剩下两个： 处理冲突的方法以及α。以下按处理冲突的不同方法分别列出相应的平均查找长度。

线性探测再散列：

伪随机探测再散列、 二次探测：

链址法：

?从以上讨论可知：哈希表的平均查找长度是装填因子α的函数，而与待散列元素数目n无关。因此， 论元素数目n有多大，都能通过调整α，使哈希表的平均查找长度较小。

手工计算等概率情况下查找成功的平均查找长度规则如下：

手工计算等概率情况下查找不成功的平均查找长度规则如下 ：