数据结构与算法：散列表

2023-09-11

字数统计: 1.7k字 | 阅读时长≈ 6分

散列表定义

散列表（HashTable，也叫哈希表），是根据关键码值(Key)而直接进行访问的数据结构。也就是说，它通过把键值映射到整数的方法(Value=f(Key))，来访问记录，这加快了查找速度。

在存储散列表时，通过散列函数来确定每个键值对应的存储位置，当我们要查找一个Key时，便可以通过散列函数直接找到Value的位置。

散列冲突：查找时可能会出现f(Key1)=f(Key2)这种情况，即两个不同的Key，通过散列函数计算出来的值相同，这种现象称为散列冲突。

散列表的实现

为了实现散列表，我们需要一个散列函数，以下是散列函数的几个构造方法。

直接定址法

直接定址法就是取关键码的某个线性函数值为散列地址。
定义f(Key)=a*Key+b (a,b为常数)，f(Key)的值就是散列地址。

假设有1-100个数字作为年龄，以年龄为Key，对应人数为Value，就可以使用直接定址法。

数字分析法

散列表的Key是数字，数字分析法就是分析数字的每一位特征，取数字的各个数位来构造散列函数。
例如以手机号或者身份证号作为Key时，就可以使用数字分析法。

还是以手机号为例，在设计散列函数时，可以选取手机号的后四位作为Key，为防止冲突，还可以将后四位反转、右环移、左环移等，这样就可以保证Key的分布均匀。

平方取中法

取关键码平方后的中间几位作为散列地址。

假如Key=1234，我们可以取Key的平方15227，再取中间的321作为散列地址。
它适用于关键字分布未知且位数不是很大的情况。

折叠法

将关键字分割成位数相等的几个部分（最后一部分可以不等），然后将这几部分叠加求和，然后按散列表的长度，取后几位作为散列地址。

例如Key=123456789，可以分割成123+456+789=1368，取后三位368作为散列地址。
折叠法适用于关键字位数比较大且不需要知道关键字分布的情况。

除留余数法

取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。
散列函数定义为f(Key)=Key%p (p<=m)，p的取值范围根据实际情况而定。

例如有12个数据，我们取p=12，得到如下表：

散列地址	0	1	2	3	4	5	6	7	8	9	10	11
Key	12	25	38	15	16	29	78	67	56	21	22	47

但如果有同时出现18、30，那么就会发生冲突，所以p的取值要小于等于m的最小质数。

随机数法

选择一个随机函数，把关键码映射成这个函数输出的值，作为散列地址。
散列函数定义为f(Key)=Random(Key),Random为随机函数

处理冲突

当两个Key的散列地址发生冲突时，只需要在表中找到一个空位将冲突Key放入即可，可以使用以下方法。

开放地址法

开放地址法就是当冲突发生时，按照某种规则取一个下一地址作为新的存储地址。

线性探测法

公式定义为：f(Key)=(f(Key)+di)%m (di<=m-1)，m为散列表的长度。

假设有集合{12,67,56,16,25,37,22,29,15,47,48,34},表长为12，用f(Key)=Key%12。
当计算24与37时，它们的f(Key)都为1，发生冲突，所以对于37，带入公式f(Key)=(f(Key)+1)%12=2，所以37应该插入到第2个位置，此时冲突便解决。

假如加入50，计算时又与37在的位置冲突，而50与37本来可以不冲突，我们成这张现象为堆积。

二次探测法

我们重新定义公式：f(Key)=(f(Key)+di)%m (di=1^2,-1^2,2^2,-2^2……q^2,-q^2)，q<=m/2,m为散列表的长度。

这样在寻找空址时，我们就可以双向寻找，可以不让关键字都聚集在某一块区域。

随机探测法

随机探测法与二次探测法类似，只是随机探测法是随机找一个位置。

将公式定义为：f(Key)=(f(Key)+di)%m，di为随机数列，m为散列表的长度。

再散列表法

对于散列表，我们可以使用多个散列函数寻找地址，当发生冲突时可以将冲突的Key使用另一个散列函数寻找地址，直到找到空位。
但作为代价，它的时间性能可能会变差。

链地址法

核心思路在于当发生冲突时，不再寻找新的地址，而是使用一个链表将所有冲突的Key连接起来。
链地址法对于会发生很多冲突的散列函数来说，提供了不会找不到地址的保障，但代价却是查找的性能会下降。

建立公共溢出区

建立公共溢出区，将所有冲突的Key放在一个公共溢出区，将所有冲突的Key放在公共溢出区。
在查找时，先通过散列函数寻找地址，再与基本表中内容进行比较，相等则取出，冲突则到公共溢出区寻找。
对于冲突比较少的散列函数来说，建立公共溢出区可以提高查找的效率。

散列表的实现

定义以下结构：

#define NULLKEY 2^31-1
#define HashSize 12
struct HashTable
{
    int *Elem;
    int *Cur;
    int TableSize;
}
int m=0;

m为散列表的长度，作为全局变量。
Elem为散列表元素，Cur为下标用于判断是否冲突，TabSize为大小。

初始化

void InitHashTable(HashTable& H)
{
    int i=0;
    m=HashSize;
    H.TableSize=HashSize;
    H.Elem=new int[HashSize];
    for(i=0;i<HashSize;i++){
        H.Elem[i]=NULLKEY;
    }
}

定义散列函数

int HashFunc(int Key)
{
    return Key%m;
}

插入操作

void InsertHash(HashTable& H,int Key,int Value)
{
    int Addr=HashFunc(Key);
    while(H.Elem[Addr]!=NULLKEY){
        Addr=(Addr+1)%m;
        //处理冲突
    }
    H.Elem[Addr]=Value;
    H.Cur[Addr]=Key;
}

查找操作

void SearchHash(HashTable& H,int Key)
{
    int Addr=HashFunc(Key);
    while(H.CUr[Addr]!=Key){
        Addr=(Addr+1)%m;
        //处理冲突
        if(H.Cur[Addr]==NULLKEY || Addr==HashFunc(Key)){
            cout<<"Not Find Key"<<endl;
            return;
        }
    }

    cout<<"Find Value:" << H.Elem[Addr] <<endl;

}

本文作者： KongXinQing
本文链接： https://13114987559.github.io/2023/09/11/note/数据结构与算法-散列表/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！