数据结构-哈希表

3/10/2021 JavaScriptAlgorithm

# 文章目录

# 一、什么是哈希表?

# 1.1 认识哈希表

在这里插入图片描述
在开始了解哈希表之前,我们先来看一下数组的优缺点:

  1. 数组进行 插入 操作时, 效率低
  2. 数组进行删除操作时,效率低
  3. 数组进行 查找 操作:
    3.1 如果基于 索引 进行查找操作时, 效率非常高
    3.2 基于内容去查找,比如(name=“why”),效率则非常

综上所述,其实我们不难看出,数组其实效率比较低,那么我们可不可以提高它的效率呢,答案是可以的,我们的前辈们就完成了这样一种伟大的发明(哈希表的由来),哈希表是基于数组去实现的

接下来我们通过三个案例来充分认识哈希表的优势。

# 1.2 案例一 公司员工存储

在这里插入图片描述.在这里插入图片描述

# 1.3 案例二 联系人与电话存储

在这里插入图片描述在这里插入图片描述

# 1.4 案例三 50000 个单词存储

在这里插入图片描述

# 二、字母转数字的方案

似乎所有的案例都指向了一目标:将字符串转成下标值

但是,怎样才能将一个字符串转成数组的下标值呢

单词/字符串转下标值,其实就是字母/文字转数,怎么转

现在我们需要设计一种方案可以将单词转成适当的下标。

其实计算机中有很多的编码方案就是用数字代替单词的字符。就是字符编码。(常见的字符编码?)
比如 ASCII 编码:a 是 97,b 是 98,依次类推 122 代表 z

我们也可以设计一个自己的编码系统比如 a 是 1,b 是 2,c 是 3,依次类推,z 是 26.当然我们可以加上空格用 0 代替,就是 27 个字符(不考虑大写问题)
但是,有了编码系统后,一个单词如何转成数字呢?

# 2.1 方案一

在这里插入图片描述

# 2.2 方案二

在这里插入图片描述
这里我们选择改进第二种方案,改进的过程就叫做: 哈希化

# 三、哈希表

在了解哈希表之前,我们需要知道何为哈希化?
在这里插入图片描述
认识情况了上面的内容,相信你应该懂了哈希表的原理了,我们来看看几个概念。

  • 哈希化:将大数字转化成数组范围内下标的过程,我们就称之为哈希化
  • 哈希函数:通常我们会将单词转成大数字大数字在进行哈希化的代码实现放在一个函数中,这个函数我们称为哈希函数
  • 哈希表:最终将数据插入到的这个数组,对整个结构的封装,我们就称之为是一个哈希表

但是,我们还有问题需要解决
虽然,我们在一个 100000 的数组中,放 50000 个单词已经足够

但是通过哈希化后的下标值依然可能会重复如何解決这种重复的问题呢?

# 3.1 哈希化之后产生的 冲突

在这里插入图片描述
两种解决方案:

  1. 链地址法
  2. 开放地址法

# 3.2 深入 链地址法(拉链法)

在这里插入图片描述
以前的位置不在是单独的存放数据了,而是创造一个数组或者链表,把数据放入里边,如果之后再次产生了冲突,则依次放入链表或者数组。
在这里插入图片描述

# 3.3 开放地址法

在这里插入图片描述

# 3.4 开放地址法——线性探测

# 3.4.1 什么是线性探测?

在这里插入图片描述

# 3.4.2 线性探测的问题——删除、插入、聚集

在这里插入图片描述

# 3.5 开放地址法——二次探测

在这里插入图片描述

# 3.6 开放地址法——再哈希法

在这里插入图片描述

stepSize = constant - (key % constant)
注:constant 是质数(除 1 和本事外,不能被整除的数),且 constant 小于数组容量
在这里插入图片描述
由此得出,哈希表的容量最好也是 质数

# 3.7 哈希化的效率

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

# 3.8 优秀的哈希表

在这里插入图片描述
在这里插入图片描述

最后更新于: 2021年9月15日星期三晚上10点10分
Faster Than Light
Andreas Waldetoft / Mia Stegmar