数据库及 Mybatis 知识汇总
0x00 事务
0x00 事务的ACID 特性
原子性（Atomicity）：事务是最小的执行单位，不允许分割。事务的原子性确保动作要么全部完成，要么完全不起作用。
一致性（Consistency）：执行事务前后，数据库从一个一致性状态转换到另一个一致性状态。
隔离性（Isolation）：并发访问数据库时，一个用户的事物不被其他事务所干扰。
持久性（Durability）：一个事务被提交之后。它对数据库中数据的改变是持久的，即使数据库发生故障也不应该对其有任何影响。
0x01 并发事务带来的问题
脏读（Dirty read）：当一个事务正在访问数据并且对数据进行了修改，而这种修改还没有提交到数据库中，这时另外一个事务也访问了这个数据，然后使用了这个数据。因为这个数据是还没有提交的数据，那么另外一个事务读到的这个数据是“脏数据”，依据“脏数据”所做的操作可能是不正确的。
丢失修改（Lost to modify）：在一个事务读取一个数据时，另外一个事务也访问了该数据，那么在第一个事务中修改了这个数据后，第二个事务也修改了这个数据。这样第一个事务内的修改结果就被丢失，因此称为丢失修改 ...
Hashmap 的实现
0x00 背景知识
首先HashMap是基于hash表的，hash表的相关知识及其存储原理，可以参考我之前写的一篇文章：查找算法总结，要着重看此文章关于冲突处理所讲述的拉链法。
我们仅在这稍微明确一点概念：首先对于拉链式的hash表，其是由数组和链表共同组成的，当然Java中还引入了红黑树，当链表长度大于8时，将链表转为红黑树以提高查找效率。我们先来看上面的这个图，保存这个hash表的数组称之为桶（bucket），而每个桶中保存了一系列的数据入口（entries）。
同理，我们在这明确一个概念“等同”：我们假定如果两个对象其hashCode相同，且任一一个调用equals方法与另一个返回true，即认为两个对象等同。
同时，在HashMap中有如下几个量需要注意，代码如下：
12345678910111213141516171819202122232425/** * The number of key-value mappings contained in this map. */// MAP中所包含的键值对的数量transient int size;/** * The next s ...
Java锁
0x00 简介
0x01 乐观锁与悲观锁
对于同一个数据的并发操作，悲观锁认为自己在使用数据的时候一定有别的线程来修改数据，因此在获取数据的时候会先加锁，确保数据不会被别的线程修改。Java中，synchronized关键字和Lock的实现类都是悲观锁。悲观锁适用于写操作多的过程，先加锁可以保证写操作时的数据正确。
而乐观锁认为自己在使用数据时不会有别的线程修改数据，所以不会添加锁，只是在更新数据的时候去判断之前有没有别的线程更新了这个数据。如果这个数据没有被更新，当前线程将自己修改的数据成功写入。如果数据已经被其他线程更新，则根据不同的实现方式执行不同的操作（例如报错或者自动重试）。乐观锁在Java中是通过使用无锁编程来实现，最常采用的是CAS算法，Java原子类中的递增操作就是通过CAS自旋实现的。
乐观锁的主要实现方式为CAS技术，CAS即为Compare And Swap（比较与交换）。这是一种无锁算法，在不使用锁的情况下，实现多线程之间的变量同步。诸如AtomicInteger之类的原子类就是通过CAS实现的乐观锁。其主要涉及3个操作数，需要读写的内存值V，进行比较的值A和 ...
分布式唯一 Id 生成策略
0x00 分布式唯一id的生成策略简介
作为一个分布式唯一id，一般要求其具有以下特征：
全局唯一：在同一业务场景里面必须保持全局的唯一。
趋势递增：在MySQL InnoDB存储引擎中使用的是聚集索引，所以在主键的选择上我们应该尽量使用有序的主键来保证写入的性能。
信息安全：如果id是连续的，那恶意用户的扒取工作就非常容易做了，直接按照顺序下载指定URL即可；如果是订单号就更危险，竞争对手可以直接知道我们一天的单量。所以在一些应用场景下，会需要ID无规则、不连续。
0x01 数据库自增长序列或字段
最常见的方法，利用数据库，可保证全数据库唯一。
优点：
简单，性能可以接受。
代码方便，在INSERT语句中直接把主键字段空出来，交由数据库自动填充即可。
生成的数字id天然排序，对分页或者需要排序的结果很有帮助。
缺点：
不同数据库的语法和内部实现方法不同，在数据库迁移的时候可能需要额外的处理。
在单个数据库或者一主多从的情况下，只有一个主库可以生成，有单点故障的风险。
在性能达不到要求的情况下，难于扩展。
分表分库时可能会带来麻烦。
对于有多个主库的情况下，可以设置每个主库 ...
Spring Data Jpa 主键生成策略
0x00 Spring Data JPA主键生成策略
如果你用Spring Data JPA的@Entity将一个类标注为一个实体类的话，那首先我们会定义一个id字段，并标注其生成类型，示例如下：
1234567891011@Entity@Table(name = "tj_colleges")public class College { @Id @GeneratedValue(strategy = GenerationType.IDENTITY) private Integer id; private String name; // ... getters and setters}
对于@GeneratedValue中的strategy字段一共有四种枚举类型，如下：
123456public enum GenerationType { TABLE, SEQUENCE, IDENTITY, AUTO;}
不同数据库对四种主键生成策略的支持如下：
GenerationTy ...
布隆过滤器
0x00 适用场景
一开始学这个布隆过滤器是为了一个分布式爬虫的项目，在这个项目中有一个需求就是判断队列中的URL是否先前已经爬取过了。如果先前已经爬取过了，那就不爬了，如果没有，那就爬取这个URL。然后就了解到了这个布隆过滤器和RedisBloom。
布隆过滤器说白了主要应用于在大量数据中判断给定数据是否存在。 这是一种基于概率的算法，什么意思呢，就是说，不存在的一定返回false，而返回true的却不一定存在。也就说它有一定的误判率。
0x01 基本原理
布隆过滤器的基本组件其实很简单，一系列的hash函数以及一个存放位序列的大表。现在我们假定一个长度为8的表，初始状态下，表中的元素均为0：
123+---+---+---+---+---+---+---+---+| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |+---+---+---+---+---+---+---+---+
现在有一组Hash函数，hash1(data)和hash2(data)。对于一个给定数据liu，我们假设hash1和hash2函数的返回值分别为为2, 4，那在这个大表中，翻置下标为2和4的 ...
缓存穿透击穿雪崩
0x00 正常缓存的处理流程
正常情况下，服务端收到用户请求，先从缓存中查找相关请求信息，如果缓存命中，则直接返回，如果未命中，则从数据库中查找，如果数据库中存有相关信息则返回结果并更新缓存，如果数据库中也没有，那直接返回空结果。
0x01 缓存穿透
缓存穿透指的是有用户频繁请求一个缓存和数据库中都不存在的资源。就比如我们的用户id均为正整数，当我们请求一个值为-1的id时，如果没有加任何的id合法性校验机制就会导致缓存穿透。请求这个不存在的id时，缓存中是肯定没有的，所以指定会造成数据库的查找请求，当不断请求一个不存在的id时，就会造成过大的数据库压力。
解决方案：
可以加入id合法性校验机制，当输入不合法的id时直接返回。
可以采用布隆过滤器，布隆过滤器是一种高效的用来快速判断一个值在一个庞大的数据集中是否存在的数据结构。当请求的数据在缓存中不存在需要访问数据库获取数据时，我们可以首先使用布隆过滤器过滤掉在数据库中不存在的数据，如果布隆过滤器返回true，即在数据库中存在，然后再进行数据库的查询操作。
0x02 缓存击穿
缓存击穿就是当一个缓存中的key非常地热点，扛着大并发并 ...
树
0x00 二叉树
二叉树（Binary tree）是一个以树型存储的数据结构，每个结点除数据域外都有一个左孩子（left child）以及一个右孩子（right child）。
满二叉树（**perfect **binary tree），除最后一层无任何子节点外，每一层上的所有节点都有两个子结点二叉树。另有定义：一棵高度为hhh，并且含有2h−12^h-12h−1个节点的二叉树称为满二叉树。此定义与上述定义等价。
完全二叉树（complete binary tree），对于深度为K的有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
我有必要跟你说一下perfect binary tree和full binary tree的区别，如果按照英文字面来理解的话，full binary tree翻译过来应该是满二叉树，其实不然，这样的字面翻译也是错误的，我们需要依据其具体的定义来理解，国外教材是这样定义full binary tree的：
A full binary tree (sometimes referred to as ...
浅拷贝与深拷贝
0x00 浅拷贝和深拷贝
浅拷贝会创建一个新对象，然后将当前对象的非静态字段复制到该新对象，如果字段是值类型的，那么对该字段执行复制**。如果该字段是引用类型的话，则复制引用但不复制引用的对象。因此，原始对象及其副本引用同一个对象**。看如下代码：
12345678910111213141516171819202122232425262728public class Main { static class Test { private ArrayList<String> strings = new ArrayList<>(); public void addString(String s) { strings.add(s); } @Override public String toString() { StringBuilder stringBuilder = new StringBuilder ...
序列化与反序列化
0x00 序列化与反序列化
其实这应该是一对很简单的概念，但是有一些资料用了一些很高大上的语句和词汇，整得初学者往往很头大。简单来说，序列化的主要用途主要就是为了传递或保存整个对象。对象存储在内存中的，在传递过程中需要将其以某种形式表现出来，先举个简单的例子，比如将一个对象序列化为一个JSON字符串的形式。
12345public class Person { private String name; // ="Qun" private int age; // =22 // 省略getter, setter}
序列成JSON字符串就成为了：
1234{ "name":"Qun", "age":22}
这个JSON字符串的形式在网络上传递就很方便了，也可以将其保存成一个JSON文件做持久化存储，这其实就是序列化的意义。同样，我也可以通过这个JSON字符串来还原回一个Person对象，这也就是反序列化的意义。
注意：如果一个类A ...