数据结构与算法

这是一篇关于数据结构与算法的思维导图，讲述了算法思想、字符串、链表、数组、哈希表、队列、算法、实际解决方案等。

数据结构与算法

• 字符串
  • KMP算法
• 链表
  • 单链表
  • 双向链表
    • Nginx
  • 跳表
    • 应用
      • 定时器
      • Redis
• 数组
  • 应用
    • Nginx
    • Redis
• 哈希表
  • 布隆过滤器bloomfilter
  • 避免冲突
    • 拉链法
    • 开放寻址法
      • 双重hash
• 堆
• 栈stack
• 队列queue
  • 双向队列dqueue
  • 优先级队列
• 树
  • 术语
  • 二叉树
  • 平衡二叉树BST
  • 红黑树
    • 6大特性
    • 优缺点
    • 操作
    • 代码实现
    • 应用
      • Nginx
  • B树/B-树
  • B+树
  • 字典树
• 图
  • 预热
    • 应用背景（哪些场景需要）
      • 最短路径
  • 学习
    • 分类
      • 无向图
      • 有向图
      • 权重图（有向/无向）
    • 概念
      • 顶点集合
      • 边集合
      • 度
        • 出度
        • 入度
    • 存储
      • 顶点存储
        • 数组
      • 边存储
        • 邻接矩阵（二位数组）
        • 邻接表
    • 实现
      • 封装
      • 操作
        • 创建（构造）
        • 销毁（析构）
        • 边增加、删除、获取信息
        • 顶点增加、删除、获取信息
        • 遍历
        • 获取顶点的出/入度
        • 判断是否连通（有环）
    • 遍历
      • 深度优先搜索
      • 广度优先搜索
      • Dijkstra算法（迪杰斯特拉）
• 实际解决方案
  • 海量数据去重（字符串）
    • 背景（应用场景）
      • URL去重
      • 垃圾邮件判别
      • 防止缓存击穿
      • 单词拼写检查
    • 解决方案
      • 红黑树rbtree
        • set/map
      • 哈希表hashtable
        • unordered_set/unordered_map
      • 布隆过滤器
        • 背景
          • 解决字符串比较问题
        • 定义
          • 概率型数据结构，特点是高效插入查询，明确判断字符串一定不存在或可能存在
        • 原理（本质）
          • 插入时，使用k个hash函数对其进行映射到位图上k个点，并置1；检索时，使用k个hash函数检测位图上k个点是否全为1，若全为1则可能存在，若存在一个为0则一定不存在
          • 位图（bit数组）存储
          • 使用k个hash函数
        • 优缺点（存在对比性）
          • 相比传统查询结构（红黑树、哈希表）更加高效，占用空间更小
          • 结果存在概率性，但误差可控
          • 不支持删除操作
            • 位图上的槽位只有0/1两种状态，当为1时无法明确被设置了几次，即不知道被哪些字符串映射或被哪些hash函数映射而来
        • 实际应用
          • 存储多少元素？
          • 如何控制假阳率（误差率）？
          • 如何确定位图的大小（存储空间）？
          • 如何确定hash函数个数？
          • 套用公式（数学推导）
            • n -- 布隆过滤器中元素的个数 p -- 假阳率，在0-1之间，如0.0000001 m -- 位图所占空间 k -- hash函数的个数 公式如下： n = ceil(m / (-k / log(1 - exp(log(p) / k)))) p = pow(1 - exp(-k / (m / n)), k) m = ceil((n * log(p)) / log(1 / pow(2, log(2)))); k = round((m / n) * log(2));
            • 使用确定的元素个数和假阳率确定存储空间大小和hash函数的个数
          • 如何选择k个hash函数？
            • 使用同一hash函数，对旧hash值添加不同偏移量重新计算hash
              • // 采用一个hash函数，给hash传不同的种子偏移值 // #define MIX_UINT64(v) ((uint32_t)((v>>32)^(v))) uint64_thash1=MurmurHash2_x64(key, len, Seed); uint64_thash2=MurmurHash2_x64(key, len, MIX_UINT64(hash1)); for (i=0; i<k; i++) // k 是hash函数的个数 { Pos[i] = (hash1+i*hash2) %m; // m 是位图的大小 } // 通过这种方式来模拟 k 个hash函数跟我们前面开放寻址法双重hash是一样的思路
            • 类似hash避免冲突”开放寻址法“中的双重hash法
        • 操作
          • 构建
          • 销毁
          • 插入
          • 查询
          • 删除
          • 时间复杂度
        • 实际案例
          • Squid 网页代理缓存服务器
          • Venti 文档存储系统
          • SPIN 模型检测器
          • Google Chrome浏览器
          • Key-Value系统
• 算法
  • 排序算法
    • 冒泡排序
      • O(n2)
    • 快速排序
    • 插入排序
    • 希尔排序
    • 归并排序
    • 桶排序
    • 堆排序
    • 类型
  • 查找算法
    • 直接查找
      • O(n)
    • 二分查找
      • O(lgN)
  • 贪心算法
  • 递归、迭代算法
• 算法思想
  • 贪心思想
• 算法思考过程
  • 思路步骤
  • 代码实现
  • 时间/空间复杂度
  • 应用场景