数据结构与算法－散列表

无论是顺序表还是树表，查找数据元素时要进行一系列的键值比较的过程，为了减少比较次数，就需要使数据元素的存储位置和键值之间建立某种联系，为此我们就需要使用散列技术动态查找表。首先我们需要熟悉几个基本一概念：

1. 散列函数－数据元素的键值和存储位置之间建立的对应关系。

2. 散列表－用键值通过散列函数获取存储位置的这种存储方式构造的存储结构。

3. 散列地址－由散列函数决定数据元素的存储位置，该位置 称为散列地址。

4. 散列查找－给定关键字，由散列函数进行转换在表中的地址，查看该位置上有无欲查的元素，有则输入该元素，没有则将它插入到该位置上。

理想的情况下，使用的散列函数使每个键值与散列地址是分别对应的，但在实际应用中，这种情况很少出现。若两个元素的键值不相等，但是通过散列函数转换后的散列地址却是一样的，这就形成了冲突，因为散列函数是从键值集合到地址集合的映像，所以一般情况下，冲突只能尽可能的减少，而不能完全避免。因此，采用散列技术时需要考虑两个问题：

第一，如何选择"均匀的"散列函数？

一个好的散列函数应该满足计算简便，运算速度快，随机性好，地址尽可能均匀分布，冲突小。

第二，用什么方法有效解决冲突？

解决冲突的办法将在下面散列表实现中讲解。

常用的散列法

1. 数字分析法

数字分析法又称数字选择法，其方法是收集所有可能出现的键值，排列在一起，对键值的每一位进行分析，选择分布较均匀若干位组成散列地址。所取的位数取决于散列表的表长，若表长为100，取2位即可。

假定已知可能出现的键值如下：

对所有的键值分析不难看出，左起的前三位都是“7 1 2”，第5位只能取1、4，第7位只能取6、7、8，所以这5位都不可取。剩下的4、6、8、9位都是分布较均匀的，可考虑将它们或它们中的几位组织起来作为散列地址。

2. 除留余数法

除留余数法是一种简单有效却最常用的构造方法，其方法是选择一个不大于散列表长n的正整数p，以键值除以p所得的余数作为散列地址，值得注意的是，这一方法的关键在于p的选择，若p选择的不合适，容易发生冲突，通常应遵循以下规则：

1. p不取偶数。

2. p不取关键字字符集的n倍。

3. 一般p选为最接近表长的质数。

3. 平方取中法

平方取中法以键值平方的中间几位作为散列地址。这一方法计算简单，是一种较常用的构造散列函数的方法，通常在选定散列函数时不一定能知道键值的分布情况，取其中哪几位也不一定合适，而一个数的平方中间几位与这个数的每一位都有关，所得散列地址比较均匀。

4. 基数转换法

将键值看成另一种进制的数再转换成原来进制的数，然后选其中几位作为散列地址。

例如：对于一个十进制键值443730，先把它看成十三进制的数并转换为十进制的数，然后根据散列表的长度从中选取几位作散列地址。

散列表的实现

由于冲突不可避免，所以采用散列技术需要考虑的第二个问题是如何解决冲突。

在遇到冲突时，会按照一定的规则选择该地址的下一个址，如果仍然冲突，则继续按规则选择下一个地址，以此类推直到不发生冲突为止。

通常用来解决冲突的办法有以下几种：

1. 线性探测法

对任何键值 key，设H(key) = d，设散列表的容量为m，则线性探测法生成的后继散列地址为：

d+1，d+2，...，m-1，0，1，...，d-1

例如：如下图所示，长度为13的散列表，其散列函数为H(key) = key mod 13，在表中已填入键值分别为16，30，54的元素。现要插入其键值 为29的元素，散列函数求出散列地址为3，在地址3上已有元素16，发生冲突。应用线性探测法，得到下一个地址为d+1=4，仍冲突，则再求下一个地址d+2 = 5，这个位置上没有元素，将元素填入散列表中序号为5的单元。

从上面的例子可以看出，用线性探测法生成后继散列地址计算简单，但由于探测的是一个连续的地址续列，这样容易导致非同义词之间对同一个散列地址出现争夺现象，俗称"堆积"，为了减小堆积的机会，应设法使后继散列地址尽量均匀的分布在整个散列表中。

2. 二次探测法

二次探测法的基本思想：生成的后继散列地址不是连续的，而是跳跃式的，以便为后续数据元素留下空间而减少堆积。按照二次探测法，键值key的散列地址序列为：

其中m为散列表的表长，i = 1^2，-1^2，2^2，-2^2，...，k^2，-k^2，其中k<=m/2

例如：仍然使用线性探测法中的散列表和散列函数，插入键值为29的元素，当发生冲突时，使用二次探测法，得到下一个地址d1 = (3+1^2) mod 13 = 4，仍然冲突，则再求一下地址d2 = (3-1^2) mod 13 = 2，仍然冲突，直到散列地址为d3 = (3+2^2) mod 13 = 7时其位置没有元素，所以将元素填入散列表中序号为7的位置。

二次探测法的缺点是不易探测到整个散列表的空间，也就是说，上述后继散列地址可能难以包括散列表的所有存储位置。

3.链地址法

链地址法是对每一个同义词都建一个单链表来解决冲突。

设选定的散列函数H，H的值域(即散列地址的范围)为0~(n-1)。设置一个指针向量Pointer HP[n]，其中每个指针HP[i]指向一个单链表，该单链表用于存储散列地址为i的数据元素，每一个这样的单链表称为一个同义词子表。

例如：若选定的散列函数为 H(key) = key mod 13，已存入的键值为26、41、25、05、07、15、12、49、51、31、62的散列表。

4. 多重散列法

此法要求设立多个散列函数Hi，i=1，...，k，当给定值key与散列表中的某个值是相对于某个散列函数 Hi 的同义词而发生冲突时，继续计算这个给定值key在下一个散列函数H(i+1)下的散列地址，直到不再产生冲突为止。这种方法的优点是不易产生"堆积"，缺点是计算量较大。

5. 公从溢出区法

这种方法的散列表由两个一维数组组成。一个称为基本表，它实际上就是上面所说的散列表，另一个称为溢出表。插入首先在基本表上进行，假如发生冲突，则将同义词存入溢出表。这样，基本表不可能发生冲突。

散列表基本操作算法

1. 链地址法散列表

类型定义

// 定义表长
const int n=20;
typedef struct  TagNode{
    KeyType key;
    struct TagNode *next;
   
}*Pointer ,Node;

typedef Pointer LinkHash[n];

查找算法

Pointer SeahchLinkHash(KeyType key,LinkHash HP){

    // 计算key的散列地址
    int i = H(key);
    // 将同义词子表表头指针传给p
    p = HP[i];
    if(p==NULL){
        return NULL;
    };
    // 循环扫描
    while((p!=NULL) && (p->key!=key)){
        p = p->next;
    };
    return p 

}

插入算法

void InsertLinkHash(KeyType key, LinkHash HP){
    if (SearchLinkHash(key, HP) == NULL){
        int i = H(key);
        // 生成新结点
        q = Pointer malloc(size(Node));
        q->key = key;
        // 将新结点插到同义子表的表头结点之后，原表首结点之前
        q->next = HP[i];
        HP[i] = q;
    }
}

删除算法

void DeleteLinkHash(KeyType key, LinkHash HP){

    int i=H(key);

    if(HP[i]==NULL){
        // 同义词子表为空则返回
        return;
    }else{
        p = HP[i];
        // 待删结点位于子表表首
        if(p->key == key){
            HP[i] = p->next;
            free(p);
            return;
        }else{
            // 循环子表
            while(p->next!=NULL){
                q = p;
                p = p->next;
                if(p->key == key){
                    q->next = p->next;
                    free(p);
                    return;
                }
            }
        }

    }
  
}

2. 线性探测法散列表

类型定义

const int MaxSize = 20;
typedef struct{
    KeyType key;
}Element;
typedef Element OpenHash[MaxSize];

查找算法

int SearchOpenHash(KeyType key,OpenHash HL){
    // 计算散列地址
    int d = H(key);
    int i = d;
    while((HL[i].key!=NULL) && (HL[i].key!=key)){
        i = (i+1)%m;
    };
    if(HL[i].key ==key){
        // 查找成功
        return i;
    }else{
        // 查找失败
        return 0;
    }

}