《数据结构与算法》-数据结构篇
[TOC]
《数据结构与算法》-数据结构篇
总览-数据结构
- 讲复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗
- 讲复杂度分析（下）：浅析最好、最坏、平均、均摊时间复杂度
- 讲数组：为什么很多编程语言中数组都从0开始编号
- 讲链表（上）：如何实现LRU缓存淘汰算法
- 讲链表（下）：如何轻松写出正确的链表代码
- 讲栈：如何实现浏览器的前进和后退功能
- 讲队列：队列在线程池等有限资源池中的应用
- 讲递归：如何用三行代码找到“最终推荐人”
- 讲排序（上）：为什么插入排序比冒泡排序更受欢迎
- 讲排序（下）：如何用快排思想在O(n)内查找第K大元素
- 讲线性排序：如何根据年龄给100万用户数据排序
- 讲排序优化：如何实现一个通用的、高性能的排序函数
- 讲二分查找（上）：如何用最省内存的方式实现快速查找功能
- 讲二分查找（下）：如何快速定位IP对应的省份地址
- 讲跳表：为什么Redis一定要用跳表来实现有序集合
- 讲散列表（上）：Word文档中的单词拼写检查功能是如何实现的
- 讲散列表（中）：如何打造一个工业级水平的散列表
- 讲散列表（下）：为什么散列表和链表经常会一起使用
- 讲哈希算法（上）：如何防止数据库中的用户信息被脱库
- 讲哈希算法（下）：哈希算法在分布式系统中有哪些应用
- 讲二叉树基础（上）：什么样的二叉树适合用数组来存储
- 讲二叉树基础（下）：有了如此高效的散列表，为什么还需要二叉树
- 讲红黑树（上）：为什么工程中都用红黑树这种二叉树
- 讲红黑树（下）：掌握这些技巧，你也可以实现一个红黑树
- 讲递归树：如何借助树来求解递归算法的时间复杂度
- 讲堆和堆排序：为什么说堆排序没有快速排序快
- 讲堆的应用：如何快速获取到Top10最热门的搜索关键词
- 讲图的表示：如何存储微博、微信等社交网络中的好友关系
- 讲深度和广度优先搜索：如何找出社交网络中的三度好友关系
- 讲字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹配
- 讲字符串匹配基础（中）：如何实现文本编辑器中的查找功能
- 讲字符串匹配基础（下）：如何借助BM算法轻松理解KMP算法
- 讲Trie树：如何实现搜索引擎的搜索关键词提示功能
- 讲AC自动机：如何用多模式串匹配实现敏感词过滤功能
- 讲算法实战（一）：剖析Redis常用数据类型对应的数据结构
- 讲算法实战（二）：剖析搜索引擎背后的经典数据结构和算法
- 讲算法实战（三）：剖析高性能队列Disruptor背后的数据结构和算法
- 讲算法实战（四）：剖析微服务接口鉴权限流背后的数据结构和算法
- 讲算法实战（五）：如何用学过的数据结构和算法实现一个短网址系统
数学科普
科普内存存储数据大小
- 常用的英文单词有20万个左右，假设单词的平均⻓度是10个字母，平均一个单词占用10个字节的内存空间，那20万英文单词 大约占2MB的存储空间，就算放大10倍也就是20MB。
- 如何在1000万个整数中快速查找某个整数?
- 这个问题并不难。我们的内存限制是100MB，每个数据大小是8字节，最简单的办法就是将数据存储在数组中，内存占用差不 多是80MB，符合内存的限制。借助今天讲的内容，我们可以先对这1000万数据从小到大排序，然后再利用二分查找算法，就 可以快速地查找想要的数据了。
- 规律：抽象数字转字节，字节*数量，再转mb。其中100w字节（Bytes）=1MB
- 也就是1000w整数，占用内存为80MB
- 因为logn是一个非常“恐怖”的数量级，即便n非常非常大，对应的logn也很小。比如n等于2的32次方，这个数很大了吧?大约 是42亿。也就是说，如果我们在42亿个数据中用二分查找一个数据，最多需要比较32次。
取余和求模
求余操作(%)：
1、被除数小于除数，那么余数就是被除数。
2、余数和取模计算公式：
c=a/b;
d=a-c*b3、余数的取值范围[0,除数-1]
时间复杂度科普
素数
(也说质数) 数学上指在大于1的整数中只能被1和它本身整除的数。如2、3、5、7、11、43、109
题目汇总
链表：
基于数组（链表）实现LRU缓存淘汰算法
- 单链表反转
- 链表中环的检测
- 两个有序的链表合并
- 删除链表倒数第n个结点
- 求链表的中间结点
栈：
数组实现的顺序栈、链表实现的栈
- 函数调用栈
- 表达式求值（双栈）
- 括号匹配
- 浏览器前进和后退
栈最小元素的 min 函数（双栈）
队列：
数组实现的顺序队列，链表实现的队列
- 循环队列
- 阻塞队列（Lock+Condition）
- 并发队列（循环队列+cas）
递归
有n个台阶，每次你可以跨1个台阶或者2个台阶，请问走这n个台阶有多少种走法?
n台阶使用散列函数来优化
哨兵
- 哨兵代码：归并排序、有序链表合并
快速排序
- O(n)时间复杂度内求无序数组中的第K大元素。
线性排序
- 如何根据年龄给100万用户数据排序
- 我们有10GB的订单数据，我们希望按订单金额(假设金额都是正整数)进行排序，但是我们的内存有限，只有几百 MB
- 如何实现100w考生的成绩和排名
- 假设我们有10万个手机号码，希望将这10万个手机号码从小到大排序，
讲数组：为什么很多编程语言中数组都从0开始编号
为什么数组要从0开始编号，而不是从1开始呢？
数组：如何实现随机访问
什么是数组？数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
线性表：数据排成像一条线一样的结构。每个线性表上的数据最对只有前和后两个方向。包括：数组、链表、队列、栈等。
连续的内存空间和相同类型的数据：这两大特性，让数组实现了随机访问。而为了维护这种结构插入和删除操作，就需要做大量的数据搬迁工作。
非线性表：数据之间并不是简单的前后关系，包括：二叉树、堆、图等。
- 计算机访问内存中数组公式：a[i]_address = base_address + i * data_type_size
数组：如何解决数组”插入”和”删除”低效
- 插入操作：在第K个位置插入数据
- 如果数组是没有任何规律的：将第K位置的数据搬迁到数组的末尾，然后再把要插入第K位置的数据插入.
- 如果数组是有序的：就根据K的位置，搬迁数据。
- 删除操作
- 多次删除操作集中在一起执行，删除的效率是不是会提高很多呢?
- 标记这个元素已经被删除。类比：JVM标记清除垃圾回收算法。
数据总览
- 警惕数组的访问越界问题：Java本身帮我们做了越界检查。
ArrayIndexOutOfBoundsException - 容器能否完全替代数组？（换句话：容器（ArrayList）和数组的区别）
- 容器可以将很多数组操作的细节封装起来 ，支持动态扩容(1.5倍 )。
- 但是扩容操作涉及内存申请和数据搬迁，比较耗时。建议在创建ArrayList的时候事先指定数据大小。
- Java ArrayList无法存储基本类型，比如int、long，需要封装为Integer、Long类，而Autoboxing、Unboxing则有一定的性能 消耗，所以如果特别关注性能，或者希望使用基本类型，就可以选用数组。
- 如果数据大小事先已知，并且对数据的操作非常简单，用不到ArrayList提供的大部分方法，也可以直接使用数组。
- 业务开发，直接使用容器就足够了 。非常底层的开发 ，数组是首选。
- 容器可以将很多数组操作的细节封装起来 ，支持动态扩容(1.5倍 )。
问题解答
- 如何下标是0开始：
- 计算公式：a[i]_address = base_address + i * data_type_size
- 如果下标是1开始：
- 计算公式：a[i]_address = base_address + (i-1) * data_type_size
- 从1开始的话，每次访问数组就多了一次减法运算。但是更多原因是历史的原因，因为C语言设计是0开始计数数组下标的.
讲链表（上）：如何实现LRU缓存淘汰算法
经典的链表应用场景：LRU缓存淘汰算法。
缓存淘汰策略：常见的有三种。
- 先进先出策略：FIFO(First In,First Out)
- 最少使用策略：LFU（Least Frequently Used）
- 最近最少使用策略：LRU（Least Recently Used）
链表
链表：零散的内存块串联起来的。包括：单链表、双向链表和循环链表。
循环链表：优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时，就特别适合采用循环链表。
双向链表：开发中，实际运用的更多。比单链表的优点就是知道前驱节点(用空间换时间)。
LinkedHashMap
双向循环链表 ：上面二者结合
- 空间换时间、时间换空间等设计思想。
数组、容器、链表的区别
- 数组简单易用，在实现上使用的是连续的内存空间，可以借助CPU的缓存机制，预读数组中的数据，所以访问效率更高。而 链表在内存中并不是连续存储，所以对CPU缓存不友好，没办法有效预读。
- 数组的缺点是大小固定，一经声明就要占用整块连续内存空间。 链表本身没有大小的限制，天然地支持动态扩容，我觉得这也是它与数组最大的区 别。
- 数组太大，有可能会内存不足（out of memory）
- 数组太小，扩容和搬迁数据非常耗时。
- 如果你的代码对内存的使用非常苛刻，那数组就更适合你。因为链表中的每个结点都需要消耗额外的存储空间去存 储一份指向下一个结点的指针，所以内存消耗会翻倍。
问题解答
- LRU缓存淘汰算法（LRU和LFU的区别）
- LRU按照访问时间排序，LFU按照访问频次排序
总结
链表。它跟数组一样，也是非常基础、非常常用的数据结构。不过链表要比数组 稍微复杂，从普通的单链表衍生出来好几种链表结构，比如双向链表、循环链表、双向循环链表。
和数组相比，链表更适合插入、删除操作频繁的场景，查询的时间复杂度较高。不过，在具体软件开发中，要对数组和链表的 各种性能进行对比，综合来选择使用两者中的哪一个。
讲链表（下）：如何轻松写出正确的链表代码
- 技巧一：理解指针和引用的含义
- 在java中指针和引用都是存储所指对象的内存地址。
- 将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向 了这个变量，通过指针就能找到这个变量。
- 技巧二：警惕指针丢失和内存泄漏
- 插入结点时，一定要注意操作的顺序
- 技巧三:利用哨兵简化实现难度
- 技巧四:重点留意边界条件处理
- 如果链表为空时，代码是否能正常工作?
- 如果链表只包含一个结点时，代码是否能正常工作?
- 如果链表只包含两个结点时，代码是否能正常工作?
- 代码逻辑在处理头结点和尾结点的时候，是否能正常工作?
- 技巧五:举例画图，辅助思考
- 举例法和画图法。
- 技巧六:多写多练，没有捷径
- 单链表反转
- 链表中环的检测
- 两个有序的链表合并
- 删除链表倒数第n个结点
- 求链表的中间结点
技巧三:利用哨兵简化实现难度
- 如果我们在结点p后面插入一个新的结点
new_node->next = p->next; |
- 当我们要向一个空链表中插入第一个结点 ，特殊处理，其中head表 示链表的头结点 .
if (head == null) { |
- 如果要删除结点p的后继结点
p->next = p->next->next; |
- 要删除链表中的最后一个结点 ，特殊处理
if (head->next == null) { |
针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行 特殊处理。
- 带头链表：我们引入哨兵结点，在任何时候，不管链表是不是空，head指针都会一直指向这个哨兵结点。我们也把这种有哨兵结点的链表。相反，没有哨兵结点的链表就叫作不带头链表。
讲栈：如何实现浏览器的前进和后退功能
理解栈：后进者先出，先进者后出，这就是典型的栈结构。类比：碟盘子。
- 栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。
- 当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选“栈”这种数据结构。
实现栈：
- 用数组实现的栈，我们叫作顺序栈 ，用链表实现的栈，我们叫作链式 栈。
- 空间复杂度和时间复杂度都是O(1)
支持动态扩容的顺序栈 ：
- 类比数组的动态扩容，也是申请一个更大的栈然后搬迁数据。
栈的应用：
- 函数调用栈
- 表达式求值（双栈）
- 括号匹配
- 浏览器前进和后退（双栈）
讲队列：队列在线程池等有限资源池中的应用
理解队列：先进者先出，这就是典型的队列。类比：排队购票。
- 操作受限的线性表数据结构。 支持在队尾插入元素，在队头删除元素
实现队列：
- 用数组实现的队列叫作顺序队列（有界队列），用链表实现的队列叫作链式队列（无界队列）。
循环队列
- 解决了tail==n数据搬迁性能问题。
- 循环队列的实现：确定好队空和队满的判定条件
- 数组实现的非循环队列
- 队列满：tail==n
- 队列空：head==tail
- 循环队列
- 队列满：**(tail+1)%n=head**
- 队列空：head==tail
- 数组实现的非循环队列
阻塞队列和并发队列
阻塞队列：当队列为空的时候，出队会被阻塞。当队列满的时候，入队会被阻塞。
- 典型的生产者-消费者模型。线程池的本质。
并发队列：线程安全的队列。基于数组的循环队列，利用CAS原子操作 。
讲递归：如何用三行代码找到“最终推荐人”
如何理解递归
学习算法和数据结构比较难理解的两个知识点：动态规划和递归。
非常标准的递归求解问题的分解过程，去的过程叫“递”，回来的过程叫“归”。基本上，所有的递归问题都可以用递 推公式来表示。
//场景：自己坐在第几排
//递推公式：f(n)=f(n-1)+1 其中，f(1)=1
//代码实现
public f(n){
if(n==1){
return 1;
}
return f(n-1)+1;
}递归需要满足的三个条件
- 一个问题的解可以分解为几个子问题的解
- 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
- 存在递归终止条件
如何编写递归代码
- 写出递推公式，找到终止条件.
求解n个台阶的走法
/**
* 递归求解
* <p>
* 当第一步走了1格，或者第一步走了2格
* 递归公式：f(n)=f(n-1)+f(n-2)
* 终止条件：f(1)=1,f(2)=2
*
* @param n
* @return
*/
public int recursive(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
return recursive(n - 1) + recursive(n - 2);
}写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条 件，最后将递推公式和终止条件翻译成代码。
说得很好地方，讲了那么久自己递归代码为什么理解不出来的原因
计算机擅⻓做重复的事情，所以递归正和它的胃口。而我们人脑更喜欢平铺直叙的思维方式。当我们看到递归时，我们总想把 递归平铺展开，脑子里就会循环，一层一层往下调，然后再一层一层返回，试图想搞清楚计算机每一步都是怎么执行的，这样就很容易被绕进去。
对于递归代码，这种试图想清楚整个递和归过程的做法，实际上是进入了一个思维误区。很多时候，我们理解起来比较吃力， 主要原因就是自己给自己制造了这种理解障碍。那正确的思维方式应该是怎样的呢?
如果一个问题A可以分解为若干子问题B、C、D，你可以假设子问题B、C、D已经解决，在此基础上思考如何解决问题A。而 且，你只需要思考问题A与子问题B、C、D两层之间的关系即可，不需要一层一层往下思考子问题与子子问题，子子问题与子 子子问题之间的关系。屏蔽掉递归细节，这样子理解起来就简单多了。
递归代码要警惕堆栈溢出
- 递归最大深度比较小的时候，可以在代码定义一个全局变量，表示递归的深度。
递归代码要警惕重复计算
- 用散列表等数据结构来保存
- todo:n台阶问题优化
怎么将递归代码改写为非递归代码
递归代码优点和缺点
- 在时间效率上，递归代码里多了很多函数调用，当这些函数调用的数量较大时，就会积聚成一个可观的时间成本
- 在空间复杂 度上，因为递归调用一次就会在内存栈中保存一次现场数据
具体栗子：电影第几排问题
/**
* 把递推公式：f(x)=f(x-1)+1、终止条件f(1)=1
* <p>
* 修改为非递归的代码
* <p>
* 场景：我在电影第几排修改为非递归
*
* @param n
*/
public int f(int n) {
int ret = 1;
for (int i = 2; i < n; i++) {
ret += 1;
}
return ret;
}是所有的递归代码都可以改为这种迭代循环的非递归写法 。
问题解答
long findRootReferrerId(long actorId) { |
- 但是不能在线上使用，原因：递归深度太深（堆栈溢出）、a-b-c-a环检测问题。
- 使用限制递归深度解决。
总结
递归是一种非常高效、简洁的编码技巧。只要是满足“三个条件”的问题就可以通过递归代码来解决。
不过递归代码也比较难写、难理解。编写递归代码的关键就是不要把自己绕进去，正确姿势是写出递推公式，找出终止条件， 然后再翻译成递归代码。
递归代码虽然简洁高效，但是，递归代码也有很多弊端。比如，堆栈溢出、重复计算、函数调用耗时多、空间复杂度高等，所 以，在编写递归代码的时候，一定要控制好这些副作用。
讲排序（上）：为什么插入排序比冒泡排序更受欢迎
排序算法太多了，我们只讲最经典、最常用的：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、基数排序、桶排序。
根据时间复杂度分为三类：
如何分析一个”排序算法”？
最好情况、最坏情况、平均情况时间复杂度
- 正序和倒序：有序度不同，对于一些排序算法时间复杂度影响比较大。
时间复杂度的系数、常数、低阶
- 时间复杂度反应的是数据规模n很大的时候的一个增⻓趋势，所以它表示的时候会忽略系数、常数、低阶 .
- 但是实 际的软件开发中，我们排序的可能是10个、100个、1000个这样规模很小的数据，所以，在对同一阶时间复杂度的排序算法性 能对比的时候，我们就要把系数、常数、低阶也考虑进来。
比较次数和交换（或移动）次数
排序算法的内存消耗（空间复杂度）
- 原地排序：空间复杂度O(1)
排序算法的稳定性
稳定性。这个概 念是说，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。
稳定性的实际运用
比如说，我们现在要给电商交易系统中的“订单”排序。订单有两个属性，一个是下单时间，另一个是订单金额。如果我们现在 有10万条订单数据，我们希望按照金额从小到大对订单数据排序。对于金额相同的订单，我们希望按照下单时间从早到晚有 序。对于这样一个排序需求，我们怎么来做呢?
方案1（欠佳）：我们先按照金额对订单数据进行排序，然后，再遍历排序之后的订单数据，对于每个金额相同的小区间再 按照下单时间排序。这种排序思路理解起来不难，但是实现起来会很复杂。
方案2（最佳）：我们先按照下单时间给订单排序，注意是按照下单时 间，不是金额。排序完成之后，我们用稳定排序算法，按照订单金额重新排序。两遍排序之后，我们得到的订单数据就是按照 金额从小到大排序，金额相同的订单按照下单时间从早到晚排序的。
冒泡排序
原理：冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就 让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作。
优化：刚讲的冒泡过程还可以优化。当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的 冒泡操作。
/**
* 冒泡排序
*
* @param a
*/
public void bubbleSort(int[] a) {
int n = a.length - 1;
for (int i = 0; i < n; i++) {
//优化：如果没有比较次数了，直接break
boolean nochange = true;
for (int j = 0; j < n - i; j++) {
//这里决定了稳定性
if (a[j] > a[j + 1]) {
int tem = a[j + 1];
a[j + 1] = a[j];
a[j] = tem;
nochange = false;
}
}
if (nochange) {
break;
}
}
}
三连问：xx排序算法是原地排序算法吗？xx排序算法是稳定的排序算法吗？xx排序算法的时间复杂度？
- 冒泡排序是原地排序算法、是稳定的。正序最好复杂度（O(n)）倒序最坏（O(n²)）平均（O(n²)）
插入排序
原理：我们将数组中的数据分为两个区间，已排序区间和未排序区间 。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一 直有序。
实现：
/**
* 插入排序
*
* @param sorts
* @return
*/
public void insertionSort(int[] sorts) {
if (sorts.length <= 0) {
return;
}
for (int i = 1; i < sorts.length; i++) {
int val = sorts[i];
for (int j = i - 1; j >= 0; j--) {
//排序好了的最后一位值
int sortLast = sorts[j];
//决定了稳定性
if (val > sortLast) {
break;
} else {
//交换值
int s1 = sorts[j + 1];
int temp = s1;
sorts[j + 1] = sorts[j];
sorts[j] = temp;
}
}
}
}
三连问：原地排序、稳定的，正序最好情况（O(n)）、倒序最坏情况（O(n²)）、平均（O(n²)）
选择排序
原理：分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的 元素，将其放到已排序区间的末尾。
实现：
/**
* 选择排序
*
* @param a
*/
public void selectionSort(int[] a) {
int n = a.length - 1;
for (int i = 0; i < n; i++) {
int smallIndex = i;
for (int j = i + 1; j < n; j++) {
if (a[smallIndex] > a[j + 1]) {
smallIndex = j + 1;
}
}
//swap
int temp = a[i];
a[i] = a[smallIndex];
a[smallIndex] = temp;
}
}
三连问：原地排序算法、不稳定。最好情况时间复杂度、最坏情况和平均情况时间复杂度 都为O(n2)
问题解答
为什么插入 排序要比冒泡排序更受欢迎呢?
- 冒泡排序：元素交换思路。3次赋值操作
- 插入排序：元素移动思路。1次赋值操作
- 虽然冒泡排序和插入排序在时间复杂度上是一样的，都是O(n2)，但是如果我们希望把性能优化做到极致，那肯定首选 插入排序。
总结
对于小规模数据的排序，用起来非常高效。但是在大规模数据排序的时候， 这个时间复杂度还是稍微有点高 。
讲排序（下）：如何用快排思想在O(n)内查找第K大元素
冒泡排序、插入排序、选择排序的时间复杂度都是O(n²)，比较高。适合小规模数据排序。
接下来要讲的是时间复杂度为O(nlogn)的排序算法：归并排序和快速排序（分治思想）。适合达规模的数据排序，比前面三者更常用。
归并排序
原理：分治思想，归并排序的核心思想还是蛮简单的。如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排 序，再将排好序的两部分合并在一起，这样整个数组就都有序了 。
图解：
分治思想。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。
- 分治算法一般都是用递归来实现的。分治 是一种解决问题的处理思想，递归是一种编程技巧
- 如何用递归代码来实现归并排序。
递推公式：merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))
终止条件：p >= r 不用再继续分解
实现：
//伪代码
// 归并排序算法, A是数组，n表示数组大小
merge_sort(A, n) {
merge_sort_c(A, 0, n-1)
}
// 递归调用函数
merge_sort_c(A, p, r) {
// 递归终止条件
if p >= r then return
// 取p到r之间的中间位置q
q = (p+r) / 2
// 分治递归
merge_sort_c(A, p, q)
merge_sort_c(A, q+1, r)
// 将A[p...q]和A[q+1...r]合并为A[p...r]
merge(A[p...r], A[p...q], A[q+1...r])
}//java实现
/**
* 描述:
* 归并排序
*
* @author Noah
* @create 2019-11-05 08:46
*/
public class _12_MergeSort {
// 归并排序算法, a是数组，n表示数组大小
public static void mergeSort(int[] a, int n) {
mergeSortInternally(a, 0, n - 1);
}
// 递归调用函数
private static void mergeSortInternally(int[] a, int p, int r) {
// 递归终止条件
if (p >= r) return;
// 取p到r之间的中间位置q,防止（p+r）的和超过int类型最大值
int q = p + (r - p) / 2;
// 分治递归
mergeSortInternally(a, p, q);
mergeSortInternally(a, q + 1, r);
// 将A[p...q]和A[q+1...r]合并为A[p...r]
merge(a, p, q, r);
}
private static void merge(int[] a, int p, int q, int r) {
int i = p;
int j = q + 1;
int k = 0; // 初始化变量i, j, k
int[] tmp = new int[r - p + 1]; // 申请一个大小跟a[p...r]一样的临时数组
while (i <= q && j <= r) {
if (a[i] <= a[j]) {
tmp[k++] = a[i++]; // i++等于i:=i+1
} else {
tmp[k++] = a[j++];
}
}
// 判断哪个子数组中有剩余的数据
int start = i;
int end = q;
if (j <= r) {
start = j;
end = r;
}
// 将剩余的数据拷贝到临时数组tmp
while (start <= end) {
tmp[k++] = a[start++];
}
// 将tmp中的数组拷贝回a[p...r]
for (i = 0; i <= r - p; ++i) {
a[p + i] = tmp[i];
}
}
/**
* 合并(哨兵)
*
* @param arr
* @param p
* @param q
* @param r
*/
private static void mergeBySentry(int[] arr, int p, int q, int r) {
int[] leftArr = new int[q - p + 2];
int[] rightArr = new int[r - q + 1];
for (int i = 0; i <= q - p; i++) {
leftArr[i] = arr[p + i];
}
// 第一个数组添加哨兵（最大值）
leftArr[q - p + 1] = Integer.MAX_VALUE;
for (int i = 0; i < r - q; i++) {
rightArr[i] = arr[q + 1 + i];
}
// 第二个数组添加哨兵（最大值）
rightArr[r - q] = Integer.MAX_VALUE;
int i = 0;
int j = 0;
int k = p;
while (k <= r) {
// 当左边数组到达哨兵值时，i不再增加，直到右边数组读取完剩余值，同理右边数组也一样
if (leftArr[i] <= rightArr[j]) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
}
}
}
}归并排序三连问：稳定的，最好、最坏、平均时间复杂度O(nlogn)，不是原地排序算法，空间复杂度就是O(n)
快速排序（快排）
原理：分治思想。
- 如果要排序数组中下标从p到r之间的一组数据，我们选择p到r之间的任意一个数据作为pivot(分区 点)。
- 我们遍历p到r之间的数据，将小于pivot的放到左边，将大于pivot的放到右边，将pivot放到中间。
- 然后继续分治、递归处理，直到区间缩小为1。
递推公式：quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1, r)
终止条件：p >= r
实现：
// 快速排序，A是数组，n表示数组的大小
quick_sort(A, n) {
quick_sort_c(A, 0, n-1)
}
// 快速排序递归函数，p,r为下标
quick_sort_c(A, p, r) {
if p >= r then return
// 获取分区点
q = partition(A, p, r)
quick_sort_c(A, p, q-1)
quick_sort_c(A, q+1, r)
}// 快速排序，a是数组，n表示数组的大小
public void quickSort(int[] a, int n) {
quickSortInternally(a, 0, n - 1);
}
// 快速排序递归函数，p,r为下标
private void quickSortInternally(int[] a, int p, int r) {
if (p >= r) return;
int q = partition(a, p, r); // 获取分区点
quickSortInternally(a, p, q - 1);
quickSortInternally(a, q + 1, r);
}
private int partition(int[] a, int p, int r) {
int pivot = a[r];
int i = p;
for (int j = p; j < r; ++j) {
if (a[j] < pivot) {
if (i == j) {
++i;
} else {
int tmp = a[i];
a[i++] = a[j];
a[j] = tmp;
}
}
}
int tmp = a[i];
a[i] = a[r];
a[r] = tmp;
System.out.println("i=" + i);
return i;
}快速排序是不是原地排序，取决partition()获取分区点的函数实现。
非原地排序算法实现：partition()分区函数可以写得非常简单。我们申请两个临时数组X和Y，遍历A[p…r]，将小于 pivot的元素都拷⻉到临时数组X，将大于pivot的元素都拷⻉到临时数组Y，最后再将数组X和数组Y中数据顺序拷⻉到A[p… r]。
原地排序算法：
partition(A, p, r) {
pivot := A[r]
i := p
for j := p to r-1 do {
if A[j] < pivot {
swap A[i] with A[j]
i := i+1
}
}
swap A[i] with A[r]
return i
快速排序三连问：不稳定、可原地排序算法
归并和快排区别
- 处理过程
- 归并排序的处理过程是由下到上的，先处理子问题，然后再合并
- 快排正好相反，它的处理过程是由上到下的， 先分区，然后再处理子问题。
- 原地排序（空间复杂度O(1)）
- 归并排序是稳定的、时间复杂度O(nlogn)。但是在合并的时候，不是原地排序。额外内存空间。
- 快排是原地排序的，不稳定的。大多数情况的时间复杂度都为O(nlogn)，极端情况才会退化为O(n²)
问题解答
如何在O(n)找到第K大元素？
- 利用分治和分区的实现。
- 实现：Todo
讲线性排序：如何根据年龄给100万用户数据排序
线性排序：时间复杂度为O(n)，常见：桶排序、计数排序、基数排序。不是基于比较的排序算法，不涉及元素之间的比较操作。但是对排序的数据有对应的场景。
题目：如何根据年龄给100w用户排序。
桶排序(Bucket sort)
原理：将要排序的数据分到几个有序的桶里，每个桶里的数据 再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
三连问：时间复杂度O(n)
桶排序看起来那么优秀，可以替换之前讲的常规排序算法吗？
- 不能，因为我们对桶排序之前，都做了很多假设，本质就是对要排序的数据要求很苛刻。
- 但是桶排序比较适合用在外部排序中 。
- 外部排序：就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加 载到内存中。
- 题目：在内存为100MB的情况下，把10G的订单文件按照金额进行排序。
- 用桶排序。
- 第一遍扫描价格区间，根据价格区间创建适合的桶。
- 利用快排在桶内排序。
- 如果某个桶的数据太大，再继续划分桶
计数排序(Counting Sort)
- 计数排序其实是桶排序的一种特殊情况
- 原理：最大值是k，我们就可以把数据划分成k个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。
- 适用场景：计数排序只能用在数据范围不大的场景中，如果数据范围k比要排序的数据n大很多，就不适合用计数排序了。 而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整 数。
基数排序(Radix sort )
总结
线性排序：虽然时间复杂度都是O(n)，但是应用不是特别广泛，只能使用在特定的场景下。
讲排序优化：如何实现一个通用的、高性能的排序函数
如何实现一个通用的、高性能的排序函数?
如何选择合适的排序算法
总结之前学习过的算法
如何选择：
- 线性算法要适用于特定场景。
- 对于小规模的数据，可以选择时间复杂度为O(n²)
- 对于大规模的数据，时间复杂度为O(nlogn)的算法更加高效。一般也选择O(nlogn)作为排序算法首选.
- O(nlogn)的排序算法
- 快速排序：c语言使用
- 堆排序：java语言使用，如何优化最坏时间复杂度为O(n²)了？
- 归并排序：因为不是原地排序并没有使用。
如何优化快速排序？
- 问题产生的原因：
- 在有序的数据并且每次选择分区都选择最后一个。
- 这种O(n²) 时间复杂度出现的主要原因还是因为我们分区点选的不够合理。
- 解决问题：
- 那什么样的分区点是好的分区点呢?或者说如何来选择分区点呢?
- 被分区点分开的两个分区中，数据的数量差不多。
- 分区点选择算法
- 三数取中法
- 随机法
- 堆栈溢出解决
- 限制递归深度
- 在堆上模拟是一个函数调用栈
举例分析排序函数qsort()
- qsort()会优先使用归并排序输入数据（数据规模1KB~10KB）
- 要排序的数 据量比较大的时候，**qsort()**会改为用快速排序算法来排序。
- 分区点的选择：三数取中法
- 堆栈溢出：堆上模拟函数调用栈
- 在快速排序过程：如何元素个数<=4，使用插入排序。
- **O(n²)时间复杂度的算法并不一定比O(nlogn)**的算法执行时间⻓
- 哨兵简化代码
讲二分查找（上）：如何用最省内存的方式实现快速查找功能
针对有序数据集合的查找算法：二分查找（Binary search）算法，也叫折半查找算法。
问题：如何设计数据结构和算法，快速判断某个整数是否出现在这1000万数据 中?
二分查找思想
二分查找针对的是一个有序的数据集 合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的 元素，或者区间被缩小为0 。时间复杂度O(logn)
二分查找算法惊人O(logn)
二分查找算法的时间复杂度为O(logn)，后续讲到的堆、二叉树也是该时间复杂度。
因为logn是一个非常“恐怖”的数量级，即便n非常非常大，对应的logn也很小。比如n等于2的32次方，这个数很大了吧?大约 是42亿。也就是说，如果我们在42亿个数据中用二分查找一个数据，最多需要比较32次。
二分查找的递归与非递归实现
- 实现
public class _15_BinarySearchSimple { |
- 非递归实现容易出错的三个地方
- mid的取值：超过Integer的最大值，取中间值：
low+(high-low)/ 2或者low+((high-low)>>1) - 循环退出：是<=
- low和high的更新
- mid的取值：超过Integer的最大值，取中间值：
二分查找应用场景的局限性
- 二分查找依赖的是顺序表结构，简单点说就是数组。
- 二分查找针对的是有序数据。
- 二分查找只能用在插入、删除操作不频繁，一次排序多次查找的场景中。
- 针对动态变化的数据集合，二分查找将不再适 用。那针对动态数据集合，如何在其中快速查找某个数据呢?
- 二叉树那一节我会详细讲。
- 数据量太小不适合二分查找
- 比较次数过多的，也可以使用二分查找
- 数据量太大也不适合二分查找
- 二分查找的底层需要依赖数组这种数据结构，而数组为了支持随机访问的特性，要求内存空间连续，对内存的要求比较苛刻。 比如，我们有1GB大小的数据，如果希望用数组来存储，那就需要1GB的连续内存空间。
讲二分查找（下）：如何快速定位IP对应的省份地址
二分查找的变形问题：我们上一章讲的都是基于没有重复元素并且存在存在给定值的情况。
二分查找：比较难写。我们默认接下来的集合数据都是按照从小到大排好顺序了。
变体1：查找第一个值等于给定值的元素
变体2：查找最后一个值等于给定值的元素
变体3：查找第一个大于等于给定值的元素
变体4：查找最后一个小于等于给定值的元素
问题解答
如何快速定位一个IP地址的归属地？
- 这种类型问题的特点：
- 如果IP区间与归属地的对应关系不经常更新 。
- 我们可以先预处理这12万条数据，让其按照起始IP 从小到大排序。 IP地址可以转化为32位的整型数
- 根据上面的特点，我们就把问题转换为二分查找的变形问题4了，在有序数组中，找到最后一个小于等于某个给定值的元素了。
内容总结
- 凡是用二分查找能解决的，绝大部分我们更倾向于用散列表或者二叉查找树。即便是二分查找在内存使用上更 节省，但是毕竟内存如此紧缺的情况并不多。
- 二分查找的用途：
- 二分查找更适合用在“近似”查找问题 。
- 求“值等于给定值”的二分查找确实不怎么会被用到 。
- 变体问题最好二分的用户，用散列表或者二叉树很难实现。
- 二分查找算法很难，容易出错的地方：终止条件、区间上下界更新方法、返回值选择。
讲跳表：为什么Redis一定要用跳表来实现有序集合
- 二分查找的底层是依赖于数组随机访问特性来实现的。如果数据存储在链表上，我们用折半的思想对链表进行改造，改造的数据结构叫跳表（Skip list）。
- 跳表：各方面都比较优秀的动态数据结构，可以支持快速的插入、删除、查找操作。甚至可以替代红黑树。这种链表加多级索引的结构，就是跳表
如何理解”跳表”？
即使在一个有序的链表中，查找某个数据，也是要从头到尾遍历，时间复杂度O(n)。
如果我们对链表建立”索引”。
我们把抽出来的那一级叫做索引或索引层，加来一层索引之后，查找一个结点需要遍历的结点个数减少了，也就是说查找效率提高了 。查找62节点，只需要遍历11个节点
跳表的时间复杂度O(logn)，基于链表实现的二分查找。
跳表的空间复杂度O(n)，每两个结点会抽出一个结点作为上一级索引的结点（可变） 。
实际开发：空间换时间思想
在讲数据结构和算法时，我们习惯性地把要处理的数据看成整数，但是在实际的软件开发中，原始链表中存储的有可能是很大的对象，而索引只需要存储关键值和几个指针，并不需要存储对象。所以当对象比索引结点大很多时，那索引占用的额外空间就可以忽略了。
跳表：高效的动态插入和删除O(logn)
- 插入问题：要保证链表的有序性，根据跳表的查找时间复杂度为O(logn)+链表的插入复杂度O(1)
- 删除问题：删除要获取前驱节点，使用双向链表就能解决这个问题了。
跳表：索引动态更新
- 当插入数据太多，有可能出现某2个索引节点之间数据非常多。极端情况下，跳表有可能会退化为单链表。
- 链表是一种动态数据结构，需要手动维护链表大小和索引之间的平衡。
- 红黑树和AVL树通过左右旋的方式保持左右子树的大小平衡。
- 跳表维护平衡性：
- 随机函数：随机函数生成了值K，那我们就将这个结点添加到第一 级到第K级这K级索引中。
问题解答
- 为什么Redis要用跳表来实现有序集合，而不是红黑树？
- Redis中的有序集合是通过散列表和跳表实现的。
- 跳表实现相对比较容易，容易理解，好写，可读性好。
- 不过，跳表也不能完全替代红黑树 ，很多编程语言的Map都是通过红黑树实现。而跳表是没有现成的。
讲散列表（上）：Word文档中的单词拼写检查功能是如何实现的
散列思想
- 散列表的英文是”Hash Table”，也叫哈希表或者Hash表。
- 散列表用的是数组支持按照下标随机访问数据的特性，所以散列表就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。
- 应用场景：快速查找编号对应的选手信息。
- 参赛选手的编号为数组下标，数组存储选手信息。
- 这就是典型的散列思想。其中，参赛选手的编号我们叫作键(key)或者关键字。我们用它来标识一个选手。我们把参赛编号 转化为数组下标的映射方法就叫作**
散列函数**(或“Hash函数”“哈希函数”)，而散列函数计算得到的值就叫作散列值(或“Hash 值”“哈希值”)
散列函数
散列函数，顾名思义，它是一个函数。我们可以把它定义成**hash(key)**，其中key表示元素的键值，hash(key)的值表示经过散 列函数计算得到的散列值。
如何构建散列函数，三点基本要求：
- 散列函数计算得到的散列值是一个非负整数。
- if key1 = key2 ，那hash(key1) = hash(key2)
- if key2 != key2 ，那hash(key1) != hash(key2)
根据第三点，我们谈谈如何解决散列冲突。
散列冲突
- 我们常用的散列冲突解决办法有两大类：开放寻址法(open addressing)和链表法(chaining)
开放寻址法
- 开放寻址法的核心思想是，如果有了散列冲突，我们就重新探测一个空闲位置，将其插入。
- 如何重新探测新的位置呢？
- 线性探测(Linear Probing)：探测步长是1
- 二次探测(Quadratic Probing)：探测步长是线性的原来二次方
- 双重散列(Double hashing)：多个散列函数
装载因子:表示空位的多少 ，保证散列表中有一定比例的空闲槽位 ，减少散列冲突。
- 计算公式：散列表装载因子=填入表中的元素个数/散列表的长度
- 所以装载因子越大（1），说明空闲位置越小，冲突越多，散列表的性能就下降越严重。
- todo：请思想线程探测是怎么实现插入、查找、删除
链表法
链表法是一种更加常用的散列冲突的解决办法。
当散列冲突的时候，通过链表直接拼接在一起。
插入、查找、删除在分配均匀的散列表的时间复杂度为O(1)
问题解决
直接把20w单词（2MB）构建一个散列表，直接到散列表中查找这个元素是否存在。
讲散列表（中）：如何打造一个工业级水平的散列表
散列表的查询效率不能笼统地说是O(1)，它跟散列函数，装载因子、散列冲突有关。应该这样描述：在分配均匀的散列表中，查找、插入、删除的时间复杂度为O(1)。
在一些极端或者恶意攻击的情况下，在基于链表解决散列冲突的情况下，散列函数设计不好，散列表就会退化为链表。
问题：如何设计一个可以应对各种异常情况的工业级散列表，来避免在散列冲突的情况下，散列表性能的 急剧下降，并且能抵抗散列碰撞攻击?
如何设计散列函数？
- 设计散列函数的要求？
- 散列函数的设计不能太复杂
- 散列函数生成的值要尽可能随机并且均匀分布。
装载因子过大了怎么办？
- 采用动态扩容的思想来解决，那我们思考下数组、栈、队列是怎么实现动态扩容的。
- 但是扩容之后，所有的数据都要经过散列函数重新计算在散列表中的位置。
- 时间复杂度O(n)
- 但是用摊还分析法 ，平均插入的时间复杂度还是O(1)
如何避免低效地扩容？
- 如何解决”一次性”扩容重新计算和插入成本太高的问题？
- 为了解决一次性扩容耗时过多的情况，我们可以将扩容操作穿插在插入操作的过程中，分批完成。当装载因子触达阈值之后， 我们只申请新空间，但并不将老的数据搬移到新散列表中。
- 但是查询操作，需要查询新老两个散列表。
如何选择冲突解决办法？
- 解决散列冲突的两种主要方法：开放寻址法和链表法。
- Java中LinkedHashMap就采用了链表法解决冲突
- ThreadLocalMap是通过线性探测的开放寻址法来解决冲突。
- 这两种散列冲突解决办法有什么优势和劣势，适用场景又是什么？
开放寻址法
- 存储在数组中，可以有效地利用CPU缓存加快查询速度。序列化代价小。
- 缺点：删除元素特殊标志。装载因子不能太大，更加消耗内存。
- 总结：当数据量比较小、装载因子小的时候，适合采用开放寻址法。这也是Java中的ThreadLocalMap使用开 放寻址法解决散列冲突的原因。
链表法
内存利用率更高，不用事先申请好内存。
装载因子容忍度更高，只要散列函数的值随机均匀，即便装载 因子变成10，也就是链表的⻓度变⻓了而已，虽然查找效率有所下降，但是比起顺序查找还是快很多。
缺点：链表空间不连续，相对存储数据的指针大小空间问题。
我们对链表法稍加改造，可以实现一个更加高效的散列表。
链表更改为：跳表、红黑树等。查询的时间复杂度也O(logn)
总结：基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加 灵活，支持更多的优化策略，比如用红黑树代替链表。
Java中的HashMap分析
初始化大小
- HashMap的初始化大小为16，也可以手动设置，减少扩容次数，大大提高HashMap的性能。
装载因子和动态扩容
- 最大装载因子默认是0.75，当HashMap中元素个数超过0.75*capacity(capacity表示散列表的容量)的时候，就会启动扩容， 每次扩容都会扩容为原来的两倍大小。
散列冲突解决办法
- HashMap底层采用链表法来解决冲突。即使负载因子和散列函数设计得再合理，也免不了会出现拉链过⻓的情况
- 在JDK1.8版本中，为了对HashMap做进一步优化，我们引入了红黑树。而当链表⻓度太⻓(默认超过8)时，链表就转 换为红黑树。
散列函数
散列函数的设计并不复杂，追求的是简单高效、分布均匀。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
总结
主要讲了三个主题：如何设计散列函数，如何根据装载因 子动态扩容，以及如何选择散列冲突解决方法。
- 关于散列函数的设计，我们要尽可能让散列后的值随机且均匀分布，这样会尽可能地减少散列冲突，即便冲突之后，分配到每 个槽内的数据也比较均匀。除此之外，散列函数的设计也不能太复杂，太复杂就会太耗时间，也会影响散列表的性能。
- 关于散列冲突解决方法的选择，我对比了开放寻址法和链表法两种方法的优劣和适应的场景。大部分情况下，链表法更加普 适。而且，我们还可以通过将链表法中的链表改造成其他动态查找数据结构，比如红黑树，来避免散列表时间复杂度退化成 O(n)，抵御散列碰撞攻击。但是，对于小规模数据、装载因子不高的散列表，比较适合用开放寻址法。
- 对于动态散列表来说，不管我们如何设计散列函数，选择什么样的散列冲突解决方法。随着数据的不断增加，散列表总会出现 装载因子过高的情况。这个时候，我们就需要启动动态扩容。
讲散列表（下）：为什么散列表和链表经常会一起使用
总结之前链表和散列表一起使用的例子
- LRU缓存淘汰算法
- Redis有序集合（改良的跳表）
- Java LinkedHashMap
栗子1：LRU缓存淘汰算法
- 双向链表和散列表组合。
- 链表中的每个结点处理存储数据(data)、前驱指针(prev)、后继指针(next)之外，还新增 了一个特殊的字段hnext。 前驱和后继指针是为了将结点串在双向链表中，hnext指针是为了将结点串在散列表的拉链中。
- 查找、删除、新增元素的时间复杂度都为O(1)
栗子2：Redis有序集合
每个成员对象有两个重要的属性，key(键值)和score(分值)。我们不仅会通过score来查找数据，还会通过key来查找数据。
栗子3：Java LinkedHashMap
如何理解LinkHashMap中的”Linked”？
- 不仅仅代表它是通过链表法解决散列冲突的 。
- 实际上，它不仅支持按照插入顺序遍历数 据，还支持按照访问顺序来遍历数据。
- 这就是一个天生支持LRU缓存淘汰策略的缓存系统。
- 总结：LinkedHashMap是通过双向链表和散列表这两种数据结构组合实现的。LinkedHashMap中 的“Linked”实际上是指的是双向链表，并非指用链表法解决散列冲突。
内容总结
为什么散列表和链表经常一起使用？
- 散列表这种数据结构虽然支持非常高效的数据插入、删除、查找操作，但是散列表中的数据都是通过散列函数打乱之后无规律 存储的。也就说，它无法支持按照某种顺序快速地遍历数据。如果希望按照顺序遍历散列表中的数据，那我们需要将散列表中 的数据拷⻉到数组中，然后排序，再遍历。
- 因为散列表是动态数据结构，不停地有数据的插入、删除，所以每当我们希望按顺序遍历散列表中的数据的时候，都需要先排 序，那效率势必会很低。为了解决这个问题，我们将散列表和链表(或者跳表)结合在一起使用。
讲哈希算法（上）：如何防止数据库中的用户信息被脱库
什么是哈希算法？
- 因为散列、哈希在英文都是Hash。
- 哈希算法：
将任意⻓度的二进制值串映射为固定⻓度的二进制值串。而通过原始数据映射之后得到的二进制值串就是哈希值 。- 如何设计一个优秀的哈希算法？（栗子：MD5哈希算法）
- 从哈希值不能反向推导出原始数据(所以哈希算法也叫单向哈希算法)
- 对输入数据非常敏感，哪怕原始数据只修改了一个Bit，最后得到的哈希值也大不相同;
- 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小;
- 哈希算法的执行效率要尽量高效，针对较⻓的文本，也能快速地计算出哈希值。
- 哈希算法应用：安全加密、唯一标识、数据校验、散列函数、负载均衡、数据分 片、分布式存储。
应用一：安全加密
- 常用的加密哈希算法：MD5、SHA、DES、AES。
- 为什么哈希算法无法做到0冲突？
- 根据鸽巢原理（也叫抽屉原理），10个鸽子，9个鸽巢。必定有2个鸽子在1个鸽巢。
- 因为哈希算法产生的哈希值的长度是固定且有限的。所以穷举完所有+1,必定有冲突。
- 但是这是很那破解的，能够哈希值越大，冲突概率越小。
应用二：唯一标识
栗子：如果要在海量的图库中，搜索一张图是否存在，我们不能单纯地用图片的元信息(比如图片名称)来比 对，因为有可能存在名称相同但图片内容不同，或者名称不同图片内容相同的情况。那我们该如何搜索呢?
我们可以给每一个图片取一个唯一标识，或者说信息摘要。比如，我们可以从图片的二进制码串开头取100个字节，从中间取 100个字节，从最后再取100个字节，然后将这300个字节放到一块，通过哈希算法(比如MD5)，得到一个哈希字符串，用 它作为图片的唯一标识。通过这个唯一标识来判定图片是否在图库中，这样就可以减少很多工作量。
如果还想继续提高效率，我们可以把每个图片的唯一标识，和相应的图片文件在图库中的路径信息，都存储在散列表中。当要 查看某个图片是不是在图库中的时候，我们先通过哈希算法对这个图片取唯一标识，然后在散列表中查找是否存在这个唯一标 识。
应用三：数据校验
栗子：BT下载的原理是基于P2P协议的。我们从多个机器上并行下载一个2GB的 电影，这个电影文件可能会被分割成很多文件块(比如可以分成100块，每块大约20MB) 。在网络传输之后，如何确保数据块没被串改呢？
利用哈希算法特点2，数据敏感。在把多个文件块合成之前，进行哈希计算。是否跟源文件的哈希值相等。
应用四：散列函数
散列函数也是哈希算法的一种应用。
讲哈希算法（下）：哈希算法在分布式系统中有哪些应用
应用五：负载均衡
载均衡算法有很多，比如轮询、随机、加权轮询等。那如何才能实现一个会话粘滞(session sticky)的负载均 衡算法呢?也就是说，我们需要在同一个客户端上，在一次会话中的所有请求都路由到同一个服务器上。
- 使用一张映射关系表（次）：
- 客户端很多，映射表大，查看耗时并且浪费内存
- 客户端上下线，服务器扩容，映射表都会失效，维护成本高。
- 客服端ip计算哈希值，然后取模，得到服务器编号。
- 我们可以通过哈希算法，对客户端IP地址或者会话ID计算哈希值，将取 得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。
应用六：数据分片
如何统计大文件”搜索关键词”出现的次数？
- 问题：第一，搜索日志很大，一台机器内存无法放下。第二，一台机器处理，时间比较长。
- 解决：我们可以先对数据进行分片，然后采用多台机器处理的方法，来提高处理速度。 （MapReduce的基本设计思想 ）
- 具体：我们用n台机器并行处理。我们从搜索记录的日志文件中，依次读出每个搜索关键词，并且通过哈希函数计 算哈希值，然后再跟n取模，最终得到的值，就是应该被分配到的机器编号。
如何快速判断图片是否存在图库中？
- 问题：根据我们上一节讨论：对图片取唯一标识（哈希算法），然后存储在散列表中。如果1亿张图片，是无法存储在一台机器上的散列表中。
- 解决：对数据分片。
- 具体：我们准备n台机器，让每台机器只维护某一部分图片对应的散列表。我们 每次从图库中读取一个图片，计算唯一标识，然后与机器个数n求余取模，得到的值就对应要分配的机器编号，然后将这个图 片的唯一标识和图片路径发往对应的机器构建散列表。
- 数学科普：这1亿张图片构建散列表大约需要多少台机器？
- 散列表中每个数据单元包含两个信息，哈希值和图片文件的路径。假设我们通过MD5来计算哈希值，那⻓度就是128比特，也 就是16字节。文件路径⻓度的上限是256字节，我们可以假设平均⻓度是128字节。如果我们用链表法来解决冲突，那还需要 存储指针，指针只占用8字节。所以，散列表中每个数据单元就占用152字节(这里只是估算，并不准确)
- 假设一台机器的内存大小为2GB，散列表的装载因子为0.75，那一台机器可以给大约1000万(2GB*0.75/152)张图片构建散 列表。所以，如果要对1亿张图片构建索引，需要大约十几台机器。在工程中，这种估算还是很重要的，能让我们事先对需要 投入的资源、资金有个大概的了解，能更好地评估解决方案的可行性。
- 总结：实际上，针对这种海量数据的处理问题，我们都可以采用多机分布式处理。借助这种分片的思路，可以突破单机内存、CPU 等资源的限制。
应用七：分布式存储
分布式存储应用很多，常见的都是给定的值通过哈希算法计算得到哈希值，然后对机器数量取模。
- 问题：如果机器库容，那取余运算结果就不对。就要对所有数据都要重新计算哈希值。如果是缓存机器，那就会发生雪崩效应。
- 解决：一致性哈希算法。（解决分布式系统的扩容、缩容导致数据大量搬移的难题 ）
- 假设我们有k个机器，数据的哈希值的范围是[0, MAX]。我们将整个范围划分成m个小区间(m远大于k)，每个机器负责m/k 个小区间。当有新机器加入的时候，我们就将某几个小区间的数据，从原来的机器中搬移到新的机器中。
- 除此之外，它还会借助一个虚拟的环和虚拟结点，更加优美地实现出来。
讲二叉树基础（上）：什么样的二叉树适合用数组来存储
前面我们讲的都是都是线性结构：数组、链表、栈、队列等等。
现在我们开始讲非线性结构：树、图等等的内容。
- 树、二叉树
- 二叉查找树
- 平衡二叉查找树、红黑树
- 递归树
问题：二叉树有哪几种存储方式？什么样的二叉树适合用数组来存储？
树（Tree）
树相关的概念
父节点、子节点、兄弟节点、根节点、叶子节点。
高度、深度、层
二叉树（Binary Tree）
二叉树的概念
- 二叉树：每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。
- 满二叉树：叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点。
- 完全二叉树：叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大 。
如何表示（存储）一棵二叉树？
常见的有两种方法：
- 一种基于指针或者引用的二叉链式存储法（大部分二叉树都是这样存储）
- 一种是基于数组的顺序存储法
- 如果节点X存储在数组中下标为i的位置（完全二叉树）
- 下标为2 * i 的位置存储的就是左子节点
- 下标为2 * i + 1的位置存储 的就是右子节点
- 下标为i/2的位置存储就是它的父节点
- 根节点会存储在下标为1的位置
- 完全二叉树的最佳存储方式，非完全二叉树会浪费更多的数组空间。
- 堆其实就是一种完全二叉树，最常用的存储方式就是数组。
二叉树的遍历
如何遍历二叉树中的所有节点？
前序遍历：对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
中序遍历：对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。
后序遍历：对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。
一图胜前文：时间复杂度O(n)
代码实现：递归实现
写递推公式：假设要解决问题A，分解为子问题B、C（递）。那B和C的问题已经解决了，然后再看如何利用B和C来解决问题A（归）。
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)
中序遍历的递推公式:
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)
后序遍历的递推公式:
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r代码实现：
if (root == null) return;
print root // 此处为伪代码，表示打印root节点
preOrder(root->left);
preOrder(root->right);
}
void inOrder(Node* root) {
if (root == null) return;
inOrder(root->left);
print root // 此处为伪代码，表示打印root节点
inOrder(root->right);
}
void postOrder(Node* root) {
if (root == null) return;
postOrder(root->left);
postOrder(root->right);
print root // 此处为伪代码，表示打印root节点
}
讲二叉树基础（下）：有了如此高效的散列表，为什么还需要二叉树
二叉查找树：支持动态数据集合的快速插入、删除、查找操作。散列表都支持这些操作，并且时间复杂度O(1)。
问题：既然有了这么 高效的散列表，使用二叉树的地方是不是都可以替换成散列表呢?有没有哪些地方是散列表做不了，必须要用二叉树来做的 呢?
二叉查找树（Binary Search Tree）
二叉查找树的概念
二叉查找树：支持动态数据集合的快速插入、删除、查找操作。又名：二叉搜索树、二叉排序树。
二叉查找树结构特点：
- 在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个 节点的值，而右子树节点的值都大于这个节点的值。
一图胜千文：
二叉查找树的查找
/** |
二叉查找树的插入
/** |
二叉查找树的删除
二叉查找树的查找、插入操作比较容易理解。但是删除操作就比较复杂，要根据删除节点的子节点个数不同，分为三种情况。
- 如果要删除的节点没有子节点，我们只需要直接将父节点中，指向要删除节点的指针置为null。比如图中的删除节点55。
- 如果要删除的节点只有一个子节点(只有左子节点或者右子节点)，我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。比如图中的删除节点13。
- 如果要删除的节点有两个子节点，这就比较复杂了。我们需要找到这个节点的右子树中的最小节点，把它替换 到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点(如果有左子结点，那就不是最小节点 了)，所以，我们可以应用上面两条规则来删除这个最小节点。比如图中的删除节点18。
骚操作：关于二叉查找树的删除操作，还有个非常简单、取巧的方法，就是单纯将要删除的节点标记为“已删除” 。浪费点内存，对查找和新增无影响。
/** |
二叉查找树的其他操作
- 二叉查找树除了支持快速查找、插入、删除操作之外。
- 还可以支持快速地查找最大节点和最小节点、前驱节点和后继节点。
- 还有一个重要的特性，就是中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是O(n)，非常高效。
支持重复数据的二叉查找树
我们上面谈论都是键值不同的的情况下，但实际开发我们二叉查找树是存在键值相同的情况。
- 第一种方法比较容易。二叉查找树中每一个节点不仅会存储一个数据，因此我们通过链表和支持动态扩容的数组等数据结构， 把值相同的数据都存储在同一个节点上。
- 第二种方法比较不好理解，不过更加优雅。
- 每个节点仍然只存储一个数据。在查找插入位置的过程中，如果碰到一个节点的值，与要插入数据的值相同，我们就将这个要 插入的数据放到这个节点的右子树，也就是说，把这个新插入的数据当作大于这个节点的值来处理。
- 查找和删除的操作链路更长：要一直查找到叶子节点，判断是否有重复的元素。
二叉查找树的时间复杂度分析
对于同一集合数据：1,2,3,4,5,6,7,8,9。可以构建多种二叉查找树。
- 最糟糕的情况是：二叉查找树退化为链表，那查找时间复杂度退化为O(n)
- 最理想的情况是：二叉查找树是一棵完全二叉树。
- 查找、插入、删除的时间复杂度：时间复杂度其实都跟树的高度成正比，也就是 O(height)
- 也就是时间复杂度O(logn)
如何求一棵包含n个节点的完全二叉树的高度？
- 我们换个角度出发：树的高度=最大层数-1
- 完全二叉树的层数小于等于log2n +1， 完全二叉树的高度小于等于log2n。
在极度不平衡的二叉查找树的性能是不能满足我们的。我们需要构建一种无论数据怎么插入、删除都是比较平衡的二叉查找树，树的高度logn，那crud的复杂度就是O(logn)==>平衡二叉查找树。
问题解答
散列表的插入、删除、查找操作的时间复杂度可以做到常量级的O(1)，非常高效。而二叉查找树在 比较平衡的情况下，插入、删除、查找操作时间复杂度才是O(logn)，相对散列表，好像并没有什么优势，那我们为什么还要 用二叉查找树呢?
- 散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍 历，就可以在O(n)的时间复杂度内，输出有序的数据序列。
- 散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常 用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在O(logn)。
- 笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比logn小， 所以实际的查找速度可能不一定比O(logn)快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。
- 散列表的构造比二叉查找树要复杂，需要考虑的东⻄很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡 二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。
讲红黑树（上）：为什么工程中都用红黑树这种二叉树
终于开始讲我们心心期待的红黑树了，结合我们上面讲的。
- 我们已经将了树、二叉树、二叉查找树。其中二叉查找树是最常用的一种二叉树。
- 二叉查找树支持快速的crud，在理想的情况下（完全二叉树），时间复杂度跟树的高度成正比，为O(logn)
- 接下来我们就要讲如何维持二叉查找树的平衡，也就是平衡二叉查找树（红黑树）。
什么是”平衡二叉查找树”？
平衡二叉树的定义：二叉树中任意一个节点的左右子树的高度相差不能大于1 。
- 完全二叉树、满二叉树其实都是平衡二叉树，但是非完全二叉树也有可能是平衡二叉树
平衡二叉查找树定义：平衡二叉树+二叉查找树
- 最先被发明的平衡二叉查找树是AVL树，它严格 符合我刚讲到的平衡二叉查找树的定义，即任何节点的左右子树高度相差不超过1，是一种高度平衡的二叉查找树。
- 但是很多平衡二叉查找树其实并没有严格符合上面的定义（平衡二叉树）。包括红黑树
平衡二叉查找树的运用：
- 平衡二叉查找树就是为了解决时间复杂度退化的问题。
- 平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子 树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。
- 只要时间复杂度在O(logn)，就是一个合格的平衡二叉查找树。
如何定义一棵”红黑树”？
平衡二叉查找树其实有很多，比如，Splay Tree(伸展树)、Treap(树堆)等，但是我们提到平衡二叉查找树，听到的基本 都是红黑树。它的出镜率甚至要高于“平衡二叉查找树”这几个字，有时候，我们甚至默认平衡二叉查找树就是红黑树，那我们 现在就来看看这个“明星树”。
红黑树的定义：
- 根节点是黑色的;
- 每个叶子节点都是黑色的空节点(NIL)，也就是说，叶子节点不存储数据;
- 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的;
- 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点;
红黑树总结：
- 二叉查找树很多操作的性能都跟树的高度成正比。一棵极其平衡的二叉树(满二叉树或完全二叉树)的高度大约是log2n，所以如果要证明红黑树是近似平衡的，我们只需要分析，红黑树的高度是否比较稳定地趋近log2n就好了。
- 红黑树的高度只比高度平衡的AVL树的高度(log2n)仅仅大了一倍
问题解答
我们前面提到Treap、Splay Tree，绝大部分情况下，它们操作的效率都很高，但是也无法避免极端情况下时间复杂度的退 化。尽管这种情况出现的概率不大，但是对于单次操作时间非常敏感的场景来说，它们并不适用。
AVL树是一种高度平衡的二叉树，所以查找的效率非常高，但是，有利就有弊，AVL树为了维持这种高度的平衡，就要付出更 多的代价。每次插入、删除都要做调整，就比较复杂、耗时。所以，对于有频繁的插入、删除操作的数据集合，使用AVL树的代价就有点高了。
红黑树只是做到了近似平衡，并不是严格的平衡，所以在维护平衡的成本上，要比AVL树要低。
Todo：讲红黑树（下）：掌握这些技巧，你也可以实现一个红黑树
总结
红黑树很难学，那我们要如何学习呢？
我们学习数据结构和算法，要学习它的由来、特性、适用的场景以及它能解决的问题。对于红黑 树，也不例外。你如果能搞懂这几个问题，其实就已经足够了。
红黑树是一种平衡二叉查找树。它是为了解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的。红黑树的高 度近似log2n，所以它是近似平衡，插入、删除、查找操作的时间复杂度都是O(logn)。
因为红黑树是一种性能非常稳定的二叉查找树，所以，在工程中，但凡是用到动态插入、删除、查找数据的场景，都可以用到 它。不过，它实现起来比较复杂，如果自己写代码实现，难度会有些高，这个时候，我们其实更倾向用跳表来替代它。
讲堆和堆排序：为什么说堆排序没有快速排序快
“堆(Heap)”：是一种特殊的树，应用最多的是堆排序，堆排序是一种原地的、时间复杂度为O(nlogn)。
如何理解”堆”?
堆是一种特殊的树，需要满足下面的条件
- 堆是一棵完全二叉树
- 堆中每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值
图解堆：对于同一组数据，我们可以构建多种不同形态的堆
如何实现一个堆？
要实现一个堆，我们需要知道堆都支持哪些操作以及如何存储一个堆
如何存储一个堆？
- 堆是一棵完全二叉树，使用数组来存储是非常好的，既不会浪费数组的存储空间，也不用使用链表的指针。
- 如果节点X存储在数组中下标为i的位置（完全二叉树） ,下标从1开始
- 下标为2 * i 的位置存储的就是左子节点
- 下标为2 * i + 1的位置存储 的就是右子节点
- 下标为i/2的位置存储就是它的父节点
- 根节点会存储在下标为1的位置
- 如果节点X存储在数组中下标为i的位置（完全二叉树） ,下标从0开始
- 左节点2*i+1
- 右节点2*i+2（下标0开始计算）
堆支持哪些操作？
- 代码实现
/**
* 堆插入操作：自下而上堆化，数组从下标0开始,大顶堆
*
* @param data
*/
public void insert(int data) {
if (count >= n) return; // 堆满了
++count;
a[count] = data;
int i = count;
while (i / 2 > 0 && a[i] > a[i / 2]) { // 自下往上堆化
swap(a, i, i / 2); // swap()函数作用:交换下标为i和i/2的两个元素
i = i / 2;
}
}堆操作：插入、删除的时间复杂度分析
- 完全二叉树的任何crud，时间复杂度分析都可以总结为跟树的高度成正比，而完全二叉树的高度不会超过O(logn)。curd在堆的操作中，主要的操作是堆化，因此时间复杂度为O(logn)
如何基于堆实现排序
我们先回忆总结一下之前学习的排序算法。分类角度：时间复杂度、稳定性、原地算法等
- 时间复杂度O(n²)：冒泡排序、插入排序、选择排序
- 时间复杂度O(nlogn)：归并排序、快速排序
- 线性时间复杂度O(n)：桶排序、计数排序、基数排序
新的排序算法，基于堆（特殊的树）这种结构实现的堆排序算法：
- 时间复杂度非常稳定O(nlogn)，原地排序算法。
- 堆排序的两大步骤：建堆和排序
建堆
建堆有两种方案
方案一（不佳）：思路类似我们在堆中插入一个元素，数组从前往后插入（堆的尾部），然后每次堆化都是从下往上堆化。
方案二（佳）：从后往前处理数组（第一个非叶子节点（n/2）开始堆化），并且每个数据都是从上往下堆化。
图解
代码实现
/**
* 建堆
*
* @param a
* @param n
*/
private static void buildHeap(int[] a, int n) {
for (int i = n / 2; i >= 1; --i) {
heapify(a, n, i);
}
}
/**
* 堆化
*
* @param a
* @param n
* @param i
*/
private static void heapify(int[] a, int n, int i) {
while (true) {
int maxPos = i;
if (i * 2 <= n && a[i] < a[i * 2]) maxPos = i * 2;
if (i * 2 + 1 <= n && a[maxPos] < a[i * 2 + 1]) maxPos = i * 2 + 1;
if (maxPos == i) break;
swap(a, i, maxPos);
i = maxPos;
}
}
建堆的时间复杂度为O(n)。
数学科普时间：对于一棵完全二叉树，数组从下标1开始，那么第一个非叶子节点就是n/2。n/2+1~n的节点都是叶子节点。
排序
建堆之后，数组中的数据是按照大顶堆的特性来组织的。堆顶元素是最大的元素。接下来的操作类似我们刚才删除堆顶元素，和最后一个元素交换值，并且从上往下堆化，区间在[1,–n]
图解
代码实现
/**
* n表示数据的个数，数组a中的数据从下标1到n的位置。
*
* @param a
* @param n
*/
public static void sort(int[] a, int n) {
buildHeap(a, n);
int k = n;
while (k > 1) {
swap(a, 1, k);
--k;
heapify(a, k, 1);
}
}
分析
原地排序算法、总时间复杂度O(nlogn)=建堆O(n)+排序O(logn)。注意点：堆的原始数组是从下标0还是下标1开始
问题解析
为什么快速排序要比堆排序的性能好？
- 堆排序数据访问方式没有快速排序友好：cpu缓存层面
- 对于同样的数据，在排序过程中，堆排序算法的数据交换次数要>快速排序：有序度和逆序度，基于比较的排序算法：两个基本操作分别是比较和交换（移动）
总结
今天我们讲了堆这种数据结构。堆是一种完全二叉树。它最大的特性是:每个节点的值都大于等于(或小于等于)其子树节点 的值。因此，堆被分成了两类，大顶堆和小顶堆。
堆中比较重要的两个操作是插入一个数据和删除堆顶元素。这两个操作都要用到堆化。插入一个数据的时候，我们把新插入的 数据放到数组的最后，然后从下往上堆化;删除堆顶数据的时候，我们把数组中的最后一个元素放到堆顶，然后从上往下堆 化。这两个操作时间复杂度都是$O(\log n)$。
除此之外，我们还讲了堆的一个经典应用，堆排序。堆排序包含两个过程，建堆和排序。我们将下标从$\frac{n}{2}$到$1$的 节点，依次进行从上到下的堆化操作，然后就可以将数组中的数据组织成堆这种数据结构。接下来，我们迭代地将堆顶的元素 放到堆的末尾，并将堆的大小减一，然后再堆化，重复这个过程，直到堆中只剩下一个元素，整个数组中的数据就都有序排列 了。
讲堆的应用：如何快速获取到Top10最热门的搜索关键词
问题：假设现在我们有一个包含10亿个搜索关键词的日志文件，如何能快速获取到热⻔榜Top 10的搜索关键词呢?
堆几个重要的应用：优先级队列、求Top K和中位数
堆的应用一：优先级队列
- 实现优先级队列的方式很多，但是用堆来实现优先级队列是最直接、最高效的。堆和优先级队列非常相似，它们只是概念上的区分而已。
- 优先级队列的应用：很多数据结构和算法都要依赖它，比如：哈夫曼编码、图的最短路径、最小生成树算法等等。
java.util.PriorityQueue
合并有序小文件
情景：假设有100个小文件，文件存储的都是有序的字符串。如何把为一个大文件？
- 方案一（欠佳）：每次从这个100个文件，取一个字符串加入到数组中，然后循环遍历整个数组取出最小的字符串加入到大文件，并且从数组中删除这个字符串，从取出这个字符串（最小）中的文件再取出下一个字符串比较。
- 方案二（优秀）：我们使用小顶堆来解决，移除堆顶最小元素之后，每次从最小字符串的文件取出来的字符串加入到堆中。移除堆顶和插入数据，在堆的操作时间复杂度为O(logn)，因为堆是完全二叉树，操作跟树的高度有关。
高性能定时器
情景：假设我们有一个定时器，定时器有很多定时任务，有些定时任务的cron时间间隔很小(比如1s)，有些定时器任务的时间间隔很长。如何获取定时器下次执行任务的时间？
- 方案一（欠佳）：我们获取最小时间间隔的cron，然后每隔这个时间就遍历任务列表。但是这有下面问题。
- 问题一：大部分任务的约定时间隔距离当前时间还有很久，这样你每次扫描全表都是徒劳的，并且浪费系统资源。
- 问题二：每次都要扫描整个任务表，如果任务表很大的话，会非常耗时。
- 方案二（优化）：使用优先级队列来解决（小顶堆）,我们只需要取出堆顶，然后计算与当前时间的间隔T，在间隔T之后再移除堆顶元素执行。堆化后，重复上面的步骤。
堆的应用二：利用堆求Top K
情景：对于求top k的问题，可以抽象分为两类。一类是针对静态数据，一类是动态数据。无论静态还是动态都适合用堆来解决问题。
解决思路：维护大小为k的小顶堆就行了。
代码实现：
/**
* 描述:
* <p>
* 使用堆求解topk问题
* <p>
* 动态数据:在100个数据当中求top 10大的数据
* <p>
* 静态数据也使用该方法求解
*
* @author Noah
* @create 2019-11-18 14:07
*/
public class _29_TopK {
public static final int MAX_HEAP = 5;
public static int[] arr = new int[MAX_HEAP + 1];
public static int count = 0;
public static void main(String[] args) {
Random random = new Random();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 100; i++) {
int a = random.nextInt(100);
list.add(a);
buildHeap(a);
}
Object[] aa = list.toArray();
Arrays.sort(aa);
System.out.println(Arrays.toString(aa));
System.out.println(Arrays.toString(arr));
}
/**
* 构建一个大小${MAX_HEAP}的小顶堆，数组从下标1开始存储数据
*/
public static void buildHeap(int a) {
//堆中没有数据
if (arr == null || count < MAX_HEAP) {
insert(a);
return;
}
if (arr[1] >= a) {
return;
} else {
//1、移除堆顶元素。2、插入元素
removeMin();
insert(a);
}
}
public static void insert(int a) {
++count;
arr[count] = a;
//自下而上堆化
int i = count;
while (i / 2 > 0 && arr[i] < arr[i / 2]) { // 自下往上堆化
swap(arr, i, i / 2); // swap()函数作用:交换下标为i和i/2的两个元素
i = i / 2;
}
}
/**
* 移除堆顶元素
*
* @return
*/
public static int removeMin() {
int temp = arr[1];
//把最后元素移动到堆顶，然后自上而下堆化
arr[1] = arr[count];
//arr[count] = 0;
--count;
heapfiy();
return temp;
}
/**
* 自上而下堆化
*/
public static void heapfiy() {
int i = 1;
while (true) {
int minPos = i;
if (i * 2 <= count && arr[minPos] > arr[i * 2]) {
minPos = i * 2;
}
if (i * 2 + 1 <= count && arr[minPos] > arr[i * 2 + 1]) {
minPos = i * 2 + 1;
}
if (minPos == i) {
break;
}
swap(arr, minPos, i);
i = minPos;
}
}
public static void swap(int[] arr, int i, int pi) {
int temp = arr[i];
arr[i] = arr[pi];
arr[pi] = temp;
}
}
堆的应用三：利用堆求中位数
中位数：在一个有序集合当中，奇数的中位数就是$\frac{n}{2}+1$ ，偶数的中位数是$\frac{n}{2}$个和第$\frac{n}{2}+1$（折中选择一个）。
对于静态数据，我们直接把数组排序取值就完成了。
对于动态数据，我们需要借助堆这种结构来解决。
解题思路：我们需要维护两个堆，一个大顶堆，一个小顶堆。大顶堆中存储前半部分数据，小顶堆中存储后半部分数据，且小顶堆中的数 据都大于大顶堆中的数据。
- n是偶数，我们从小到大排序，那前$\frac{n}{2}$个数据存储在大顶堆中，后$\frac{n}{2}$个数据 存储在小顶堆中。
- n是奇数，情况是类似的，大顶堆就存储$\frac{n} {2}+1$个数据，小顶堆中就存储$\frac{n}{2}$个数据。
- 大顶堆中的堆顶元素就是我们要找的中位数。
- 并且我们要维护大小顶堆元素的个数各一半一半。如果不符合，我们就将一个堆中的数据移动到另一个堆，直到满足这个比例 。
图解：
如何快速求接口的99%响应时间？
- 数学科普：99百分数和99%的关系，如果将一组数据从小到大排列，这个99百分位数就是大于前面99%数据的那个数据。
- 假设有100个数据，分别是1，2，3，……，100，那99百分位数就是99，因为小于等 于99的数占总个数的99%。
- 我们再来看99%响应时间。如果有100个接口访问请求，每个接口请求的响应时间都不同，比如55毫秒、 100毫秒、23毫秒等，我们把这100个接口的响应时间按照从小到大排列，排在第99的那个数据就是99%响应时间，也叫99百 分位响应时间。
- 总结一下，如果有n个数据，将数据从小到大排列之后，99百分位数大约就是第n99%个数据，同类，80百分位数大约就 是第n80%个数据。
- 实现：假设当前总数据的个数是n，大顶堆中保存n99%个数据，小顶堆中保存n1%个数据。大顶堆堆顶的数据就是我们要找的99%响应时间。
- 如果这个 新插入的数据比大顶堆的堆顶数据小，那就插入大顶堆;如果这个新插入的数据比小顶堆的堆顶数据大，那就插入小顶堆。
- 为了保持大顶堆中的数据占99%，小顶堆中的数据占1%，在每次新插入数据之后，我们都要重新计算，这个时候大顶 堆和小顶堆中的数据个数，是否还符合99:1这个比例。如果不符合，我们就将一个堆中的数据移动到另一个堆，直到满足这个 比例。
- 代码：todo
问题解答
10亿个搜索关键字，在限定内存为1G的情况下，如何查找top 10关键字。
- 求top k问题使用堆的思路来解决。
- 限定内存情况下，通过数学计算公式，比如：1千万8字节int，占用80MB空间。去计算消耗内存的大小。
- 利用哈希算法实现数据的分片。
- 对分片的数据分别求top 10。再最终汇集求top 10
总结
我们今天主要讲了堆的几个重要的应用，它们分别是:优先级队列、求Top K问题和求中位数问题。
优先级队列是一种特殊的队列，优先级高的数据先出队，而不再像普通的队列那样，先进先出。实际上，堆就可以看作优先级 队列，只是称谓不一样罢了。
求Top K问题又可以分为针对静态数据和针对动态数据，只需要利用一个堆，就可以做到非常高 效率的查询Top K的数据。
求中位数实际上还有很多变形，比如求99百分位数据、90百分位数据等，处理的思路都是一样的， 即利用两个堆，一个大顶堆，一个小顶堆，随着数据的动态添加，动态调整两个堆中的数据，最后大顶堆的堆顶元素就是要求 的数据。
Todo：讲图的表示：如何存储微博、微信等社交网络中的好友关系
需要完成的事情
Todo：讲深度和广度优先搜索：如何找出社交网络中的三度好友关系
需要完成的事情
讲字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配
字符串匹配算法很多，今天讲比较简单和容易理解的BF算法和RK算法。后面讲的BM算法和KMP算法比较难理解、但高效。
前面讲的是单模式串匹配算法：也就是一个串跟一个串进行比较。还有一种就是多模式串匹配算法：在一个串中同时查找多个串，它们分别是Trie树和AC自动机。
RK算法是BF算法的改进，巧妙借助我们之前讲过的哈希算法。
主串和模式串概念定义：我们在字符串A中查找字符串B，那字符串A就是主串，字符串B就是模式串。我们把主串的⻓度记作n，模式串的⻓ 度记作m。因为我们是在主串中查找模式串，所以n>m
BF算法
BF算法概念：BF算法是Brute Force的缩写，又名暴力匹配算法，也叫朴素匹配算法。
概括：我们在主串中，检查起始位置分别是 0、1、2…n-m且⻓度为m的n-m+1个子串，看有没有跟模式串匹配的。
图解：BF算法过程
分析：尽管BF的算法的时间复杂度很高O(n*m)，但是在实际开发中还是使用比较多的。
- 在实际开发的过程中，主串和模式串的长度都不会太长。所以即使时间复杂度为O(n*m)，但是实际要比这个高效多。
- BF算法：思路简单，代码实现容易。
RK算法
- RK算法概念：全称是Rabin-Karp算法，分别是这两位作者创建的。是BF算法的升级版。
- 思路：我们通过哈希算法对主串中的n-m+1个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。 如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了(这里先不考虑哈希冲突的问题，后面我们会讲 到)
- 解决了BF算法模式串要一个个字母跟主串对比的耗时操作。
- 有没有方法可以提高哈希算法计算子串哈希值的效率呢?
- 利用进制表示十进制的优化方法（取值会过大，超过范围）
- 每个字符累加（字符代表是素数（冲突概率低）、而非自然数）
- 哈希冲突的时候，还要比较字符串本身
- 分析：所以RK算法的时间复杂度为O(n)
总结
BF算法是最简单、粗暴的字符串匹配算法，它的实现思路是，拿模式串与主串中是所有子串匹配，看是否有能匹配的子串。 所以，时间复杂度也比较高，是O(n*m)，n、m表示主串和模式串的⻓度。不过，在实际的软件开发中，因为这种算法实现简 单，对于处理小规模的字符串匹配很好用。
RK算法是借助哈希算法对BF算法进行改造，即对每个子串分别求哈希值，然后拿子串的哈希值与模式串的哈希值比较，减少 了比较的时间。所以，理想情况下，RK算法的时间复杂度是O(n)，跟BF算法相比，效率提高了很多。不过这样的效率取决于 哈希算法的设计方法，如果存在冲突的情况下，时间复杂度可能会退化。极端情况下，哈希算法大量冲突，时间复杂度就退化 为O(n*m)。
Todo：讲字符串匹配基础（中）：如何实现文本编辑器中的查找功能
BF算法和RK算法在某些极端的情况下，性能会退化很严重。如何实现一个工业级别的字符串匹配算法呢？
对于查找功 能是重要功能的软件来说，比如一些文本编辑器，它们的查找功能都是用哪种算法来实现的呢?有没有比BF算法和RK算法更 加高效的字符串匹配算法呢?