快速排序理解

快速排序算法核心思想,取待排序序列中的某个元素作为分区点,大于分区点的元素挪到分区点右边(从小到大排序),小于分区点的元素挪到分区点左边。然后分区点左右两边的子序列循环以上操作,直至子序列长度为 1

左右指针法实现思路

1、首先定义分区点(pivot)pp 一般为数组 a 的第一个元素或最后一个元素 2、然后定义左(l)、右(r)两个指针分别指向数组的第一个元素(a[0])和最后一个元素 (a[a.length - 1]) 3、如果 a[l] > a[p]l、p 下标元素互换,l 前进 1 位 4、如果 a[r] < a[p]r、p 下标元素互换,r 后退 1 位 5、如果 l >= r,排序结束

Read more →

堆排序理解

堆排序的关键是构建大(小)顶堆,堆顶元素就是最大(小)的元素,然后堆顶元素和末尾元素交换位置,再次堆化除最后一个元素外的其它元素,循环次过程即可完成排序。

翻译成代码如下:

public void sort(int a) {
    for(int i = a.length - 1; i > 0; i--) {
        buildHeap(a, i);
        // 堆顶元素和最后一个元素交换,除过最后一个元素外其它元素再次构建大顶堆
        swap(a, 0, i);
    }
}
Read more →

KMP 算法理解

字符串前缀字符串后缀

  • 字符串前缀(Proper prefix) :包含第一个字符,不包含最后一个字符的所有子串 例如:abababca 的前缀:a、ab、aba、abab、ababa、ababab、abababc

  • 字符串后缀(Proper suffix):不包含第一个字符,包含最后一个字符的所有子串 例如:abababca 的后缀:a、ca、bca、abca、babca、ababca、bababca

字符串部分匹配表

字符串部分匹配表 (Partial Match Table) 也称为 next 数组,例如:abababca 的部分匹配表为:

charabababca
index01234567
value00123401
Read more →

JVM TLAB

TLAB(Thread Local Allocation Buffer) 线程本地分配缓存区

  1. 由于对象一般分配在堆上,而堆是线程共用的,因此可能会有多个线程在堆上申请空间,而每一次的对象分配都必须加锁保证线程同步,会使分配的效率下降。考虑到对象分配几乎是 Java 中最常用的操作,因此 JVM 使用了 TLAB 这样的线程专有区域来避免多线程冲突,提高对象分配的效率。
  2. 我们说 TLAB 是线程独享的,但是只是在 “分配” 这个动作上是线程独享的,至于在读取、垃圾回收等动作上都是线程共享的。而且在使用上也没有什么区别
  3. JVM 为了提升对象内存分配的效率,对于所创建的线程都会分配一块独立的空间 TLAB,其大小由 JVM 根据运行的情况计算而得,在 TLAB 上分配对象时不需要加锁,因此 JVM 在给线程的对象分配内存时会尽量的在 TLAB 上分配,在这种情况下 JVM 中分配对象内存的性能和 C 基本是一样高效的,但如果对象过大的话则仍然是直接使用堆空间分配
  4. TLAB 分配之后,并不影响对象的移动和回收,也就是说,虽然对象刚开始可能通过 TLAB 分配内存,存放在 Eden 区,但是还是会被垃圾回收或者被移到 Survivor Space、Old Gen 等。
  5. “堆是线程共享的内存区域” 这句话并不完全正确,因为 TLAB 是堆内存的一部分,它在读取上确实是线程共享的,但是在内存分配上,是线程独享的。
  6. TLAB 的空间其实并不大(默认是 eden 区空间的 1%),所以大对象还是可能需要在堆内存中直接分配。那么,对象的内存分配步骤就是先尝试 TLAB 分配,空间不足之后,再判断是否应该直接进入老年代,然后再确定是再 eden 分配还是在老年代分配。
Read more →

MySQL InnoDB 事务隔离级别总结

SQL 事务隔离级别说明

SQL 标准定义了 4 类隔离级别,包括了一些具体规则,用来限定事务内外的哪些改变是可见的,哪些是不可见的。低级别的隔离级一般支持更高的并发处理,并拥有更低的系统开销。

Read Uncommitted(读取未提交内容)

在该隔离级别,所有事务都可以看到其他未提交事务的执行结果。本隔离级别很少用于实际应用,因为它的性能也不比其他级别好多少。读取未提交的数据,也被称之为脏读(Dirty Read)。

Read Committed(读取提交内容)

这是大多数数据库系统的默认隔离级别(但不是 MySQL 默认的)。它满足了隔离的简单定义:一个事务只能看见已经提交事务所做的改变。这种隔离级别 也支持所谓的不可重复读(Nonrepeatable Read),因为同一事务的其他实例在该实例处理其间可能会有新的 commit,所以同一 select 可能返回不同结果。

Repeatable Read(可重读)

这是 MySQL 的默认事务隔离级别,它确保同一事务的多个实例在并发读取数据时,会看到同样的数据行。不过理论上,这会导致另一个棘手的问题:幻读 (Phantom Read),简单的说,幻读指当用户读取某一范围的数据行时,另一个事务又在该范围内插入了新行,当用户再读取该范围的数据行时,会发现有新的 “幻影” 行。

InnoDB 存储引擎通过 MVCC 机制(快照读)和 next-key lock(当前读)解决了该问题。

Serializable(可串行化)

这是最高的隔离级别,它通过强制事务排序,使之不可能相互冲突,从而解决幻读问题。简言之,它是在每个读的数据行上加上共享锁。在这个级别,可能导致大量的超时现象和锁竞争。

Read more →