布隆过滤器（Bloom Filter）：是一个超大的位数组和几个哈希函数，同一个数据分别经过不同的 hash 函数进行散列，得到的值映射位数组中的一位。

• 将要添加的元素给k个哈希函数
• 得到对应于位数组上的k个位置
• 将这k个位置设为1

• 将要查询的元素给k个哈希函数
• 得到对应于位数组上的k个位置
• 如果k个位置有一个为0，则肯定不在集合中
• 如果k个位置全部为1，则可能在集合中

迅速判断一个元素是否在一个集合中。并且特点是：

• 如果布隆过滤器判定存在，则是否真正存在需要做进一步处理。
• 如果布隆过滤器 判定不存在，则一定不在 给定集合。

利用这个性质，可以用在工程中的很多场景：

• 网页爬虫对URL的去重，避免爬取相同的URL地址；

• 反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱（同理，垃圾短信）；

• 缓存击穿，将已存在的缓存放到布隆中，当黑客访问不存在的缓存时迅速返回避免缓存及DB挂掉。

LRU全称是Least Recently Used，即最近最久未使用的意思。

LRU算法的设计原则是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。是缓存中一种常见的机制。

• 随机算法（Rand）：

  随机法是随机地确定替换的存储块。设置一个随机数产生器，依据所产生的随机数，确定替换块。这种方法简单、易于实现，但命中率比较低。

• 先进先出算法（FIFO, First In First Out）：

  先进先出法是选择那个最先调入的那个块进行替换。当最先调入并被多次命中的块，很可能被优先替换，因而不符合局部性规律。这种方法的命中率比随机法好些，但还不满足要求。

• 最久未使用算法（LRU, Least Recently Used）

  LRU法是依据各块使用的情况， 总是选择那个最长时间未被使用的块替换。这种方法比较好地反映了程序局部性规律。

• 最不经常使用算法（LFU, Least Frequently Used）：

  将最近一段时期内，访问次数最少的块替换出Cache。

实现原理：Map + 双向链表

• Map：可以用 O(1) 的效率获取 cache
• 使用双向链表用于淘汰，用 O(1) 的时间快速移动元素。

比较类排序：是指通过比较元素来决定元素之间的顺序，由于其 时间复杂度不能突破 O(nlogn)，因此也称为非线性时间比较类排序

• 交换排序：
  • 冒泡排序：比较相邻元素，每次最大值放于最后
  • 快速排序：找一个基准值，小于基准值调整到左侧，大于基准值放于右侧（每次基本有序，然后递归调整左右部分）
• 插入排序
  • 简单插入：将前面部分作为有序子序列，对后面进行排序，每个元素找到对应的位置，进行调整（每次有很多次元素移动）
  • 希尔排序：又称为步长递减排序，是插入排序的改良版。
• 选择排序
  • 简单选择：每次找剩余元素中最小元素放到指定位置，按照顺序交换元素（与插入区别，选择是指定位置找元素，插入是指定元素，找位置）。
  • 堆排序：根据堆的性质进行排序，构建大顶堆或小顶堆进行排序。
• 归并排序
  • 二路归并：划分为两部分
  • 多路归并：划分多个子部分

非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

• 计数排序
• 基数排序

• 稳定性：是否破坏（相同值）原有元素顺序
  • 稳定算法：如果 i 原来在 j 前面，并且 i = j，排序后，i 仍然在 j 前面。
  • 不稳定算法：如果 i 原来在 j 前面，并且 i = j，排序后，i 可能会在 j 后面。
• 事件复杂度：
• 空间复杂度：

升维思想

无捷径，多练习，多总结