散列表 Hash Table
散列表也叫哈希表、Hash Table，散列表用的是数组支持按照下标随机访问数据的时候，时间复杂度是O(1)的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。
散列表通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置，当查询时，利用同样的散列函数，将键值转化为数组下标，从对应的数组下标的位置取数据。
散列发怒时的两个核心问题是散列函数设计和散列冲突解决。
散列函数
散列函数可以看成hash(key)，其中key表示元素的键值，hash(key)的值表示经过散列函数计算得到的散列值。
散列函数设计的基本要求：
- 散列函数计算得到的散列值是一个非负整数
- 如果key1==key2，那么hash(key1)==hash(key2)
- 如果key1≠key2，那么hash(key1)≠hash(key2)
几乎无法找到一个完美的无冲突的散列函数。
散列冲突
常用的解决散列冲突的解决方法有两种：开放寻址法(open addressing)和链表法(chaining)。
开放寻址法
开放寻址法的核心思想是：如果出现了散列冲突，就重新检测一个空闲位置，将其插入。
检测新位置的方法有线性探测(Linear Probing)：即当发现某个数据经过散列函数后位置已经被占用了，就从当前位置开始，一次往后查找，看是后有空闲位置，直到找到为止。
插入数据时的示意图如下：
查找数据时的示意图如下：
利用线性探测法解决冲突的散列表的删除操作有点特别，不能直接删除某个元素，而是需要将该元素对应位置设置为deleted的标志位，当线性探测遇到该位置时，不是停止，而是继续往下探测，示意图如下：
线性探测法的问题是当从插入的数据越来越多时，发生冲突的可能性就越来越大，空闲位置就会越来越少，线性探测的时间就会越来越久，最坏情况时间复杂度为O(n)。查找和删除时都可能需要遍历整个散列表，最坏时间复杂度都为O(n)。
检测新位置的方法还有：
- 二次探测Quadratic probing)： 线性探测的步长是1，探测下标序列是hash(key) + 0, hash(key)+1，二次探测的步长是原来的二次方，即hash(key) + 0, hash(key)+1^2,hash(key) + 2^2
- 双重散列(Double hashing):不仅使用一个散列函数，而是使用一组散列函数，hash1(key),hash2(key),hash3(key)…如果发现位置已经被占用的情况，就依次使用下一个散列函数计算存储位置
当散列表中的空闲位置不多的时候，散列冲突的概率就会大大提高。
通常我们尽可能保证散列表中有一定比例的空闲槽位，用转载因子(load factor)来表示空位多少，其计算公式是：
$$ 散列表的转载因子 = 填入表中的元素个数/散列表的长度 $$
转载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。
链表法
链表法是更加常用的散列冲突解决方法，即在散列表中，每个桶或者槽会对应一个链表，所有散列值相同的元素都放到相同槽位对应的链表中，示意图如下：
散列表利用链表法的插入数据时间复杂度是O(1)，删除和查找是O(k)，与链表的长度k成正比，对于散列比较均匀的散列函数来说，理论上讲k=n/m，其中n表示散列中数据的个数，m表示散列表中槽的个数。
如何实现Word文档中单词拼写检查功能
利用散列表将英文单词全部放入内存中，非常小20万个英文单词，一个单词平均长度是10个字母占10个字节，总的内存约为2MB，最大不会超过20 MB，这样将用户输入的单词利用散列函数进行散列查找，如果找到，说明单词拼写正确，没有找到即代表拼写错误，给出提示。
如何打造一个工业级水平的散列表
散列表的查询效率并不总是O(1)，它跟散列函数、装载因子、散列冲突等都有关系。当散列表中一个槽内链表的数据量巨大为K时，会造成查询的效率下降到O(K)，严重影响查询时间，导致系统无法响应其他请求，从而达到拒绝服务供给(Dos)的目的，这也就是散列表碰撞攻击的基本原理。
如何设计散列函数
- 散列函数的设计不能太复杂：计算耗时消耗CPU计算时间
- 散列函数生成的值要尽可能随机并且均匀分布：避免或者最小化散列冲突，让每个槽的数据均匀分布，不会产生个别槽数量过多的情况
转载因子过大怎么办
转载因子过大，说明散列表中的元素越多，空闲位置越少，散列冲突的概率就越大，不仅插入数据的过程要多次寻址或者拉很长的链，查找的过程也会因此变得很慢。
静态数据可以提前预估数据的范围，设计出完美的、极少冲突的散列函数，但是对于动态数据来说，数据集合是频繁变动的，无法直接设计出完美的、极少冲突的散列函数，因此需要借助动态扩容的思想解决该问题。
针对散列表，当装载因子过大时，重新申请一个更大的散列表，将数据重新hash之后迁移到新的散列表中。这样就降低了装载因子。相比于数组的动态扩容，简单复制数据即可，散列表需要通过散列函数重新计算每个数据的存储位置，更加的费时，示意图如下。
支持动态扩容的散列表，插入一个数据，最好情况下，不需要扩容，即最好时机复杂度是O(1)，最坏情况下，装载因子过大，启动扩容并且搬移数据，时间复杂度为O(n)，均摊时间复杂度为O(n)。
当转载因子过低时，为了不浪费内存，可以选择动态缩容。
转载因子的选择过大，会导致冲突过多；过小，会导致内存浪费严重，其值的选择需要权衡时间、空间复杂度。
如何避免低效地扩容
如果数据量巨大，扩容时的操作耗费时间过多，对于实时性要求较高的场合，会让用户等待过久，严重影响用户体验。
为了解决一次性扩容耗时过多的情况，可以将扩容操作穿插在插入操作的过程中，分批完成：
- 当转载因子达到阈值后，只申请新空间，并不进行数据的搬移操作。
- 当新数据插入时，直接插入到新散列表中，并且从老的散列表中拿出一个数据插入到新散列表
- 这样重复第二个步骤，就没有集中的一次性数据搬移，插入操作就会变快
示意图如下：
对于查询操作，先从新散列表中查找，如果没有，再去旧的散列表中查找即可。
如何选择冲突解决方法
开放寻址法优缺点
- 可以有效利用CPU缓存加快查询速度
- 序列化非常方便
- 删除数据的时候比较麻烦，需要特殊标记已经删除掉的数据，即冲突的代价更高，因此转载因子的上限不能太大，这也导致这种方法比链表法更浪费空间。
- 只适用于转载因子小于1的情况
当数据量小，使用采用开放寻址法，这也是Java中的ThreadLocalMap使用开放寻址法解决散列冲突的原因。
链表法优缺点
- 内存利用率比开放寻址法高，因为链表结点可以随意创建扩充，而数组需要预定大小；
- 对大转载因子的容忍度更高，只要散列函数的值随机均匀，即便转载因子变成10，即链表长度变长，但是整体查询效率比顺序查找快很多
- 对于小对象的存储，消耗更多的内存；大对象存储可以忽略链表的内存影响
- 不是连续存储，对CPU缓存是不友好的
- 包含指针，不容易序列化，
更加高效的散列表是将链表法中的链表改造为其他高效的动态数据结构，如跳表、红黑树，这样，即使出现散列冲突，极端情况下也可以在O(logn)的时间复杂度完成查找操作。
基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树替代链表。
Java中的HashMap分析
- 初始大小默认是16，可以通过设置减少动态扩容的次数
- 装载因子为0.75，当元素个数超过0.75*capacity(散列表的容量时)，动态扩容散列表为2倍大小
- 底层采用链表法来解决散列冲突，在JDK1.8中，引入了红黑树：
- 当链表长度太长(默认为6)时，链表转换为红黑树，可以利用红黑树快速增删改查的特点，提高HashMap的性能
- 当链表长度长度小于6时，将红黑树转换为链表，因为在数据量小的情况下，红黑树需要维护平衡，更加消耗时间
- 散列函数
int hash(Object key) {
int h = key.hashCode()；// 返回java对象的hash code
// h ^ (h >>> 16)：计算出来的整形值具有高位和地位的性质
// 因为 X % 2^n = X & (2^n - 1)，2^n表示2的n次方，即一个数对2^n取模 == 一个数和(2^n - 1)做按位与运算 。
// 所以，(h ^ (h >>> 16)) & (capacity -1) = (h ^ (h >>> 16)) % capacity
return (h ^ (h >>> 16)) & (capacity -1); //capacity 表示散列表的大小
}
String对象的hashCode()函数为
public int hashCode() {
int var1 = this.hash;
if(var1 == 0 && this.value.length > 0) {
char[] var2 = this.value;
for(int var3 = 0; var3 < this.value.length; ++var3) {
var1 = 31 * var1 + var2[var3];
}
this.hash = var1;
}
return var1;
}
设计一个工业级的散列表
工业级的散列表需要满足的要求：
- 支持快速的查询、插入、删除操作
- 内存占用合理，不能浪费过多的内存空间
- 性能稳定，极端情况下，性能不会退化到无法接受的情况
设计思路：
- 设计一个合适的散列函数
- 定义转载因子阈值，设计动态扩容策略
- 选择合适的散列冲突解决方法
散列表和链表的结合
LRU缓存淘汰算法
之前讲解的LRU缓存淘汰算法。
一个缓存主要包含以下几个操作：
- 往缓存中添加一个数据
- 从缓存中删除一个数据
- 在缓存中查找一个数据
这三个操作都需要查找操作，如果使用链表实现，时间复杂度只能是O(n)。如果将散列表和链表结合使用，可以将三个操作的时间复杂度都降低到O(1)，示意图如下：
图中，链表的每个节点处理存储数据(data)、前驱指针(prev)、后继指针(next)和一个特殊指针hnext，因为散列表是通过链表法解决散列冲突的，所以每个节点会在两条链中，一个是双向链表，一个是散列表中的拉链，前驱和后继指针是为了将节点串在双向链表中，hnext指针是为了将节点串在散列表的拉链中。
如何查找数据：通过散列表查找数据的时间复杂度接近O(1)，找到一个数据之后，还需要将它移动到双向链表的尾部
如何删除一个数据：利用散列表O(1)时间复杂度找到数据结点，然后因为有双向链表，可以直接通过前驱指针获取前驱结点，从而在O(1)时间复杂度内删除结点。
如何添加一个数据：
- 数据不存在缓存中：
- 通过一个计数变量判断缓存满了，先将双向链表的头部结点删除，然后将数据放到双向链表尾部
- 通过一个计数变量判断缓存没满，直接将数据放到链表尾部
- 数据已经存在缓存中：需要将其移动到双向链表的尾部
这三个操作因为散列表的加入，查找时间复杂度都为O(1),删除操作因为双向链表的存在，也是O(1)。这样借助散列表和链表实现了一个高效的、支持LRU缓存淘汰算法的缓存系统原型。
Redis有序集合
有序集合的每个成员有两个属性键值和分值，对于分值可以使用跳表建立索引，按照键值构建一个散列表，这样按照键值删除、查找一个成员对象的时间复杂度就都是O(1)了，借助跳表结构，针对分值的其他操作也非常高效。
Java LinkedHashMap
LinkedHashMap支持按照插入顺序遍历数据，默认情况是该设置，代码如下：
HashMap<Integer, Integer> m = new LinkedHashMap<>();
m.put(3, 11);
m.put(1, 12);
m.put(5, 23);
m.put(2, 22);
for (Map.Entry e : m.entrySet()) {
System.out.println(e.getKey());
}
按照插入顺序遍历打印输出为3,1,5,2。
LinkedHashMap支持按照访问顺序来遍历数据，即：在LinkedHashMap中添加数据的时候，是LRU的逻辑，先查看是否已经存在该数据，有则将该数据移动到链表的尾部，没有则添加该数据到链表的尾部，代码如下：
// 10 是初始大小，0.75 是装载因子，true 是表示按照访问时间排序
HashMap<Integer, Integer> m = new LinkedHashMap<>(10, 0.75f, true);
m.put(3, 11);
m.put(1, 12);
m.put(5, 23);
m.put(2, 22);
m.put(3, 26);
m.get(5);
for (Map.Entry e : m.entrySet()) {
System.out.println(e.getKey());
}
按照访问时间排序输出为：1,2,3,5。
代码对应的散列表状态示意图为：
插入完成3,1,5,2
更新3
获取5
LinkedHashMap是通过双向链表和散列表结合实现的，“Lined”实际上指的是双向链表，并非指链表法解决散列冲突。
为什么散列表和链表经常结合使用
散列表支持非常高效的数据插入、删除、查找操作，但是散列表中的数据都是通过散列函数打乱之后无规律存储的，无法支持按照某种顺序快速地遍历数据，如果希望按照顺序遍历散列表中的数据，就需要将散列表中的数据拷贝到数组中，然后排序，再遍历。
由于是散列表是动态数据结构，会不停插入、删除数据，采用数组会有扩容和排序问题，效率太低，因此采用散列表和链表，或者支持区间查询的跳表结合在一起使用就会更加的高效。
注：本文是《数据结构与算法之美》的读书笔记，配套代码 地址GitHub。本文仅限个人学习，请勿用作商业用途，谢谢。
Note: Cover Picture