散列思想

散列表==>Hash Table==>哈希表==>Hash 表散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表键(关键字）key===>散列函数（哈希函数）===> 散列值（Hash值）散列表利用 数组随机访问时间复杂度为O(1)的特性。通过散列函数的键值映射为下标读取的时候，通过散列函数转化键值为下标，从数组对应位置读取数据

散列函数

如何构造散列函数？三个要求

散列函数计算得到的散列值是一个非负整数如果key1 = key2,那hash(key1) == hash(key2)如果key1 != key2,那hash(key1) != hash(key2)

前两个要求容易达到，第三个要求几乎不可能，著名的hash算法MD5\SHA\CRC等哈希算法也无法避免散列冲突

散列冲突

散列冲突无法避免，怎么解决？

开放寻址法

核心思想 如果出现散列冲突，就重新探测一个空闲位置，将其插入，如何探测（线性探测），从当前位置依次往后查找，直到找的空闲位置 查找的过程中，通过散列函数映射key到下标，对比下标中的key是否和查找的key相同，不同就依次往下找，直到找到一个空闲位置，还没找到就说明该元素不在散列表中 删除操作，不能直接把要删除的元素设置为空，不然线性探测方法会失效，可以将删除的元素标记为deleted 存在问题当散列表中插入的数据越来越多时，散列冲突发生的可能性就会越来越大，空闲位置会越来越少，线性探测的时间就会越来越久。极端情况下，我们可能需要探测整个散列表，所以最坏情况下的时间复杂度为 O(n)。同理，在删除和查找时，也有可能会线性探测整张散列表，才能找到要查找或者删除的数据。 还有两种经典的探测方法二次探测（探测的步长变为原来的二次方），双重散列（使用多个散列函数，当地一个散列函数位置被占领，使用第二个散列函数）

无论哪种探测，都要保证装载因子足够大 散列表的装载因子=填入表中的元素个数/散列表的长度

链表法

链表法比较常用，简单。 插入时间复杂度O(1) 查找和删除时间复杂度O(k)，k为链表的长度，k= n/m n为元素的个数，m为槽的个数

思考

word怎么进行英文单词拼写检查？

假设我们有 10 万条 URL 访问日志，如何按照访问次数给 URL 排序？

有两个字符串数组，每个数组大约有 10 万条字符串，如何快速找出两个数组中相同的字符串？

设计散列表

散列表的查询效率不能笼统的说成是O(1)效率与散列函数、装载因子、散列冲出都有关系 散列表碰撞攻击==>Dos构造数据使散列冲突，导致散列表查询效率退化到O(n)散列表的设计不能太复杂，不然消耗过多计算时间散列函数生成的值要尽可能随机并且均匀分布装载因子过大如果内存空间不紧张，对执行效率要求很高，可以降低负载因子的阈值；相反，如果内存空间紧张，对执行效率要求又不高，可以增加负载因子的值，甚至可以大于 1。

解决哈希冲突的方法

开放寻址法

优点

散列表数据储存在数组中，可以有效利用cpu缓存加快查询速度。序列化实现简单当数据量比较小、装载因子小的时候，适合采用开放寻址法，这也是 Java 中的ThreadLocalMap使用开放寻址法解决散列冲突的原因

缺点

删除数据比较麻烦，需要特殊标记已经删除的数据冲突的代价更高，对比链表法，装载因子不能太高，因为一旦过高，效率损失太大浪费内存空间

链表法

优点

内存利用率高，链表可以需要的时候再创建，不需要像开放寻址法那样事先申请好。对大的装载因子的容忍度高，开放寻址装载因子不能大于等于1，链表法的装载因子变为10，查找效率也不会下降很多

缺点

链表法需要存储指针，对于较小对象储存非常消耗内存链表节点是零散分布在内存中，不连续，对cpu缓存是不友好的，这方面执行效率也会降低

改进

可以将链表改进为其他更高效的动态数据结构，例如 、跳表、红黑树、这样即使出现散列冲突，最差查找时间为O(logn)基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表

分析Java中的HashMap

初始大小

初始默认值大小为16默认值可以设置，预先知道数据规模，可以减少动态扩容，提升效率

装载因子和动态扩容

最大装载因子默认为0.75当装载因子超过0.75，就会动态扩容每次扩容为原来的2倍

散列冲突解决方法

HashMap 底层采用链表法来解决冲突即使负载因子和散列函数设计得再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响 HashMap 的性能引入红黑树，当链表长度超过（默认为8）时，链表转换为红黑树链表长度小于8时，转化为链表，因为红黑树要维护平衡，数据量较小时，优势不明显

散列函数

设计简单高效、分布均匀。 int hash(Object key) { int h = key.hashCode()； return (h ^ (h >>> 16)) & (capicity -1); //capicity表示散列表的大小 } // String类型的对象hashCode() public int hashCode() { int var1 = this.hash; if(var1 == 0 && this.value.length > 0) { char[] var2 = this.value; for(int var3 = 0; var3 < this.value.length; ++var3) { var1 = 31 * var1 + var2[var3]; } this.hash = var1; } return var1; }

何为一个工业级的散列表？工业级的散列表应该具有哪些特性？

结合已经学习过的散列知识，我觉得应该有这样几点要求：

支持快速地查询、插入、删除操作；内存占用合理，不能浪费过多的内存空间；性能稳定，极端情况下，散列表的性能也不会退化到无法接受的情况。

如何实现这样一个散列表呢？ 从这三个方面来考虑设计思路：

设计一个合适的散列函数；定义装载因子阈值，并且设计动态扩容策略；选择合适的散列冲突解决方法。

关于散列函数、装载因子、动态扩容策略，还有散列冲突的解决办法，我们前面都讲过了，具体如何选择，还要结合具体的业务场景、具体的业务数据来具体分析。不过只要我们朝这三个方向努力，就离设计出工业级的散列表不远了

通过散列表将LRU缓存淘汰算法从O(n)降低到O(1)

LRU算法

一个按照时间从大到小的有序排列的链表结构缓存大小有限，需要淘汰一个数据，就将链表头部节点删除当要缓存某个元素时，先在链表中查找，没有找到就插入末尾找到，就移动到末尾查找需要遍历，所以时间复杂度为O(n) 散列表优化单纯使用链表，添加、删除、查找都要经过查找的操作，时间复杂度O(n)散列表和链表结合，优化三个操作都为O(1)散列表+双向链表，多了一个hnext，是为了散列表冲突时，连接冲突节点查找通过散列表，时间复杂度为O(1)删除，通过散列表查找到删除掉，时间复杂度为O(1)添加，稍微复杂，先查找是否存在，存在的话，移动到链表尾部，时间复杂度为O(1)

Redis有序集合

在有序集合中，每个成员都有两个重要属性key ,score我们不仅通过score查找数据，还通过key查找数据如果我们仅仅按照分值将成员对象组织成跳表的结构，那按照键值来删除、查询成员对象就会很慢，解决方法与 LRU 缓存淘汰算法的解决方法类似。我们可以再按照键值构建一个散列表，这样按照 key 来删除、查找一个成员对象的时间复杂度就变成了 O(1)。同时，借助跳表结构，其他操作也非常高效。

Java LinkedHashMap

HashMap底层通过散列表这种数据结构实现LinkedHashMap也是通过散列表和链表组合在一起实现的。它不仅支持按照插入顺序遍历数据，还支持按照访问顺序来遍历数据LinkedHashMap 是通过双向链表和散列表这两种数据结构组合实现的。LinkedHashMap 中的“Linked”实际上是指的是双向链表，并非指用链表法解决散列冲突。

为什么散列表经常和链表一起使用

散列表这种数据结构虽然支持非常高效的数据插入、删除、查找操作是散列表中的数据都是通过散列函数打乱之后无规律存储的也就是散列表无法按照某种顺序快速地遍历数据如果需要按照顺序遍历，就需要先将数据拷贝到数组总，然后遍历，这样效率就非常低拷贝到数组中还会导致效率非常低解决这个问题，将散列表和链表（或者跳表）结合在一起使用

思考

几个散列表和链表结合的例子中，使用的都是双向链表，为什么?使用单向链表可以吗？ 在删除一个元素时，虽然能 O(1) 的找到目标结点，但是要删除该结点需要拿到前一个结点的指针，遍历到前一个结点复杂度会变为 O(N），所以用双链表实现比较合适。（但其实硬要操作的话，单链表也是可以实现 O(1) 时间复杂度删除结点的）。假设猎聘网有 10 万名猎头，每个猎头都可以通过做任务（比如发布职位）来积累积分，然后通过积分来下载简历。假设你是猎聘网的一名工程师，如何在内存中存储这 10 万个猎头 ID 和积分信息，让它能够支持这样几个操作： 根据猎头的 ID 快速查找、删除、更新这个猎头的积分信息； 查找积分在某个区间的猎头 ID 列表； 查找按照积分从小到大排名在第 x 位到第 y 位之间的猎头 ID 列表。 使用第一问，散列表，第二问和第三问使用跳表