【图解数据结构】外行人也能看懂的哈希表(上)

简介: 常用英文单词20万个,假设单词平均长度10个字母,平均一个单词占用10字节,那20万英文单词大约占2MB存储空间,这完全可以放在内存。所以我们可以用散列表来存储整个英文单词词典。当用户输入某个英文单词时,拿用户输入的单词去散列表中查找:查到,则说明拼写正确没有查到,则说明拼写可能有误,给予提示这就能轻松实现快速判断是否存在拼写错误。

输入一个错误的英文单词,它就会提示“拼写错误”。这个单词拼写检查功能,虽然很小但却非常实用。是如何实现的呢?

1 什么是散列?

散列表,Hash Table,用数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。

假如有89名候选人参加大选。为了方便记录投票,每个候选人胸前会贴上自己的参赛号码。这89名选手的编号依次是1到89。

通过编号快速找到对应的选手信息。你怎么做?


可以把这89人的编号跟数组下标对应,查询编号x的人时,只需将下标为x的数组元素取出,时间复杂度就是O(1)。看来按编号查对应人信息,效率很高。


这就是散列,编号是自然数,并且与数组的下标一一映射,所以利用数组支持根据下标随机访问时间复杂度是O(1),即可实现快速查找编号对应的人信息。


假设编号不能设置这么简单,要加上州名、职位等更详细信息,所以编号规则稍微修改,用6位数字表示。比如051167,其中,前两位05表示州,中间两位11表示职位,最后两位还是原来的编号1到89。


此时如何存储选手信息,才支持通过编号来快速查找人信息?


可以截取编号的后两位作为数组下标,来存取候选人信息数据。当通过编号查询人信息时,同样取编号后两位,作为数组下标读取数组数据。


这就是散列。候选人编号叫作键(key)或关键字,以标识一个候选人。把参赛编号转化为数组下标的映射方法就叫作散列函数(或“Hash函数”“哈希函数”),而散列函数计算得到的值就叫作散列值(或“Hash值”“哈希值”)。


散列表用的就是数组支持按照下标随机访问的时候,时间复杂度是O(1)的特性。我们通过散列函数把元素的键值映射为下标,然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时,我们用同样的散列函数,将键值转化数组下标,从对应的数组下标的位置取数据。

1.1 装载因子(load factor)

表示空位的多少:

散列表的装载因子=填入表中的元素个数/散列表的长度
  • 装载因子越大,说明空闲位置越少,哈希冲突概率越大,插入过程要多次寻址或拉长链,查找也会因此变得很慢。
  • 太小,会导致内存浪费严重。

1.2 哈希表碰撞攻击

有些攻击者会构造数据,使得所有数据经过hash函数后同槽。若使用的链表法,这时哈希表就会退化为链表,查询时间复杂度从O(1)急剧退化为O(n)。


若哈希表有10w数据,退化后的hash表查询效率就下降10万倍。若之前运行100次查询需0.1s,则现在需1w s。这就可能消耗大量CPU或线程资源,导致系统无法响应其他请求,即拒绝服务攻击(DoS)。

2 hash函数

即hash(key),其中key表示元素的K值,hash(key)的值表示经过散列函数计算得到的hash值。

若编号就是数组下标,所以hash(key)就等于key。改造后的例子,写成hash函数稍微有点复杂。我用伪代码将它写成函数就是下面这样:

int hash(String key) {
  // 获取后两位字符
  string lastTwoChars = key.substr(length-2, length);
  // 将后两位字符转换为整数
  int hashValue = convert lastTwoChas to int-type;
  return hashValue;
}

但现实都是复杂的,若候选人编号是随机生成的N位数或a到z之间的字符串,散列函数该如何实现?

2.1 要求

  • 散列函数计算得到的散列值是个非负整数
    因为数组下标从0开始
  • 若key1 = key2,则hash(key1) == hash(key2)
  • 若key1 ≠ key2,则hash(key1) ≠ hash(key2)
    此要求看起来合理,但实际上几乎找不到一个不同key对应散列值都不同的散列函数,即使如MD5、SHA、CRC。而且数组存储空间也是有限的,散列冲突概率就更大了。
  • 不能太复杂
    过度复杂会消耗大量计算时间,影响hash表性能
  • hash函数生成的值要尽可能随机并且均匀分布
    避免或最小化哈希冲突,而且即便出现冲突,散列到每个槽里的数据也会比较平均,不会数据倾斜

2.2 案例

处理手机号码,因为手机号码前几位重复的可能性很大,但后面几位就比较随机,可以取手机号后四位作为散列值。这种设计方法称为“数据分析法”。

单词拼写检查功能的hash函数可考虑:

  • 将单词中每个字母的ASCll码值“进位”相加
  • 再跟哈希表的size求余、取模,作为散列值

比如,英文单词java,我们转化出来的散列值就是下面这样:

hash("java")=(("j" - "a") * 26*26*26 + ("a" - "a")*26*26 + ("v" - "a")*26+ ("a"-"a")) / 78978

还有很多设计方法,比如直接寻址法、平方取中法、折叠法、随机数法等。hash函数设计的好坏,决定了哈希表冲突的概率大小,也直接决定了哈希表的性能。

无论设计的多么优秀,还是得考虑如何解决散列冲突问题。

3 散列冲突

3.1 开放寻址法

若出现hash冲突,就重新探测一个空闲位置,将其插入。

最简单的就是

3.1.1 线性探测(Linear Probing)

当我们往散列表中插入数据时,如果某个数据经过散列函数散列之后,存储位置已经被占用了,我们就从当前位置开始,依次往后查找,看是否有空闲位置,直到找到为止。如ThreadLocalMap。

案例

  • 黄块
    空闲位置
  • 橙块
    已存储数据

image.png

散列表的大小10,在元素x插入散列表之前,已有6个元素在散列表。

x经过Hash算法后,被hash到下标7处,但该位置已有数据,所以hash冲突。

顺序再往后一个个找,看有无空闲位置,遍历到尾部都没有空闲位置,就再从表头开始找,直到找到空闲位置2插入。

查找元素

类似插入过程。通过hash函数求出要查找元素的键值对应的散列值,然后比较数组中下标为散列值的元素和要查找的元素:

  • 若相等
    则为目标元素
  • 否则
    继续顺序往后查找

若遍历到数组中的空闲位置,还没找到,说明目标元素不在散列表。

9.png

线性探测法的散列表,删除操作不能单纯地把要删除的元素置null。这是为什么呢?

查找时,一旦通过线性探测方法,找到一个空闲位置,即可认定散列表不存在该数据。

但若该空闲位置是我们后来删除的,就会导致原来的查找算法失效。本来存在的数据,会被认定为不存在。


可以将删除的元素,特殊标记为deleted。当线性探测查找时,遇到deleted空间,并不是停下来,而是继续往下探测。

image.png

目录
相关文章
|
12月前
|
算法 Java 数据库
数据结构与算法学习十五:哈希表
这篇文章详细介绍了哈希表的概念、应用实例、实现思路,并提供了使用Java实现的哈希表代码。
195 0
数据结构与算法学习十五:哈希表
|
7月前
|
存储 NoSQL Java
【数据结构进阶】哈希表
哈希表是一种高效的数据结构,通过哈希函数实现数据映射,支持平均O(1)时间复杂度的查找、插入和删除操作。本文详细介绍了哈希表的基本概念、哈希函数的设计(如直接定址法和除留余数法)以及哈希冲突的解决方法(如开放定址法和链地址法)。同时,文章通过代码实例展示了线性探测和链地址法两种哈希表的实现过程,并分析了各自的优缺点。最后总结指出,合理选择哈希函数和冲突解决策略是优化哈希表性能的关键。
448 2
|
10月前
|
数据库
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
|
存储 Java Serverless
【数据结构】哈希表&二叉搜索树详解
本文详细介绍了二叉搜索树和哈希表这两种数据结构。二叉搜索树是一种特殊二叉树,具有左子树节点值小于根节点、右子树节点值大于根节点的特点,并且不允许键值重复。文章给出了插入、删除和搜索等方法的具体实现。哈希表则通过哈希函数将键名映射为数组下标,实现快速查找,其插入、删除和查找操作时间复杂度理想情况下为O(1)。文中还讨论了哈希函数的设计原则、哈希冲突的解决方法及哈希表的实现细节。
249 8
【数据结构】哈希表&二叉搜索树详解
|
12月前
|
存储 缓存 Java
【数据结构】哈希表
【数据结构】哈希表
166 1
|
存储 Java
数据结构中的哈希表(java实现)利用哈希表实现学生信息的存储
这篇文章通过Java代码示例展示了如何实现哈希表,包括定义结点类、链表类、数组存储多条链表,并使用简单的散列函数处理冲突,以及如何利用哈希表存储和查询学生信息。
数据结构中的哈希表(java实现)利用哈希表实现学生信息的存储
|
存储 算法 NoSQL
数据结构和算法——哈希查找冲突处理方法(开放地址法-线性探测、平方探测、双散列探测、再散列,分离链接法)
数据结构和算法——哈希查找冲突处理方法(开放地址法-线性探测、平方探测、双散列探测、再散列,分离链接法)
670 1
|
存储 NoSQL 算法
redis数据结构—哈希表
redis数据结构—哈希表
118 0
|
存储 算法 大数据
深入解析力扣170题:两数之和 III - 数据结构设计(哈希表与双指针法详解及模拟面试问答)
深入解析力扣170题:两数之和 III - 数据结构设计(哈希表与双指针法详解及模拟面试问答)
|
存储 算法
数据结构和算法——了解哈希表(哈希查找、散列的基本思想)
数据结构和算法——了解哈希表(哈希查找、散列的基本思想)
126 0