散列查找 | Sillywa's Blog

散列查找解决的一个基本问题是：如何快速搜索到需要的关键词？

我们知道查找的本质是已知一个对象，找到该对象的位置。因此如果我们在安排位置时，通过一个”散列函数“来计算出对象的位置进行存放，当要查找这个对象时，再通过相同的”散列函数“即可直接计算出对象的位置。

因此其时间复杂度几乎是：O(1)，即查找时间与问题规模无关！

那么问题就来了，我们如何构造出一个比较好的散列函数，如果多个关键词通过某个散列函数计算出了相同的位置，我们如何解决这种冲突。

所以散列查找法的两项基本工作就是：

计算位置：构造散列函数确定关键词的存储位置
解决冲突：应用某种策略解决多个关键字位置相同的问题

基本概念

散列表（哈希表）：

类型名称：符号表(SymbolTable)

数据对象集：符号表是“名字(Name)—属性(Attribute)”对的集合

操作集：对于一个具体的符号表Table∈SymbolTable，一个给定的名字Name∈NameType，属性Attr∈AttributeType，以及正整数TableSize，符号表的基本操作有：

SymbolTable CreateTable(int TableSize)：创建空的符号表，其最大长度为TableSize；

bool IsIn(SymbolTable Table,NameType Name)：查找指定 Name 是否在符号表 Table 中；

AttributeType Find(SymbolTable Table,NameType Name)：获取符号表 Table 中指定名字 Name 对应的属性；

bool Modify(SymbolTable Table,NameType Name,AttributeType Attr)：将Table 中指定名字 Name 的属性修改为 Attr；

bool Insert(SymbolTable Table,NameType Name,AttributeType Attr)：向 Table 中插入一个新名字 Name 及其属性 Attr；

bool Delete(SymbolTable Table,NameType Name)：从 Table 中删除一个名字 Name 及其属性。

散列(Hashing)的基本思想是：

1.以关键字key为自变量，通过一个确定的函数h（散列函数），计算出对应的函数值h(key)，作为数据对象的存储地址。

2.可能不同的关键字会映射到同一个散列地址上，即h(key_i )=h(key_j ),key_i≠key_j，称为冲突——因此需要某种冲突解决策略。

例：有 n=11 个对象的集合 {18,23,11,20,2,7,27,30,42,15,34}。符号表的大小 TableSize = 17（通常为素数），选取散列函数如下：

h(key) = key mod TableSize (求余)

用这个散列函数对 11 个对象建立查找表，如下所示：

存放：
如果新插入35，h(35)=1，该位置已有对象，冲突
查找：
key = 22,h(22) = 5，该地址为空，不在表中
key = 30,h(30) = 13，该地址存放的是30，找到

定于装填因子：设散列表空间大小为 m，填入表中的元素个数是 n，则称 a=n/m 为散列表的装填因子。

散列函数的构造方法

一个好的散列函数应该考虑以下两个因素：

1.计算简单，以便提高转换速度；

2.关键词对应的地址空间分布均匀，以尽量减少冲突。

数字关键词的散列函数构造

1.直接定址法

如果我们要统计人口的年龄分布情况（0——120），那么对于年龄这个关键词可以直接作为地址，即 h(key) = key。

如果要统计的是 1990 年以后出任的人口分布情况，那么对于出生年份这个关键词可以减去 1990 作为地址，即 h(key) = key-1990。

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

h(key) = a X key + b (a,b为常数)

2.除留余数法

现实生活中比较常用的方法是除留余数法。假设散列表长为 TableSize，选择一个正整数 p ≤ TableSize，散列函数构造为：

h(key) = key mod p

这里 p 一般取为小于等于散列表长 TableSize 的某个最大的素数比较好。

3.数字分析法

分析数字关键字在各位上的变化情况，取比较随机的位作为散列地址

比如：取手机号 key 的后 4 位作为地址：

散列函数位：h(key) = atoi(key+7)

字符串关键词的散列函数构造

1.一个简单的散列函数——ASCII码加和法

2.简单的改进——前3个字符移位法

3.好的散列函数——移位法

处理冲突的方法

在前面的散列函数构造过程中，我们努力使散列地址均匀分布在整个地址空间，但实际应用中，冲突只能尽量减少，而不能完全避免。接下来我们讨论在冲突发生时，如何有效地解决它。常用的处理冲突的方法有开放地址法（Open Addressing）和链地址法（Linear Probing）。

开放地址法

一旦产生了冲突（该地址已有其它元素），就按照某种规则去寻找另一空地址。

若发生了第 i 次冲突，试探的下一个地址将增加 di，基本公式是：

hi(key) = (h(key) + di) mod TableSize (1 <= i < TableSize)

di决定了不同的解决冲突方案：线性探测、平方探测、双散列。

1.线性探测

以增量序列1,2,3…TableSize-1循环试探下一个存储地址。

设关键词序列为 {47,7,29,11,9,84,54,20,30}

散列表长 TableSize=13（装填因子 9/13=0.69）；

散列函数为：h(key) = key mod 11。

用线性探测法处理冲突，列出一次插入后的散列表，并估算查找性能。

注意”聚集“现象。

散列表查找性能分析

成功平均查找长度(ASLs)
不成功平均查找长度(ASLu)

散列表如下：

分析：

ASLs：查找表中关键词的平均查找比较次数（其冲突次数加 1）

ASLs = (1+7+1+1+2+1+4+2+4)/9 = 2.56

ASLu：不在散列表中的关键词的平均查找次数（不成功）

一般方法：将不在散列表中的关键词分为若干类。如根据 h(key) 分类

ASLu = (3+2+1+2+1+1+1+9+8+7+6)/11 = 3.73

2.平方探测法——二次探测

以增量序列 1，-1，4，-4，9，-9，…，q^2，-q^2，且 q <= [TableSize/2] 循环试探下一个存储地址。

设关键词序列为 {47,7,29,11,9,84,54,20,30}，散列表长度 TableSize = 11，散列函数为：h(key) = key mod 11。用平方探测法处理冲突，列出依次插入后的散列表，并估算ASLs。

ASLs = (1+1+2+1+1+3+1+4+4)/9 = 2

是否有空间，平方探测（二次探测）就能找到？

有证明表明，如果散列表的长度 TableSize 是某个 4k+3（k是正整数）形式的素数时，平方探测法就可以检测到整个散列表空间。这一点很重要，使我们能够放心使用平方探测法的理论保证。

在开放地址的散列表中，不能进行标准的删除操作，因为相应的单元可能引起过冲突，数据对象绕过它存在了别处。为此开放地址散列表需要“惰性删除”，即需要增加一个“删除标记”，而并不是真正的删除它。这样可以不影响查找，但额外的存储负担增加了代码的复杂性。

以下是开放地址法的类型声明：

#define MAXTABLESIZE 100000     /* 允许开辟的最大散列表长度 */
typedef int ElementType;        /* 关键词类型 */
typedef int Index;              /* 散列地址类型 */
typedef Index Position;         /* 数据所在位置与散列地址是同一类型 */

/* 散列单元的状态，分别对应：有合法元素、空单元、有已删除元素 */
typedef enum { Legitimate, Empty, Deleted } EntryType;

typedef struct HashEntry Cell;  /* 散列表单元类型 */
struct HashEntry {
    ElementType Data;   /* 存放的元素 */
    EntryType Info;     /* 单元状态 */
};

typedef struct TblNode* HashTable;  /* 散列表类型 */
struct TblNode {        /* 散列表节点定义 */
    int TableSize;      /* 散列表的最大长度 */
    Cell *Cells;        /* 存放散列单元的数组 */
};

如下代码给出了散列表的初始化函数。首先申请散列表需要的空间，再将每个单元的 info 设置为 Empty，表示为空。注意需要确定一个不下于 TableSize 的素数，用作真正的散列表的地址空间大小，这个功能由 NextPrime 实现。

int NextPrime(int N) {
    /* 返回大于N且不超过MAXTABLESIZE的最小素数 */
    int i;
    int p = (N%2) ? N+2 : N+1;  /* 从大于N的第一个奇数开始 */

    while(p <= MAXTABLESIZE) {
        for(i = (int)sqrt(p); i>2; i--)
            if(!(p%i)) break;   /* p不是素数 */
        if(i==2) break; /* for循环正常结束，说明p是素数 */
        else p+=2;  /* 否则试探下一个奇数 */
    }
    return p;
}
HashTable CreateTable(int TableSize) {

    HashTable H = (HashTable)malloc(sizeof(struct TblNode));
    /* 保证散列表的最大长度是素数 */
    H->TableSize = NextPrime(TableSize);
    /* 声明单元数组 */
    H->Cells = (Cell*)malloc(sizeof(Cell)*H->TableSize);
    /* 初始化单元数组为空单元 */
    for(int i=0; i < H->TableSize;i++) {
        H->Cells[i].Info = Empty;
    }

    return H;
}

以下代码是平方探测法的查找函数。首先调用 Hash 函数计算地址，以确定关键词所在的散列表地址。用 while 循环控制直至明确查找成功或者找到空位置表示查找失败，遇到冲突则继续查找。

注意关键词 key 的类型 ElementType 不一定为整形，也可能被定义为字符串，若是字符串，则 while 的判断条件要用 C 语言的 strcmp 函数来替换。若找到关键词，函数直接返回结点的地址，若找不到则返回一个空的单元。

Position Find(HashTable H, ElementType Key) {
    Position CurrentPos,OldPos;
    int CNum = 0; /* 记录冲突次数 */
    CurrentPos = OldPos = Hash(Key, H->TableSize); /* 计算出其位置 */
    /* 当该单元为非空并且不是要找的元素时，发生冲突 */
    while(H->Cells[CurrentPos].Info != Empty && H->Cells[CurrentPos].Data != Key) {
        /* 字符串类型需调用 strcmp 函数 */
        /* 统计冲突次数 */
        if((++CNum % 2)) {  /* 奇数次冲突 */
            /* 增量为 [(CNum+1)/2]^2 */
            CurrentPos = OldPos + (CNum+1) * (CNum+1) /4;

            if(CurrentPos >= H->TableSize)
                CurrentPos = CurrentPos%H->TableSize;   /* 调整为合法地址 */

        } else {    /* 偶数次冲突 */
            /* 增量为 -(CNum/2)^2 */
            CurrentPos = OldPos - CNum * CNum /4;
            while(CurrentPos < 0)   /* 调整为合法地址 */
                CurrentPos += H->TableSize;
        }
    }
    return CurrentPos;
    /* 此时 CurrentPos 或者是 Key 的位置，或者是一个空单元的地址（表示找不到） */
}

以下是插入函数，先检查 Key 是否已经存在，该单元的状态只要不是合法的，就可以在此插入。

bool Insert(HashTable H, ElementType Key) {
    Position p = Find(H,Key);   /* 首先检查Key值是否存在 */
    if(H->Cells[p].Info != Legitimate) {    /* 如果这个单元没有被占用，说明Key可以插入在此 */
        H->Cells[p].Info = Legitimate;
        H->Cells[p].Data = Key;
        /* 字符串类型需调用strcpy函数 */
        return true;
    } else {
        printf("键值已存在");
        return false;
    }
}

开放地址法的删除操作只需要该改变单元的状态 Info 即可。

3.双散列探测法

4.再散列（Rehashing）

当散列表元素太多时（即装填因子太大时），查找效率就会下降；实用的装填因子一般取0.5——0.85。

当装填因子过大时，解决的方法就是加倍扩大散列表，这个过程叫做**”再散列”**。

分离链接法

分离链接法就是将相应位置上冲突的所有关键词存储在同一个单链表里面。

设关键字序列为{47,7,29,11,16,92,22,8,3,50,37,89,94,21}，散列函数取：h(key) = key mod 11；用分离链接法处理冲突，结果如下：

表中有 9 个结点只需查找 1 次，5 个结点需要查找 2 次，查找成功的平均查找次数：

ASLs = (9+5*2)/14 = 1.36

以下是分离链接法的代码实现：

#define KEYLENGTH 15    /* 关键字符串的最大长度 */
typedef char ElementType[KEYLENGTH+1];  /* 关键词类型用字符串 */
typedef int Index;  /* 散列地址类型 */

typedef struct LNode* PtrToNode;
struct LNode {
    ElementType Data;
    PtrToNode Next;
};
typedef PtrToNode List;
typedef PtrToNode Position;

typedef struct TblNode* HashTable;
struct TblNode {
    int TableSize;
    List Heads; /* 指向链表头结点的数组 */
};

散列表结构包括一个 TableSize 记录表的最大长度以及一个节点数组对应的单链表，它们在初始化时动态分配空间，并设置相应的初值。

以下是散列表的初始化函数 CreateTable。首先申请散列表的头结点空间；然后确定一个不小于 TableSize 的素数，用作真正的散列表的地址空间大小；最后动态分配散列表的地址列表数组并初始化空的头结点。

HashTable CreateTable(int TableSize) {
    HashTable H = (HashTable)malloc(sizeof(struct TblNode));

    /* 保证散列的最大长度是素数 */
    H->TableSize = NextPrime(TableSize);

    /* 分配链表表头节点数组 */
    H->Heads = (List)malloc(sizeof(struct LNode)*H->TableSize);

    /* 初始化表头节点 */
    for(int i=0; i<H->TableSize; i++) {
        H->Heads[0].Data[0] = '\0';
        H->Heads.Next = NULL;
    }
    return H;
}

以下是查找 Find 函数。首先调用 Hash 函数计算地址，得到关键字所在的 Heads 中单元的下标 Pos；P 则指向 Heads[Pos] 链表中真正的第一个元素。因为关键字是字符串，所以 while 循环条件判断要用 strcmp 函数来比较 Data 与 Key 的值。若找到了关键词，函数直接返回结点的地址，若找不到则返回空地址。

Position Find(HashTable H, ElementType Key) {

    Position Pos = Hash(Key,H->TableSize);  /* 找到该Key的位置 */

    Index P = H->Heads[Pos].Next;   /* 从该链表的第一个节点开始 */
    /* 当未到表尾，并且Key未找到时 */
    while(P && strcmp(P->Data,Key))
        P=P->Next;
    /* 此时P指向找到的节点或者NULL */
    return P;

}

以下是插入函数 Insert。该函数首先调用 Find 函数，如果找到了关键词则不需要插入，返回插入不成功的信息；如果找不到关键词才需要插入。插入时，先申请一个新结点 NewCell，然后计算 Key 的地址 Pos，插入成为单链表 Heads[Pos] 的第一个结点。

bool Insert(HashTable H, ElementType Key) {
    Position P = Find(H, Key);
    if(!P) {

        Position NewCell = (Position)malloc(sizeof(struct LNode));
        strcpy(NewCell->Data, Key);
        Index Pos=Hash(Key,H->TableSize);
        /* 将NewCell插入为H->Heads[Pos]链表的第一个节点 */
        NewCell->Next = H->Heads[Pos].Next;
        H->Heads[Pos].Next =NewCell;
        return true;

    } else {
        printf("关键词已存在");
        return false;
    }
}

释放 CreateTable 所占用的内存空间可以调用如下 DestroyTable 函数：

void DestoryTable(HashTable H) {
    int i;
    Position P, temp;
    /* 释放链表的每个节点 */
    for(i=0; i<H->TableSize; i++) {
        P = H->Heads[i].Next;
        while(P) {
            temp = P->Next;
            free(P);
            P = temp;
        }
    }
    free(H->Heads); /* 释放头结点数组 */
    free(H);    /* 释放散列表节点 */
}

分离链接法的删除操作与链表的删除操作相似。不过需要先通过 Hash 函数得到链表的头结点，再在该链表中进行删除即可。

散列表的性能分析

在上面的介绍中，我们已经用 ASL 来度量散列表的查找效率。查找过程中，关键词比较的次数，取决于产生冲突的多少。产生的冲突多，查找效率就高；产生的冲突多，查找效率就低.因此，影响产生冲突多少的因素，也就是影响查找效率的因素。主要有以下三个因素：

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

线性探测法的查找性能

可以证明，线性探测法的期望探测次数满足下列公式：

平方探测法和双散列探测法的查找性能

可以证明，平方探测法和双散列探测法的期望探测次数满足下列公式：

下图表示了上面几种探测法的期望探测次数与装填因子之间的关系：

由图可知，当装填因子 < 0.5 的时候，各种探测法的期望探测次数都不大，也比较接近。随着装填因子的增大，线性探测法的期望探测次数增加较快，不成功查找和插入操作的期望探测次数明显比成功查找的期望探测次数要大。合理的装填因子应该不超过0.85。

分离链接法的查找性能

我们把分离链接法中的每个链表的平均长度定义成装填因子，因此装填因子有可能超过 1。

不难证明，其期望探测次数为：

散列的特点

1.选择合适的 h(key)，散列法的查找效率期望是常数 O(1)，它几乎与关键字的空间的大小 N 无关，也适合于关键字直接比较计算量大的问题；

2.它是以较小的装填因子为前提，因此，散列方法是一个以空间换时间；

3.散列方法的存储对关键字是随机的，不便于顺序查找关键字，也不适合于范围查找，或最大值最小值查找。

开放地址法的特点

1.散列表是一个数组，存储效率高，随即查找；

2.散列表有聚集现象

分离链接法的特点

1.散列表是顺序存储和链式存储的结合，链表部分的存储效率和查找效率都比较低；

2.关键字删除不需要懒惰删除法，因此没有存储垃圾；

3.太小的装填因子可能导致空间浪费，大的装填因子又会付出更多的时间代价。不均匀的链表长度导致时间效率严重下降。