数据结构与算法之美-散列表(中)

前言：本篇文章只是记录王争的数据结构与算法之美的学习笔记，写下来能强迫自己系统的再过一遍，加深理解。这门课以实际开发中遇到的问题为例，引入解决问题涉及到的的数据结构和算法，但不会讲的太细，最好结合一本实体书进行学习。

有些可能通过精心构造的数据，让所有的数据经过散列函数之后，都散列到同一个槽里，如果使用的是基于链表的冲突解决方法，此时散列表就会退化为链表，查询的时间复杂度就退化为了 O(n)。所以散列函数的设计就很重要了。

1. 散列函数的设计

散列函数的设计好坏，决定了散列表冲突的概率大小，决定了散列表的性能。

• 散列函数不能太复杂
• 散列函数生成的值要尽可能随机并且均匀分布

2. 装载因子过大

装载因子 = 已经存入的元素个数 / 数组的长度。

装载因子过大，说明散列表中的元素越多，空闲位置越少，散列冲突的概率就越大。

对于动态散列表来说，数据集合是频繁变动的，无法预估将要加入的数据个数，所以也就无法事先申请一个足够大的散列表，随着数据慢慢加入，装载因子就会变大，散列冲突会越来越多。

所以当装载因子过大时，可以进行动态扩容，重新申请一个更大的散列表，将数据搬移到这个新散列表中。

针对数组的扩容，数据搬移操作比较简单。但是针对散列表的扩容，数据搬移操作就要复杂了，因为散列表的大小变了，数据的存储位置也变了，所以我们需要通过散列函数重新计算每个数据的存储位置，如下图所示：

image.png

有了扩容也就有缩容，对于动态散列表，随着数据的删除，散列表中的数据会越来越少，空闲空间会越来越多，如果对空间消耗比较敏感，可以在装载因子小于某个值之后，进行动态缩容。

装载因子阈值的设置要权衡时间&空间复杂度。

3. 避免低效的扩容

大部分情况下，动态扩容的散列表插入一个数据很快，但是在装载因子达到阈值的情况下，则需要先扩容，再插入数据，这个时候，插入数据就会很慢，甚至无法接受。

假设散列表当前大小为 1GB，想要扩容为原来的两倍大小，就需要对 1GB 的数据重新计算哈希值，并且从原来的散列表搬移到新的散列表，这就很耗时了。

所以这个时候，“一次性”扩容的机制就不合适了，我们可以将扩容操作穿插在插入操作的过程中，分批完成。当装载因子达到阈值之后，只是先申请新空间，但并不将老的数据搬移到新的散列表中。

当有新的数据要插入时，同时将老的散列表中拿出一个数据放入到新的散列表，重复这个过程，经过多次插入之后，老的散列表的数据就会全部搬移到新的散列表中了，这样插入操作就会很快了，如下图：

image.png

但是这样的话，查询操作就需要先从新的散列表中查，再从旧的散列表中查了。

这样将一次性扩容的代价，均摊到多次插入操作中，就避免了一次扩容耗时过多的情况，这种实现方式下，任何情况下，插入一个数据的时间复杂度都是 O(1)。

3. 散列冲突解决方法

3.1 开放寻址法

优点：

• 散列表中的数据都存储在数组中，可以有效的利用 CPU 缓存加快查询速度

缺点：

• 删除数据比较麻烦，需要先标记已删除的数据
• 冲突的代价更高，所以装载因子的阈值不能太大，比链表发更浪费空间

数据量比较小、装载因子小的时候，适合采用开放寻址法

3.2 链表法

优点：

• 对内存的利用率比开放寻址法高
• 对大装载因子的容忍度更高，可以>1，只是链表的长度变长了而已

缺点：

• 链表需要存储指针，对于小对象的存储，会更多的消耗内存
• 结点是零散分布的，对 CPU 缓存不友好

可以对链表法进行改造，比如使用红黑树或者跳表替换链表，即使最坏情况下，查找时间复杂度也是 O(logn)。

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

4. 工业级散列表特点

以 java 中的 hashMap 为例：

• 初始大小
  初始大小是 16，可以修改默认初始大小，减少动态扩容的次数

• 装载因子和动态扩容
  最大装载因子默认为 0.75，每次扩容都会扩容为原来的两倍大小

• 散列冲突解决方法
  使用链表法来解决冲突，在 JDK1.8 版本中，引入了红黑树，当链表长度太长（默认超过 8）时，链表会转换为红黑树（利用红黑树快速增删改查，提高性能），当红黑树结点个数少于 8 个的时候，又将红黑树转化为链表。

• 散列函数
  简单高效、分布均匀

1.计算hash值：
 hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

在获取对象的 hashcode（32 位整型值） 以后，先右移 16 位，再和自己做异或运算，这一步称为扰动函数，用自己的高位和低位做异或，混合原始哈希码的高位和低位，以此来加大低位的随机性，为后续计算 index 截取低位，保证低位的随机性。这样可以保证对象的 hashCode 的 32 位值只要有一位发生改变整个 hash()的返回值就会改变，高位的变化可以反应到低位里，保证 hash 值的随机性。

2.在插入或查找的时候，计算Key被映射到桶的位置：
int index = hash(key) & (capacity - 1)

这一步其实是除留余数法，保证了 index 的位置分布均匀。
A % B = A & (B - 1) ，当 B 是 2的整次幂时，等式成立。

数组长度是 2 的整次幂时，数组长度-1 正好相当于一个低位掩码，“与”操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。

以初始长度 16 位例，16-1 = 15，2 进制为00000000 00000000 00001111，“与”操作的结果就是截取了最低的四位值，也相当于取模操作。

这一步在查看 iOS 底层源码时经常遇到，这次总算明白了。