分类

支持动态数据高效操作：跳表、散列表、红黑树、字典树

以空间换时间：

搜索算法：回溯算法

数据结构

最大最小堆

• 主要意义在于能够 O(1) 时间找到当前最大，最小值，且取走后，维护整个堆的复杂度只有 O(logn)
• 堆的实践用途不在于排序，而是调度算法中，比如优先级调度，最长等待时间调度

哈希表

• 主要意义在于 O(1) 的快速查找，但是由于哈希冲突的原因，性能不稳定

应用场景

1. 数组

• 数组批量集中删除有利于减少删除操作导致的数据搬迁，也是 JVM 标记清除垃圾回收算法的核心思想

2. 链表

• 通过链表和散列表，可以实现 LRU 缓存淘汰策略

3. 栈

• 浏览器的前进后退：使用两个栈即可实现

4. 队列

• 线程池处理请求：利用栈进行排队调度

5. 跳表

• Redis 有序集合的实现使用到了跳表

6. 散列表

• Word 中的单词拼写检查功能：使用散列表存储整个英文字典，用户输入时，在散列表中查找该单词，如未查找则视为非法单词

7. 堆

• 优先级队列：合并 100 个有序小文件，高性能定时器
• Top K
• 求中位数

8. 图

• 存储微博（有向图）、微信（无向图）的好友关系

9. 字典树

• 搜索引擎搜索关键词提示
• IDE 中的代码自动补全

10. 红黑树

• Linux epoll
• Linux Completely Fair Sheduler

算法

1. 二分查找

• 1000 万个数据，每个数据 8 字节，快速判断某个数据是否出现在这 1000 万 数据中，要求内存不超过 100 MB
• 给定 IP 范围与归属对应表，如何快速定位 IP 地址归属：将对应表按起始 IP 排序，查找最后一个起始 IP 小于等于目标 IP 的区间

2. 哈希算法

• 快速判断图片是否在图库中，海量图库（如 1 亿）
• 会话粘滞（Session Sticky）的负载均衡算法，即同一个客户端上，一次会话上的所有请求路由到同一个服务器上
• 统计关键词被搜索次数，1 T 的日志文件
• 分布式系统结点部署频繁变化 -> 一致性哈希算法

3. 分治算法

• 海量数据处理，如 MapReduce 的本质思想

贪心算法

• 区间覆盖问题
• 霍夫曼编码
• Prim 和 Kruskal 最小生成树算法
• Dijkstra 单源最短路径算法

综合类问题

1. 10 亿个搜索关键词的日志文件，如何快速获取 Top 10 的搜索关键词

• 哈希算法 + 散列表 + 堆