哈希表

发布于: 2020 年 07 月 07 日

1、背景

在查找的数据结构,无论是 线性表 或者 树 结构,记录在结构中的相对位置是【随机】的,和记录的关键字不存在确定关系,这类查找方法建立在“比较”的基础上。

在顺序查找中,比较的结果为 “=” 与 “≠” 两种可能;

在折半查找、二叉排序树查找和B树查找时,比较的结果为 “<”, “=” 和 “>” 三种可能;

【查找的效率】依赖于查找过程中进行的【比较次数】;

理想的情况是【不经过比较】,一次就可以得到记录,这就必须在记录的存储位置与它的关键字之间建立一个确定的【对应关系】,是每个关键字和结构中唯一的存储位置相对应;

因此需要根据【对应关系】找到关键字的位置,这个【对应关系】称作【哈希(Hash)函数】,按这个思想建立的表为【哈希表】;

2、哈希表

2-1、问题

1、【哈希函数】是一个映射,只要关键字经过哈希函数计算得到的值都在【哈希表长】允许范围之内即可;

2、哈希冲突:对不同的关键字可能得到同一哈希地址,这种现象称为【冲突(collision)】;

即 key1 ≠ key2,但 F(key1) = F(key2);

一般情况,冲突只能尽可能减少,而不能完全避免;

在构建哈希表时不仅要设定“好”的哈希函数,而且要设定一种处理冲突的方法;

2-2、定义

根据设定的哈希函数F(key) 和 处理冲突的方法 将一组关键字映射到一个【有限的】【连续的】地址集上,并以关键字在地址集中的“像”作为记录在表中的存储位置,这种表称为【哈希表】;

这一映像过程称为【散列】,所得存储位置称【哈希地址】或【散列地址】;

2-3、哈希函数的构造方法

2-3-1、什么是“好”的函数?

关键字经过哈希函数得到一个随机地址,使一组关键字的哈希地址【均匀分布】在整个地址区间,从而减少冲突

2-3-2、直接地址法

取关键字或关键字的某个线性函数值为哈希地址。即:

H(key) = key 或 H(key) = a * key + b

其中 a 和 b 为常数(这种哈希函数叫做自身函数);

2-3-3、数字分析法

  • 关键字以R为基数;

  • 并且哈希表中可能出现的【关键字事先知道】;

  • 则可取关键字的【若干数位】组成哈希地址;

2-3-4、平方取中法

取关键字平方后的中间几位为哈希地址;

2-3-5、折叠法

将关键字分割成【位数相同】的几部分(最后一部分的位数可以不同),然后取这几部分的【叠加和】作为哈希地址,该方法称为折叠法(folding);

使用场景:关键字位数很多,而且关键字中每一位上数据分布大致均匀时;

2-3-6、除留余数法

取关键字被某个【不大于】哈希表表长的数,将这个数作为除数,关键字作为被除数,所得【余数】为哈希地址;即

H(key) = key MOD p, p ≤ 哈希表长度;

注意:

使用除留取余法时,对除数的选择很重要,一旦选择不好,会产生较大冲突;

2-3-7、随机数法

选择一个随机函数,取关键字的随机函数值为哈希地址,即 H(key) = random(key),其中 random 为 随机函数;通常,当关键字长度不等时适合用随机数法构造哈希函数;

2-3-8、选择哈希函数考虑的因素

  • 计算哈希函数所需时间;

  • 关键字长度;

  • 哈希表大小;

  • 关键字的分布情况;

  • 记录的查找频率;

2-4、处理冲突的方法

2-4-1、开放地址法

H = ( H(key) + d ) MOD m,

其中: H(key) 为哈希函数;m 为哈希表表长;d为增量序列;

2-4-2、再哈希法

H = RH(key),R 和 H 是不同的哈希函数,再产生哈希冲突时计算另一个哈希函数地址,直到冲突不再发生;

好处:不易产生“聚集”;

坏处:增加计算时间;

2-4-3、链地址法

关键字的哈希值相同的记录存储在同一线性链表上,每个值的初始状态都是空指针;

2-4-4、建立一个公共溢出区

哈希函数的值的范围[0, m-1],则HashTable为[0 ... m -1 ] 的基本表,每个值存放一个记录;

在另外创建一个向量 OverTable[0 ... V] 为溢出表;

所有关键字和基本表中的关键字为同义词记录,一旦发生冲突,都填入溢出表;

发布于: 2020 年 07 月 07 日 阅读数: 9
用户头像

Albert

关注

还未添加个人签名 2018.08.31 加入

还未添加个人简介

评论

发布
暂无评论
哈希表