散列表
概念
1.散列表来源于数组，它借助散列函数对数组这种数据结构进行扩展，利用的是数组支持按照下标随机访问元素的特性。
2.需要存储在散列表中的数据我们称为键，将键转化为数组下标的方法称为散列函数，散列函数的计算结果称为散列值。
3.将数据存储在散列值对应的数组下标位置。
散列函数
1.散列函数计算得到的散列值是一个非负整数。
2.若key1=key2，则hash(key1)=hash(key2)
3.若key≠key2，则hash(key1)≠hash(key2)
正是由于第3点要求，所以产生了几乎无法避免的散列冲突问题。
散列冲突
- 开放寻址法
①核心思想：如果出现散列冲突，就重新探测一个空闲位置，将其插入。
②实现：
线性探测法（Linear Probing）：冲突则依次向后查找空闲位置
二次探测（Quadratic probing）：线性探测每次探测的步长为1，即在数组中一个一个探测，而二次探测的步长变为原来的平方。
双重散列（Double hashing）：使用一组散列函数，直到找到空闲位置为止。
③用“装载因子”来表示空位多少，公式：散列表装载因子 = 填入表中的个数 / 散列表的长度。
装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。
- 链表法（常用）
插入时，通过散列函数定位槽位，添加到槽位链表末尾
查询更新时，通过散列函数定位槽位，再遍历链表比较key
删除时，定位槽位，遍历比较key，删除链表相应节点
思考题
1. 假设我们有 10 万条 URL 访问日志，如何按照访问次数给 URL 排序？
遍历 10 万条数据，以 URL 为 key，访问次数为 value，存入散列表，同时记录下访问次数的最大值 K，时间复杂度 O(N)。
如果 K 不是很大，可以使用桶排序，时间复杂度 O(N)。如果 K 非常大（比如大于 10 万），就使用快速排序，复杂度 O(NlogN)。
2. 有两个字符串数组，每个数组大约有 10 万条字符串，如何快速找出两个数组中相同的字符串？
以第一个字符串数组构建散列表，key 为字符串，value 为出现次数。再遍历第二个字符串数组，以字符串为 key 在散列表中查找，如果 value 大于零，说明存在相同字符串。时间复杂度 O(N)。
如何设计散列函数?
- 不能太复杂：太复杂影响性能
- 散列函数生成的值要尽可能随机并且均匀分布：最小化散列冲突
- 求余、取模、直接寻址法、平方取中法、折叠法、随机数法
装载因子过大了怎么办？
- 动态扩容
数据搬移需要重新计算位置
- 避免低效扩容：
为了解决一次性扩容耗时过多的情况，我们可以将扩容操作穿插在插入操作的过程中，分批完成。
当装载因子触达阈值之后，我们只申请新空间，但并不将老的数据搬移到新散列表中。
当有新数据要插入时，我们将新数据插入新散列表中，并且从老的散列表中拿出一个数据放入到新散列表。每次插入一个数据到散列表，我们都重复上面的过程。
经过多次插入操作之后，老的散列表中的数据就一点一点全部搬移到新散列表中了。这样没有了集中的一次性数据搬移，插入操作就都变得很快了。
如何选择冲突解决方法
- 当数据量比较小、装载因子小的时候，适合采用开放寻址法。这也是 Java 中的ThreadLocalMap使用开放寻址法解决散列冲突的原因。
- 基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表
工业级散列表--Java 中的 HashMap分析
- 初始大小：16
- 装载因子和动态扩容：最大装载因子默认是 0.75，当 HashMap 中元素个数超过 0.75*capacity（capacity 表示散列表的容量）的时候，就会启动扩容，每次扩容都会扩容为原来的两倍大小。
- 散列冲突解决方法：HashMap 底层采用链表法来解决冲突；JDK1.8 版本中，对 HashMap 做进一步优化，引入了红黑树。而当链表长度太长（默认超过 8）时，链表就转换为红黑树。我们可以利用红黑树快速增删改查的特点，提高 HashMap 的性能。当红黑树结点个数少于 8 个的时候，又会将红黑树转化为链表。因为在数据量较小的情况下，红黑树要维护平衡，比起链表来，性能上的优势并不明显。
- 散列函数：
int hash(Object key) {
int h = key.hashCode()；
return (h ^ (h >>> 16)) & (capicity -1); //capicity表示散列表的大小
}
链表和散列表的结合使用
- LRU（Least Recently Used）缓存淘汰算法
操作
①往缓存中添加一个数据；
②从缓存中删除一个数据；
③在缓存中查找一个数据；
④总结：上面3个都涉及到查找。
只使用链表实现
①需要维护一个按照访问时间从大到小的有序排列的链表结构。
②缓冲空间有限，当空间不足需要淘汰一个数据时直接删除链表头部的节点。
③当要缓存某个数据时，先在链表中查找这个数据。若未找到，则直接将数据放到链表的尾部。若找到，就把它移动到链表尾部。
④前面说了，LRU缓存的3个主要操作都涉及到查找，若单纯由链表实现，查找的时间复杂度很高为O(n)。若将链表和散列表结合使用，查找的时间复杂度会降低到O(1)。
链表和散列表结合使用实现
①使用双向链表存储数据，链表中每个节点存储数据（data）、前驱指针（prev）、后继指针（next）和hnext指针（解决散列冲突的链表指针）。
②散列表通过链表法解决散列冲突，所以每个节点都会在两条链中。一条链是双向链表，另一条链是散列表中的拉链。前驱和后继指针是为了将节点串在双向链表中，hnext指针是为了将节点串在散列表的拉链中。
③LRU缓存淘汰算法的3个主要操作如何做到时间复杂度为O(1)呢？
首先，我们明确一点就是链表本身插入和删除一个节点的时间复杂度为O(1)，因为只需更改几个指针指向即可。
接着，来分析查找操作的时间复杂度。当要查找一个数据时，通过散列表可实现在O(1)时间复杂度找到该数据，再加上前面说的插入或删除的时间复杂度是O(1)，所以我们总操作的时间复杂度就是O(1)。
- Java LinkedHashMap
和LRU缓存淘汰策略实现一模一样。支持按照插入顺序遍历数据，也支持按照访问顺序遍历数据。
- Redis有序集合
有序集合的操作有哪些？
举个例子，比如用户积分排行榜有这样一个功能：可以通过用户ID来查找积分信息，也可以通过积分区间来查找用户ID。这里用户ID就是key，积分就是score。所以，有序集合的操作如下：
①添加一个对象；
②根据键值删除一个对象；
③根据键值查找一个成员对象；
④根据分值区间查找数据，比如查找积分在[100.356]之间的成员对象；
⑤按照分值从小到大排序成员变量。
这时可以按照分值将成员对象组织成跳表结构，其中按照键值来删除、查询成员对象就会很慢，按照键值构建一个散列表，这两个操作就会变成O(1)。