散列表

  • 实例：编译器处理源代码中的变量，涉及变量及属性(如：变量类型)的管理
    • 插入：新变量定义
    • 查找：变量的引用
    • 变量处理的本质：动态查找问题
    • 已知的几种查找方法：
      • 顺序查找 O(N)O(N)
      • 二分查找 O(logN)O(logN)
      • 二叉搜索树 O(h)O(h)，h为二叉查找树的高度
        • 平衡二叉树 O(logN)O(logN)
    • 使用查找树、AVL进行变量管理
      • 两个变量名(字符串)比较效率不高(要一个个字符进行比较)
        • 考虑将字符串转化为整数的比较
  • 实例：登陆qq时，qq服务器如何核对身份，面对庞大用户群如何快速找到用户信息？
    • 如果使用二分法查找：
      • 假设十亿(109≈23010^9\approx2^{30})有效用户，用二分查找30次
      • 假设用户信息大小为1KB，则需要1TB(1×1091\times10^9KB)连续空间
      • 需要按有效qq号大小有序存储：在连续存储空间中，插入和删除一个新qq号码需要移动大量数据
        • 二分查找不适合动态查找
    • 问题：如何快速搜索到需要的关键词，如果关键词不方便比较怎么办
      • 查找的本质：已知对象找位置
        • 有序安排对象：全序、半序
        • 典型：二分查找(全序)、查找树(半序)
        • 直接算出对象位置：散列

散列

散列(Hashing)的基本思想：

  • 以关键字key为自变量，通过一个确定的函数h(散列函数)，计算出对应的函数值h(key)，作为数据对象的存储地址
  • 不同的关键字坑会映射到同一个散列地址上，即h(key(i))=h(key(j))，当key(i)!=key(j)，称为“冲突(Collision)”
  • 散列查找法的两项基本工作：
    • 计算位置：构造散列函数确定关键词存储位置
      • 将对象映射成一个整型
    • 解决冲突：应用某种策略解决多个关键词位置相同的问题
  • 时间复杂度：几乎为常量复杂度O(1)O(1)，即查找时间与问题规模无关
    • 如果没有溢出，则T(T(查询)=T()=T(插入)=T()=T(删除)=O(1))=O(1)
  • 装填因子(Loading Factor)：设散列空间大小为m，填入表中元素的个数是n，则称α=nmα=\frac{n}{m}为散列表的装填因子
  • 散列表查找性能评价
    • 成功平均查找长度(ASLs) ——> 查找成功的情况
      • 查找表中包含的关键词的平均查找比较次数(查找过程中的冲突次数+1)
    • 不成功平均查找长度(ASLu) ——> 插入或查找失败的情况
      • 不在散列表中的关键词的平均查找次数(假设查找不到情况下的比较次数：h(key)与最近一个空闲位置的距离)
      • 一般方法：将不在散列表中的关键词分若干类
      • 如：根据h(key)值分类

实例1：有n=11个数据对象的集合{18,23,11,20,2,7,27,30,42,15,34}，符号表的大小用TableSize=17，选取散列函数h如下：

  • h(key)=keyh(key)=key modmod TableSizeTableSize
  • 数据存放：
    • h(18)=1,h(23)=6,h(11)=11,h(20)=3,h(2)=2,……h(18)=1,h(23)=6,h(11)=11,h(20)=3,h(2)=2,……
地址h(key) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
关键词key 34 18 2 20 23 7 42 27 11 30 15
  • 此时如果插入新整型数据35，h(35)=1，由于该位置已有对象——“冲突”
    • 此时如果进行查找，如：
      • key=22，h(22)=5，地址(5)为空，22不在表中
      • key=30，h(30)=13，地址(13)存放是30，查找成功
  • 装填因子α=11/17≈0.65α=11/17≈0.65
  • 成功平均查找长度ASLs=1+1+1+1+1+1+1+1+1+1+111=1ASLs=\frac{1+1+1+1+1+1+1+1+1+1+1}{11}=1
  • 不成功平均查找长度ASLu=5+4+3+2+1+1+6+5+4+3+2+1+2+1+2+117=2.53ASLu=\frac{5+4+3+2+1+1+6+5+4+3+2+1+2+1+2+1}{17}=2.53 (假设冲突处理为线性探测)

实例2：将acos、define、float、exp、char、atan、ceil、floor、clock、ctime顺次放入一张散列表中

  • 散列表设计为一个二维数组Table[26][2]，2列分别代表两个槽
  • 散列函数h(key)=key[0]−h(key)=key[0]-’aa’

散列表的抽象数据类型描述

类型名称：符号表(SymbolTable)
数据对象集：符号表是“名字(Name)-属性(Attribute)”对的集合
操作集：Table ∈ SymbolTable，Name ∈ NameType，Attr ∈ AttributeType
SymbolTable initializeTable(int TableSize):创建一个长度为TableSize的符号表;
Boolean IsIn(SymbolTable Table,NameType Name):查找特定的名字Name是否在符号表Table中;
AttributeType Find(SymbolTable Table,NameType Name):获取Table中指定名字Name对应的属性;
SymbolTable Modefy(SymbolTable Table,NameType Name,AttributeType Attr):将Table中指定名字Name的属性改为Attr;
SymbolTable Insert(SymbolTable Table,NameType Name,AttributeType Attr):向Table中插入一个新名字Name及其属性Attr;
SymbolTable Delete(SymbolTable Table,NameType Name):从Table中闪出一个名字Name及其属性.

散列函数

  • 一个“好”的散列函数一般应考虑下列两个因素：
    • 计算简单，一边提高转换速度
    • 关键词对应的地址空间分布均匀，以尽量减少冲突

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

直接定址法

  • 取关键词的某个线性函数值为散列地址，即h(key)=a×key+bh(key)=a\times key+b (a、b为常数)
  • 数据格式如：(h(key)=key−1990h(key)=key-1990)
地址h(key) 出生年份(key) 人数(attribute)
0 1990 1285万
1 1991 1281万
2 1992 1280万
…… …… ……
10 2000 1250万
…… …… ……
21 2011 1180万
  • 散列地址转换例：h(1990)=0，h(2000)=10

数字分析法

  • 分析数字关键字在各位上的变化情况，取比较随机的位作为散列地址
    • 比如取11位手机号码key的后4位作为地址进行手机号存储：h(key)=atoi(key+7)h(key)=atoi(key+7)
      • atoi(char* key)将字符串转换为整型
      • 散列地址转换如：h(15079054887)=4887
    • 再如关键字key是18位的身份证号码的存储：
      • h(key)=(key[6]−h(key)=(key[6]-‘00’)×104+(key[10]−)\times10^4+(key[10]-’00’)×103+(key[14]−)\times10^3+(key[14]-’00’)×102+(key[16]−)\times10^2+(key[16]-’00’)×10+(key[17]−)\times10+(key[17]-’00’))))
      • 散列地址转换例：h(330106199010080419)=1109

除留余数法

  • 散列函数为：h(key)=keyh(key)=key modmod PP
  • 散列表例：(h(key)=key%17)(h(key)=key\%17)
地址h(key) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
关键词key 34 18 2 20 23 7 42 27 11 30 15
  • 此例中P=Tablesize=17
    • 一般情况下P取素数
      • 设key=N=kn，P=kp，h(key)=rkey=N=kn，P=kp，h(key)=r，其中n，p，r，kn，p，r，k均为整数
      • 由NN%p=r得，N=Pq+r，kn=kpq+r，n=pq+rkN=Pq+r，kn=kpq+r，n=pq+\frac{r}{k}
      • 由于n,pn,p均为整数，因此rk\frac{r}{k}也是整数，因此r的取值为[0,k,2k,…,(p−1)k][0,k,2k,…,(p-1)k]
      • 另一方面，由于rr代表h(key)h(key)，其取值需要覆盖地址空间范围内所有连续的整数[0,1,2,…,P−1][0,1,2,…,P-1]
      • 此时只有一种情况即k=1k=1，说明NN和PP互质，由于keykey的取值是任意的，因此令PP为素数

折叠法、平方取中法

  • 折叠法
    • 将关键字分割成位数相同的几个部分，然后叠加
  • 平方取中法
    • 将关键字平方后取其中间几位的码值
  • 如：56793542

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

基本构造方法————ASCII码加和法

  • 对字符型关键词key定义散列函数如：

    • h(key)=(Σkey[i])h(key)=(Σkey[i]) modmod TableSizeTableSize
    • 这种构造方法过于简单，冲突可能性较大，如：
      • a3、b2、c1，eat、tea(关键字和相等的情况)
      • 实际上ASCII码取值为0～1270～127，长度为n的字符串的字符ASCII值和仅有127n127n中取值，而实际上字符串有127n127^n种组合

  • 对基本方法的改进————前三个字符移位法

    • 把字符串的前三个字符取出来，看成27进制种的个位数，十位数，百位数，
      • 使用27的原因：26个字母加空格，即27
    • 如：h(key)=(key[0]×272+key[1]×27+key[2])h(key)=(key[0]\times27^2+key[1]\times27+key[2]) modmod TableSizeTableSize
      • 这种构造方法较较基本方法冲突相对少，但仍然存在一定的冲突问题，如：
        • string、street、strong、structure等(前三个关键字相同)
        • 存在空间浪费的问题
        • 在本例的散列函数，以前三位作为关键码则所有可能的取值为26326^3(26个字母)
          • 而前三个字符的不同组合在实际使用中大概有3000种可能
          • 空间浪费≈3000263≈30≈\frac{3000}{26^3}≈30%

位移法

  • 涉及关键词的所有n个字符，并且合理分布
  • 考虑字符串的所有位，将其看作32进制数的每一位
    • h(key)=(Σkey[n−i−1]×32i)h(key)=(Σkey[n-i-1]\times32^i) modmod TableSizeTableSize
    • 散列地址转换例：h(h("abcdeabcde")=)=’aa’×324+\times32^4+’bb’×323+\times32^3+’cc’×322+\times32^2+’dd’×32+\times32+’ee’$

位移散列函数伪代码

Index Hash(const char*Key,int TableSize){
    unsigned int h=0;                   //散列函数值，初始化为0
    while(*Key)h=(h<<5)+*Key++;         //位移映射，h<<5相当于h*32，*Key++是先取*Key再Key++
    return h%TableSize;
}

冲突处理方法

  • 常用处理冲突的思路：
    • 换个位置：开放地址法
    • 同一位置的冲突对象组织在一起：链地址法

开放定址法(Open Addressing)

  • 一旦产生了冲突(该地址已有其他元素)，就按某种规则去寻找另一空地址
    • 若发生了第i次冲突，试探的下一个地址将增加d(i)，基本公式为：
      • hi(key)=(h(key)+d(i))h_i(key)=(h(key)+d(i)) modmod TableSize(1<=i<TableSize)TableSize (1<=i<TableSize)
      • 不同的解决冲突方案决定了不同的d(i)，不同方案如：
        • 线性探测：d(i)=id(i)=i
        • 平方探测：d(i)=i2d(i)=i^2
        • 双散列：d(i)=i×h(key)d(i)=i\times h(key)
        • 其他如伪随机方法等
  • 在开放地址散列表中，删除操作通常只能“懒惰删除”
    • 由于开放定址的每次冲突解决操作互相是相关的，因此如果删除一个会导致“断链”
    • 因此，需要增加一个“删除标记(Deleted)”，表示所在位置元素已删除，其空间可以在下次插入时重用

线性探测法(Linear Probing)

  • 以增量序列1，2，……，(TableSize-1)循环试探下一个存储地址
  • 例1：设关键词序列为{47,7,29,11,9,84,54,20,30}
    • 设散列表表长TableSize=13(装填因子α=9/13≈0.69α=9/13≈0.69)
    • 散列函数：h(key)=keyh(key)=key modmod 1111
    • 采用线性探测法处理冲突并计算散列表和查找性能
关键词key 47 7 29 11 9 84 54 20 30
散列值h(key) 3 7 7 0 9 7 10 9 8
冲突次数 0 0 1 0 0 3 1 3 6
  • “聚集”现象：由于冲突的元素会依次向下试探并存储，导致冲突元素将本不属于自身的地址占据，进而在冲突发生的相邻区域产生更多冲突从而形成“聚集”现象
  • 将序列插入散列表的操作过程：
操作\地址 0 1 2 3 4 5 6 7 8 9 10 11 12 说明
插入47 47 无冲突
插入7 47 7 无冲突
插入29 47 7 29 d(1)=1
插入11 11 47 7 29 无冲突
插入9 11 47 7 29 9 无冲突
插入84 11 47 7 29 9 84 d(3)=3
插入54 11 47 7 29 9 84 54 d(1)=1
插入20 11 47 7 29 9 84 54 20 d(3)=3
插入30 11 30 47 7 29 9 84 54 20 d(6)=6
  • ASLs=1+7+1+1+2+1+4+2+49=239≈2.56\frac{1+7+1+1+2+1+4+2+4}{9}=\frac{23}{9}≈2.56
  • ASLu=3+2+1+2+1+1+1+9+8+7+6+5+413=5013≈3.85\frac{3+2+1+2+1+1+1+9+8+7+6+5+4}{13}=\frac{50}{13}≈3.85
  • 例2：将acos、define、float、exp、char、atan、ceil、floor顺序存入一张大小为26的散列表中
    • 散列函数：h(key)=key[0]-‘a’，采用线性探测d(i)=i
acos atan char define exp float ceil floor ……
0 1 2 3 4 5 6 7 8
  • ASLs=1+2+1+1+1+1+5+38=158≈1.87\frac{1+2+1+1+1+1+5+3}{8}=\frac{15}{8}≈1.87
  • ASLu=9+8+7+6+5+4+3+2+1∗1826=6226≈2.38\frac{9+8+7+6+5+4+3+2+1*18}{26}=\frac{62}{26}≈2.38

平方探测法(Quadratic Probing)，又称二次探测

  • 以增量序列12,−12,22,−22,……,q2,−q21^2,-1^2,2^2,-2^2,……,q^2,-q^2且q≤⌊TableSize2⌋q\leq⌊\frac{TableSize}{2}⌋循环试探下一个存储地址
  • 例：以线性探测法例1为例
    • 散列表表长TableSize=11
    • 散列函数为：h(key)=keyh(key)=key modmod 1111
    • 采用平方探测法处理冲突并计算散列表和查找性能
关键词key 47 7 29 11 9 84 54 20 30
散列值h(key) 3 7 7 0 9 7 10 9 8
冲突次数 0 0 1 0 0 2 0 3 3
  • 将序列插入散列表的操作过程
操作\地址 0 1 2 3 4 5 6 7 8 9 10 说明
插入47 47 无冲突
插入7 47 7 无冲突
插入29 47 7 29 d(1)=1
插入11 11 47 7 29 无冲突
插入9 11 47 7 29 9 无冲突
插入84 11 47 84 7 29 9 d(2)=-1
插入54 11 47 84 7 29 9 54 无冲突
插入20 11 20 47 84 7 29 9 54 d(3)=4
插入30 11 30 20 47 84 7 29 9 54 d(3)=4
  • ASLs=(1+1+2+1+1+3+1+4+4)/9=18/9=2ASLs=(1+1+2+1+1+3+1+4+4)/9=18/9=2
  • ASLu=(5+4+3+2+1+1+10+9+8+7+6)/11=56/11≈5.09ASLu=(5+4+3+2+1+1+10+9+8+7+6)/11=56/11≈5.09
  • 某些情况下平方探测法可能无法探查到所有空间
    • 例：向下方列表中中插入11(TableSize=5)
操作\地址 0 1 2 3 4
插入11 5 6 7
  • h(11)=1,1+1=2,1−1=0,(1+22)%5=0,(1−22)%5=2,(1+32)%5=0,(1−32)%5=2……h(11)=1,1+1=2,1-1=0,(1+2^2)\%5=0,(1-2^2)\%5=2,(1+3^2)\%5=0,(1-3^2)\%5=2……
  • 不过有定理显示：如果散列表长度TableSize是某个4k+3(k是正整数)形式的素数时，平方探测可以探查到整个散列表空间
    • 设TableSize=S(S为大于5的素数)
    • 向表中插入一个冲突元素x，并从剩余位置中任选两个，设探测次数分别为i,j，0<i,j≤⌊S/2⌋i,j，0<i,j\leq⌊S/2⌋
    • 设(h(x)+d(i))%S=(h(x)+d(j))%S(h(x)+d(i))\%S=(h(x)+d(j))\%S
    • 由d(i)=i2=d(j)=j2，0<i,j≤⌊S/2⌋d(i)=i^2=d(j)=j^2，0<i,j\leq⌊S/2⌋知，当且仅当i=j时两次不同的探测之间才会发生冲突，即剩余位置是互异的
    • 由于剩余位置互异，每次探测都找到一个新位置，因此总存在一个i使得(h(x)+d(i))%S(h(x)+d(i))\%S能探测到空闲单元
  • 探测次数q≤⌊TableSize/2⌋q\leq⌊TableSize/2⌋
    • 由于每次探测的位置是互异的，因而对每个探测q而言都会减少2个未探测过的单元(q2，−q2)(q^2，-q^2)
    • q最多只需要⌊TableSize/2⌋⌊TableSize/2⌋次就可以探测整个空间

双散列探测法(Double Hashing)

  • d(i)d(i)为i×h2(key)i\times h_2(key)，其中h2(key)h_2(key)是另一个散列函数
  • 探测序列为h2(key),2h2(key),3h2(key),……h_2(key),2h_2(key),3h_2(key),……
    • 对任意的ke,h2(key)≠0ke,h_2(key)\neq 0
    • 探测序列还应该保证所有的散列存储单元都应该能够被探测到，选择一下形式效果较好：
      • h2(key)=p−(keyh_2(key)=p-(key modmod p)p)
      • 其中：p<TableSize，p、TableSizep<TableSize，p、TableSize都是素数

再散列(Rehashing)

  • 当散列表元素太多(即装填因子α太大)时，查找效率会下降
    • 实用最大装填因子一般取0.5≤α≤0.850.5\leq α\leq 0.85
      • 当装填因子过大时，解决的方案时加倍扩大散列表，这个过程叫做“再散裂(Rehashing)”
      • 注意：当散列表规模扩大以后，必须把所有元素重新计算后放入到散列表相应位置

分离链接法(Separate chaining)

  • 将相应位置上冲突的所有关键词存储在同一个单链表中
  • 例：设关键字序列为47,7,29,11,16,92,22,8,3,50,37,89,94,21；
    • 散列函数为：h(key)=keyh(key)=key modmod 1111
    • 用分离链接法处理冲突
      • 表中有9个结点只需一次查找，5个结点需要2次查找
      • 查找成功的平均查找次数：ASLs=9+5∗214≈1.36ASLs=\frac{9+5*2}{14}≈1.36

冲突处理方法的伪代码描述

开放定址法散列表结构、查找操作、插入操作的伪代码描述：

typedef struct HashTbl*HashTable;
struct HashTbl{
    int TableSize;Cell*TheCells;
}H;
HashTable InitializeTable(int TableSize){
    HashTable H;
    int i;
    if(TableSize<MinTableSize){
        Error("散列表太小");
        return NULL;
    }
    //分配散列表
    H=(HashTable)malloc(sizeof(struct HashTbl));
    if(H==NULL)
        FatalError("空间溢出！！！");
    H->TableSize=NextPrime(TableSize);
    //分配散列表Cells
    H->TheCells=(Cells*)malloc(sizeof(Cell)*H->TableSize);
    if(H->TheCells==NULL)
        FatalError("空间溢出！！！");
    for(i=0;i<H->TblaeSize;i++)
        H->TheCells[i].Info=Empty;
    return H;
}
Position Find(ElementType Key,HashTable H){                     //平方探测
    Position CurrentPos,NewPos;
    int CNum=0;                                                 //记录冲突次数
    NewPos=CurrentPos=Hash(Key,H->TableSize);
    while(H->TheCells[NewPos].Info!=Empty&&
        H->TheCells[NewPos].Element!=Key){                      //字符串类型的关键词需要strcmp函数！！
        if(++CNum%2){                                           //判断冲突的奇偶次
            NewPos=CurrentPos+(CNum+1)/2*(CNum+1)/2  
            //如：
            //d(i)    +1^2  -1^2  +2^2  -2^2  +3^2  -3^2  ……
            //Cnum      1     2     3     4     5     6   ……
            while(NewPos>=H->TableSize)
                NewPos-=H->TableSize;
        }else{
            NewPos=CurrentPos-(CNum+1)/2*(CNum+1)/2  
            while(NewPos<0)
                NewPos+=H->TableSize;
        }
    }
    return NewPos;
}
void Insert(ElementType Key,HashTable H){
    //插入操作
    Position Pos;
    Pos=Find(Key,H);
    if(H->TheCells[Pos].Info!=Legitimate){
        //确认在此插入
        H->TheCells[Pos].Info=Legitimate;
        H->TheCells[Pos].Info=Key;
            //字符串类型的关键词需要strcpy函数
    }
}

分离链接法散列表结构，查找操作的伪代码描述：

typedef struct ListNode*Position,*List;
struct ListNode{
    ElementType Element;
    Position Next;
};
typedef struct HashTbl*HashTable;
struct HashTbl{
    int TableSize;
    List TheList;
};
Position Find(ElementType Key,HashTable H){
    Position P;
    int Pos=Hash(Key,H->TableSize);             //初始散列位置
    P=H->TheLists[Pos].Next;                    //获得链表头
    while(P!=NULL&&strcmp(P->Element,Key))
        P=P->Next;
    return P;
}

散列表实现演示

使用开放定制法解决冲突

#include<cstdio>
#include<cmath>
#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;   /* 存放散列单元数据的数组 */
};

int Hash( int , int );
int NextPrime( int N )
{ /* 返回大于N且不超过MAXTABLESIZE的最小素数 */
    int i, 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;
    int i;

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

    return H;
}
Position Find( HashTable H, ElementType Key )
{
    Position CurrentPos, NewPos;
    int CNum = 0; /* 记录冲突次数 */

    NewPos = CurrentPos = Hash( Key, H->TableSize ); /* 初始散列位置 */
    /* 当该位置的单元非空，并且不是要找的元素时，发生冲突 */
    while( H->Cells[NewPos].Info!=Empty && H->Cells[NewPos].Data!=Key ) {
                                           /* 字符串类型的关键词需要 strcmp 函数!! */
        /* 统计1次冲突，并判断奇偶次 */
        if( ++CNum%2 ){ /* 奇数次冲突 */
            NewPos = CurrentPos + (CNum+1)*(CNum+1)/4; /* 增量为+[(CNum+1)/2]^2 */
            if ( NewPos >= H->TableSize )
                NewPos = NewPos % H->TableSize; /* 调整为合法地址 */
        }
        else { /* 偶数次冲突 */
            NewPos = CurrentPos - CNum*CNum/4; /* 增量为-(CNum/2)^2 */
            while( NewPos < 0 )
                NewPos += H->TableSize; /* 调整为合法地址 */
        }
    }
    return NewPos; /* 此时NewPos或者是Key的位置，或者是一个空单元的位置（表示找不到）*/
}

bool Insert( HashTable H, ElementType Key )
{
    Position Pos = Find( H, Key ); /* 先检查Key是否已经存在 */

    if( H->Cells[Pos].Info != Legitimate ) { /* 如果这个单元没有被占，说明Key可以插入在此 */
        H->Cells[Pos].Info = Legitimate;
        H->Cells[Pos].Data = Key;
        /*字符串类型的关键词需要 strcpy 函数!! */
        return true;
    }
    else {
        printf("键值已存在");
        return false;
    }
}

使用分离链接法解决冲突

#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#define KEYLENGTH 15                   /* 关键词字符串的最大长度 */
#define MAXTABLESIZE 100000            /* 允许开辟的最大散列表长度 */
typedef char ElementType[KEYLENGTH+1]; /* 关键词类型用字符串 */
typedef int Index;                     /* 散列地址类型 */
/******** 以下是单链表的定义 ********/
typedef struct LNode *PtrToLNode;
struct LNode {
    ElementType Data;
    PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;
/******** 以上是单链表的定义 ********/

typedef struct TblNode *HashTable; /* 散列表类型 */
struct TblNode {   /* 散列表结点定义 */
    int TableSize; /* 表的最大长度 */
    List Heads;    /* 指向链表头结点的数组 */
};

int Hash( ElementType , int );
int NextPrime( int N )
{ /* 返回大于N且不超过MAXTABLESIZE的最小素数 */
    int i, 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;
    int i;

    H = (HashTable)malloc(sizeof(struct TblNode));
    /* 保证散列表最大长度是素数，具体见代码6.3.1 */
    H->TableSize = NextPrime(TableSize);

    /* 以下分配链表头结点数组 */
    H->Heads = (List)malloc(H->TableSize*sizeof(struct LNode));
    /* 初始化表头结点 */
    for( i=0; i<H->TableSize; i++ ) {
         H->Heads[i].Data[0] = '\0';
         H->Heads[i].Next = NULL;
    }

    return H;
}

Position Find( HashTable H, ElementType Key )
{
    Position P;
    Index Pos;
  
    Pos = Hash( Key, H->TableSize ); /* 初始散列位置 */
    P = H->Heads[Pos].Next; /* 从该链表的第1个结点开始 */
    /* 当未到表尾，并且Key未找到时 */ 
    while( P && strcmp(P->Data, Key) )
        P = P->Next;

    return P; /* 此时P或者指向找到的结点，或者为NULL */
}

bool Insert( HashTable H, ElementType Key )
{
    Position P, NewCell;
    Index Pos;
  
    P = Find( H, Key );
    if ( !P ) { /* 关键词未找到，可以插入 */
        NewCell = (Position)malloc(sizeof(struct LNode));
        strcpy(NewCell->Data, Key);
        Pos = Hash( Key, H->TableSize ); /* 初始散列位置 */
        /* 将NewCell插入为H->Heads[Pos]链表的第1个结点 */
        NewCell->Next = H->Heads[Pos].Next;
        H->Heads[Pos].Next = NewCell; 
        return true;
    }
    else { /* 关键词已存在 */
        printf("键值已存在");
        return false;
    }
}

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

散列表性能分析

  • 平均查找长度(ASL)用来度量散列表查找效率：成功或不成功
  • 关键词的比较次数，取决于产生冲突的多少
    • 影响产生冲突多少有以下三个因素：
    • 散列函数是否均匀
    • 处理冲突的办法
    • 散列表的装填因子α

开放定址法的查找性能

线性探测法

  • 可以证明，线性探测法的期望查找次数，满足以下公式：
    • 对插入成功和不成功查找而言：p=12[1+11−α2]p=\frac{1}{2}[1+\frac{1}{1-α^2}]
    • 对成功查找而言：p=12[1+11−α]p=\frac{1}{2}[1+\frac{1}{1-α}]
    • 比如，当α=0.5，此时有一半的位置被填满(假设每个散列值发生的可能性相同，则插入或查询有一半的可能会发生冲突)
      • 插入操作和不成功查找的期望ASLu=0.5×(1+1(1−0.5)2)=2.5ASLu=0.5\times(1+\frac{1}{(1-0.5)^2})=2.5次
      • 成功查找的期望ASLs=0.5×(1+11−0.5)=1.5ASLs=0.5\times(1+\frac{1}{1-0.5})=1.5次
  • 例：插入序列{11,47,7,29,9,84,54,20,30}
H(key) 0 1 2 3 4 5 6 7 8 9 10 11 12
key 11 30 47 7 29 9 84 54 20
冲突次数 0 6 0 0 1 0 3 1 3
  • α=913≈0.69α=\frac{9}{13}≈0.69，于是
    • 期望ASLu=0.5×(1+1(1−0.69)2≈5.70ASLu=0.5\times(1+\frac{1}{(1-0.69)^2}≈5.70次
    • 期望ASLs=0.5×(1+11−0.69≈2.11ASLs=0.5\times(1+\frac{1}{1-0.69}≈2.11次

平方探测法和双散列探测法

  • 可以证明，平方探测法和双散列探测法探测次数满足以下公式：
    • 对插入和查找不成功而言：p=11−αp=\frac{1}{1-α}
    • 对成功查找而言：p=−ln(1−α)αp=-\frac{ln(1-α)}{α}
    • 比如，当α=0.5时
      • 插入操作和不成功查找的期望ASLu=10.5=2ASLu=\frac{1}{0.5}=2
      • 成功查找的期望ASLs=−1×ln(0.5)0.5≈1.39ASLs=-1\times \frac{ln(0.5)}{0.5}≈1.39次
    • 例：插入序列{11,47,7,29,9,84,54,20,30}
H(key) 0 1 2 3 4 5 6 7 8 9 10
key 11 30 20 47 84 7 29 9 54
冲突次数 0 3 3 0 2 0 1 0 0
  • α=911≈0.82α=\frac{9}{11}≈0.82，于是
    • 期望ASLu=11−0.82≈5.56ASLu=\frac{1}{1-0.82}≈5.56次
    • 期望ASLs=−1×ln(1−0.82)0.82≈2.09ASLs=-1\times \frac{ln(1-0.82)}{0.82}≈2.09次

期望探测次数与装填因子α的关系

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

分离链接法性能分析

所有地址链表长度的和(装入的元素个数)相对于表长的比例定义为装填因子α，因此α有可能超过1

  • 不难证明：其期望探测次数p为
    • 对插入和不成功查找而言：α+e−αα+e^{-α}
    • 对成功查找而言：$1+\frac{α}{2}$
    • 比如，当α=1时
      • 插入操作和不成功查找的期望ASLu=1+e−1≈1.37ASLu=1+e^{-1}≈1.37次
        • 成功查找的期望ASLs=1+12=1.5ASLs=1+\frac{1}{2}=1.5次
    • 例：插入序列{11,47,7,29,9,84,54,20,30}
      • 14个元素分配在11个单链表中，α=1411≈1.27α=\frac{14}{11}≈1.27
      • 期望ASLs=1.27+e−1.27≈1.55ASLs=1.27+e^{-1.27}≈1.55次
      • 期望ASLu=1+1.272=1.635ASLu=1+\frac{1.27}{2}=1.635次

散列表性能总结

  • 选择合适的h(key)，散列表的查找效率期望是常数O(1)O(1)，几乎与关键字的空间大小n无关，也适合于关键字直接比较计算量大的问题
  • 散列表是以较小的α为前提，因此散列方法是一个以空间换时间的策略
  • 散列方法的存储对关键字是随机的，不便于顺序查找关键字，也不适合于范围查找，或最大值最小值查找

开放定址法

  • 散列表是一个数组，存储效率高，随机查找
  • 散列表有“聚集”现象

分离链接法

  • 散列表是顺序存储和链式存储的结合，链表部分的存储效率和查找效率都比较低
  • 关键字删除不需要“懒惰删除”法，从而没有存储“垃圾”
  • 太小的α可能导致空间浪费，大的α又将付出更多的时间代价，不均匀的链表长度导致时间效率的严重下降

应用实例

散列表应用：文件中单词词频统计
例：给定一个英文文本文件，统计文件中所有单词出现的频率，并输出词频最大的前10%的单词及其词频，假设单词字符定义为大小写字母、数字和下划线，其他字符均认为是单词分隔符，不予考虑

分析：

  • 关键：对新读入的单词在已有的单词表中查找
    • 如果已经存在，则将该单词的词频加1
    • 如果不存在，则插入该单词并记词频为1
  • 如何设计该单词表的数据结构才可以进行快速的查找和插入：应用散列表
int main(){
    int TableSize=10000;                    //散列表估计大小
    int wordcount=0,length;
    HashTable H;
    ElementType word;
    FILE*fp;
    char document[30]="HarryPotter.txt";    //要被统计词频的文件名
    H=InitializeTable(TableSize);           //建立散列表
    if((fp=fopen(document,'r'))==NULL)FatalError("无法打开文件！\n");
    while(!feof(fp)){
        length=GetAWord(fp,word);           //从文件中读取一个单词
        if(length>3){                       //只考虑适当长度的单词
            wordcount++;                    //统计文件中单词总数
            InsertAndCount(word,H);              
        }
    }
    fclose(fp);
    printf("该文档总共出现%d个有效单词，",wordcount);
    Show(H,10.0/100);                       //显示词频前10%的所有单词
    //统计最大词频：
    //用一组数统计从1到最大词频的单词数
    //计算前10%的词频应该是多少
    //输出前10%的单词
    DestroyTable(H);                        //销毁散列表
    return 0;
}