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 如何设计散列函数？
- 首先，散列函数的设计不能太复杂。过于复杂的散列函数，势必会消耗很多计算时间，也就间接的影响到散列表的性能。
- 其次，散列函数生成的值要尽可能随机并且均匀分布，这样才能避免或者最小化散列冲突，而且即便出现冲突，散列到每个槽里的数据也会比较平均，不会出现某个槽内数据特别多的情况
// 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使用开放寻址法解决散列冲突的原因。
方案一：线性探测
当我们往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。下图是一个示例：
方案二：二次探测
所谓二次探测，跟线性探测很像，线性探测每次探测的步长是 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) 会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。
复杂度分析：
-
当插入的时候，我们只需要通过散列函数计算出对应的散列槽位，插入到对应链表的中即可（借助tail指针），所以插入的时间复杂度是 O(1)。
-
当查找、删除一个元素时，我们同样通过散列函数计算出对应的槽，然后遍历链表查找或者删除。
实际上，这两种操作的时间复杂度都跟链表的长度 k 成正比，也就是 O(k)。对于散列比较均匀的散列函数来说，理论上讲，k=n/m，其中 n 表示散列中数据的个数，m 表示散列表 中“槽”的个数。
方案二：树化
实际上，我们对链表法稍加改造，可以实现一个更加高效的散列表。那就是，我们将链表法 中的链表改造为其他高效的动态数据结构，比如跳表、红黑树。这样，即便出现散列冲突， 极端情况下，所有的数据都散列到同一个桶内，那最终退化成的散列表的查找时间也只不过 是 O(logn)。这样也就有效避免了前面讲到的散列碰撞攻击。
3.3 动态扩容
针对散列表，当装载因子过大时，我们也可以进行动态扩容，重新申请一个更大的散列表， 将数据搬移到这个新散列表中。
假设每次扩容我们都申请一个原来散列表大小两倍的空间。 如果原来散列表的装载因子是 0.8，那经过扩容之后，新散列表的装载因子就下降为原来的 一半，变成了 0.4。
针对数组的扩容，数据搬移操作比较简单。但是，针对散列表的扩容，数据搬移操作要复杂很多。因为散列表的大小变了，数据的存储位置也变了，所以我们需要通过散列函数重新计 算每个数据的存储位置。
分批扩容思路
举一个极端的例子，如果散列表当前大小为 1GB，要想扩容为原来的两倍大小，那就需要对 1GB 的数据重新计算哈希值，并且从原来的散列表搬移到新的散列表，听起来就很耗时，是不是？
如果我们的业务代码直接服务于用户，尽管大部分情况下，插入一个数据的操作都很快，但是，极个别非常慢的插入操作，也会让用户崩溃。这个时候，“一次性”扩容的机制就不合适了。为了解决一次性扩容耗时过多的情况，我们可以将扩容操作穿插在插入操作的过程中，分批完成。
- 当装载因子触达阈值之后，我们只申请新空间，但并不将老的数据搬移到新散列表中。
- 当有新数据要插入时，我们将新数据插入新散列表中，并且从老的散列表中拿出一个数据放入到新散列表。
- 每次插入一个数据到散列表，我们都重复上面的过程。
- 经过多次插入操作之后，老的散列表中的数据就一点一点全部搬移到新散列表中了。这样没有了集中的一次性数据搬移，插入操作就都变得很快了。
而对于查询操作，为了兼容了新、老散列表中的数据，我们先从新散列表中查找，如果没有找到，再去老的散列表中查找。
通过这样均摊的方法，将一次性扩容的代价，均摊到多次插入操作中，就避免了一次性扩容耗时过多的情况。这种实现方式，任何情况下，插入一个数据的时间复杂度都是 O(1)。
4.散列表应用
4.1 HashMap、HashSet
这里就放两个源码分析的链接吧：
4.2 散列表+双向链表：LinkedListMap
散列表这种数据结构虽然支持非常高效的数据插入、删除、查找操作，但是散列表中的数据都是通过散列函数打乱之后无规律存储的。也就说，它无法支持按照某种顺序快速地遍历数据。
如果希望按照顺序遍历散列表中的数据，那我们需要将散列表中的数据拷贝到数组中， 然后排序，再遍历。因为散列表是动态数据结构，不停地有数据的插入、删除，所以每当我们希望按顺序遍历散列表中的数据时，都需要先排序，那效率势必会很低。
为了解决这个问题，我们将散列 表和链表（或者跳表）结合在一起使用。
LinkedListHashMap 采用的就是哈希表+双向链表，这里用双向链表是因为在删除操作时，不用再遍历一遍得到前序节点，可以在O(1)完成。具体可以参考源码 【Java容器源码】LinkedHashMap源码分析。
4.3 Word 文档中单词拼写检查功能
常用的英文单词有 20 万个左右，假设单词的平均长度是 10 个字母，平均一个单词占用 10 个字节的内存空间，那 20 万英文单词大约占 2MB 的存储空间，就算放大 10 倍也就是 20MB。对于现在的计算机来说，这个大小完全可以放在内存里面。所以我们可以用散列表来存储整个英文单词词典。
当用户输入某个英文单词时，我们拿用户输入的单词去散列表中查找。如果查到，则说明拼写正确；如果没有查到，则说明拼写可能有误，给予提示。借助散列表这种数据结构，我们 就可以轻松实现快速判断是否存在拼写错误。
还没有评论，来说两句吧...