查找算法总结

数据结构与算法

---

顺序表查找

查找表按照操作方式来分有两大种：静态查找表和动态查找表。

静态查找表（Static Search Table）：只作查找操作的查找表。
它的主要操作有：（1）查询某个“特定的”数据元素是否在查找表中。（2）检索某个“特定的”数据元素和各种属性。
动态查找表（Dynamic Search Table）：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。
动态查找表的操作有：（1）查找时插入数据元素。（2）查找时删除数据元素。

有序表查找

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

该算法每次都要判断i是否越界，可设置哨兵

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

时间复杂度 O(n)

二分查找

前提是有序数组

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
            /* 若相等则说明mid即为查找到的位置 */
            return mid;            
    }
    return 0;
}

时间复杂度 O(logn)

插值查找

二分查找的推广，有时候不一定折半最优。

$$mid = \frac{low + high}{2} = low + \frac{1}{2}(high - low)$$
也就是mid等于最低下标low加上最高下标high与low的差的一半。1/2可以进行改进，改进为下面的计算方案：
$$mid = \frac{low + high}{2} = low + \frac{key - a[low]}{a[high] - a[low]}(high - low)$$
相应代码需要改写为

mid=low+ (high-low)*(key-a[low])/(a[high]-a[low]); /* 插值 */

时间复杂度也是O(logn)，但对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好得多。反之，数组中如果分布类似{0,1,2,2000,2001,......,999998,999999}这种极端不均匀的数据，用插值查找未必是很合适的选择。

斐波那契查找

利用黄金分割原理进行查找：
斐波那契数列 F={0,1,1,2,3,5,8,13,21,34...}

/* 斐波那契查找 */
int Fibonacci_Search(int *a, int n, int key)
{
    int low, high, mid, i, k;
    /*定义最低下标为记录首位 */
    low = 1;                          
    /*定义最高下标为记录末位 */
    high = n;                         
    k = 0;
    /* 计算n位于斐波那契数列的位置 */
    while (n > F[k] - 1)              
        k++;
    /* 将不满的数值补全 */
    for (i = n; i < F[k] - 1; i++)    
       a[i] = a[n];
    while (low <= high)
    {
        /* 计算当前分隔的下标 */
        mid = low + F[k - 1] - 1;     
        /* 若查找记录小于当前分隔记录 */
        if (key < a[mid])             
        {
            /* 最高下标调整到分隔下标mid-1处 */
            high = mid - 1;           
            /* 斐波那契数列下标减一位 */
            k = k - 1;                
        }
        /* 若查找记录大于当前分隔记录 */
        else if (key > a[mid])        
        {
            /* 最低下标调整到分隔下标mid+1处 */
            low = mid + 1;            
            /* 斐波那契数列下标减两位 */
            k = k - 2;                
        }
        else
        {
            if (mid <= n)
                /* 若相等则说明mid即为查找到的位置 */
                return mid;           
            else
                /* 若mid>n说明是补全数值，返回n */
                return n;             
        }
    }
    return 0;
}

斐波那契查找算法的核心在于：
1）当key=a[mid]时，查找就成功；
2）当key<a[mid]时，新范围是第low个到第mid-1个，此时范围个数为F[k-1]-1个；
3）当key>a[mid]时，新范围是第m+1个到第high个，此时范围个数为F[k-2]-1个。

就是说，如果要查找的记录在右侧，则左侧的数据都不用再判断了，不断反复进行下去，对处于当中的大部分数据，其工作效率要高一些。所以尽管斐波那契查找的时间复杂也为O(logn)，但就平均性能来说，斐波那契查找要优于折半查找。可惜如果是最坏情况，比如这里key=1，那么始终都处于左侧长半区在查找，则查找效率要低于折半查找。

折半查找是进行加法与除法运算（mid=(low＋high)/2），插值查找进行复杂的四则运算（mid=low＋(high-low)*(key-a[low])/(a[high]-a[low])），而斐波那契查找只是最简单加减法运算（mid=low＋F[k-1]-1），在海量数据的查找过程中，这种细微的差别可能会影响最终的查找效率。

线性索引查找

数据结构的最终目的是提高数据的处理速度，索引是为了加快查找速度而设计的一种数据结构。索引就是把一个关键字与它对应的记录相关联的过程，一个索引由若干个索引项构成，每个索引项至少应包含关键字和其对应的记录在存储器中的位置等信息。索引技术是组织大型数据库以及磁盘文件的一种重要技术。

索引按照结构可以分为线性索引、树形索引和多级索引。所谓线性索引就是将索引项集合组织为线性结构，也称为索引表。

稠密索引

稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引项。，索引项一定是按照关键码有序的排列。索引项有序也就意味着，要查找关键字时，可以用到折半、插值、斐波那契等有序查找算法，大大提高了效率。

倒排索引

倒排索引源于实际应用中需要根据属性（或字段、次关键码）的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引。

倒排索引的优点显然就是查找记录非常快，基本等于生成索引表后，查找时都不用去读取记录，就可以得到结果。但它的缺点是这个记录号不定长，维护比较困难，插入和删除操作都需要作相应的处理。

分块索引

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

分块有序，是把数据集的记录分成了若干块，并且这些块需要满足两个条件：

• 块内无序，即每一块内的记录不要求有序。当然，你如果能够让块内有序对查找来说更理想，不过这就要付出大量时间和空间的代价，因此通常我们不要求块内有序。
• 块间有序，例如，要求第二块所有记录的关键字均要大于第一块中所有记录的关键字，第三块的所有记录的关键字均要大于第二块的所有记录关键字……因为只有块间有序，才有可能在查找时带来效率。

如图所示，分块索引的索引项结构分三个数据项：

• 最大关键码，它存储每一块中的最大关键字，这样的好处就是可以使得在它之后的下一块中的最小关键字也能比这一块最大的关键字要大；
• 存储了块中的记录个数，以便于循环时使用；
• 用于指向块首数据元素的指针，便于开始对这一块中记录进行遍历。

分块索引表中查找，需要分两步进行：
- 1.在分块索引表中查找要查关键字所在的块。由于分块索引表是块间有序的，因此很容易利用折半、插值等算法得到结果。
- 2.根据块首指针找到相应的块，并在块中顺序查找关键码。因为块中可以是无序的，因此只能顺序查找。

分块索引的平均查找长度
设n个记录的数据集被平均分成m块，每个块中有t条记录，显然n=m×t，或者说m=n/t。再假设Lb为查找索引表的平均查找长度，因最好与最差的等概率原则，所以Lb的平均长度为(m+1)/2。Lw为块中查找记录的平均查找长度，同理可知它的平均查找长度为(t+1)/2。

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

$$ASL_w = \frac{1}{2}(m + t) + 1 = \frac{1}{2}(\frac{n}{t} + t) + 1$$
平均长度不仅仅取决于数据集的总记录数n，还和每一个块的记录个数t相关。最佳的情况就是分的块数m与块中的记录数t相同，此时意味着n=m×t=t2，即ASLw=1/2·(n/t+t)+1=t+1=sqrt(n)+1。

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

二叉排序树

二叉排序树（Binary Sort Tree），又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树。

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结构的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 它的左、右子树也分别为二叉排序树。

构造一棵二叉排序树的目的，并不是为了排序，而是为了提高查找和插入删除关键字的速度。在一个有序数据集上的查找，速度总是要快于无序的数据集的，而二叉排序树这种非线性的结构，也有利于插入和删除的实现。

二叉树结构：

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

二叉树查找实现：

/* 递归查找二叉排序树T中是否存在key,  指针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)
        /* 在左子树继续查找 */
        return SearchBST(T->lchild, key, T, p);    
    else
        /* 在右子树继续查找 */
        return SearchBST(T->rchild, key, T, p);    
}

二叉排序树插入操作

/* 当二叉排序树T中不存在关键字等于key的数据元素时，插入key并返回TRUE，否则返回FALSE */
Status InsertBST(BiTree *T, int key)
{
    BiTree p, s;
    /* 查找不成功 */
    if (!SearchBST(*T, key, NULL, &p))    
    {
        s = (BiTree)malloc(sizeof(BiTNode));
        s->data = key;
        s->lchild = s->rchild = NULL;
        if (!p)
            /* 插入s为新的根结点 */
            *T = s;                       
        else if (key < p->data)
            /* 插入s为左孩子 */
            p->lchild = s;                
        else
            /* 插入s为右孩子 */
            p->rchild = s;                
        return TRUE;
    }
    else
        /* 树中已有关键字相同的结点，不再插入 */
        return FALSE;                     
}
int main()
{
    int i;
    int a[10] = { 62, 88, 58, 47, 35, 73, 51, 99, 37, 93 };
    BiTree T = NULL;
    for (i = 0; i < 10; i++)
    {
        InsertBST(&T, a[i]);
    }
    return 0;
}

二叉排序树删除操作
找到需要删除的结点p的直接前驱（或直接后继）s，用s来替换结点p，然后再删除此结点s

* 若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点,并返回TRUE；否则返回FALSE */
Status DeleteBST(BiTree *T, int key)
{
    /* 不存在关键字等于key的数据元素 */
    if (!*T)                      
        return FALSE;
    else
    {
        /* 找到关键字等于key的数据元素 */
        if (key == (*T)->data)    
            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; s = (*p)->lchild;
        /* 转左，然后向右到尽头(找待删结点的前驱) */
        while (s->rchild)             
        {
            q = s; s = s->rchild;
        }
        /* s指向被删结点的直接前驱 */
        (*p)->data = s->data;         
        if (q != *p)
            /* 重接q的右子树 */
            q->rchild = s->lchild;    
        else
            /* 重接q的左子树 */
            q->lchild = s->lchild;    
        free(s);
    }
    return TRUE;
}

平衡二叉树

平衡二叉树（Self-Balancing Binary SearchTree或Height-Balanced Binary Search Tree），是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1。
平衡因子BF（Balance Factor）： 二叉树上结点的左子树深度减去右子树深度的值，平衡二叉树上所有结点的平衡因子只可能是-1、0和1。
最小不平衡子树： 距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树

原理

平衡二叉树构建的基本思想就是在构建二叉排序树的过程中，每当插入一个结点时，先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树。在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。

因为BF值为正，因此我们将整个树进行右旋（顺时针旋转），此时结点2成了根结点，3成了2的右孩子，这样三个结点的BF值均为0，非常的平衡
然后我们再增加结点4，平衡因子没有超出限定范围（-1，0，1），如图3。增加结点5时，结点3的BF值为-2，说明要旋转了。由于BF是负值，所以我们对这棵最小平衡子树进行左旋（逆时针旋转）


增加结点9，此时结点7的BF变成了-2，理论上我们只需要旋转最小不平衡子树7、9、10即可，但是如果左旋转后，结点9就成了10的右孩子，这是不符合二叉排序树的特性的，此时不能简单的左旋，如图11所示。

仔细观察图11，发现根本原因在于结点7的BF是-2，而结点10的BF是1，也就是说，它们俩一正一负，符号并不统一，而前面的几次旋转，无论左还是右旋，最小不平衡子树的根结点与它的子结点符号都是相同的。故应先把符号转到统一。

算法

二叉排序树的结点结构

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

右旋操作

/* 对以p为根的二叉排序树作右旋处理，
处理之后p指向新的树根结点，即旋转处理之前的左子树的根结点 */
void R_Rotate(BiTree *P)
{
    BiTree L;
    /* L指向P的左子树根结点 */
    L = (*P)->lchild;            
    /* L的右子树挂接为P的左子树 */
    (*P)->lchild = L->rchild;    
    L->rchild = (*P);
    /* P指向新的根结点 */
    *P = L;                      
}

此函数代码的意思是说，当传入一个二叉排序树P，将它的左孩子结点定义为L，将L的右子树变成P的左子树，再将P改成L的右子树，最后将L替换P成为根结点。这样就完成了一次右旋操作，如图8-7-9所示。图中三角形代表子树，N代表新增结点。

左旋操作

/* 对以P为根的二叉排序树作左旋处理，处理之后P指向新的树根结点
即旋转处理之前的右子树的根结点0 */
void L_Rotate(BiTree *P)
{
    BiTree R;
    /* R指向P的右子树根结点 */
    R = (*P)->rchild;            
    /* R的左子树挂接为P的右子树 */
    (*P)->rchild = R->lchild;    
    R->lchild = (*P);
    /* P指向新的根结点 */
    *P = R;                      
}

左平衡旋转处理的函数代码

#define LH +1  /* 左高 */
#define EH 0   /* 等高 */
#define RH -1  /* 右高 */
/* 对以指针T所指结点为根的二叉树作左平衡旋转
   处理 */
/* 本算法结束时，指针T指向新的根结点 */
void LeftBalance(BiTree *T)
{
    BiTree L,Lr;
    /* L指向T的左子树根结点 */
    L = (*T)->lchild;               
    switch (L->bf)
    {                               
    /* 检查T的左子树的平衡度，并作相应平衡处理 */
    /* 新结点插入在T的左孩子的左子树上，要作单右旋处理 */
    case LH:                        
        (*T)->bf = L->bf = EH;
        R_Rotate(T);
        break;
    /* 新结点插入在T的左孩子的右子树上，要作双旋处理 */
    case RH:                        
        /* Lr指向T的左孩子的右子树根 */
        Lr = L->rchild;             
        /* 修改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;
        /* 对T的左子树作左旋平衡处理 */
        L_Rotate(&(*T)->lchild);    
        /* 对T作右旋平衡处理 */
        R_Rotate(T);                
    }
}

右平衡旋转处理的函数代码非常类似。

主函数

/* 若在平衡的二叉排序树T中不存在和e有相同关键
   字的结点，则插入一个 */
/* 数据元素为e的新结点并返回1，否则返回0。若
   因插入而使二叉排序树 */
/* 失去平衡，则作平衡旋转处理，布尔变量taller
   反映T长高与否。 */
Status InsertAVL(BiTree *T, int e, Status *taller)
{
    if (!*T)
    {                                                    
        /* 插入新结点，树“长高”，置taller为TRUE */
        *T = (BiTree)malloc(sizeof(BiTNode));
        (*T)->data = e;
        (*T)->lchild = (*T)->rchild = NULL;
        (*T)->bf = EH;
        *taller = TRUE;
    }
    else
    {
        if (e == (*T)->data)
        {                                                
            /* 树中已存在和e有相同关键字的结点则不再插入 */
            *taller = FALSE;
            return FALSE;
        }
        if (e < (*T)->data)
        {                                                
            /* 应继续在T的左子树中进行搜索 */
            /* 未插入 */
            if (!InsertAVL(&(*T)->lchild, e, taller))    
                return FALSE;
            /* 已插入到T的左子树中且左子树“长高” */
            if (*taller)                                 
            {
                /* 检查T的平衡度 */
                switch ((*T)->bf)                        
                {
                /* 原本左子树比右子树高，需要作左平衡处理 */
                case LH:                                 
                    LeftBalance(T);
                    *taller = FALSE;
                    break;
                /* 原本左右子树等高，现因左子树增高而树增高 */
                case EH:                                 
                    (*T)->bf = LH;
                    *taller = TRUE;
                    break;
                /* 原本右子树比左子树高，现左右子树等高 */
                case RH:                                 
                    (*T)->bf = EH;
                    *taller = FALSE;
                    break;
                }
            }
        }
        else
        {                                                
            /* 应继续在T的右子树中进行搜索 */
            /* 未插入 */
            if (!InsertAVL(&(*T)->rchild, e, taller))    
                return FALSE;
            /* 已插入到T的右子树且右子树“长高” */
            if (*taller)                                 
            {
                /* 检查T的平衡度 */
                switch ((*T)->bf)                        
                {
                /* 原本左子树比右子树高，现左、右子树等高 */
                case LH:                                 
                    (*T)->bf = EH;
                    *taller = FALSE;
                    break;
                /* 原本左右子树等高，现因右子树增高而树增高 */
                case EH:                                 
                    (*T)->bf = RH;
                    *taller = TRUE;
                    break;
                 /* 原本右子树比左子树高，需要作右平衡处理 */
                case RH:                                
                    RightBalance(T);
                    *taller = FALSE;
                    break;
                }
            }
        }
    }
    return TRUE;
}

查找时间复杂度就为O(logn)，而插入和删除也为O(logn)。这显然是比较理想的一种动态查找表算法。

多路查找树

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

2-3树

2-3树：其中的每一个结点都具有两个孩子（我们称它为2结点）或三个孩子（我们称它为3结点）。

2-3树的插入实现
对于2-3树的插入来说，与二叉排序树相同，插入操作一定是发生在叶子结点上。可与二叉排序树不同的是，2-3树插入一个元素的过程有可能会对该树的其余结构产生连锁反应。

2-3树的删除实现
2-3树的删除也分为三种情况。与插入相反

2-3-4树

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

插入过程：

删除过程：

B树

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

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

• 如果根结点不是叶结点，则其至少有两棵子树。
• 每一个非根的分支结点都有k-1个元素和k个孩子，每一个叶子结点n都有k-1个元素。
• 所有叶子结点都位于同一层次。
• 所有分支结点包含下列信息数据
  

  （n,A0,K1,A1,K2,A2,...,Kn,An），其中：Ki(i=1,2,...,n)为关键字，且Ki

一个典型的B树应用中，要处理的硬盘数据量很大，因此无法一次全部装入内存。因此我们会对B树进行调整，使得B树的阶数（或结点的元素）与硬盘存储的页面大小相匹配。比如说一棵B树的阶为1001（即1个结点包含1000个关键字），高度为2，它可以储存超过10亿个关键字，我们只要让根结点持久地保留在内存中，那么在这棵树上，寻找某一个关键字至多需要两次硬盘的读取即可。
通过这种方式，在有限内存的情况下，每一次磁盘的访问我们都可以获得最大数量的数据。由于B树每结点可以具有比二叉树多得多的元素，所以与二叉树的操作不同，它们减少了必须访问结点和数据块的数量，从而提高了性能。可以说，B树的数据结构就是为内外存的数据交互准备的。

B+树

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

这样的数据结构最大的好处就在于，如果是要随机查找，就从根结点出发，与B树的查找方式相同，只不过即使在分支结点找到了待查找的关键字，它也只是用来索引的，不能提供实际记录的访问，还是需要到达包含此关键字的终端结点。

哈希表查找

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f（key）。查找时，根据这个确定的对应关系找到给定值key的映射f（key），若查找集合中存在这个记录，则必定在f（key）的位置上。
这种对应关系f称为散列函数，又称为哈希（Hash）函数。按这个思想，采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表（Hash table）。关键字对应的记录存储位置称为散列地址。

散列技术既是一种存储方法，也是一种查找方法。然而它与线性表、树、图等结构不同的是，前面几种结构，数据元素之间都存在某种逻辑关系，可以用连线图示表示出来，而散列技术的记录之间不存在什么逻辑关系，它只与关键字有关联。因此，散列主要是面向查找的存储结构。

散列函数的构造方法

原则：
计算简单
散列地址分布均匀

直接定址法

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

f(key)=a×key+b（a、b为常数）

这样的散列函数优点就是简单、均匀，也不会产生冲突，但问题是这需要事先知道关键字的分布情况，适合查找表较小且连续的情况。由于这样的限制，在现实应用中，此方法虽然简单，但却并不常用。

折叠法

折叠法是将关键字从左到右分割成位数相等的几部分（注意最后一部分位数不够时可以短些），然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
比如关键字9876543210，散列表表长为三位，将它分为四组，987|654|321|0，然后将它们叠加求和987+654+321+0=1962，再求后3位得到散列地址为962。
有时可能这还不能够保证分布均匀，可以从一端向另一端来回折叠后对齐相加。比如我们将987和321反转，再与654和0相加，变成789+654+123+0=1566，此时散列地址为566。
折叠法事先不需要知道关键字的分布，适合关键字位数较多的情况。

数字分析法

比如要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是相同的。而选择后面的四位成为散列地址就是不错的选择。如果这样的抽取工作还是容易出现冲突问题，还可以对抽取出来的数字再进行反转（如1234改成4321）、右环位移（如1234改成4123）、左环位移、甚至前两数与后两数叠加（如1234改成12+34=46）等方法。总的目的就是为了提供一个散列函数，能够合理地将关键字分配到散列表的各位置。
这里提到了一个关键词——抽取。抽取方法是使用关键字的一部分来计算散列存储位置的方法，这在散列函数中是常常用到的手段。
数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀，就可以考虑用这个方法。

除留余数法

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

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

mod是取模。事实上，这方法不仅可以对关键字直接取模，也可在折叠、平方取中后再取模。

本方法的关键就在于选择合适的p，p如果选得不好，就可能会容易产生同义词。
根据经验，若散列表表长为m，通常p为小于或等于表长（最好接近m）的最小质数或不包含小于20质因子的合数。

平方取中法

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

随机数法

选择一个随机数，取关键字的随机函数值为它的散列地址。也就是f(key)=random(key)。这里random是随机函数。当关键字的长度不等时，采用这个方法构造散列函数是比较合适的。

处理散列冲突的方法

在使用散列函数后发现两个关键字key1≠key2，但是却有f(key1)=f(key2)，此时发生冲突，设计得再好的散列函数也不可能完全避免冲突。

开放定址法

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

fi(key)=(f(key)+di)MOD m(di=1,2,3,......,m-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}时，都是没有冲突的散列地址，直接存入

计算key=37时，发现f(37)=1，此时就与25所在的位置冲突。于是应用上面的公式f(37)=(f(37)+1)mod 12=2。于是将37存入下标为2的位置

这种解决冲突的开放定址法称为线性探测法。
类似的，还有其他方法：
二次探测法

fi(key)=(f(key)+di)MOD m(di=12,-12,22,-22,...,q2,-q2,q≤m/2)

随机探测法

fi(key)=(f(key)+di)MOD m(di是一个随机数列)

这里的随机其实是伪随机数。伪随机数是说，如果设置随机种子相同，则不断调用随机函数可以生成不会重复的数列，在查找时，用同样的随机种子，它每次得到的数列是相同的，相同的di当然可以得到相同的散列地址。

链地址法

将所有关键字为同义词的记录存储在一个单链表中，称这种表为同义词子表，在散列表中只存储所有同义词子表的头指针
。对于关键字集合{12,67,56,16,25,37,22,29,15,47,48,34}，用前面同样的12为除数，进行除留余数法，可得到如图结构，此时，已经不存在什么冲突换址的问题，无论有多少个冲突，都只是在当前位置给单链表增加结点的问题。

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

再散列函数法

事先准备多个散列函数:

fi(key)=RHi(key)(i=1,2,...,k)
这里RHi就是不同的散列函数，可以把前面说的除留余数、折叠、平方取中全部用上。每当发生散列地址冲突时，就换一个散列函数计算，相信总会有一个可以把冲突解决掉。这种方法能够使得关键字不产生聚集，当然，相应地也增加了计算的时间。

公共溢出法

为所有冲突的关键字建立了一个公共的溢出区来存放

在查找时，对给定值通过散列函数计算出散列地址后，先与基本表的相应位置进行比对，如果相等，则查找成功；如果不相等，则到溢出表去进行顺序查找。如果相对于基本表而言，有冲突的数据很少的情况下，公共溢出区的结构对查找性能来说还是非常高的。

散列表查找实现

定义散列表的结构:

#define SUCCESS 1
#define UNSUCCESS 0
/* 定义散列表长为数组的长度 */
#define HASHSIZE 12    
#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 = (int *)malloc(m * sizeof(int));
    for (i = 0; i < m; i++)
        H->elem[i] = NULLKEY;
    return OK;
}

定义散列函数

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

/* 插入关键字进散列表 */
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;
}

散列表查找性能分析

• 散列函数是否均匀
• 处理冲突的方法
• 散列表的装填因子
  

  所谓的装填因子α=填入表中的记录个数/散列表长度。α标志着散列表的装满的程度。当填入表中的记录越多，α就越大，产生冲突的可能性就越大。