悲观锁

对数据被外界修改持保守态度，在整个数据处理过程中，将数据处于锁定状态。其实现依靠数据库的锁机制，以保证操作最大程度的独占性。但随之而来的就是数据库性能的大量开销。
以MySQL InnoDB为例,当使用SELECT FOR UPDATE就会使用悲观锁，前提是把事务自动提交取消

1

set autocommit = 0;

使用悲观锁的原理就是，当我们在查询出信息后就把当前的数据锁定，直到我们修改完毕后再解锁。
根据查询条件的不同，锁定的范围也不同

1. 当查询条件中指定明确主键，并且有此数据——–行级锁（row lock）
2. 当查询条件中指定明确主键，但无次数据———-无锁
3. 当查询条件中无主键————————-表级锁（table lock）
4. 当查询条件中主键不明确———————-表级锁（table lock）

乐观锁

乐观锁大多基于数据版本记录机制实现，即为数据增加一个版本标识，在基于数据库表的版本解决方案，一般是通过为数据库表增加一个 “version” 字段来实现。也可以采用另一种方式，同样是在需要乐观锁控制的table中增加一个字段，名称无所谓，字段类型使用时间戳timestamp中，
操作步骤

1. 读取出数据时，将此版本号（时间戳）一同读出
2. 更新时，比较数据库中该数据当前的版本号和手上的版本号，不一致说明版本冲突，一致则OK，将版本号+1或者获取当前时间戳后将数据更新回数据库

缺点
乐观锁机制往往基于系统中的数据存储逻辑，那么来自外部系统的更新操作不受我们系统的控制，因此可能会造成脏数据被更新到数据库中。
解决
如将乐观锁策略在数据库存储过程中实现，对外只开放基于此存储过程的数据更新途径，而不是将数据库表直接对外公开

参考

muyuren | mysql悲观锁详解

muyuren | mysql乐观锁详解

@NotNull

不允许为null，但可以是empty

@NotEmpty

不允许为null且长度要大于0

@NotBlank

只能作用在String上，不能为null，而且调用trim()后，长度必须大于0

例子

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

String name = null;
NotNull = false
NotEmpty = false
NotBlank = false
String nam = "";
NotNull = true
NotEmpty = false
NotBlank = false
String name = "  ";
NotNull = true
NotEmpty = true
NotBlank = false
String name = "zojian"
NotNull = true
NotEmpty = true
NotBlank = true

@PropertySource注解

将properties配置文件中的值存储到Spring的 Environment中，Environment接口提供方法去读取配置文件中的值，参数是properties文件中定义的key值

1
2
3
4

@PropertySource("classpath:message.properties")
public class AppConfig extends WebMvcConfigurerAdapter {
	//something
}

多个配置文件@PropertySources注解

1
2
3
4
5
6
7

@PropertySources({
	@PropertySource("classpath:config.properties"),
	@PropertySource("classpath:db.properties")
})
public class AppConfig {
	//something
}

ignoreResourceNotFound属性

如果*.properties不存在或找不到,系统则会抛出异常FileNotFoundException。
但是ignoreResourceNotFound设为true之后会忽略找不到的文件

1
2
3
4
5

@PropertySource(value="classpath:missing.properties"
					  ,ignoreResourceNotFound=true)
	public class AppConfig {
		//something
	}

1.并发编程的挑战

什么是上下文切换

CPU通过时间片分配算法循环执行任务[线程]，当任务执行完一个时间片后会切换到下一个任务，在切换前会保存上一个任务的状态，以便下次切换回来时可以再加载这个任务的状态。所以任务从保存到加载的过程就是一次上下文切换。

如何减少上下文切换

1. 无锁并发编程：如数据取模分段，不同线程处理不同数据
2. CAS算法：Atomic包使用CAS算法来更新数据， 而不需要加锁
3. 使用最少线程：避免创建不必要的线程，使得大多数线程处于等待状态
4. 协程：在单线程里实现多任务调度，并在单线程里维持多个任务的切换

如何避免死锁

1. 避免一个线程同时获得多个锁
2. 避免一个锁同时占用多个资源
3. 限制加锁顺序
4. 尝试使用定时锁 lock.tryLock(timeout)
5. 对应数据库锁，加锁和解锁必须在同一个数据库连接里

2.Java并发机制底层实现原理

volatile

轻量级的synchronized，在多处理器开发中保证了共享变量的“可见性”（当一个线程修改一个共享变量时，另一个线程能读到这个修改的值）
比synchronized的使用和执行成本低，因为它不会引起线程上下文的切换和调度

背景

为了提高处理速度，CPU不直接和内存进行通信，而是将系统内存的数据读到内部缓存（L1,L2,L3）后再操作，但操作完不确定何时会写回内存。这样可能导致其他CPU不能获取到共享变量的最新值。

实现原理

在x86处理器下通过工具获取JIT编译器生成的汇编指令来看看对Volatile进行写操作CPU

Lock前缀的命令作两件事：

1. 将当前CPU缓存行的数据写回到内存
2. 令其他CPU里缓存了该内存地址的数据失效

缓存一致性协议
每个CPU通过嗅探在总线中传播的数据来检查自己的缓存的值是否过期，当CPU发现自己缓存行对应的内存地址被修改，就会将当前处理器的缓存行设置成无效状态，当CPU对这个数据进行修改操作时，会重新从系统内存中把数据读到CPU缓存中。

使用优化

LinkedTransferQueue部分源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

/** head of the queue */
private transient final PaddedAtomicReference < QNode > head;
/** tail of the queue */
private transient final PaddedAtomicReference < QNode > tail;
static final class PaddedAtomicReference < T > extends AtomicReference < T > {
    // enough padding for 64bytes with 4byte refs 
    Object p0, p1, p2, p3, p4, p5, p6, p7, p8, p9, pa, pb, pc, pd, pe;
    PaddedAtomicReference(T r) {
        super(r);
    }
}
public class AtomicReference < V > implements java.io.Serializable {
    private volatile V value;
    //省略其他代码 ｝

因为缓存行是64个字节且不支持部分填充缓存，这意味着，如果队头队尾不足64字节，有可能他们会读到同一个缓存行中，那么有可能在修改头结点时，会将整个缓存行锁定，使得其他CPU无法访问尾节点，导致效率低下。
在PaddedAtomicReference内部类中将共享变量追加到64字节，使得头结点和尾节点不会加载同一个缓存行，即不会互相锁定。

不适合使用这种优化的情景

1. 缓存行非64字节的CPU
2. 共享变量不会被频繁地写

synchronized

liuxiaopeng | Java并发编程：Synchronized底层优化（偏向锁、轻量级锁）

原子操作

不可被中断的一个或一系列操作

CPU实现原子操作

总线锁定

使用CPU提供的一个LOCK#信号，当一个CPU在总线上输出此信号时，其他CPU的请求将会被阻塞，那么该CPU就能独享共享内存了

缓存锁定

内存区域如果被缓存在处理器的缓存行中，并且在Lock操作期间被锁定，那么当它执行锁操作回写到内存时，处理器不需要在总线上声言LOCK#信号，而是修改内部的内存地址，通过缓存一致性机制保证操作的原子性。
例外：当操作的数据不能被缓存在处理器内部，或操作的数据跨多个缓存行，处理器会调用总线锁定。或者处理器不支持缓存

Java实现原子操作

循环CAS（CompareAndSet|CompareAndSwap）

jvm中的CAS操作是基于处理器的CMPXCHG指令实现的，CAS存在三个问题：

1. ABA问题（解决：使用版本号A-B-A变成1A-2B-3A）
2. 循环时间长开销大
3. 只能保证一个共享变量的原子操作（解决：AtomicReference类将多个变量放到一个对象中进行CAS操作）

锁

锁机制保证了只有获得锁的线程才能操作锁定的内存区域

什么是缓存

缓存是介于应用程序和物理数据源之间，其作用是为了降低应用程序对物理数据源访问的频次，从而提高了应用的运行性能。缓存内的数据是对物理数据源中的数据的复制，应用程序在运行时从缓存读写数据，在特定的时刻或事件会同步缓存和物理数据源的数据。

一级缓存（会话级）

1. 存放在session中，数据适用范围在当前session内
2. 生命周期与当前session相同
3. 默认启用
4. evict()方法：用于将某个对象从Session的一级缓存中清除
5. clear()方法：用于将一级缓存中的所有对象全部清楚

二级缓存（应用级）

1. 数据可使用范围是当前应用的所有会话
2. 默认不启用，选择性开启（默认是EHCache，其他二级缓存组件如：HashTable、OSCache、SwarmCache等。）
3. 由sessionFactory控制

N+1次问题

订单表(ORDERS)

客户表(CUSTOMERS)

订单表和客户表是多对一的关系，当检索所有客户时
将依次执行以下SQL语句

select from CUSTOMERS;
select from ORDERS where CUSTOMER_ID=1;
select from ORDERS where CUSTOMER_ID=2;
select from ORDERS where CUSTOMER_ID=3;

N+1问题解决方案

1. 使用表连接查询 select * from CUSTOMERS left outer join ORDERS on CUSTOMERS.ID=ORDERS.CUSTOMER_ID
2. 使用延迟加载 fetch = FetchType.lazy
3. 在关联对象类上标注@BatchSize(size=x) , 设置管理对象查询时一次性查询多少条记录， 使转为为 1+n/x问题。（不推荐）

适用二级缓存的情况

1. 数据不会被第三方修改（绕过ORM会使数据不一致）
2. 数据大小在可接收范围之内（缓存会占用内存资源，占太多反而会降低性能）
3. 数据更新频率低（频繁的同步缓存中数据也会降低性能）
4. 非关键数据（正确性 高于 高性能）

query.list（）和query.iterator（）

1. list（）不使用一级缓存，即每次调用都会向底层数据库查询，但是会将结果保存到一级缓存中
2. iterator（）会先执行一条语句向数据库取出符合条件的数据id，然后通过id在hibernate的一级缓存中查找是否存在该对象，如果存在则直接取出，如果没有则再次发出一条sql语句通过id取得对象（并且加入到缓存中），这样如果所有的id在缓存中都没有的话就会出现n+1条sql语句的问题。

一. 永久搬离的资源

访问的资源被（永久性）移动新的位置或者被（永久性）重命名，从而形成新的URL。Web服务器返回重定向响应告诉客户从新的地址获取资源，并且在访问新地址之前更新书签之类的信息。

二. 临时搬离的资源

访问的资源被临时移走或临时重命名，服务器希望客户端重定向到新的位置上去，但由于资源的改变是临时的，所以服务器希望客户端将来还是可以回头去使用老的URL。不要对书签进行更新

三. URL增强

通过重定向来重写URL，往往用于嵌入上下文。[经过扩展和状态增强的URL称为“胖URL”]
客户端会跟随这个重定向信息，重新发起请求，但这次的请求会包含完整的、经过状态增强的URL，这是在事务间维护状态的一种有效的方法。

四. 负载均衡

如果一个超载的服务器收到一条请求，服务器可以将客户端的请求重定向到一个负载不太重的服务器上去。

五. 规范目录名称

客户端请求的URI是一个不带尾部斜线的目录吗时，大多数Web服务器会将客户端重定向到一个加了斜线的URI上，这样相对链接就可以正常工作了。

补充：状态码302，303，307的区别

• 302是HTTP/1.0的标准，303，307则是HTTP/1.1标准中对302的细化
• 302：如果客户端发出POST请求后，收到服务端的302状态码，那么不能自动的向新的URI发送重复请求，必须跟用户确认是否该重发，因为第二次POST时，环境可能已经发生变化（POST方法不是幂等的），POST操作会不符合用户预期
• 303：对于POST请求，它表示请求已经被处理，客户端可以接着使用GET方法去请求Location里的URI
• 307：对于POST请求，表示请求还没有被处理，客户端应该向Location里的URI重新发起POST请求

什么是并查集

什么是ST算法

ST（Sparse Table，稀疏表）是解决RMQ问题的经典在线算法
O(NlogN)预处理
O(1)查询
本质就是动态规划算法

预处理

维护二维数组ST[n][n]，ST[i][j]表示i开始，长度为2^j的子数组中的最值
在求ST[i][j]的最值时，将这段子数组切成两半，每段长度为2^j-1，于是前面一段的最值为ST[i][j-1]，后面一段的最值为ST[i+2^j-1][j-1]，即状态转移方程为
ST[i][j] = max(ST[i][j-1], ST[i+2^j-1][j-1])

1
2
3
4
5
6
7
8
9

void initST(){
  for (int i = 0; i < n; i++)
        ST[i][0] = num[i];
    for(int j = 1; (1<<j) <= n; j++){//枚举长度
        for(int i = 0; i + (1<<j) - 1 < n;i++){//枚举起点
            ST[i][j] = max(ST[i][j-1], ST[i+(1<<(j-1))][j-1]);
        }
    }
}

查询

由于每次查询的区间长度不一定是偶数，即不能直接用ST[i][j]表示，所以还需进一步处理。
对于查询区间[a，b]，我们将其分为两段长度相等（2^k）的偶数区间,他们可能相交，但不影响最值的求解，即
(b-a)/2 ≤ 2^k ≤ b-a+1
所以k的最小值为log₂(b-a)
即
query(a, b) = max(ST[a][k], ST[b - (2^k + 1)][k])

1
2
3
4

int query(int a,int b){
    int k = (int)(log(b-a+1.0)/log(2.0));
    return max(ST[u][k],ST[b-(1<<k)+1][k]);
}

动态修改

当修改某个位置的数值时，需要将覆盖此位置的所有区间做相应的更新

1. 更新ST[i][0]
2. 枚举长度 j=1；2^j ≤ n；j++
3. 枚举起点从以i为最后一个元素的区间到以i为起点的区间

1
2
3
4
5
6
7
8
9

void update(int x, int y){
    ST[x][0] = y;
    for(int j = 1; (1<<j) <= n; j++){
        for(int i = x-(1<<j)+1 > 1 ? x-(1<<j)+1 : 1; 
        i <= x && i + (1<<j)-1 <= n; 
        i++)
            ST[i][j] = max(ST[i][j-1], ST[i + (1<<(j-1))][j-1]);
    }
}

题目传送门

脑力游戏

题目大意

给定n个带锁的盒子和n把钥匙，每把钥匙对应着唯一的一个盒子。初始状态下每把钥匙分别放在不同的盒子中，且所有盒子是上锁的。可以通过“暴力”打开某些盒子，取出放在里面的钥匙，然后利用拿到的钥匙去开相应的盒子。问如果只允许“暴力”打开最多k个盒子，那么在多少种状态下，可以最终打开所有盒子。(1≤n≤100, 0≤k≤n)

涉及知识点

置换

1.什么是置换

假设S={1,2,3,.., n}，σ是S上的双射函数，则S上的n元置换记为σ
$$
\left(
\begin{matrix}
1 & 2 & … & n \
σ(1) & σ(2) & … & σ(n)
\end{matrix}
\right)
$$

2.什么是轮换

设σ是S上的n元置换，若σ(i₁)=i₂,σ(i₂)=i₃ ,…, σ(i_k-1)=i_k,σ(i_k)=i₁
且保持S中的其他元素不变，则称σ为S上的k阶轮换，记作(i₁ i₂ … i_k),若k=2，称σ为S上的对换。

3.置换和轮换的关系

任何n元置换可以分解为不相交的轮换之积。
$$
\left(
\begin{matrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \
5 & 3 & 6 & 4 & 2 & 1 & 8 & 7
\end{matrix}
\right)
$$
拆成(1 5 2 3 6)(4)(7 8)

动态规划

1.判断一个问题是否可以用动态规划解决

1. 具有最优子结构
2. 具有重叠子问题
3. 无后效性

2.什么是最优子结构

1. 一个问题的最优解包含其子问题的最优解
2. 局部最优解能解决全局最优解

3.什么重叠子问题

1. 每次产生的子问题并不总是新问题，有些子问题会被重复计算多少
2. 而分治产生的子问题都是相互独立的

4.什么是无后效性

1. 某个状态以后的过程不会影响到以前的过程

5.处理动态规划问题的步骤

1. 定义最优子结构
2. 把问题看作多阶段决策的过程来求解问题
3. 递归定义最优解
4. 按自定向上的方式解最优解

解题思路

1. n把钥匙的不同放置方法实际上对应1~n的不同的排列。

2. 第一次暴力打开一个盒子会出现两种情况：

   1. 拿到的钥匙是该暴力打开的盒子的钥匙。
   2. 拿着该钥匙打开另一个盒子，直到拿到第一次暴力打开的那个盒子的钥匙，而这实际上构成了一个循环。

1. 根据离散数学的角度，这里的每种排列情况对应着一个置换，每一个循环对应一个轮换。

2. 所以问题转化成 n！个n元置换中，有多少个置换可以分解为不超过k个不相交的轮换。由于100！非常大，所以问题不能单纯的暴力算出答案，而且需要高精度整数运算。

3. f[i][j]表示i元置换中可以分解为j个不相交轮换的个数。

4. f[n][1] + f[n][2] + … + f[n][k]即为问题所求。所以预处理求出所有状态，再将符合题目要求的结果求和。

5. 状态转移的时候有两种情况：

   1. 前面i-1个元素组成j-1个轮换，第i个元素单独作为一个一元轮换。
   2. 前面i-1个元素组成j个轮换，第i个元素加入到前面的元素组成的某个轮换中，能加入的位置有i-1个。

1. 假设现在有3个元素，这会将隔出4个位置 1□2□3□4 但是位置1和位置4所构成的循环是相同的。

2. 状态转移方程 f[i][j] = f[i-1][j-1] + f[i-1][j]*(i-1)，特殊边界情况f[0][0]=1,f[0][j]=0。

关键代码

1
2
3
4
5
6
7
8

void preprocess(){
	f[0][0] = 1;
	for(int i = 1; i <= MAXN; i++){
		for(int j = 1;j <= MAXN; j++){
			f[i][j] = f[i-1][j-1] + f[i-1][j]*(i-1);
		}
	}
}