散列表
在前面我们已经知道，我们可以使用数组中的下标对数据进行定位，这种定位方式非常快速。但是在数组定位中有一个局限性：被用于定位的数据只能是数字（也就是下标），这就让数组的应用被限制在了一个比较狭窄的领域。
散列表的出现就是为了打破这种局限，可以说，散列表由数组演化而来，没有数组，就没有散列表。
散列思想
散列表的使用形式是： key（键）：v（数据值）。我们用 key 标记一个数据，并使用 散列函数（哈希函数） 将 key 转换成数组下标（在这里是数字），其中数组下标可以称为 散列值（哈希值）。
哈希思想.jpg
你也能看到，散列函数对散列表来说是非常重要的。
散列函数
散列值被用作存储数组的下标，在这里，我们需要对散列函数做出三点基本要求：
- 通过散列函数计算得到的散列值必须非负。
- 如果 k1 = k2 ,那么 hash(k1) == hash(k2)。
- 如果 k1 != k2 ，那么 hash(k1) != hash(k2)。
这很容易理解，但是对于第三个要求来说，这几乎是不可能的。即使是著名的哈希算法，也无法避免这种散列冲突。而且，因为数组的存储空间有限，也会大大增加散列冲突的概率。
散列冲突
再好的散列函数也无法避免散列冲突，在这里有两种方式处理散列冲突：开放寻址法 和 链表法：
1.开放寻址法
开放寻址法的核心思想是：如果出现散列冲突，就在数组中重新寻找一个空闲位置，将数据插入到这个空闲位置处。根据重新寻找位置的方法的不同，有线性探测、二次探测、双重散列等。这里使用最简单的线性探测为例：
如果我们想要将散列值为 n 的数据插入，结果发现 n 处已经被占用，就尝试存放在 n+1 处，如果仍然被占用，就一直向下探测：
散列冲突-开放寻址法.jpg
图中 hash（key） = n
同理，我们如果要查询一个数据，就在数组 n 中查询，若该位置的数据内容与 key 不同，就向下进行探测，直到找到 key 或 探测到空数据（表明散列表中没有这条数据）：
开放寻址法-判是否存在.jpg
使用线性探测法删除数据有些特别：你不能单纯地把要删除的元素设置为空，因为在查找的时候，一旦我们通过线性探测的方法找到一个空闲位置，我们就认定散列表中不存在这个数据。但是，如果这个空闲位置是我们后来删除的，就会导致原来的算法失效。本来存在的数据，会被认定不存在，这怎么解决呢？
我们可以将删除的元素特殊标记为 deleted ，当探测查找的时候，遇到 deleted 不会停止，而是继续探测：
开放寻址法-删除操作.jpg
你可能已经发现，线性探测存在很大的问题：当散列表中的数据越来越多时，散列表的冲突可能性越来越大，寻找或删除所需要的探测时间越来越久，极端情况下我们需要遍历整个数组，时间复杂度退化为O(n)。
不是使用什么样的探测方法，在散列表空闲位置不多的时候，冲突概率会大大提高，这里我们使用装载因子来表示散列表和数据的关系：
装载因子 = 填入表中的元素个数 / 散列表的长度
当装载因子为 1 的时候，开放寻址法下的散列表就已经无法工作了。
2.链表法
链表法是更常见的冲突解决办法，看下面的图：在散列表中，每个“桶” 或 “槽” 会对应一条链表，所有散列值相同的元素都会放在对应的链表中：
散列冲突-链表法.jpg
我们用 n 表示散列表中的数据个数，m 表示散列表中的“槽”的个数，如果散列分布均匀，有 k = n / m ，则散列表的查询和删除操作的时间复杂度为 O(k)。
小小结
在这一小结中，我们讨论了散列表的两个核心问题：散列函数设计 和 散列冲突解决。散列函数的设计决定了散列冲突的概率，对散列冲突的处理决定了散列表的性能。
设计一个高性能的散列表
我们通过上面的介绍已经了解到了散列表的基本知识，下面我们讨论一下如何设计一个高性能的散列表：
如何设计散列函数？
- 首先，散列函数不能太复杂，过于复杂的散列函数需要资源计算，会影响散列表的性能。
- 其次，散列函数生成的值要尽可能随机且均匀，如果分布不均，会出现大量的散列冲突，会影响性能。
装载因子过大怎么办？
动态散列表会频繁变动，我们无法事先预估需要存储的数据的个数，所以我们会遇到装载因子渐渐变大的情况，之前我们已经了解，装载因子过大会影响处理性能，此时，我们应该如何处理呢？
答案很简单，使用动态扩容：为散列表设置一个装载因子的阈值，当装载因子超过阈值时就启动动态扩容操作，相比于数组的动态扩容，散列表的数据搬移工作要复杂一些：你需要根据 key 重新计算散列值并填充到新表中：
散列表-动态扩容.jpg
扩容需要O(n)的时间复杂度，这势必会影响数据插入的效率，我们可以使用之前我们讲过的摊还分析法分析插入的时间复杂度，最终结果仍然为O(1)。
当然，如果散列表的装载因子过小，我们也可以启动动态缩容。
扩容和缩容的阈值需要根据计算机的内存大小和计算性能综合考虑。
如何避免低效扩容？
在旧散列表中有 1G 的数据，如果要求动态扩容的操作“一次性”搬移全部的数据，这个操作是十分费时的，势必也会影响性能，这个时候，我们就需要一种新的扩容机制了：
我们可以将扩容操作穿插在插入过程中，分批完成。当新散列表申请完成后我们并不进行数据搬移，当有新的数据要插入时，我们将新数据插入新散列表中，并且从老散列表中拿出一个数据放到新散列表中。每进行一个插入操作，我们都重复上面的过程，经过多次插入后，老的数据就会一点一点搬移到新的散列表中了。这样不会影响插入操作的性能：
动态扩容-数据搬移操作.jpg
如何选择冲突解决方法？
我们需要分析两种解决方法，并根据应用场景选择：
1.开放寻址法
- 优点：可以使用 cache 加快查询速度 ；序列化比较简单。
- 缺点：需要对删除操作做特殊处理 ； 散列冲突的代价高 ，装载因子较大时性能损失难以接受。
- 场景选择：数据量较小，装载因子较小的时候选择开放寻址法。
2.链表法
-
优点：有数据加入时再创建链表结点，内存使用效率高 ； 对大装载因子的容忍度较高，我们甚至可以在链表中使用红黑树，以应对极端情况：
链表法-拉链改造.jpg
-
缺点：指针消耗内存 ；无法使用 cache 。
-
场景选择：适合存储较大对象，大数据量的应用场景。
小小结
设计一个高性能的散列函数需要考虑：
- 在各个场景下仍然可以支持快速的插入、查询、删除操作（性能稳定）
- 内存占用合理
要实现这样的目标我们要：
- 设计合适的散列函数
- 定义恰当的装载因子阈值和二扩容策略
- 选择合适的散列冲突解决方法
散列表和链表的组合使用
通过以前的学习我们知道，链表可以很方便地进行插入、删除操作，但是它查找的时间复杂度是O(n)。
通过这一节的学习我们知道，散列表的查询的时间复杂度为O(1)。
我们能否将两种数据结构结合起来，实现不论查找还是插入、删除操作都十分快速的数据结构呢？下面我们使用散列表和链表构建一个可以实现 LRU缓存淘汰算法的数据结构，让你直观的感受一些这种组合的魅力。
LRU缓存淘汰算法
LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，要了解算法的具体细节可以自行百度。
一个缓存(cache) 系统主要包括下面几个操作：
- 在缓存中查找一个数据。（根据LRU算法，找到后需要将该数据结点放到链表尾部）
- 向缓存中添加一个数据。（添加位置：散列表的拉链 和 双向链表的尾部）
- 从缓存中删除一个数据。（记得维护散列表中的拉链）
在这三个操作中，首先都要进行查找操作，如果单纯地使用链表，受限于链表糟糕的查询表现，整体的性能不会太好，所以我们使用散列表完成查询操作：
哈希+链表-lru缓存淘汰.jpg
如上图，我们使用双向链表存储数据，每个链表结点除 存储数据（data）、前驱指针（prev）、后继指针（next）之外，还新增了一个特殊的字段 ：hnext。
我们使用链表法解决散列冲突，所以在每个结点会处于两条链中：一条是双向链表，另一条是散列表中的拉链。
在结点中，前驱和后继指针将结点维护在双向链表中，hnext指针将结点穿在散列表的拉链中。
知道了这个cache系统的结构，我们就可以分析它的三个操作了：
- 查找数据：
散列表中查找数据的时间复杂度接近O(1)，所以通过散列表，我们可以很快地在缓存中找到一个数据。当找到这个数据后，我们还要将它移动到双向链表的尾部。 - 删除数据：
首先使用散列表查找到结点，由于我们使用双向链表存储数据，所以可以很方便地删除结点。 - 添加数据：
添加数据有点麻烦，我们要先看这个数据是否已经在缓存中。如果已经在，就将其移动到双向链表的尾部；如果不在，要看缓存有没有满。如果满了，将双向链表的头结点删除，然后再将数据放到链表的尾部；如果没有满，直接将数据放到链表的尾部。
所有涉及查找操作的动作都可以通过散列表来完成。其它的操作，比如删除、插入等，都可以利用链表完成。所以，三个操作的时间复杂度都是O(1)。至此，我们通过散列表和双向链表的组合使用，实现了一个高效的、支持LRU缓存淘汰算法的缓存系统原型。
以上就是散列表的全部内容
注：本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结，我大量引用了其中的代码和截图，如果想要了解具体内容，可以前往极客时间
网友评论