【数据结构】散列表：从特性分析到散列冲突再到应用总结

柔情只为你懂 2022-12-12 00:32 192阅读 0赞

## 1.散列表是什么 ##

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

### 1.1 散列表与数组 ###

从上面对散列表的定义可以看到，散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。与数组的区别在于：

*  使用数组时，我们一般按序放入，即 for(i) arr\[i\]
 *  使用散列表时，具体的索引位置是key经过散列函数计算得到的，即 i = hash(key)

所以，散列表其实包含了一种 k-v 的思想：

*  K：hash值，是数据内部计算的不是我们传的那个key
 *  V：实际存入的值，可以是一个基本类型比如 int，也可以是一个 Node，或者包含了key的 Entry<k,v>

### 1.2 散列表与Map ###

Map 是一种**容器**，并且以 Entry<K, V> 作为基本存储单位，而 Map 的底层**数据结构**实现，即组织 Entry 的可以是数组，链表，散列表，树等：

*  链表：不合适，k-v查询太慢O(n），链表操作还需要遍历
 *  散列表：契合，其设计思想就是 K-V，而查询和操作复杂度都是O（1）==> HashMap
 *  树：特定情况契合，树组织Entry是有序的，其查询复杂度是O（logn）==> TreeMap

## 2.散列函数 ##

### 2.1 基本要求 ###

散列函数必须满足下面几个要求：

*  散列函数计算得到的散列值是一个非负整数。因为数组下标是从 0 开 始的，所以散列函数生成的散列值也要是非负整数
 *  相同的 key，经过散列函数得到的散列值也应该是相同的。比如 key1 = key2，那么 hash(key1) == hash(key2)
 *  不同的 key，经过散列函数得到的散列值也应该是不同的。比如 key1 ≠ key2，那 hash(key1) ≠ hash(key2)
    
    这个要求看起来合情合理，但是在真实的情 况下，要想找到一个不同的 key 对应的散列值都不一样的散列函数，几乎是不可能的。即便像业界著名的MD5、SHA、CRC等哈希算法，也无法完全避免这种散列冲突。

### 2.2 如何设计散列函数？ ###

1.  首先，散列函数的设计**不能太复杂**。过于复杂的散列函数，势必会消耗很多计算时间，也就间接的影响到散列表的性能。
2.  其次，散列函数生成的值要尽可能**随机并且均匀分布**，这样才能避免或者最小化散列冲突，而且即便出现冲突，散列到每个槽里的数据也会比较平均，不会出现某个槽内数据特别多的情况

// HashMap 的散列函数
    int hash(Object key) {
           
        int h = key.hashCode()；
        	// apicity 表示散列表的大小，结果等同于 h % (capitity -1)
            return (h ^ (h >>> 16)) & (capitity -1); 
    }

## 3.散列冲突 ##

在讲散列冲突解决方案前，我们先来看看看什么是装载因子。

散列表的装载因子 = 填入表中的元素个数 / 散列表的长度

所以，我们一般用装载因子（load factor）来表示空位的多少：

*  **装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降**。
 *  HashMap的装载因子 = 0.75 当 HashMap 中元素个数超过 0.75\*capacity（capacity 表示 散列表的容量）的时候，就会启动扩容，每次扩容都会扩容为原来的两倍大小。

下面我们就来看看散列冲突的几种解决方案…

### 3.1 开放寻址法 ###

如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入。

*  优点
    
     *  开放寻址法不像链表法，需要拉很多链表。散列表中的数据都存储在数组中，可以**有效地利用 CPU 缓存加快查询速度**。
     *  而且，这种方法实现的散列表，**序列化**起来比较简单。链表法包含指针，序列化起来就没那么容易。
 *  缺点
    
     *  用开放寻址法解决冲突的散列表，**删除数据的时候比较麻烦**，需要特殊标记已经删除掉的数据。
     *  而且，在开放寻址法中，所有的数据都存储在一个数组中，比起链表法来说，**冲突的代价更高**。所以，使用开放寻址法解决冲突的散列表，**装载因子的上限不能太大。这也导致这种方法比链表法更浪费内存空间**。

**当数据量比较小、装载因子小的时候，适合采用开放寻址法**。这也是 Java 中的**ThreadLocalMap**使用开放寻址法解决散列冲突的原因。

**方案一：线性探测**

当我们往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。下图是一个示例：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center]  
**方案二：二次探测**

所谓二次探测，跟线性探测很像，线性探测每次探测的步长是 1，那它探测的下标序列就是 hash(key)+0，hash(key)+1，hash(key)+2……

而二次探测探测的步长就变成了原来 的“二次方”，也就是说，它探测的下标序列就是 hash(key)+0²，hash(key)+1²， hash(key)+2²……

**方案三：双重散列**

所谓双重散列，意思就是不仅要使用一个散列函数。

我们使用一组散列函数 hash1(key)， hash2(key)，hash3(key)……我们先用第一个散列函数，如果计算得到的存储位置已经被占 用，再用第二个散列函数，依次类推，直到找到空闲的存储位置。

### 3.2 链表法(桶/槽) ###

链表法是一种更加常用的散列冲突解决办法，相比开放寻址法，它要简单很多。

*  优点：链表法对内存的利用率比开放寻址法要高\*\*。因为链表结点可以在需要的时候再创建， 并不需要像开放寻址法那样事先申请好。实际上，这一点也是链表优于数组的地方。
 *  缺点：
    
     *  链**表因为要存储指针，所以对于比较小的对象的存储，是比较消耗内存的**，还有可能会让内存的消耗翻倍。
        
        当然，如果我们存储的是大对象，也就是说要存储的对象的大小远远大于一个指针的大小 （4 个字节或者 8 个字节），那链表中指针的内存消耗在大对象面前就可以忽略了。
     *  因为链表中的结点是零散分 布在内存中的，不是连续的，所以**对 CPU 缓存是不友好的**，这方面对于执行效率也有一定的影响。

**方案一：拉链**

在散列表中，每个**桶(bucket)** 或者 **槽(slot)** 会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center 1]  
复杂度分析：

*  当插入的时候，我们只需要通过散列函数计算出对应的散列槽位，插入到对应链表的中即可（借助tail指针），所以插入的时间复杂度是 **O(1)**。
 *  当查找、删除一个元素时，我们同样通过散列函数计算出对应的槽，然后遍历链表查找或者删除。
    
    实际上，这两种操作的时间复杂度都跟链表的长度 k 成正比，也就是 **O(k)**。对于散列比较均匀的散列函数来说，理论上讲，k=n/m，其中 n 表示散列中数据的个数，m 表示散列表 中“槽”的个数。

**方案二：树化**

实际上，我们对链表法稍加改造，可以实现一个更加高效的散列表。那就是，我们将链表法 中的链表改造为其他高效的动态数据结构，比如跳表、红黑树。这样，即便出现散列冲突， 极端情况下，所有的数据都散列到同一个桶内，那最终退化成的散列表的查找时间也只不过 是 **O(logn)**。这样也就有效避免了前面讲到的散列碰撞攻击。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center 2]

### 3.3 动态扩容 ###

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

假设每次扩容我们都申请一个原来散列表大小两倍的空间。 如果原来散列表的装载因子是 0.8，那经过扩容之后，新散列表的装载因子就下降为原来的 一半，变成了 0.4。

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

**分批扩容思路**

举一个极端的例子，如果散列表当前大小为 1GB，要想扩容为原来的两倍大小，那就需要对 1GB 的数据重新计算哈希值，并且从原来的散列表搬移到新的散列表，听起来就很耗时，是不是？

如果我们的业务代码直接服务于用户，尽管大部分情况下，插入一个数据的操作都很快，但是，极个别非常慢的插入操作，也会让用户崩溃。这个时候，“一次性”扩容的机制就不合适了。为了解决一次性扩容耗时过多的情况，我们可以将扩容操作穿插在插入操作的过程中，分批完成。

1.  当装载因子触达阈值之后，我们只申请新空间，但并不将老的数据搬移到新散列表中。
2.  当有新数据要插入时，我们将新数据插入新散列表中，并且从老的散列表中拿出一个数据放入到新散列表。
3.  每次插入一个数据到散列表，我们都重复上面的过程。
4.  经过多次插入操作之后，老的散列表中的数据就一点一点全部搬移到新散列表中了。这样没有了集中的一次性数据搬移，插入操作就都变得很快了。

而对于查询操作，为了兼容了新、老散列表中的数据，我们先从新散列表中查找，如果没有找到，再去老的散列表中查找。

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

## 4.散列表应用 ##

### 4.1 HashMap、HashSet ###

这里就放两个源码分析的链接吧：

*  [【Java容器源码】HashMap最详细万字源码分析（JDK8）][Java_HashMap_JDK8]
 *  [【Java容器源码】HashSet源码分析][Java_HashSet]

### 4.2 散列表+双向链表：LinkedListMap ###

散列表这种数据结构虽然支持非常高效的数据插入、删除、查找操作，但是散列表中的数据都是**通过散列函数打乱之后无规律存储的**。也就说，它**无法支持按照某种顺序快速地遍历数据**。

如果希望按照顺序遍历散列表中的数据，那我们需要将散列表中的数据拷贝到数组中， 然后排序，再遍历。因为散列表是动态数据结构，不停地有数据的插入、删除，所以每当我们希望按顺序遍历散列表中的数据时，都需要先排序，那效率势必会很低。

为了解决这个问题，我们将散列 表和链表（或者跳表）结合在一起使用。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center 3]  
LinkedListHashMap 采用的就是哈希表+双向链表，这里用双向链表是因为在删除操作时，不用再遍历一遍得到前序节点，可以在O(1)完成。具体可以参考源码 [【Java容器源码】LinkedHashMap源码分析][Java_LinkedHashMap]。

### 4.3 Word 文档中单词拼写检查功能 ###

常用的英文单词有 20 万个左右，假设单词的平均长度是 10 个字母，平均一个单词占用 10 个字节的内存空间，那 20 万英文单词大约占 2MB 的存储空间，就算放大 10 倍也就是 20MB。对于现在的计算机来说，这个大小完全可以放在内存里面。所以我们可以用散列表来存储整个英文单词词典。

当用户输入某个英文单词时，我们拿用户输入的单词去散列表中查找。如果查到，则说明拼写正确；如果没有查到，则说明拼写可能有误，给予提示。借助散列表这种数据结构，我们 就可以轻松实现快速判断是否存在拼写错误。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/ba6e8e076889400b8498d3614f52c760.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/86879626bbbd4dc4a5aedcaf54136f64.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/144baeaa1c944b2390fe85389cdceaef.png
[Java_HashMap_JDK8]: https://blog.csdn.net/weixin_43935927/article/details/108889167
[Java_HashSet]: https://blog.csdn.net/weixin_43935927/article/details/108519853
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/ded58feed67f498697df2c657a4fe94b.png
[Java_LinkedHashMap]: https://blog.csdn.net/weixin_43935927/article/details/108512608