算法类

1. Aho-Corasick算法

   1	1. 进行全文匹配关键字，比如：敏感词匹配。需要预处理数据

2. Boyer- Moore算法

   1	1. 字符串查找。需要预处理数据

3. KMP算法

   1	1. 字符串查找。需要预处理数据

4. Manacher算法

   1	1. 中心扩展，计算最长回文子串。需要辅助空间

树(字符串类)

1. 字典树(前缀树)

   1	1. 利用字符串的公共前缀来减少无谓的字符串比较以达到提高查询效率的目的

2. 后缀树

   1	1. 快速解决很多关于字符串的问题；百度上说，具体应用待学习

编码类

1. 霍夫曼编码(哈夫曼树)

   1	1. 压缩数据存储，需要辅助空间。

树遍历构造

1. 二叉树遍历：前序，中序，后序，Morris
2. 树构造：状态机

知识界限

• 个人理解，以下内容在于多多学习，学习其中思想理念，能够在使用中想到有什么解决方案。
  

数据一致性协议

• raft协议图解网站
• Paxos协议

使用

• 实际使用中会有参考然后重新实现或者变种

1. zab协议，zookeeper使用。根据paxos协议而来

定义

问题描述：

• 字典树(前缀树)
  Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

1. Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

   1 2 3 4

   它有3个基本性质： 根节点不包含字符，除根节点外每一个节点都只包含一个字符。 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。 每个节点的所有子节点包含的字符都不相同。

2. Aho-Corasick算法

应用

1. java敏感词过滤实现

定义

1. 布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。

• 优点

  1 2	相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数。另外, Hash函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。 布隆过滤器可以表示全集，其它任何数据结构都不能。

• 缺点

  1 2 3

  但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加，误算率随之增加。常见的补救办法是建立一个小的白名单，存储那些可能被误判的元素。但是如果元素数量太少，则使用散列表足矣。 另外，一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位列阵变成整数数组，每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全的删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。 在降低误算率方面，有不少工作，使得出现了很多布隆过滤器的变种。

应用

1. 网页URL的去重，垃圾邮件的判别，集合重复元素的判别，查询加速（比如基于key-value的存储系统）、数据库防止查询击穿， 使用BloomFilter来减少不存在的行或列的磁盘查找。

• 算法讲解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

算法解决的问题是求最长回文子串。
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1. 类似解法还有：中心扩散法。该方法时间复杂度为O(n2)。马拉车算法降低到n

mysql知识点

先放出友情链接

• B树 b+ lsm
• mysql索引讲解
• mysql全文索引处理
• mysql页分裂
• B+树可以存储多少行数据
• mysql全篇总结

事务的说明探讨

参考：1

mysql知识点

1. mysql事务实现:MVCC概念

2. 组合索引：innodb 索引会带上当前的索引，同时加上主键Id,order 也会用索引

3. mysql order by 工作过程:文章1 | 文章2

   1 2 3 4 5

   上诉排序问题：sql为:select city,name,age from t where city in ('杭州','苏州') order by name limit 1000;这时候怎么办？ 1： 组合索引的排序规则是city_name 这时候city=杭州 但是name排序不对。 2： 业务上分别拆分成2条:select city,name,age from t where city='杭州' order by name limit 1000; and select city,name,age from t where city='苏州' order by name limit 1000; 然后再业务代码中进行name排序取出前1000. 也是一种方法

4. mysql explan 中type含义: 文章

5. B树 B+数区别 :文章

   1 2 3 4 5 6 7 8

   B树和B+树的区别 这都是由于B+树和B具有这不同的存储结构所造成的区别，以一个m阶树为例。 1. 关键字的数量不同；B+树中分支结点有m个关键字，其叶子结点也有m个，其关键字只是起到了一个索引的作用，但是B树虽然也有m个子结点，但是其只拥有m-1个关键字。 2. 存储的位置不同；B+树中的数据都存储在叶子结点上，也就是其所有叶子结点的数据组合起来就是完整的数据，但是B树的数据存储在每一个结点中，并不仅仅存储在叶子结点上。 3. 分支结点的构造不同；B+树的分支结点仅仅存储着关键字信息和儿子的指针（这里的指针指的是磁盘块的偏移量），也就是说内部结点仅仅包含着索引信息。 4. 查询不同；B树在找到具体的数值以后，则结束，而B+树则需要通过索引找到叶子结点中的数据才结束，也就是说B+树的搜索过程中走了一条从根结点到叶子结点的路径。

红黑树

1. 友情博客链接

• 重点解读
  1. 红黑树是近视平衡。插入 删除比平衡二叉树要快，相对查找要略低。但是相对于其他树来说稳定。在极端情况下也不会蜕变为单边树
  2. 红黑树中包含最多黑色节点的路径不会超过 log2n，所以加入红色节点之后，最长路径不会超过 2log2n，也就是说，红黑树的高度近似 2log2n
  3. 高度和查找性能成反比。高度高查找慢
     

redis的zset为何用跳表，不用红黑树

1. Redis 中的有序集合支持的核心操作主要有以下几个：

   1 2 3 4 5 6 7 8 9

   1.插入一个数据 1.删除一个数据 1.查找一个数据 1.按照区间查找数据 1.迭代输出有序序列 其中，插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度和跳表是一样的。 但是，按照区间查找数据这个操作，红黑树的效率没有跳表高。跳表可以在 O(logn) 时间复杂度定位区间的起点，然后在原始链表中顺序向后查询就可以了，这样非常高效。 此外，相比于红黑树，跳表还具有代码更容易实现、可读性好、不容易出错、更加灵活等优点，因此 Redis 用跳表来实现有序集合

二叉树遍历

理解二叉树中4种遍历方法

演示网站

DataStructureVisualizations

一个数据可视化和算法可视化的网站，用它可以生成各种各样的数据结构，模拟它们添加和删除的过程，而且还可以用它来演示算法的执行过程。

1. 地址

VisuAlgo

此网站包含了更多的算法，这个从首页就可以看出来，不仅如此，它还支持关键字检索

1. 地址

algorithm-visualizer

此网站也支持很多算法，并且此网站提供算法的具体代码实现，它支持的语言有：Java，C++，JS 等，还有控制台也会输出整个执行的过程，能帮你更好的理解算法

1. 地址