19、散列表（中）

思考：如何设计一个可以应对各种异常情况的工业级散列表，来避免在散列冲突的情况下，散列表性能的急剧下降，并且能抵抗散列碰撞攻击？

主要内容

散列表的时间复杂度受散列函数、装载因子、散列冲突影响。
好的情况是 O(1)，坏的情况是 O(n)
比如有 10W 数据，好的时候查询是 0.1 s，坏的时候查询是 1W s。这样查询会占用系统资源，导致无法响应其他请求，可以达到拒绝服务攻击(Dos)的目的。这也是散列表碰撞攻击的基本原理。

如何设计散列函数？

考虑点：
1、不能太负责。越复杂计算越耗费时间
2、生成的散列值尽可能的随机与平均。避免或最小化降低冲突
3、其他：散列值的长度、大小等等

所以好的散列函数能极大降低散列冲突。

常用的设计方法：数据分析法、平方取中数、随机数法等等

装载因子过大时？

装载因子 = 已填入的数量 / 散列表长度
过大，表明空位少，则散列冲突概率更大。

则可以考虑动态扩容，即申请 2 倍大小的散列表，更新散列函数的计算(跟散列长度挂钩)，然后将旧散列表中的值通过新散列函数生成的散列值迁移到新散列表中
如果不更新散列函数的计算或不散跟列长度挂钩，则扩容后的空间永远也用不上，失去扩容意义。

是否扩容跟我们设计的装载因子阈值有关，太大则容易冲突，太小则会浪费内存去扩容

如何避免低效的扩容？

什么是低效的扩容：当旧散列表数据很大，装载因子刚达到阈值时，若扩容时一次性搬运所有数据，则很耗时。
可以采用分批搬运，即扩容时不触发搬运。等有新的插入操作时，先将该值插入新散列表，然后从旧散列表搬运一个到新散列表。这样随着插入次数变多，搬运就一步步完成了

查找时：先找新散列表，没找到再找就散列表

如何选择冲突解决方案

解决散列冲突的方案有：开放寻址法、链表法
那它们的优缺点与场景是什么呢？

开放寻址法

优点：数据还是保存在数组中的，则还能吃数组的红利
缺点：随着数组填充，散列冲突的概率还是很高
适用场景：数据量小、装载因子上限小的。因为装载因子太大，则冲突严重，插入时找空闲的时间会更长

链表法

对装载因子容忍度更高。
因为冲突的地方已变成链表结构了，所以装载因子为 10 都无所谓。只是链表查找时稍微麻烦，但我们可以将链表结构改为更高效的：[跳表](https://www.yuque.com/u53094/vd58kv/kfz92fee6k217wes?singleDoc# 《17 | 跳表》)，这样查找效率也可以更快。

所以基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用跳表、红黑树代替链表。

工业级散列表举例

以 Java 中的 HashMap 举例
它的初始大小为默认为：16，算比较小的了，但支持动态扩容的哈
它的最大装载因子默认为 0.75，每次扩容 2 倍大小
它的散列冲突解决方法是链表，之后若节点个数大于 8 转为红黑树，小于 8 又转为链表
它的散列函数很简单高效、平均分布

int hash(Object key) {
  int h = key.hashCode()；
  return (h ^ (h >>> 16)) & (capicity -1); //capicity表示散列表的大小
}

解答思考

思考：如何设计一个可以应对各种异常情况的工业级散列表，来避免在散列冲突的情况下，散列表性能的急剧下降，并且能抵抗散列碰撞攻击？

解答：
工业级的散列表要求：

1. 支持快速地查询、插入、删除操作；
2. 内存占用合理，不能浪费过多的内存空间；
3. 性能稳定，极端情况下，散列表的性能也不会退化到无法接受的情况。

设计考虑点：简单高效与平均分布的散列函数、合理的装载因子阈值与高效扩容方式、合理的散列冲突解决方式与灵活的数据结构变化

内容总结

散列表的核心考虑点是：散列函数、装载因子、扩容策略、散列冲突解决方案

新的思考

在你熟悉的编程语言中，哪些数据类型底层是基于散列表实现的？散列函数是如何设计的？散列冲突是通过哪种方法解决的？是否支持动态扩容呢？

来自通义千问：

在 JavaScript 中，虽然没有直接提供名为“散列表”或“哈希表”的内置数据类型，但 JavaScript 的对象（Object）类型在底层可以看作是一个散列表的实现。

JavaScript 的对象允许你通过键（key）来存储和检索值（value），这些键通常是字符串类型，但也可能包括 Symbols。当你使用点记法或方括号记法给对象添加属性时，JavaScript 引擎实际上是在执行一个散列查找过程，将属性名转换成一个散列码（即哈希值），然后使用这个散列码来决定值在对象内部的存储位置。这意味着你可以近乎 O(1)的时间复杂度来插入、更新和查找对象的属性，这正是散列表数据结构的核心特性之一。

let obj = {};
obj[‘name’] = ‘Alice’; // 这里，’name’ 就是一个键，’Alice’ 是对应的值

在这个例子中，obj 类似于一个散列表，其中 'name' 被散列并映射到其对应的值 'Alice'。由于这种键值对的存储方式以及对键进行快速访问的能力，JavaScript 的对象可以被视作是散列表的应用实例。