乐趣区

关于hash:教你几招HASH表查找的方法

jiezi

摘要：依据设定的哈希函数 H(key) 和所选中的解决抵触的办法，将一组关键字映象到一个无限的、地址间断的地址集 (区间) 上，并以关键字在地址集中的“象”作为相应记录在表中的存储地位，如此结构所得的查找表称之为“哈希表”。

本文分享自华为云社区《查找——HASH》，原文作者：ruochen。

对于频繁应用的查找表，心愿 ASL = 0
记录在表中地位和其关键字之间存在一种确定的关系

HASH

定义

依据设定的 哈希函数 H(key) 和所选中的 解决抵触 的办法，将一组关键字 映象 到一个无限的、地址间断的地址集 (区间) 上，并以关键字在地址集中的“象”作为相应记录在表中的存储地位，如此结构所得的查找表称之为“哈希表”

HASH 函数的结构

  • 结构准则

    • 函数自身便于计算
    • 计算出来的地址散布平均，即对任一关键字 k，f(k) 对应不同地址的概率相等，目标是尽可能减少抵触

间接定址法

  • 哈希函数为关键字的线性函数

    • H(key) = key
    • H(key) = a * key + b
  • 此法仅适宜于：
    地址汇合的大小 = = 关键字汇合的大小
  • 长处：以关键码 key 的某个线性函数值为哈希地址，不会产生抵触
  • 毛病：要占用间断地址空间，空间效率低

数字分析法

  • 假如关键字汇合中的每个关键字都是由 s 位数字组成 (u1, u2, …, us)，剖析关键字集中的整体，并从中提取散布平均的若干位或它们的组合作为地址
  • 此办法仅适宜于：
    能事后预计出整体关键字的每一位上各种数字呈现的频度

平方取中法

  • 以关键字的平方值的两头几位作为存储地址。求“关键字的平方值”的目标是“扩充差异”，同时平方值的两头各位又能受到整个关键字中各位的影响
  • 此办法适宜于:
    关键字中的每一位都有某些数字反复呈现频度很高的景象

折叠法

  • 将关键字宰割成若干局部，而后取它们的叠加和为哈希地址。有两种叠加解决的办法：移位叠加和间界叠加
  • 此办法适宜于:
    关键字的数字位数特地多

除留余数法

  • Hash(key)=key mod p (p 是一个整数)
    p≤m (表长)

    • p 应为小于等于 m 的最大素数
    • 为什么要对 p 加限度？

给定一组关键字为: 12, 39, 18, 24, 33, 21 若取 p=9, 则他们对应的哈希函数值将为:
3, 3, 0, 6, 6, 3

可见，若 p 中含质因子 3, 则所有含质因子 3 的关键字均映射到“3 的倍数”的地址上，从而减少了“抵触”的可能

随机数法

  • H(key) = Random(key)（Random 为伪随机函数）
  • 此办法用于对长度不等的关键字结构哈希函数

思考因素

  1. 执行速度（即计算哈希函数所需工夫）
  2. 关键字的长度
  3. 哈希表的大小
  4. 关键字的散布状况
  5. 查找频率

采纳何种结构哈希函数的办法取决于建表的关键字汇合的状况
准则是使产生抵触的可能性降到尽可能地小

解决抵触的办法

1. 凋谢定址法

根本思维

有抵触时就去寻找下一个空的哈希地址，只有哈希表足够大，空的哈希地址总能找到，并将数据元素存入

线性探测法

Hi=(Hash(key)+di) mod m (1≤i < m)
其中：m 为哈希表长度
di 为增量序列 1，2，…m-1，且 di=i
一旦抵触，就找下一个空地址存入

  • 长处：只有哈希表未被填满，保障能找到 一个空地址单元寄存有抵触的元素

  • 毛病：能使第 i 个哈希地址的同义词存入第 i + 1 个地址，这样本应存入第 i + 1 个哈希地址的元素变成了第 i + 2 个哈希地址的同义词，……，产生“汇集”景象，升高查找效率

    二次探测法

    di = 12, -12, 22, -22, …±k2

伪随机探测法

Hi=(Hash(key)+di) mod m (1≤i < m)
其中：m 为哈希表长度
di 为随机数

凋谢定址法建设哈希表步骤

- 取数据元素的关键字 key，计算其哈希函数值（地址）。若该地址对应的存储 空间还没有被占用，则将该元素存入；否则执行 step2 解决抵触
- 依据抉择的抵触解决办法，计算关键字 key 的下一个存储地址。若下一个存储地址仍被占用，则继续执行 step2，直到找 到能用的存储地址为止

#### 凋谢定址哈希表的存储构造
/* ------------- 凋谢定址哈希表的存储构造 ------------- */

int hashsize[] = {997, ...};
typedef struct{
    ElemType* elem;
    int count;  // 以后数据元素个数
    int sizeindex;  // hashsize[sizeindex]为以后容量
} HashTable;

#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1

Status SearchHash(HashTable H, KeyType K, int &p, int &c){
    // 在凋谢定址哈希表 H 中查找关键码为 K 的记录
    p = Hash(K);  // 求得哈希地址
    while(H.elem[p].key != NULLKEY && !EQ(K, H.elem[p].key))
        collisiion(p, ++c);  // 求得下一探测地址 p
    if(EQ(K, H.elem[p].key)) return SUCCESS;  // 查找胜利，返回待查数据元素地位 p
    else return UNSUCCESS;  // 查找不胜利
}

2. 再 HASH 法

H2(key) 是另设定的一个哈希函数，它的函数值应和 m 互质

3. 链地址法

根本思维

  • 雷同哈希地址的记录链成一单链表， m 个哈希地址就设 m 个单链表，而后用用一个数组将 m 个单链表的表头指针存储起来，造成一个动静的构造

长处：

  • 非同义词不会抵触，无“汇集”景象
  • 链表上结点空间动静申请，更适宜于表长不确定的状况

哈希表的查找

对于给定值 K, 计算哈希地址 i = H(K)

  • 若 r[i] = NULL 则查找不胜利
  • 若 r[i].key = K 则查找胜利，否则“求下一地址 Hi”，直至 r[Hi] = NULL (查找不胜利) 或 r[Hi].key = K (查找胜利) 为止

案例 v01

线性探测法解决抵触

案例 v02

链地址法解决抵触

哈希表查找的剖析

从查找过程得悉，哈希表查找的均匀查找长度实际上 并不等于零

决定哈希表查找的 ASL 的因素

  • 选用的哈希函数
  • 选用的解决抵触的办法
  • 哈希表饱和的水平，装载因子 α=n/m 值的大小(n—记录数，m—表的长度)

α 越大，表中记录数越多，阐明表装得越满，发生冲突的可能性就越大，查找时比拟次数就越多

  1. 对哈希表技术具备很好的均匀性能，优于一些传统的技术
  2. 链地址法优于开地址法
  3. 除留余数法作哈希函数优于其它类型函数

哈希表利用举例

编译器对标识符的治理多是采纳哈希表

  • 结构哈希函数的办法

    • 将标识符中的每个字符转换为一个非负整数
    • 将失去的各个整数组合成一个整数（能够将第一个、两头的和最初一个字符值加在一起，也能够将所有字符的值加起来）
    • 将后果数调整到 0~M- 1 范畴内，能够利用取模的办法，Ki%M（M 为素数）

点击关注，第一工夫理解华为云陈腐技术~

退出移动版