关于散列表(哈希表)我所知道的

持续创作，加速成长！这是我参与「掘金日新计划 · 10 月更文挑战」的第1天，点击查看活动详情

关键词：散列表 哈希表 哈希算法

什么是散列/哈希表？

散列表其实是数组的一种扩展，由数组演化而来。利用了数组随机访问数据的特性，降低了数据读取的复杂度。使用哈希表可以解决数组由于线性查找效率低，耗时过长的问题。

散列表存储的是由键（key）和值（value）组成的数据。在 JS 中，也可以将对象理解成一种散列表。

其实有点像解码，变量名是 key , 变量值是 value , 输入是入参，输出是出参。函数在里面对应的角色就是将入参通过某种处理，处理成出参。

举个例子：

const A = '1'
const B = '2'
const C = '3'
const D = '4'
const fn = (...args) => {
  return args.join('') * 1
}
console.log(fn(A, B, C))
console.log(fn(A, B, C, D))

复杂度

在平均情况下，散列表的查找（获取给定索引处的值）速度与数组一样快，而插入和删除速度与链表一样快，因此它兼具两者的优点。

但在最糟情况下，散列表的各种操作的速度都很慢。因此，在使用散列表时，避开最糟情况至关重要。

为此，需要避免冲突。（最好是个正方形）

什么是哈希函数

把给定的数据转换成固定长度的无规律数值。

哈希函数的特征

• 输出的哈希值数据长度不变。
• 如果输入的数据相同，那么输出的哈希值也必定相同。

• 输入的数据相似，输出的哈希值也会有很大差异。
• 输入的两个数据完全不同，输出的哈希值也有可能相同。这种情况就是 哈希冲突，造成这种情况的原因就是：数组的存储空间有限，数组越短，哈希冲突的概率越大。

典型的哈希算法有：MD5、SHA-1、SHA-2。不同算法有不同的计算方式，所以输入数据相同，算法不同的话，输出的哈希值也会不同。

如何解决哈希冲突

开放地址法

通过多次使用哈希函数或“线性探测法”计算候补地址。如果仍然有冲突，便继续计算下一个候补地址，直到有空地址为止。

优点

• 不需要拉链表，哈希表中的数据都储存在数组中，查询速度更快。
• 方便序列化。

缺点

• 删除数据需要特殊处理。要删除的数据并没有被删除，只是添加了被删除了的标记。
• 更浪费内存，因为数据都存在数组中

应用场景： 数据量小、需要序列化的时候

链地址法

发生冲突就利用链表在已有数据的后面插入新数据来解决冲突。

优点：

• 内存利用率高

缺点：

• 查找的时候比开放地址法复杂。

参考资料：

《算法图解》