侧边栏壁纸
博主头像
乌拉队长博主等级

你只管努力,其余的交给命运

  • 累计撰写 122 篇文章
  • 累计创建 34 个标签
  • 累计收到 31 条评论

目 录CONTENT

文章目录

数据结构部分知识点总结

乌拉队长
2022-04-26 / 0 评论 / 0 点赞 / 444 阅读 / 1,009 字

数据结构部分知识点总结

红黑树

特点

  1. 每个节点非红即黑;
  2. 根节点总是黑色的;
  3. 每个叶子节点都是黑色的空节点(NIL节点);
  4. 如果节点是红色的,则它的子节点必须是黑色的(反之不一定);
  5. 从根节点到叶节点或空子节点的每条路径,必须包含相同数目的黑色节点(即相同的黑色高度)。

应用

TreeMap、TreeSet以及JDK1.8的HashMap底层都用到了红黑树。

强烈推荐阅读以下两篇文章:

布隆过滤器

原理

当一个元素加入布隆过滤器中的时候,会进行如下操作:

  1. 使用布隆过滤器中的哈希函数对元素值进行计算,得到哈希值(有几个哈希函数得到几个哈希值)。
  2. 根据得到的哈希值,在位数组中把对应下标的值置为 1。

当我们需要判断一个元素是否存在于布隆过滤器的时候,会进行如下操作:

  1. 对给定元素再次进行相同的哈希计算;
  2. 得到值之后判断位数组中的每个元素是否都为 1,如果值都为 1,那么说明这个值在布隆过滤器中,如果存在一个值不为 1,说明该元素不在布隆过滤器中。

综上,我们可以得出:布隆过滤器说某个元素存在,小概率会误判。布隆过滤器说某个元素不在,那么这个元素一定不在。

布隆过滤器使用场景

  1. 判断给定数据是否存在:比如判断一个数字是否存在于包含大量数字的数字集中(数字集很大,5 亿以上!)、 防止缓存穿透(判断请求的数据是否有效,避免直接绕过缓存请求数据库)等等、邮箱的垃圾邮件过滤、黑名单功能等等。
  2. 去重:比如爬给定网址的时候对已经爬取过的 URL 去重。

常见排序算法

  1. 插入排序:直接插入排序、二分法插入排序、希尔排序
  2. 选择排序:直接选择排序、堆排序
  3. 交换排序:冒泡排序、快速排序
  4. 归并排序
  5. 基数排序

时间复杂度

排序方法时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性复杂性
直接插入排序O(n2)O(n2)O(n)O(1)稳定简单
希尔排序O(nlogn)O(n2)O(n1.3)O(1)不稳定较复杂
直接选择排序O(n2)O(n2)O(n2)O(1)不稳定简单
堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定较复杂
冒泡排序O(n2)O(n2)O(n)O(1)稳定简单
快速排序O(nlogn)O(n2)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)稳定较复杂
0

评论区