【数据结构知识】查找

前言

      这一章围绕查找，有顺序查找，折半查找，插值查找，斐波那契查找，关于线性索引查找，有稠密查找、分块索引和倒排索引。还有动态查找的数据结构二叉排序树，关于针对内存和外存之间存取而设计的B树。之间一步到位查找结果的散列表。

【数据结构系列】【前一章：图】【后一章：排序】

目录

七、查找

1、查找概论

2、顺序表查找

3、有序表查找 

（1）折半查找

（2）插值查找

 （3）斐波那契查找

4、线性索引查找

（1）稠密索引

（2）分块索引

（3）倒排索引

5、二叉排序树

（1）二叉排序树查找操作

（2）二叉排序树插入操作

（3）二叉排序树删除操作

6、平衡二叉树（AVL树）

（1）平衡二叉树实现原理

（2）平衡二叉树实现算法

 7、多路查找树（B树）

（1）2-3树

（2）2-3-4树

（3）B树

（4）B+树

8、散列表查找（哈希表）概述

（1）定义

（2）步骤

9、散列函数的构造方法

（1）构造原则

（2）直接定址法

（3）数字分析法

（4）平方取中法

（5）折叠法

（6）除留余数法

（7）随机数法

10、处理散列冲突的方法

（1）开放定址法

（2）再散列函数法

（3）链地址法

（4）公共溢出区法

11、散列表查找实现

（1）散列表查找算法实现

（2）散列表查找性能分析

七、查找

查找就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。

1、查找概论

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

（2）关键字：数据元素中某个数据项的值，又称为键值，用它可以标识数据元素。

（3）主关键字：此关键字可以唯一地标识一个记录。

（4）主关键码：主关键字所在的数据项。

（5）次关键字：可以识别多个数据元素（或记录）的关键字。

（6）次关键码：次关键字对应的数据项。

查找表按照操作方式分为两种：静态查找表和动态查找表

1）静态查找表：只做查找操作

• 查询某个“特定的“数据元素是否在查找表中
• 检索某个“特定的”数据元素和各种属性

2）动态查找表：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素

• 查找时插入数据元素
• 查找时删除数据元素

2、顺序表查找

        顺序查找又称线性查找，查找过程是：从表中第一个（或者最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或第一个）记录，其关键字和给定值都不相等，则表中没有所查记录，查找不成功。

代码如下：

//顺序查找，a为数组，n为要查找的数组个数，key为要查找的关键字
int Sequential_Search(int *a, int n, int key)
{
	for (int i = 1; i <= n; i++)
	{
		if (a[i] == key)
			return i;
	}
	return 0;
}
           

顺序表查找优化：

由于每次循环时都需要对i是否越界，即是否小于等于n做判断。在这里可以设置一个哨兵，解决每次让i与n作比较。

代码如下：

//有哨兵顺序查找
int Sequential_Search2(int *a, int n, int key)
{
	int i;
	a[0] = key;  //设置a[0]为关键字值，我们称之为“哨兵”
	i = n;  //循环从数组尾部开始
	while (a[i] != key)
		i--;
	return i; //返回0则说明查找失败
}
           

时间复杂度：O(n)

当n较大时，查找效率较低，不过由于查找概率的不同，可以把容易查找到的记录放在前面，不常用的记录放在后面，可以提高效率。

3、有序表查找 

（1）折半查找

折半查找，又称为二分查找。前提是线性表中的记录必须是关键码有序，线性表必须采用顺序存储。基本思想：取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若小于中间记录的关键字，则在中间记录的左半区继续查找；若大于中间记录的关键字，则在中间记录的右半区继续查找。

//折半查找
int Binary_Search(int *a, int n, int key)
{
	int low, high, mid;
	low = 1;
	high = n;
	while (low <= high)
	{
		mid = (low + high) / 2; //折半
		if (key < a[mid])
			high = mid - 1;
		else if (key > a[mid])
			low = mid + 1;
		else
			return mid;
	}
	return 0;
}
           

时间复杂度：O(logn)

（2）插值查找

例如：0~1000，我们需要查找到5，我们并不会从一半进行查找，我们而是会从较前面一些数，比如0~100内进行查找。所以对于折半查找，我们做了一些改造：

，考虑对这个

进行改进，改进如下：

，把

改成了

插值查找是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法。

时间复杂度：O(logn)  

对于表长较长，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好很多 

 （3）斐波那契查找

利用斐波那契数列来进行找到查找中的mid，由于斐波契那数列的前一个数除以相邻的后一个数比值无限接近黄金比例。

1、n=F[k]-1，若n!=F[k]-1，则补全，例如：n=10，我们可以找到F[k]=13是第一个大于10的斐波那契数，所以n'=F[k]-1=12，即需要补全a[11]、a[12]，我们让a[11]=a[12]=a[10]，所以对于新的数列，个数为n=F[k]-1

2、查找范围：[low,high]，mid=low+F[k-1]-1

（1）若key=a[mid]，则查找成功

（2）若key<a[mid]，high'=mid-1，k=k-1，查找范围：[low,high']，列表个数：high'-low=mid-1-low=(low+F[k-1]-1)-low=F[k-1]-1，所以可以采用递归，只需要让k=k-1即可

（3）若key>a[mid]，low'=mid+1，k=k-2，查找范围：[low',high]，列表个数：总长-左侧长度-1=n-(F[k-1]-1)-1=F[k]-1-F[k-1]+1-1=F[k]-F[k-1]-1=F[k-2]-1，所以可以采用递归，只需要让k=k-2即可

重点解释下：n=F[k]-1，只是为了方便后面进行递归，因为除去中间的mid，一共有F[k]-1-1=F[k]-2，把左右进行分成F[k-1]-1和F[k-2]-1个，和F[k]-1形式一样，可以进行递归。

                                                                                              图1  

代码如下：

//斐波那契查找
int Fibonacci_Serach(int *a, int n, int key)
{
	int low, high, mid;
	low = 1;
	high = n;
	int k = 0;
	while (n > F[k] - 1)  //计算n位于斐波那契数列的位置
		k++;
	for (int i = n; i < F[k] - 1; i++) //将不满的数值补全
		a[i] = a[n];

	while (low <= high)  
	{
		mid = low + F[k - 1] - 1;
		if (key < a[mid])  //小于
		{
			high = mid - 1;
			k = k - 1;
		}
		else if (k > a[mid])  //大于
		{
			low = mid + 1;
			k = k - 2;
		}
		else     //等于
		{
			if (mid <= n)
				return mid;
			else
				return n;
		}
	}
	return 0;
}
           

 时间复杂度：O(logn)       平均性能优于折半查找

4、线性索引查找

        对于数据量巨大，若全部按照当中某个关键字有序，其时间代价是非常高昂的，所以这种数据通常都是按先后顺序存储。

        数据结构的最终目的是提高数据的处理速度，索引是为了加快查找速度而设计的一种数据结构。

        索引就是把一个关键字与它对应的记录相关联的过程。一个索引由若干个索引项构成，每个索引项至少应包含关键字和其对应的记录在存储器中的位置等信息。

        索引按照结构可分为：线性索引、树形索引和多级索引，在这里只介绍线性索引。

        线性索引就是将索引项集合组织为线性结构，也称为索引表。

        线性索引：稠密索引、分块索引和倒排索引。

（1）稠密索引

稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引项。如图2所示

                                                                               图2 稠密索引

        稠密表对应的可能是成千上万的数据，因此对于稠密索引这个索引表来说，索引项一定是按照关键码有序的排列。索引项有序，意味着我们要查找关键字时，可以用到折半、插值、斐波契那等有序查找算法，大大提高了效率。

（2）分块索引

        稠密表因为索引项与数据集的记录个数相同，所以空间代价很大。为了减少索引项的个数，我们可以对数据集进行分块，使其分块有序，然后再对每一块建立一个索引项，从而减少索引项的个数。

分块有序，这些快需满足两个条件：

（1）块内无序        （2）快间有序

分块索引的索引项结构分三个数据项：

• 最大关键码：存储每一块中的最大关键字
• 存储了块中的记录个数，以便于循环时使用
• 用于指向块首数据元素的指针，便于开始对这一块中记录进行遍历

 如图3所示：

                                                                                       图3 分块索引 

进行分块索引，分两步进行：

1）由于快间有序，因此很容易利用折半、插值等算法得到结果。例如在图3的数据集中查找62，我们可以很快从左上角的索引表中由57<62<96得到62在第三个块中。

2）在块中顺序查找关键码。

分析下分块索引的平均查找长度：设n个记录的数据集被平均分成m块，每个块中有t条记录，所以n=m*t，或者m=n/t。再假设Lb为查找索引表的平均长度，所以Lb的平均长度为

。Lw为块中查找记录的平均查找长度，同理它的平均查找长度为

。这样分块索引查找的平均查找长度为：

 由以上推论可知，平均长度不仅仅取决于数据集的总记录数n，还和每一个块的记录个数t相关。最佳情况就是m=t，所以n=m*t=t^2，即

。

总结：分块索引在兼顾了对于细分块不需要有序的情况下，大大增加了整体查找的速度，所以普遍被用于数据库表查找等技术的应用中。

（3）倒排索引

倒排索引是最简单的，也算是最基础的搜索技术。

索引项的通用结构：

• 次关键码
• 记录号表

       其中记录号表存储具有相同次关键字的所有记录的记录号（可以是指向记录的指针或者是该记录的主关键字），这样的索引方法就是倒排索引。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引。

举例：

现在有两篇极短的英文文章，编号分别是1和2.

1. Books and friends should be few but good.

2. A good book is a good friend.

假设我们忽略如“books”、“friends”中的复数"s"以及如"A"这样的大小写差异。我们可以整理一张单词表，并对单词做了排序，也就是表格显示了每个不同的单词分别出现在哪篇文章中。

英文单词	文章编号
a	2
and	1
be	1
book	1,2
but	1
few	1
friend	1,2
good	1,2
is	2
should	1

                                                                                                  表1

如表1所示，次关键码：英文单词，记录号表：文章编号。

5、二叉排序树

        在插入数据时，我们就让其有序，假设我们的数据集开始只有一个数{62}，然后需要把88插入数据集，于是数据集成了{62，88}，再有一个数据58，发现没有则插入，对于线性表的顺序存储结构，让其有序，需要移动62和88的位置，当我们用二叉树的方式时，首先我们将第一个数62定为根节点，88比62大，因此作为62的右子树，58比62小，所以作为62的左子树。此时58的插入并没有影响62和88的关系。

二叉排序树，又称为二叉查找树，它或者是一棵空树，或者是具有下列性质的二叉树：

• 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值
• 若它的右子树不空，则右子树上所有的节点值均大于它的根节点的值
• 它的左、右子树也分别为二叉排序树
• 对它进行中序遍历时，就可以得到一个有序的序列

      构造一颗二叉树的母的，其实并不是为了排序，而是为了提高查找和插入删除关键字的速度。

（1）二叉排序树查找操作

//二叉树的二叉链表节点定义
typedef struct BiTNode     //节点结构
{
    int data;              //节点数据
    struct BiTNode *lchild,*rchild;  //左右孩子指针
}BiTNode,*BiTree;
           

//f指向T的双亲，其处初值为NULL
//若查找成功，则指针p指向该数据元素节点，并返回TRUE
//否则p指向查找路径上访问的最后一个节点并返回FALSE
Status SearchBST(BiTree T,int key,BiTree f,BiTree *p)
{
    if(!T)
    {
        *p=f;
        return FALSE;
    }
    else if(key==T->data)
    {
        *p=T;
        return TRUE;
    }
    else if(key>T->data)
    {
        SearchBST(T->rchild,key,T,p);
    }
    else
    {
        SearchBST(T->lchild,key,T,p);
    }
}
           

（2）二叉排序树插入操作

Status InsertBST(BiTree *T,int key)
{
    BiTree p;
    if(!SearchBST(*T,key,NULL,&p))  //若查找不成功，即没有此节点
    {
        BiTree s=new BiTree;
        s->data=key;
        s->rchild=NULL;
        s->lchild=NULL;
        if(!p)    //插入s为根节点
        {
            *T=s;
        }
        else if(key>p->data)
        {
            p->rchild=s;
        }
        else
        {
            p->lchild=s;
        }
        return TRUE;
    }
    return FALSE;   //有此节点
}
           

有了插入操作，对于构建这样的树就非常容易了：

int a[10]={62,88,58,47,35,73,51,99,37,93};
BiTree T=NULL;
for(int i=0;i<10;i++)
{
    InsertBST(&T,a[i]);
}
           

（3）二叉排序树删除操作

对删除的节点有三种情况：

• 叶子节点
• 仅有左或右子树节点
• 左右子树都有节点

代码如下：

Status DeleteBST(BiTree *T,int key)
{
    if(!*T)   //不存在关键字等于key的数据元素
        return FALSE;
    else
    {
        if(key==(*T)->data)   //找到关键字等于key的数据元素
            return Delete(T);
        else if(key<(*T)->data)
            return DeleteBST(&(*T)->lchild,key);
        else
            return DeleteBST(&(*T)->rchild,key);
    }
}
           

和查找程序差不多，差别就是当找到关键字时，进行删除操作，所以接下来最重要的就是看看删除操作是怎样进行的。

//从二叉排序树中删除节点p，并重接它的左或右子树
Status Delete(BiTree *p)
{
    BiTree q,s;
    if((*p)->rchild==NULL)  //右子树空则只需要重接它的左子树
    {
        q=*p;
        *p=(*p)->lchild;
        free(q);
    }
    else if((*p)->lchild==NULL)   //只需要重接它的右子树
    {
        q=*p;
        *p=(*p)->rchild;
        free(q);
    }
    else  //左右子树均不空
    {
        q=*p;               //q永远是s的根节点
        s=(*p)->lchild;     //s即是p的前驱节点
        while(s->rchild)
        {
            q=s;
            s=s->rchild;
        }
        (*p)->data=s->data;
        if(q!=*p)  //即p的左子树不是一个斜左树
        {
            q->rchild=s->lchild;
        }
        else
            q->lchild=s->lchild;
        free(s);
    }
    return TRUE;
}
           

总结：二叉排序树，对于插入和删除，只需要修改链接的指针即可，不需要移动元素，但对于查找，是从根节点开始，其比较次数等于给定值的节点在二叉排序树的层数。所以说二叉排序树的查找性能取决于二叉排序树的形状，可问题在于，二叉树的形状是不确定的。我们希望二叉排序树是比较平衡的，即其深度与完全二叉树相同，均为[log2n]+1，那么查找的时间复杂度就是O(logn)，近似于折半查找。问题就在于如何让二叉排序树平衡的问题。

6、平衡二叉树（AVL树）

平衡二叉树是一种二叉排序树，其中一个节点的左子树和右子树的高度差至多等于1。

我们将二叉树上节点的左子树深度减去右子树深度的值称为平衡因子BF。那么平衡二叉树上所有节点的平衡因子只有可能是-1、0和1。

距离插入节点最近的，且平衡因子的绝对值大于1的节点为根的子树，我们称为最小不平衡子树，如图4所示。

                                                                                     图4

（1）平衡二叉树实现原理

基本思想：在构建二叉排序树的过程中，每当插入一个节点时，先检查是否因插入而破坏了树的平衡性，若是，则找到最小平衡树，当平衡因子为正，则进行右旋，若为负，则进行左旋。

下面举例说明：有一个数组a[7]={3,2,1,4,5,7,6}需要构建二叉排序树。在没有学习平衡二叉排序树之前，我们会构造出如图5所示的左图，而我们需要的平衡排序二叉树是图5中的右图。

                                                                                              图5

步骤：

1）对于前面的3，2正常构造，当插入1时，会发现根节点3的平衡因子为2，需要进行右旋，如图6所示。

                                                                                             图6

2）插入4，如图7所示

                                                                                                图7

3）插入5时，会发现对于节点3，平衡因子为-2，需要进行左旋，如图8所示。

                                                                                       图8 

4）插入7时，会发现根节点2的平衡因子为-2，需要进行左旋，如图9所示。

                                                                                        图9

5）插入6时，会发现节点5的平衡因子为-2，需要进行左旋，但左旋后对于节点7，左右孩子都比7小，这就不对了。

在这里，我们会发现一个规律，就是在进行左旋或者右旋时，不平衡根节点的平衡因子和插入节点的双亲节点的平衡因子符号是一致的，而在这里，节点5的平衡因子是-2，节点7的平衡因子是+1，不一致，所以不能进行简单的左旋操作，而是应该先对节点7进行右旋，再对节点5进行左旋。

一系列操作如图10所示：

                                                                                          图10 

以上即是整个操作过程。

总结：

• 当最小不平衡子树根节点的平衡因子BF大于1时，右旋
• 当最小不平衡子树根节点的平衡因子BF小于-1时，左旋
• 当最小不平衡子树的BF与它的子树的BF符号相反时，就需要先对节点进行一次旋转以使得符号相同后，再反向旋转一次才能够完成平衡操作

（2）平衡二叉树实现算法

1）改进二叉排序树的节点结构，增加一个bf，用来存储平衡因子

//二叉树的二叉链表节点结构定义
typedef struct BiTNode               //节点结构
{
    int data;                        //节点数据
    int bf;                          //节点的平衡因子
    struct BiTNode *lchild,*rchild;   //左右孩子指针
}BiTNode,*BiTree;
           

2）右旋操作

示意图：

                                                                                     图11 右旋

代码如下：

void R_Rotate(BiTree *p)
{
    BiTree L;
    L=(*p)->lchild;   //L指向p的左子树根节点
    (*p)->lchild=L->rchild;   //L的右子树挂接为p的左子树
    L->rchild=(*p);
    *p=L;   //p指向新的根节点
}
           

 3）左旋操作

同理左旋代码如下：

void L_Rotate(BiTree *p)
{
    BiTree R;
    R=(*p)->rchild;           //R指向p的右子树根
    (*p)->rchild=R->lchild;   //R的左子树挂接在p的右子树上
    R->lchild=(*p);          
    *p=R;                   //p指向新的根节点
}
           

4）左平衡旋转处理

#define LH +1  //左高
#define EH 0  //等高
#define RH -1  //右高
//对以指针T所指节点为根的二叉树作平衡旋转处理，即左高右低
//本算法结束时，指针T指向新的根节点
void LeftBalance(BiTree *T)
{
	BiTree L, Lr;
	L = (*T)->lchild;  //L指向T的左子树根节点
	//T->bf=2
	switch (L->bf)
	{
	case LH:  //1  单右旋  新节点插入在T的左孩子的左子树上
		(*T)->bf = L->bf = EH;
		R_Rotate(T);
		break;
	case RH:  //-1  双旋  新节点插入在T的左孩子的右子树上
		Lr = L->rchild;  //Lr指向T的左孩子的右子树根
		switch (Lr->bf)
		{
		case LH:
			(*T)->bf = RH;
			L->bf = EH;
			break;
		case EH:
			(*T)->bf = L->bf = EH;
			break;
		case RH:
			(*T)->bf = EH;
			L->bf = LH;
			break;
		}
		Lr->bf = EH;
		L_Rotate(&(*T)->lchild);  //对T的左子树作左旋平衡处理
		R_Rotate(T);    //对T作右旋平衡处理
	}
}
           

难点：关于双旋的L->bf、T->bf和Lr->bf的变化

                                                                                                 图12

如图12所示，就是程序中L->bf=RH，Lr->bf=LH这种情况。

                                                                                               图13 

如图13所示，就是程序中L->bf=RH，Lr->bf=RH这种情况。

                                                                                                 图14 

如图14所示，就是程序中L-bf=RH，Lr->bf=EH这种情况。

5）右平衡旋转处理

右平衡旋转处理的函数代码非常类似，就不做讲解了。

6）主函数

博主注：还没理解透彻，后面再进行补充

 7、多路查找树（B树）

       为了降低对外存设备的访问次数，我们就需要新的数据结构来处理这样的问题。之前谈的树，都是一个节点可以有多个孩子，但是它自身只存储一个元素，二叉树限制更多，节点最多只能有两个孩子。在元素非常多的时候，就使得要么树的度非常大，要么树的高度非常大，甚至两者都必须足够大才行。这就使得内存存取外存次数非常多，这显然成了时间效率上的瓶颈，这迫使我们要打破每一个节点只存储一个元素的限制，为此引入了多路查找树的概念。

多路查找树，其每一个节点的孩子树可以多于两个，且每一个节点处可以存储多个元素。由于它是查找树，所有元素之间存在某种特定的排序关系。

         在这里，每一个节点可以存储多少个元素，以及它的孩子数的多少是非常关键的，为此，重点讲解它的4中特殊形式：2-3树、2-3-4树、B树和B+树。

（1）2-3树

      2-3树是其中的每一个节点都具有两个孩子（称为2节点）或三个孩子（称为3节点）。

      一个2节点包含一个元素和两个孩子（或没有孩子），不可以只有一个孩子。

      一个3节点包含一小一大两个元素和三个孩子（或没有孩子），若有三个孩子，左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两元素之间的元素。

      并且2-3树中所有叶子都在同一层次上。

1）2-3树的插入操作

插入可以分为三种情况：

• 对于孔数，插入一个节点即可，很容易理解
• 插入到一个2节点的叶子上，即把2节点变成3节点
• 插入到一个3节点中，这就比较复杂了

如图15所示：

                                                                                图15  插入操作 

通过以上分析，我们会发现，2-3树插入的传播效应导致根节点的拆分，则树的高度就会增加。

2）2-3树的删除实现

删除操作也分三种情况：

• 所删除元素位于一个3节点的叶子上
• 所删除元素位于一个2节点上
• 所删除元素位于非叶子的分支节点

具体操作如图16所示：

                                                                                图16 2-3树的删除 

当然还有很多情况，就不一一举例了，需要自己去发现和总结。

（2）2-3-4树

       2-3-4树其实就是2-3树的概念扩展，包括了4节点的使用，一个4节点包含小中大三个元素和四个孩子（或没有孩子）。如果某个4节点有孩子的话，左子树包含小于最小元素的元素；第二子树包含大于最小元素，小于第二元素的元素；第三子树包含大于第二元素，小于最大元素的元素；右子树包含大于最大元素的元素。

       由于和2-3树类似，在这里就不重复它的插入和删除操作了。

（3）B树

       B树是一种平衡的多路查找树，2-3树和2-3-4树都是B树的特例，节点最大的孩子数目称为B树的阶，因此，2-3树就是3阶B树，2-3-4树是4阶B树。

一个m阶的B树具有如下属性：

• 如果根节点不是叶子节点，则其至少有两棵子树。
• 每一个非根的分支节点都有k-1个元素和k个孩子，其中[m/2]<=k<=m，每个叶子节点n都有k-1个元素，其中[m/2]<=k<=m。
• 所有叶子节点都位于同一层次。
• 所有分支节点包含下列信息数据（n,A0,K1,A1,K2,A2,...,Kn,An），其中：Ki(i=1,2,..,n)为关键字，且Ki<Ki+1(i=1,2,...,n-1)；Ai(i=0,2,...,n)为指向子树根节点的指针，且指针Ai-1所指子树中所有节点的关键字均小于Ki(i=1,2,...,n)，An所指子树中所有节点的关键字均大于Kn，n([m/2]-1<=n<=m-1)为关键字的个数（或n+1为子树的个数）

例如，有9个数的2-3-4树转成B树示意图就如图17所示，左侧蓝色数字表示当前节点的元素个数。

                                                                                图17 由2-3-4树转成B树 

       在B树上查找的过程是一个顺时针查找节点和节点中查找关键字的交叉过程。

       例如，我们要查找数字7，首先从外存（比如硬盘中）读取得到根节点3、5、8三个元素，发现7不在当中，但在5和8之间，因此就通过A2再读取外存的6、7节点，查找所要的元素。

       至于B树的插入和删除，方式是与2-3树和2-3-4树相类似的，只不过阶数可能会很大而已。

       回到最初的问题，B树结构怎么就可以做到减少内存与外存交换数据的次数？我们的外存，比如硬盘，是将所有的信息分割成相等大小的页面，每次硬盘读写都是一个或多个完整的页面，对于一个硬盘来说，一页的长度可能是221到214个字节，在一个典型的B树应用中，要处理的硬盘数据量很大，因此无法一次全部装入内存，因此我们会对B树进行调整，使得B树的阶数（或节点的元素）与硬盘存储的页数大小相匹配，比如说一棵B树的阶为1001（即一个节点包含1000个关键字），高度为2，它可以存储超过10亿个关键字，我们只要让根节点持久地保留在内存中，那么在这棵树上，寻找某一个关键字至多需要两次硬盘的读取即可。这就好比我们普通人数钱都是一张一张的数，而银行职员数钱则是五张、十张，甚至几十张一数，速度当然比常人快了不少。

      那么对于n个关键字的m阶B树，最坏情况是要查找几次了？

第一层至少1个节点，第二层至少2个节点，由于除根节点外每个分支节点至少有[m/2]棵子树，则第三层至少有2*[m/2]节点，这样第k+1层至少有

个节点，而实际上，k+1层的节点就是叶子节点，若m阶B树有n个关键字，那么当你找到叶子节点，其实也就等于查找不成功的节点为n+1，因此

，即：

也就是说，在含有n个关键字的B树上查找时，从根节点到关键字节点的路径上涉及的节点数不超过 

.

（4）B+树

        希望遍历时每个元素只访问一次。在B树中，每个元素在该树中只出现一次，有可能在叶子节点上，也有可能在分支节点上，而在B+树中，出现在分支节点中的元素会被当作他们在该分支节点位置的中序后继者（叶子节点）中再次列出，另外，每个叶子节点都会保存一个指向后一叶子节点的指针。

                                                                                       图18 一棵B+树的示意图 

如图18所示，红色关键字即是根节点中的关键字在叶子节点再次列出，并且所有叶子节点都连接在一起。

一棵m阶的B+树和m阶的B树的差异在于：

• 有n棵子树的节点中包含有n个关键字
• 所有的叶子节点包含全部关键字的信息，及指向含这些关键字记录的指针，叶子节点本身依关键字的大小自小而大顺序连接
• 所有分支节点可以看成是索引，节点中仅含有其子树中的最大（或最小）关键字。

最大好处：若要随机查找，就从根节点出发，与B树的查找方式相同，只不过即使在分支节点找到了待查找的关键字，它也只是用来索引的，不能提供实际记录的访问，还是需要达到包含此关键字的终端节点。若需要从小关键字进行从小到大的顺序查找，就可以从最左侧叶子节点出发，不经过分支节点，而是延着指向下一个叶子节点的指针就可以遍历所有的关键字。

      B+树的结构特别适合带有范围的查找。

      B+树的插入、删除也都与B树类似，只不过插入和删除的元素都是在叶子节点上进行的。

8、散列表查找（哈希表）概述

（1）定义

直接通过关键字key得到要查找的记录内存存储位置，也就是说，我们只需要通过某个函数f，使得

存储位置=f(关键字)

那样我们可以通过查找关键字不需要比较就可以获得需要的记录的存储位置，这就是一种新的存储技术——散列技术。

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key) 

       在这里，关系f称为散列函数，又称为哈希函数，采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表。那么关键字对应的记录存储位置称为散列地址。 

（2）步骤

1）在存储时，通过散列函数计算记录的散列地址，并按此散列地址存储该记录，如图19所示。

                                                                                                  图19 

2）当查找记录时，通过同样的散列表函数计算记录的散列地址，按此散列地址访问该记录，由于存取用的是同一个散列函数，因此结果当然是相同的。

散列技术既是一种存储方法，也是一种查找方法，散列技术的记录之间不存在什么逻辑关系，它只与关键字有关系，是一个面向查找的存储结构。

散列技术最适合的求解问题是查找与给定值相等的记录。不具备很多常规数据结构的能力。

 不具备很多常规数据结构的能力，比如一个关键字对应很多记录的情况；也不适合范围查找。

       关于设计散列表，关键问题在于设计一个简单、均匀、存储利用率高的散列函数。另一个问题就是冲突，在理想情况下，每一个关键字，通过散列函数计算出来的地址都是不一样的，可现实中，时常会碰到两个关键字key1!=key2，但是有f(key1)=f(key2)，这种现象我们称为冲突，并把key1和key2称为这个散列函数的同义词。所以重点就是解决冲突问题。

9、散列函数的构造方法

（1）构造原则

1）计算简单

散列函数函数的计算时间不应该超过其他查找技术与关键字比较的时间。

2）散列地址均匀分布

保证存储空间的有效利用，并减少为处理冲突而耗费的时间。

（2）直接定址法

取关键字的某个线性函数值为散列地址，即

f(key)=a

key+b  (a、b为常数)

优点：简单、均匀，也不会发生冲突，但问题是这需要事先知道关键字的分布情况，适合查找表较小且连续的情况。现实中不常用。 

（3）数字分析法

        抽取方法是使用关键字的一部分来计算散列存储位置的方法，这在散列函数种是常用到的手段。

        数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀，就可以考虑用这个方法。

（4）平方取中法

        这个方法计算很简单，假设关键字是1234，那么它的平方就是1522756，再抽取中间的3位就是227，用作散列地址。再比如关键字是4321，那么它的平方就是18671041，抽取中间的3位就可以是671，也可以是710，用作散列地址。平方取中法比较适合于不知道关键字的分析，而位数又不是很大的情况。

（5）折叠法

       折叠法是将关键字从左到右分割成位数相等的几部分（注意最后一部分位数不够时可以短些），然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。

       比如我们的关键字是9876543210，散列表表长为三位，我们将它分成四组，987|654|321|0，然后将他们叠加求和987+654+321+0=1962，再求后3位得到散列地址为962。有时候可能还不能够保证分布均匀，不妨从一端向另一端折叠对齐相加，比如将987和321反转，再与654和0相加，得到结果为1566，此时散列地址为566.

        折叠法事先不需要知道关键字的分布，适合关键字位数较多的情况。

（6）除留余数法

此方法为最常用的构造散列函数方法，对于散列表长为m的散列函数公式为：

f(key)=key mod p (p<=m)

        mod是取模（求余数）的意思，这方法不仅可以对关键字直接取模，也可以在折叠、平方取中后再取模。本方法的关键就在于选择合适的p，p如果选择不好，就可能容易产生同义词。

        因此根据前辈们的经验，若散列表表长为m，通常p为小于或等于表长（最好接近m）的最小质数或不包含小于20质因子的合数。

（7）随机数法

f(key)=random(key)

random是随机函数，当关键字长度不等时，采用这个方法构造散列函数是比较合适的。

总结：若是字符串则可以转化为某种数字来对待，比如ASCII码或者Unicode码等，因此也就可以使用上面的这些方法了 

给出一些考虑的因素来提供参考该如何选择散列函数：

1. 计算散列地址所需的时间
2. 关键字的长度
3. 散列表的大小
4. 关键字的分布情况
5. 记录查找的频率

10、处理散列冲突的方法

（1）开放定址法

一旦发生了冲突，就去寻找下一个空的散列地址，只要散列足够大，空的散列地址总能找到，并将记录存入。

它的公式是：

比如，我们的关键字集合为{12，67，56，16，25，37，22，29，15，47，48，34}，表长为12，我们用散列函数f(key)=key mod 12。当计算前5个数{12，67，56，16，25}时，都没有冲突的散列地址，直接存入，如表2所示。

下标	1	2	3	4	5	6	7	8	9	10	11
关键字	12	25	16	67	56

      计算key=37时，发现f(key)=1，此时就与25所在的位置冲突，于是我们应用上面的公式f(37)=(f(37)+1) mod 12=2，于是37存入下标为2的位置，就这样当出现冲突时就进行换一个地址存入。

        我们把这种解决冲突的开放地址法称为线性探测法。在解决冲突时，还会碰到如48和37这种本来都不是同义词却需要争夺一个地址的情况，我们称这种现象为堆积。很显然，堆积的出现，使得我们需要不断处理冲突，无论是从存入还是查找效率都会大大降低。如果发生这样的情况，当最后一个key=34，f(key)=10，与22所在的位置冲突，可是22后面没有位置，而前面有一个空位置，尽管可以不断地求余数后得到结果，但效率很差，因此我们可以改进di=

，

，...，

，

，（q<=m/2），这样就等于是可以双向寻找可能的空位置。另外增加平方运算的目的是为了不让关键字都聚集在某一块区域，我们称这种方法为二次探测法。

,

还有一种方法是，在冲突时，对于位移量di采用随机函数计算得到，我们称之为随机探测法。 

是一个随机数列)

总之，开放定址法只要在散列表未填满时，总是能找到不发生冲突的地址，是我们常用的解决冲突的方法。 

（2）再散列函数法

对于我们的散列表来说，我们事先准备多个散列表函数。

RHi就是不同的散列函数，可以把前面说的什么除留余数、折叠、平方取中全部用上，当有冲突时，相信总会有一个可以把冲突解决。这种方法能够使得关键字不产生聚集，当然，相应地也增加了计算的时间。 

（3）链地址法

当有冲突发生时，并不想着换地方，而是在原地想办法。比如之前那个问题，对于关键字集合{12，67，56，16，25，37，22，29，15，47，48，34}，用前面同样的12为除数，进行除留余数法，得到如图20的结构，当有冲突时，只需要在当前位置给单链表加节点就行。

                                                                                              图20 

链地址法对于可能会造成很多冲突的散列函数来说，提供了绝不会出现找不到地址的保障，当然，这也就带来了查找时需要遍历单链表的性能损耗。

（4）公共溢出区法

      为所有冲突的关键字建立一个公共的溢出区来存放，所以就会有两个表：基本表和溢出表。在查找时，对给定值通过散列函数计算出散列地址后，先与基本表的相应位置进行对比，如果相等，则查找成功；如果不相等，则到溢出表去进行顺序查找。

11、散列表查找实现

（1）散列表查找算法实现

首先需要定义一个散列表的结构以及一些相关的常数，其中HashTable就是散列表结构，结构当中elem为一个动态数组。

#define SUCCESS 1
#define UNSUCCESS 0     //定义数列表长为数组的长度
#define NULLKEY -32768

typedef struct
{
    int *elem;   //数据元素存储基址，动态分配数组
    int count;   //当前数据元素个数
}HashTable;
int m=0;     //数列表表长，全局变量
           

有了结构定义，进行对散列表的初始化

//初始化散列表
Status InitHashTable(HashTable *H)
{
    int i;
    m=HASHSIZE;
    H->count=m;
    H->elem=new int[m];
    for(i=0;i<m;i++)
    {
        H->elem[i]=NULLKEY;
    }
    return OK;
}
           

 为了插入时计算地址，需要定义散列函数，散列函数可根据不同情况更改算法。

//散列函数
int Hash(int key)
{
    return key%m;  //除留余数法
}
           

初始化完成后，可以对散列表进行插入操作，假设关键字集合是{12，67，56，16，25，37，22，29，15，47，48，34}

//插入关键字散列表
void InsertHash(HashTable *H,int key)
{
    int addr=Hash(key);   //求散列地址
    while(H->elem[addr]!=NULLKEY)  //若发生冲突
    {
        addr=(addr+1)%m;          //开放定址法的线性探索
    }
    H->elem[addr]=key;      //直到有空位后插入关键字
}
           

 散列表存在后，就可以在需要的时候通过散列表查找要的记录。

//散列表查找关键字
Status SearchHash(HashTable H,int key,int *addr)
{
    *addr=Hash(key);   //求散列地址
    while(H.elem[*addr]!=key)   //发生了冲突
    {
        *addr=(*addr+1)%m;   //开放定址法的线性探测
        if(H.elem[*addr]==NULLKEY||*addr==Hash(key))  //如果循环到原点
            return UNSUCCESS;
    }
    return SUCCESS;
}
           

（2）散列表查找性能分析

当没有冲突时，效率最高，时间复杂度为O(1)，可惜只是理想情况。那么散列查找的平均查找长度取决于哪些因素了？

1）散列函数是否均匀

由于不同的散列函数对同一组随机关键字，产生冲突的可能性是相同的，因此不考虑它对平均查找长度的影响。

2）处理冲突的方法

比如线性探测处理冲突可能会产生堆积，显然就没有二次探测法好，而链地址法处理冲突不会产生任何堆积，因而具有更佳的平均查找性能。

3）散列表的装填因子

装填因子

=填入表中的记录个数/散列表长度。

标志着散列表的装满程度。

越大，产生冲突的可能性就越大，也就是说散列表的平均查找长度取决于装填因子，而不是取决于查找集合中记录的个数。通常我们都是将散列表的空间设置得比查找集合大，此时虽然浪费了一定的空间，但换来的是查找效率的大大提升。