作者：陌北有棵树，Java人，架构师社区合伙人！
作为程序员，我们似乎经常忽略数据结构和算法的重要性，认为平时只是写写业务代码，这些知识根本用不到，这也是我之前犯的错误，现在想来，不正是因为有这样的思维，才让我们只能做一个CRUD程序员么。
闲言少叙，回到本文的主题，散列表是一种十分常见的数据结构，我们日常更喜欢叫它哈希表，如果用一句话概括，散列表利用数组下标查找效率是O(1)的特性，将键值利用散列函数转换为数组下标，所以这个过程中就会有如下的问题：
通过什么方式让键值映射为数组下标？涉及到散列函数的设计。
如果不同的键值，映射到同一个数组下标怎么办？涉及到冲突解决。
数据量过大怎么处理？涉及到动态扩容。
文章后面也会按照这几个问题，对散列表这种数据结构进行分析，最后还会列举几个典型的散列表的应用。
【一】散列函数
散列函数就是将键转化为数组索引的实现过程。那需要我们来想一下，什么样的散列函数是我们喜欢的？应该有两个特点：易于计算、能够均匀分布所有键。
我们继续思考，键值类型不是唯一的，是不是所有的类型都能复用同样的散列函数呢，答案是否定的。每种类型都需要一个与之对应的散列函数才比较合理。
正是出于这个目的，Java在Object类定义了hashcode()方法，并且为常用的数据类型重写了hashcode()方法。提到Java，就不得不说到有一点是需要注意，当你需要为自定义的数据类型定义散列函数，需要重写的不仅仅只有hashcode()方法，还有equals()方法。
如果你来设计一个散列函数，需要考虑什么？
散列函数直接决定了散列表产生冲突的概率，也就是直接决定了散列表的性能，常见的散列函数设计方法：除留余数法、直接寻址、平方取中、折叠法、随机数法等。在《算法》一书中，总结了一个优秀的散列函数应该具备的三个特性。
一致性 - 相同的键必然产生相同的散列值。
高效性 - 不能过于复杂，避免消耗过的计算时间，如果计算散列值的过程很耗时，就可以考虑将每个键的散列值缓存起来，也就是在每个键中使用一个hash变量保存其hashCode()返回值。
均匀性 - 能够将键平均分散。
【二】碰撞处理
几乎无法找到一个没有冲突的散列函数，所以如何解决冲突，就是我们接下来要考虑的事情了。也就是处理多个键值相同的情况，有下面两种方式可以解决散列冲突。两种方法都有其应用的场景，例如Java中HashMap和LinkedHashMap采用拉链法，而ThreadLocalMap采用开放寻址法。
1.拉链法
拉链法就是将发生冲突的元素存储在链表中，我们假定散列表的大小为M，于是我们将大小为M的数组中的每个元素指向一条链表。下图是一个简单的模型，画的很丑不要介意~~
在使用拉链法解决散列冲突时，我们的主要目标是选择合适大小的数组M，不会因为空链表浪费大量内存，也不会因为链表过长影响查找的性能。
2.线性探测法
线性探测法属于开放寻址法中的一种，概括开放寻址法的思想，就是如果出现了散列冲突，就重新探测一个空闲位置，将其插入。那么如何重新探测这个空闲位置，也有很多实现，除了下面提到的线性探测，还有二次探测和双重散列。
线性探测的核心思想在于，将冲突的元素放在散列表其他空余的位置，在下图中，我们希望将{key1,value1}这个键值对插入散列表，蓝色代表已经存储了元素，绿色代表空闲位置通过hash(key1) = 5，但是不是空闲位置，于是向下寻找，一直到最后也没有空闲位置，于是从散列表的头位置开始寻找，3位置空闲，于是将元素插入。
3.两种方法的比较
对于线性探测法，也可以进一步说是开放寻址法，优点是利用数组存储，查询速度较快，同时便于序列化。缺点是对散列表中空闲位置的要求较高，如果空闲位置不多，冲突的概率会大大增加。
对于拉链法，优点是内存利用率高，同时对于表中空闲位置的要求没那么高，只要保证散列函数均匀，最差的情况无非是链表变长，同时还可以应用跳表，红黑树等数据结构对链表进行优化。
【三】动态扩容
在说明动态扩容之前，我们要先明确装载因子的概念，装载因子定义的是散列表中空位的多少。
装载因子的计算公式：
装载因子 = 散列表中元素个数 / 散列表的长度
装载因子越大，说明散列表中空闲位置越少，也就说明产生碰撞的概率越大，同时进一步说明，散列表的性能在越来越差，所以从这个角度来看，装载因子在某个程度上衡量了散列表的性能指标。
当装载因子达到一定程度后，散列冲突会让我们觉得无法接受，这时，我们不得不对散列表的数据进行动态扩容。例如扩容2倍的空间，经过扩容后，装载因子会减小至原来的一半。
但散列表的扩容，并不像扩容一个动态数组那么简单，需要对散列表中原有元素重新计算hash值，这时可能会产生的情况是，会使得插入元素的时间复杂度降为O(n)，在这里，我们可以考虑不要一次性将所有元素都进行插入，每当有新数据插入时，分次批量的将数据从原有散列表搬入新散列表，这样就避免了个别插入操作性能下降的问题。
【四】典型散列表的应用
1. LRU算法
我们知道，常规的LRU算法是基于双向链表实现,添加，查找和插入操作的时间复杂度都是O(n)，那么我们如何利用散列表将时间复杂度降为O(1)呢?
其实不难发现，之所以三种操作的时间复杂度都是O(n)，是因为都涉及到查找操作，而链表的查找操作时间复杂度就是O(n)，于是我们想到引入了散列表，将查找的时间复杂度降为O(1)。
这种散列表+链表的组合结构，还是比较常用的优化方式，后面两种应用也是采用这种模型。
2.Redis有序集合
Redis有序集合通过跳表实现，那么会遇到与LRU类似的问题，根据键值的查询，插入删除很慢，于是采用类似的策略，根据键值构造散列表，查找一个成员对象的时间复杂度变成O(1)。
3.LinkedHashMap
LinkedHashMap中同样用到了散列表和双向链表这两种数据结构，这就不难解释，为什么可以通过LinkedHashMap，可以直接实现按照时间排序的LRU缓存模型了。
参考：《算法（第四版）》《算法图解》
长按订阅更多精彩▼
如有收获，点个在看，诚挚感谢
