（Toc generated by simple-php-github-toc ）
数据结构
队列
集合
链表、数组
字典、关联数组
栈
树
二叉树
每个节点最多有两个叶子节点。
完全二叉树
- 《完全二叉树》
- 叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。
平衡二叉树
左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
二叉查找树（BST）
二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree）。
红黑树
B，B+，B*树
MySQL是基于B+树聚集索引组织表
LSM（Log-Structured Merge-Trees）和 B+ 树相比，是牺牲了部分读的性能来换取写的性能(通过批量写入)，实现读写之间的平衡。
Hbase、LevelDB、Tair（Long DB）、nessDB 采用 LSM 树的结构。LSM可以快速建立索引。
- 《LSM树 VS B+树》
- B+ 树读性能好，但由于需要有序结构，当key比较分散时，磁盘寻道频繁，造成写性能较差。
- LSM 是将一个大树拆分成N棵小树，先写到内存（无寻道问题，性能高），在内存中构建一颗有序小树（有序树），随着小树越来越大，内存的小树会flush到磁盘上。当读时，由于不知道数据在哪棵小树上，因此必须遍历（二分查找）所有的小树，但在每颗小树内部数据是有序的。
- 《LSM树（Log-Structured Merge Tree）存储引擎》
- 极端的说，基于LSM树实现的HBase的写性能比MySQL高了一个数量级，读性能低了一个数量级。
- 优化方式：Bloom filter 替代二分查找；compact 小数位大树，提高查询性能。
- Hbase 中，内存中达到一定阈值后，整体flush到磁盘上、形成一个文件（B+数），HDFS不支持update操作，所以Hbase做整体flush而不是merge update。flush到磁盘上的小树，定期会合并成一个大树。
BitSet
经常用于大规模数据的排重检查。
常用算法
排序、查找算法
选择排序
冒泡排序
插入排序
快速排序
希尔排序
TODO
堆排序
计数排序
桶排序
基数排序
按照个位、十位、百位、…依次来排。
二分查找
布隆过滤器
常用于大数据的排重，比如email，url 等。
核心原理：将每条数据通过计算产生一个指纹（一个字节或多个字节，但一定比原始数据要少很多），其中每一位都是通过随机计算获得，在将指纹映射到一个大的按位存储的空间中。注意：会有一定的错误率。
优点：空间和时间效率都很高。
缺点：随着存入的元素数量增加，误算率随之增加。
字符串比较
KMP 算法
KMP：Knuth-Morris-Pratt算法（简称KMP）
核心原理是利用一个“部分匹配表”，跳过已经匹配过的元素。
深度优先、广度优先
贪心算法
回溯算法
剪枝算法
动态规划
朴素贝叶斯
推荐算法
最小生成树算法
最短路径算法
并发
Java 并发
多线程
线程安全
一致性、事务
事务 ACID 特性
事务的隔离级别
MVCC
锁
Java中的锁和同步类
公平锁 & 非公平锁
公平锁的作用就是严格按照线程启动的顺序来执行的，不允许其他线程插队执行的；而非公平锁是允许插队的。
- 《公平锁与非公平锁》
- 默认情况下 ReentrantLock 和 synchronized 都是非公平锁。ReentrantLock 可以设置成公平锁。
悲观锁
悲观锁如果使用不当（锁的条数过多），会引起服务大面积等待。推荐优先使用乐观锁+重试。
乐观锁 & CAS
ABA 问题
由于高并发，在CAS下，更新后可能此A非彼A。通过版本号可以解决，类似于上文Mysql 中提到的的乐观锁。
CopyOnWrite容器
可以对CopyOnWrite容器进行并发的读，而不需要加锁。CopyOnWrite并发容器用于读多写少的并发场景。比如白名单，黑名单，商品类目的访问和更新场景，不适合需要数据强一致性的场景。
RingBuffer
可重入锁 & 不可重入锁
- 《可重入锁和不可重入锁》
- 通过简单代码举例说明可重入锁和不可重入锁。
- 可重入锁指同一个线程可以再次获得之前已经获得的锁。
- 可重入锁可以用户避免死锁。
- Java中的可重入锁：synchronized 和 java.util.concurrent.locks.ReentrantLock
- 《ReenTrantLock可重入锁（和synchronized的区别）总结》
- synchronized 使用方便，编译器来加锁，是非公平锁。
- ReenTrantLock 使用灵活，锁的公平性可以定制。
- 相同加锁场景下，推荐使用 synchronized。
互斥锁 & 共享锁
互斥锁：同时只能有一个线程获得锁。比如，ReentrantLock 是互斥锁，ReadWriteLock 中的写锁是互斥锁。
共享锁：可以有多个线程同时或的锁。比如，Semaphore、CountDownLatch 是共享锁，ReadWriteLock 中的读锁是共享锁。
死锁
操作系统
计算机原理
CPU
多级缓存
典型的 CPU 有三级缓存，距离核心越近，速度越快，空间越小。L1 一般 32k，L2 一般 256k，L3 一般12M。内存速度需要200个 CPU 周期，CPU 缓存需要1个CPU周期。
进程
TODO
线程
协程
Linux
设计模式
设计模式的六大原则
- 《设计模式的六大原则》
- 开闭原则：对扩展开放,对修改关闭，多使用抽象类和接口。
- 里氏替换原则：基类可以被子类替换，使用抽象类继承,不使用具体类继承。
- 依赖倒转原则：要依赖于抽象,不要依赖于具体，针对接口编程,不针对实现编程。
- 接口隔离原则：使用多个隔离的接口,比使用单个接口好，建立最小的接口。
- 迪米特法则：一个软件实体应当尽可能少地与其他实体发生相互作用，通过中间类建立联系。
- 合成复用原则：尽量使用合成/聚合,而不是使用继承。
23种常见设计模式
应用场景
- 《细数JDK里的设计模式》
- 结构型模式：
- 适配器：用来把一个接口转化成另一个接口，如 java.util.Arrays#asList()。
- 桥接模式：这个模式将抽象和抽象操作的实现进行了解耦，这样使得抽象和实现可以独立地变化，如JDBC；
- 组合模式：使得客户端看来单个对象和对象的组合是同等的。换句话说，某个类型的方法同时也接受自身类型作为参数，如 Map.putAll，List.addAll、Set.addAll。
-
| 装饰者模式：动态的给一个对象附加额外的功能，这也是子类的一种替代方式，如 java.util.Collections#checkedList |
Map |
Set |
SortedSet |
SortedMap。 |
- 享元模式：使用缓存来加速大量小对象的访问时间，如 valueOf(int)。
- 代理模式：代理模式是用一个简单的对象来代替一个复杂的或者创建耗时的对象，如 java.lang.reflect.Proxy
- 创建模式:
- 抽象工厂模式：抽象工厂模式提供了一个协议来生成一系列的相关或者独立的对象，而不用指定具体对象的类型，如 java.util.Calendar#getInstance()。
- 建造模式(Builder)：定义了一个新的类来构建另一个类的实例，以简化复杂对象的创建，如：java.lang.StringBuilder#append()。
- 工厂方法：就是 一个返回具体对象的方法，而不是多个，如 java.lang.Object#toString()、java.lang.Class#newInstance()。
- 原型模式：使得类的实例能够生成自身的拷贝、如：java.lang.Object#clone()。
- 单例模式：全局只有一个实例，如 java.lang.Runtime#getRuntime()。
- 行为模式：
- 责任链模式：通过把请求从一个对象传递到链条中下一个对象的方式，直到请求被处理完毕，以实现对象间的解耦。如 javax.servlet.Filter#doFilter()。
- 命令模式：将操作封装到对象内，以便存储，传递和返回，如：java.lang.Runnable。
- 解释器模式：定义了一个语言的语法，然后解析相应语法的语句，如，java.text.Format，java.text.Normalizer。
- 迭代器模式：提供一个一致的方法来顺序访问集合中的对象，如 java.util.Iterator。
- 中介者模式：通过使用一个中间对象来进行消息分发以及减少类之间的直接依赖，java.lang.reflect.Method#invoke()。
- 空对象模式：如 java.util.Collections#emptyList()。
- 观察者模式：它使得一个对象可以灵活的将消息发送给感兴趣的对象，如 java.util.EventListener。
- 模板方法模式：让子类可以重写方法的一部分，而不是整个重写，如 java.util.Collections#sort()。
- 《Spring-涉及到的设计模式汇总》
- 《Mybatis使用的设计模式》
单例模式
责任链模式
TODO
MVC
- 《MVC 模式》
- 模型(model)－视图(view)－控制器(controller)
IOC
- 《理解 IOC》
- 《IOC 的理解与解释》
- 正向控制：传统通过new的方式。反向控制，通过容器注入对象。
- 作用：用于模块解耦。
- DI：Dependency Injection，即依赖注入，只关心资源使用，不关心资源来源。
AOP
UML
微服务思想
康威定律
- 《微服务架构的理论基础 - 康威定律》
- 定律一：组织沟通方式会通过系统设计表达出来，就是说架构的布局和组织结构会有相似。
- 定律二：时间再多一件事情也不可能做的完美，但总有时间做完一件事情。一口气吃不成胖子，先搞定能搞定的。
- 定律三：线型系统和线型组织架构间有潜在的异质同态特性。种瓜得瓜，做独立自治的子系统减少沟通成本。
- 定律四：大的系统组织总是比小系统更倾向于分解。合久必分，分而治之。
- 《微服务架构核⼼20讲》
运维 & 统计 & 技术支持
常规监控
命令行监控工具
APM
APM — Application Performance Management
统计分析
持续集成(CI/CD)
Jenkins
环境分离
开发、测试、生成环境分离。
自动化运维
Ansible
puppet
chef
测试
TDD 理论
- 《深度解读 - TDD（测试驱动开发）》
- 基于测试用例编码功能代码，XP（Extreme Programming）的核心实践.
- 好处：一次关注一个点，降低思维负担；迎接需求变化或改善代码的设计；提前澄清需求；快速反馈；
单元测试
压力测试
全链路压测
A/B 、灰度、蓝绿测试
虚拟化
KVM
Xen
OpenVZ
容器技术
Docker
云技术
OpenStack
DevOps
文档管理
中间件
Web Server
Nginx
OpenResty
Tengine
Apache Httpd
Tomcat
架构原理
调优方案
Jetty
- 《Jetty 的工作原理以及与 Tomcat 的比较》
- 《jetty和tomcat优势比较》
- 架构比较:Jetty的架构比Tomcat的更为简单。
- 性能比较：Jetty和Tomcat性能方面差异不大，Jetty默认采用NIO结束在处理I/O请求上更占优势，Tomcat默认采用BIO处理I/O请求，Tomcat适合处理少数非常繁忙的链接，处理静态资源时性能较差。
- 其他方面：Jetty的应用更加快速，修改简单，对新的Servlet规范的支持较好;Tomcat 对JEE和Servlet 支持更加全面。
