corner的前端知识库

DAY2 散列哈希

# DAY2 散列哈希

# 问题

  1. 哈希表的空间复杂度
  2. 哈希Map，重复的怎么算
  3. webpack中生成的哈希值作用是啥？
  4. 哈希 什么是哈希冲突 如何解决哈希冲突
  5. 哈希函数 md5 sha1
    • md5: 对于原始消息做有损的压缩计算，生成消息摘要；单向不可逆；可用于密码保存
  6. 线性表散列存储哈希解决

# 正文

# 基本概念

采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间即称为散列表。

image-20220321140806343

我们可以理解为数学函数，Y=F(X)，X 为自变量也就是这里的 Key, F( ) 对应图中的 H( )，也就是一个映射关系，Y 因变量也就是对应的值的 存放位置


散列既是一种查找技术，也是一种存储技术。

散列只是通过记录的关键码定位该记录，没有完整地表达记录之间的逻辑关系，即通过关键码能推出 Key 值，但是通过关键码对应的值（即位置处的值）不能推出关键码，所以散列存储的关键码和值之间并不对称，因此散列主要是面向查找的存储结构。

# 优缺点

优点：

  1. 查找效率高
  2. 高性能，时间复杂度为O(1)

缺点：

散列表并不是适用于所有的需求场景，那么哪些情况下不适合使用呢？

  1. 散列技术一般不适合在允许多个记录有同样关键码的情况下使用。

    因为这种情况下，通常会有冲突存在，将会降低查找效率，体现不出散列表查找效率高的优点。

    并且如果一定要在这个情况下使用的话，还需要想办法消除冲突，这将花费大量时间，那么就失去了 O(1) 时间复杂度的优势，所以在存在大量的冲突情况下，我们就要弃用散列表。

  2. 散列方法也不适用于范围查找，比如以下两个情况。

    • 查找最大值或者最小值

      因为散列表的值是类似函数的，映射函数一个变量只能对应一个值，不知道其他值，也不能查找最大值、最小值，RMQ(区间最值问题）可以采用 ST 算法、树状数组和线段树解决。

    • 也不可能找到在某一范围内的记录

      比如查找小于 N 的数有多少个，是不能实现的，原因也是映射函数一个变量只能对应一个值，不知道其他值。

# 散列技术的关键问题

在使用散列表的时候，我们有两个关键的技术问题需要解决：

  1. 散列函数的设计，如何设计一个简单、均匀、存储利用率高的散列函数？
  2. 冲突的处理，如何采取合适的处理冲突方法来解决冲突。

# 如何设计实现散列函数

在构建散列函数时，我们需要秉持两个原则：

  1. 简单
    • 散列函数不应该有很大的计算量，否则会降低查找效率。
  2. 均匀：
    • 函数值要尽量均匀散布在地址空间，这样才能保证存储空间的有效利用并减少冲突。

# 散列函数实现三种方法

# 1.直接定址法

散列函数是关键码（Key）的映射的线性函数，形如：

H(key) = a * key + b

来看一个小案例：

如果关键码的集合已知且为 [11,22,33,66,88,44,99]

H(key) = 1/11 * key + b

image-20220321142556746

缺点

  • 我们是看到了这个集合，然后想到他们都是 11 的倍数才想到这 Hash 函数。我们在平常的使用中一般不会提前知道 Key 值集合，所以使用较少。

适用范围：

  • 事先知道关键码，关键码集合不大且较为连续而不离散。
# 2.除留余数法

H(key)=key mod p

来个小例子：

H(key)=key mod 21

image-20220321142910733

会发现产生了很多相同的 H(K)，这就是发生冲突，因为一个位置只能放一个数，有两个值对应这里一个位置，是不可以的。

这种方法是最常用的方法，这个方法的关键在于如何选取 P，使得利用率较高并且冲突率较低，一般情况下，我们会选取最接近表长且小于等于表长的最大素数。

缺点

  • P 选取不当，会导致冲突率上升。

适用范围：

  • 除留余数法是一种最简单、也是最常用的构造散列函数的方法，并且不要求事先知道关键码的分布。

这个方法非常常用，我们后面题目的展开就是使用的这个方法。在大部分的算法实现中也都是选取的这一种方式。

# 3.数字分析法

比如我将我的集合全部转化为 16 进制数，根据关键码在各个位上的分布情况，选取分布比较均匀的若干位组成散列地址。或者将 N 位 10 进制数，观察各各位的数字分布，选取分布均匀的散列地址。

举个小例子：

image-20220321143347902

首先我们考虑一位作为散列函数，发现都是很多冲突，选取两位时，百位和十位组合最适宜，分布均匀且没有冲突。

当然，我们说的是这一方法的一个具体实列，既然叫做数字分析法，那么只有对于不同数据的不同分析，才能写出更是适配的 H(x)。

# 4.平方取中法
# 5.折叠法

# 解决冲突方法

# 1. 开散列方法（open hashing）

open hashing 也称为拉链法，separate chaining 称为链地址法，简单来说，就是由关键码得到的散列地址一旦产生了冲突，就去寻找下一个空的散列地址，并将记录存入。

寻找下一个空的散列地址的方法：


(1)线性探测法

当发生冲突时，从冲突位置的下一个位置起，依次寻找空的散列地址。

对于键值 key，设 H(key)=d，闭散列表的长度为 m，则发生冲突时，寻找下一个散列地址的公式为：

image-20220321145445106

堆积现象：在处理冲突的过程中出现的非同义词之间对同一个散列地址争夺的现象。

例子：

Key 集合为 47, 7, 29, 11, 27, 92, 22, 8, 3。

P 值为 11，进行 Hash 映射，采用线性探测法处理冲突。

image-20220321145709220

image-20220321145741209

image-20220321145800900

image-20220321145812849


（2）二次探测法

即当发生冲突时，寻找下一个散列地址的公式为：

image-20220321145936846


(3)随机探测法

当发生冲突时，下一个散列地址的位移量是一个随机数列，即寻找下一个散列地址的公式为：

image-20220321150056129

(4)再hash法


# 2.闭散列方法

closed hashing 也称为开地址方法，open addressing 开放地址法，开放地址法中涵盖了以下两种实现方式；

  • 拉链法（链地址法）

    将所有散列地址相同的记录即 Key 值相同的项目，坠成一个链表，每个链表的头指针存放位置为 Key 值对应的位置。

    image-20220321150922916

  • 建立公共溢出区

    散列表包含基本表和溢出表两部分（通常溢出表和基本表的大小相同），将发生冲突的记录存储在溢出表中。

    查找时，如果在基本表里找的到就返回成功，没找到就在溢出区顺序查找，注意这里不再是映射而是顺序查找，放置时也是按照顺序的方式。

    image-20220321151120593

柯里化.md