# 数据结构部分知识点总结 ## 红黑树 ### <u>特点</u> 1. 每个节点非红即黑； 2. 根节点总是黑色的； 3. 每个叶子节点都是黑色的空节点（NIL节点）； 4. 如果节点是红色的，则它的子节点必须是黑色的（反之不一定）； 5. 从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）。 ### <u>应用</u> TreeMap、TreeSet以及JDK1.8的HashMap底层都用到了红黑树。 **强烈推荐**阅读以下两篇文章： - [漫画：什么是红黑树？](https://juejin.im/post/5a27c6946fb9a04509096248#comment) - [《红黑树深入剖析及Java实现》](https://zhuanlan.zhihu.com/p/24367771) ## 布隆过滤器 ### <u>原理</u> **当一个元素加入布隆过滤器中的时候，会进行如下操作：** 1. 使用布隆过滤器中的哈希函数对元素值进行计算，得到哈希值（有几个哈希函数得到几个哈希值）。 2. 根据得到的哈希值，在位数组中把对应下标的值置为 1。 **当我们需要判断一个元素是否存在于布隆过滤器的时候，会进行如下操作：** 1. 对给定元素再次进行相同的哈希计算； 2. 得到值之后判断位数组中的每个元素是否都为 1，如果值都为 1，那么说明这个值在布隆过滤器中，如果存在一个值不为 1，说明该元素不在布隆过滤器中。 综上，我们可以得出：**布隆过滤器说某个元素存在，小概率会误判。布隆过滤器说某个元素不在，那么这个元素一定不在。** ### <u>布隆过滤器使用场景</u> 1. 判断给定数据是否存在：比如判断一个数字是否存在于包含大量数字的数字集中（数字集很大，5 亿以上！）、 防止缓存穿透（判断请求的数据是否有效，避免直接绕过缓存请求数据库）等等、邮箱的垃圾邮件过滤、黑名单功能等等。 2. 去重：比如爬给定网址的时候对已经爬取过的 URL 去重。 ## 常见排序算法 1. 插入排序：直接插入排序、二分法插入排序、希尔排序 2. 选择排序：直接选择排序、堆排序 3. 交换排序：冒泡排序、快速排序 4. 归并排序 5. 基数排序 ### 时间复杂度 | 排序方法 | 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 | 复杂性 | | ------------ | ---------------- | ---------------- | ---------------- | ---------- | ------ | ------ | | 直接插入排序 | O(n^2^) | O(n^2^) | O(n) | O(1) | 稳定 | 简单 | | 希尔排序 | O(nlogn) | O(n^2^) | O(n^1.3^) | O(1) | 不稳定 | 较复杂 | | 直接选择排序 | O(n^2^) | O(n^2^) | O(n^2^) | O(1) | 不稳定 | 简单 | | 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 | 较复杂 | | 冒泡排序 | O(n^2^) | O(n^2^) | O(n) | O(1) | 稳定 | 简单 | | 快速排序 | O(nlogn) | O(n^2^) | O(nlogn) | O(nlogn) | 不稳定 | 较复杂 | | 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 | 较复杂 | | 基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(n+r) | 稳定 | 较复杂 |