散列查找表(哈希表)

散列查找表

之前我们的查找,都需要通过比较a[i] 和 key

• 顺序查找的方式是 “=” 还是 “!=”

• 折半查找的方式是 “>” 还是 “<”

• 在树的结构中依旧包含了 < > =

无论如何比较都不可避免,能否存在直接通过关键词key找到记录的内存存储位置呢?

这就是我们要讨论的散列技术

散列技术

散列技术是在记录的位置和它的关键字之间建立一个确定的对应关系 f

使得每个关键字key都有对应的存储位置 f(key)

在这里我们把这种对应关系 f 称为散列函数,又称为哈希(hash)函数

根据这种思想,采用散列技术将记录存储在一块连续的存储空间中,这块连续存储空间称之为散列表或者哈希表,关键字所对应的记录存储位置我们称之为散列地址

散列表查找步骤

• 在存储时,通过散列函数计算记录的散列地址,按此地址存储该记录
• 在查找时,通过散列函数计算记录的散列地址,按此散列地址访问该记录

所以,散列函数既是一种存储方法,也是一种查找方法

区别

对比其他查找结构

• 线性表、树、图都具有一定的逻辑关系
• 散列技术记录之间没有逻辑关系，记录只与关键字有关

因此 散列表是面向查找的存储结构，最适合求解的问题：查找与给定值相等的记录

实现

hash表的重点是设计一种简单、均匀、存储利用率高的的散列函数

如果出现了key₁ != key₂ ，但是f(key₁ ) = f(key₂ ) ，这种表现称之为哈希冲突（collision）,并且把key₁和key₂ 称之为这个散列函数的同义词（synonym）

散列函数的构造方法

优秀散列函数的定义：

1. 计算简单（起码低于其他查找技术和关键字比较的时间）
2. 散列地址的均匀分布 （保证存储空间有效利用、减少处理哈希冲突的时间）

以下介绍几种常见的散列构造函数（有些类似于密码学，将原来的数字按某种规律变成另一个数字）

直接定址法

取关键字的某个线性函数值为散列地址
$$
f(key) = a*key + b
$$

数字分析法

例如身份证号码，前几位数字相同，后几位数字运用散列函数

**抽取方法:**使用关键字的一部分来计算散列函数

使用范围：适合处理关键字特别多、事先知道关键字的分布、关键字若干位分布均匀

平方取中法

用法：将关键字平方之后取中间三位数

适用：不知道关键字分布、位数不多

折叠法

用法：将关键字从左到右分割成位数相等的几部分（最后一部分可以小一些），这这几部分相加求和，根据散列表长，取最后几位为散列地址

如果分布不均匀，可以将数据反转一下，如将下表的987 转为789

若散列表长为3

987654321—— 987 + 654 + 321 + 0 = 1962

求最后三位为 962

适用：不需要知道关键字分布、关键字比较多

除留余数法

最常用的散列函数，对一个散列表长度为m的散列函数公式为，mod为取余数
$$
f(key) = key;mod ,p(p<=m)
$$

• 不仅可以对关键字直接取模，也可以折叠、平方后再取模
• 关键的方法在于选择合适的P，减少hash冲突
• 根据经验，p为小于或者等于表厂m（最好接近m）的最小质数或者不包含小于20质因子的合数

随机算法

用法
$$
f(key) = random(key)
$$
适用：关键字长度不等

random函数考虑因素

• 计算散列地址的时间
• 关键字长度
• 散列表大小
• 关键字分布情况
• 记录查找的频率

处理哈希冲突

哈希冲突在所难免，所以有了后续的处理方法

开放地址法

所谓开放地址法就是发生了哈希冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并记录
$$
f1（key）=(f(key) + di)MOD;m:(di=1、2、3、4…….m-1)
$$
简单得说，就是在hash地址冲突时，将计算出的结果地址向下延续n位，直到有空位

我们将这种解决冲突的开放地址法称之为线性探测法

• 本来就不是同义词的关键字取争夺同一个地址时，我们称之为堆积
• 堆积的出现大大影响了查找和记录的效率

为此还有其他的开放地址方法

• 二次探测法：将d_i的递增改为平方

  其中d_i=1、-1、2、-2、4…….q²、-q²（q <= m/2）

• 随机探测法：d_i是一个随机数列

再散列函数法

发生hash冲突时采用备用的散列函数

优势是使得关键字不发生集聚，缺点是增加了计算时间

链地址法

散列地址变成指针指向一个单链表

缺点是带来了查找时遍历单链表的性能损耗

公共溢出法

将所有冲突的关键字存入一个公共的溢出区来存放

查找时先计算散列地址的值，比较后若是相等就取出；如果不相等就去溢出区进行顺序查找

适用于冲突比较少的情况

查找实现

• 首先定义散列表结构和基本常数
• 对散列表进行初始化
• 定义散列函数（函数可以更具情况更改算法）
• 插入时计算散列地址，若地址存在关键字，进行hash冲突处理
• 查找和插入类似，额外做一个不存在关键字的判断

散列表性能分析

如果没有冲突，hash表的时间复杂度为最低 : O（1）

可惜哈希冲突在所难免，需要额外处理的计算，那么平均查找长度取决哪些因素呢？

其中散列函数是否均匀对查找性能是几乎不用考虑的，其主导的有以下

处理冲突的方法

这个浅显可以理解

散列表的填装因子

填装因子α：填入表中的记录个数/散列表长度

其中α表示散列表的装满程度，α越大，发生哈希冲突的情况越多

为此我们在了解记录个数n的情况下，总可以选择一个合适的填装因，以便将平均查找长度限定在一个长度范围内。通常是将散列表空间设置得比查找集合大，一牺牲空间换取时间效率