学习笔记

• 关联性：HashTable + 拉链式存储重复元素
• 概念：一个很长的二进制向量和一系列随机映射函数。可以用于检索一个元素是否在一个集合中。
• 优点： 空间和查询时间远超过一般算法
• 缺点：一定的误识别率和删除困难
• 最外面当缓存使用

• 实现： 布隆过滤器的原理和实现
• 应用： 解决缓存击穿、垃圾邮件识别、集合判重 使用BloomFilter布隆过滤器解决缓存击穿、垃圾邮件识别、集合判重
• 要素：大小、替换策略 O(1) 查询 修改 更新
• 最少最近使用原则 least frequertly used
• 最少频次使用原则 least frequert recent used
• 案例：

1. 比特币网络
2. 分布式系统 - Hadoop
3. Redis缓存
4. 垃圾邮件、评论等等过滤

[十大经典排序算法](https://www.cnblogs.com/onepixel/p/ 7674659.html) 十大经典排序算法 9 种经典排序算法可视化动画 6 分钟看完 15 种排序算法动画展示

• 分类：

1. 比较类排序：通过比较来决定元素间相对次序，由于时间复杂度不能突破O(nlogn),非线性比较类排序

• 交换排序 冒泡排序、快速排序

1. 快速排序 取标杆p, 小于的放p左侧，大的在右侧，对左右子数组递归快排，后归并

• 插入排序 简单插入排序、希尔排序
• 选择排序 简单选择排序、堆排序
• 归并排序 二路归并排序、多路归并排序

2. 非比较类排序：不通过比较来决定元素间相对次序。可以突破基于比较排序大时间下界，可以线性时间，线性比较类排序

• 计数排序
• 桶排序
• 基数排序