数据结构与算法--散列表数据结构与算法--散列表

散列表(Hash Table)，也叫它“哈希表”或者“Hash 表”.
散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。
散列表用的就是数组支持按照下标随机访问的时候，时间复杂度是 O(1) 的特性。我们通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时，我们用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。
散列函数散列函数，顾名思义，它是一个函数。我们可以把它定义成 hash(key)，其中 key 表示元素的键值，hash(key) 的值表示经过散列函数计算得到的散列值。
散列函数设计的基本要求：

散列函数计算得到的散列值是一个非负整数； (数组下标从0开始)
如果 key1 = key2，那 hash(key1) == hash(key2)；
如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。 (注: 要想找到一个不同的 key 对应的散列值都不一样的散列函数，几乎是不可能的)

散列冲突我们常用的散列冲突解决方法有两类，开放寻址法（open addressing）和链表法（chaining）。
1. 开放寻址法（open addressing）

文章图片
散列冲突-开放寻址法.png 开放寻址法的核心思想是，如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入。

线性探测（Linear Probing）
插入时, 数组下标已经存在元素时,继续向后寻找空闲位置；
查询时,我们通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素。如果相等，则说明就是我们要找的元素；否则就顺序往后依次查找。如果遍历到数组中的空闲位置，还没有找到，就说明要查找的元素并没有在散列表中。
删除时, 不能直接将对应位置元素置空, 我们可以将删除的元素，特殊标记为 deleted。当线性探测查找的时候，遇到标记为 deleted 的空间，并不是停下来，而是继续往下探测。
二次探测（Quadratic probing）
所谓二次探测，跟线性探测很像，线性探测每次探测的步长是 1，那它探测的下标序列就是 hash(key)+0，hash(key)+1，hash(key)+2……而二次探测探测的步长就变成了原来的“二次方”，也就是说，它探测的下标序列就是 hash(key)+0，hash(key)+12，hash(key)+22……
双重散列（Double hashing）
所谓双重散列，意思就是不仅要使用一个散列函数。我们使用一组散列函数 hash1(key)，hash2(key)，hash3(key)……我们先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置。

不管采用哪种探测方法，当散列表中空闲位置不多的时候，散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率，一般情况下，我们会尽可能保证散列表中有一定比例的空闲槽位。我们用装载因子（load factor）来表示空位的多少(已经存入数据的位置的多少)。
装载因子的计算公式是：

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

装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。
【数据结构与算法--散列表】当数据量比较小、装载因子小的时候，适合采用开放寻址法。
这也是 Java 中的ThreadLocalMap使用开放寻址法解决散列冲突的原因。
2. 链表法（chaining）

文章图片
散列冲突--链表法.png
基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。
Java 中 LinkedHashMap 就采用了链表法解决冲突.
散列函数的设计散列函数的设计原则:

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

工业级散列表举例分析(HashMap) Java 中的 HashMap 这样一个工业级的散列表，来具体看下，这些技术是怎么应用的。
1. 初始大小 HashMap 默认的初始大小是 16，当然这个默认值是可以设置的，如果事先知道大概的数据量有多大，可以通过修改默认初始大小，减少动态扩容的次数，这样会大大提高 HashMap 的性能。
2. 装载因子和动态扩容最大装载因子默认是 0.75，当 HashMap 中元素个数超过 0.75*capacity（capacity 表示散列表的容量）的时候，就会启动扩容，每次扩容都会扩容为原来的两倍大小。
3. 散列冲突解决方法 HashMap 底层采用链表法来解决冲突。即使负载因子和散列函数设计得再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响 HashMap 的性能。
于是，在 JDK1.8 版本中，为了对 HashMap 做进一步优化，我们引入了红黑树。而当链表长度太长（默认超过 8）时，链表就转换为红黑树。我们可以利用红黑树快速增删改查的特点，提高 HashMap 的性能。当红黑树结点个数少于 8 个的时候，又会将红黑树转化为链表。因为在数据量较小的情况下，红黑树要维护平衡，比起链表来，性能上的优势并不明显。
4. 散列函数

# HashMap # 1. hash值的计算，源码如下： static final int hash(Object key) { int hash; return key == null ? 0 : (hash = key.hashCode()) ^ hash >>> 16; }# 2. 在插入或查找的时候，计算Key被映射到桶的位置： int index = hash(key) & (capacity - 1)

LRU 缓存淘汰算法

文章图片
散列表+双向列表实现LRU缓存淘汰.png
因为我们的散列表是通过链表法解决散列冲突的，所以每个结点会在两条链中。一个链是刚刚我们提到的双向链表，另一个链是散列表中的拉链。前驱和后继指针是为了将结点串在双向链表中，hnext 指针是为了将结点串在散列表的拉链中。

查找一个数据
散列表中查找数据的时间复杂度接近 O(1)，所以通过散列表，我们可以很快地在缓存中找到一个数据。
==> 找到散列表中的index, 然后在index对应的拉链中通过hnext指针找到数据.
当找到数据之后，我们还需要将它移动到双向链表的尾部。
==> LRU缓存调整访问记录, 改变双向链表的pre/next, 不改变拉链的hnext.
删除一个数据
我们需要找到数据所在的结点，然后将结点删除。借助散列表，我们可以在 O(1) 时间复杂度里找到要删除的结点。因为我们的链表是双向链表，双向链表可以通过前驱指针 O(1) 时间复杂度获取前驱结点，所以在双向链表中，删除结点只需要 O(1) 的时间复杂度。
添加一个数据
添加数据到缓存稍微有点麻烦，我们需要先看这个数据是否已经在缓存中。如果已经在其中，需要将其移动到双向链表的尾部；如果不在其中，还要看缓存有没有满。如果满了，则将双向链表头部的结点删除，然后再将数据放到链表的尾部；如果没有满，就直接将数据放到链表的尾部。

Java LinkedHashMap 按照访问时间排序的 LinkedHashMap 本身就是一个支持 LRU 缓存淘汰策略的缓存系统。实际上，它们两个的实现原理也是一模一样的。
LinkedHashMap 是通过双向链表和散列表这两种数据结构组合实现的。LinkedHashMap 中的“Linked”实际上是指的是双向链表，并非指用链表法解决散列冲突。
参考:
极客时间：《数据结构与算法》王争-- 散列表