跳表和散列表

一、跳表

复杂度：O(logn)；
跳表的更新：插入数据时，可以选择将这个数据插入到部分索引中，可以选择一个随机函数，产生随机数K，边将索引添加到第一到第K级索引中。

Redis为何选择跳表来实现有序集合？和红黑树有什么区别？
对于插入、删除、查找两者的复杂度是一样的，但是对于按照区间查找来说，红黑树效率没有跳表高。
对于区间查找，跳表可以做到O(logn)的复杂度来定位起点和终点，然后顺序遍历即可。
跳表实现相对简单、理解容易，也可以改变索引构建策略，平衡执行效率和内存消耗。

二、散列表

散列函数：MD5、SHA、CRC等哈希算法。
散列冲突

1. 开放寻址法：冲突后重新寻找一个位置，线性探测、二次探测、双重散列（再哈希）。使用装在因子表示剩余空位的多少；
2. 链表法：散列表（桶、槽）都会对应一条链表，散列值相同的元素放到后面的链表中；
   
   思考题
   1.假设我们有 10 万条 URL 访问日志，如何按照访问次数给 URL 排序？
   2.有两个字符串数组，每个数组大约有 10 万条字符串，如何快速找出两个数组中相同的字符串？
   思路：1.key为URL，value为访问次数，建立散列表。每次put之前先get，如果value存在则，value +=1；不存在则value = 1.
   2.以其中一个字符串数组的每个字符串为key，value为是否出现构建散列表。再遍历第二个字符串数组，以字符串为key在散列表中查找，如果value值为true，则说明存在相同的字符串，时间复杂度O(n)。

如何设计散列函数？
手机号码取后几位为散列值、Word单词拼写检查将每个字母ASCII码值进位相加，再根据散列表大小求余、取模。直接寻址法、平方取中、折叠法、随机数法。

装载因子过大怎么办？
动态扩容，动态扩容需要重新通过散列函数计算数据的存储位置，所以会导致在动态扩容的时候时间复杂度变为O(n),为了避免动态扩容时导致耗时过长，可以选择将扩容后的数据迁移操作分散开，每次插入只迁移部分数据，这样平均下来每次时间复杂度也是O(1)。

查找时可以在新旧两个散列表中都进行查找。

开放寻址法：要求装载因子上限不能太大，所以比较浪费内存。数据量较小，装载因子小的时候，适合开放寻址法；
链表法：内存利用率高。链表要存储指针，存储较小对象时，比较消耗内存，另外链表中的节点时零散的，对CPU的缓存不友好。可以对链表进行改造为其他高效的数据结构，如跳表、红黑树等。所以链表法比较适合存储大对象，可以支持更多的优化策略。

如何设计一个工业级的散列表？工业级的散列表有哪些特征？

• 支持快速查找、插入、删除等操作；
• 内存占用合理、不过多的浪费内存空间；
• 性能稳定，极端情况下退化不是很严重；

设计思路：

• 设计一个合理的哈希函数；
• 定义装载因子阈值，病支持动态扩容策略；
• 选择合适的散列冲突解决方法；

三、散列表和链表的组合使用

LRU缓存淘汰算法

• 链表是常规的双向链表有前驱指针、后继指针。另外新增hnext用于做散列表的桶节点。这样可以做到查找和删除、增加操作时间复杂度O(1)。

Redis有序集合
有序集合成员有两个重要属性，key（键值）和score（分值）。所以一般需要根据key查找数据，通过score进行范围查找。
用户ID和积分score，可以按照score从小到大构建一个跳表。这样按照score进行范围查找。另外使用key构建一个散列表，查找成员对象复杂度变成O(1)。

Java LinkedhashMap
LinkedHashMap 是通过双向链表和散列表这两种数据结构组合实现的。LinkedHashMap 中的“Linked”实际上是指的是双向链表，并非指用链表法解决散列冲突。

思考题
假设猎聘网有 10 万名猎头，每个猎头都可以通过做任务（比如发布职位）来积累积分，然后通过积分来下载简历。假设你是猎聘网的一名工程师，如何在内存中存储这 10 万个猎头 ID 和积分信息，让它能够支持这样几个操作：

• 根据猎头的 ID 快速查找、删除、更新这个猎头的积分信息；
• 查找积分在某个区间的猎头 ID 列表；
• 查找按照积分从小到大排名在第 x 位到第 y 位之间的猎头 ID 列表。

按照猎头ID组件散列表，这样按照ID快速查找、删除，另外按照积分进行排序组件跳表，这样可以进行区间和范围查找

四、哈希算法

1. 哈希值不能推导出原始数据；
2. 输入数据敏感，只改动一个Bit，得到哈希值也大不相同；
3. 散列冲突的概率小
4. 执行效率高，长字符串，也可以快速的计算出哈希值；

哈希函数的应用

1. 安全加密：MD5、DES、AES（鸽巢原理）；
2. 唯一标识：在海量图库中搜索一张图片。传统方法可以比较图片的二进制字符串。也可以取图片的唯一标识，如从图片的二进制码串头取100字节，从中间取100字节，从最后取100字节计算哈希值进行对比；
3. 数据校验：电驴BT电影下载，电影文件被分割多个文件块，下载完成之后将多个文件组合，但是网络传输不安全，下载的文件可能被修改过。所以需要下载后进行校验对比，可以将种子文件中的哈希值和下载后的各个文件一一哈希对比；
4. 散列函数

如何保存用户的密码？
如果只是将用户的密码进行加密后保存，黑客也可以使用字典攻击进行破解。因此需要维护一个常用密码的字典表，将字典中的密码进行哈希计算再哈希，针对字典攻击，可以引入盐（salt），和用户密码组合在一起，增加密码的复杂度。另外除了hash+salt，大多公司采用无论密码长度多少，计算字符串的hash函数时间都固定，进一步减少风险。

区块链的设计思路
区块链每个区块分为两部分：区块头和区块体，区块头保存自己区块体和上一个区块体的哈希值。所以只要任意一个区块被修改过，后面所有区块的哈希值就不对了。

五、哈希算法在分布式系统中的应用

1. 负载均衡：对客户端IP进行计算哈希值，取得哈希值与服务器链表大小进行取模运算，得到的值就是分到的服务器编号。这样可以不适用映射表。另外客户端的上下线也不用去维护映射表；
2. 数据分片：1T的日志，统计关键词搜索的次数，将数据进行分片（依次读出每个关键词，通过哈希函数计算哈希值，根据服务器个数n进行取模，分配到对应的机器编号上，这样保证每个关键词都会被分配到一个服务器上）。
3. 判断图片是否在图库中
4. 分布式存储：海量数据采用分布式缓存，如果进行服务器扩容那么所有的数据都要进行重新计算哈希值，重新搬移到对应的机器上，这样大量的数据失效，会发生雪崩效应 。这时候就要用到一致性哈希算法。