hashCode 方法及 equals 方法的规范

在Java中，hashCode 方法和 equals 方法都是 java.lang.Object 类的方法，在 The Java Language Specification, Java SE 8 Edition 中定义如下：

  • The method equals defines a notion of object equality, which is based on value,
    not reference, comparison.
  • The method hashCode is very useful, together with the method equals , in
    hashtables such as java.util.HashMap .

简而言之，equals 是判断两个对象是否等价的方法，而 hashCode 则是为散列数据结构服务的计算散列值的方法。下面分别对这两个方法进行讨论。

equals方法

重写规则

equals 方法注重 两个对象在逻辑上是否相等。重写 equals 方法看似比较简单，但实际编写的时候还是要考虑具体类的意义。
一般来说，以下几种情况不需要重写 equals 方法：

  • 一个类的每个实例在本质上都是独立的、不同的，比如 Thread 类
  • 不需要 equals 方法，也就是判断对象相等的逻辑是没有必要的
  • 父类已重写 equals 方法，并且子类的判断逻辑与父类相符
  • 一个类的访问权限为 private 或 package-private，并且可以确定 equals 方法不会被调用

那么，另外的情况通常需要重写 equals 方法。一般来说，equals 方法遵循离散数学中的 等价关系（equivalence relation）。从 OOP 的角度来说，等价关系三原则如下：

  • 自反性（Reflexive）：一个对象与自身相等，即 $x = x$。对任何非空对象 x， x.equals(x) 必定为 true。
  • 对称性（Symmetric）：对象之间的等价关系是可交换的，即 $a=b \Leftrightarrow b=a$。对任何非空对象 x、y， x.equals(y) 为 true，当且仅当 y.equals(x) 为 true。
  • 传递性（Transitive）：$(a=b)\wedge(b=c) \Rightarrow (a=c)$。对任何非空对象 x、y、z， 若 x.equals(y) 为 true 且 y.equals(z) 为 true，则 x.equals(z) 为 true。

除了遵循这三原则之外，还要遵循：

  • 一致性（Consistent）：对任何非空对象 x、y，只要所比较的信息未变，则连续调用 x.equals(y) 总是得到一致的结果。这要求了 equals 所依赖的值必须是可靠的。
  • 对任何非空对象 x， x.equals(null) 必定为 false。

所以，根据上面的原则，equals 函数的一个比较好的实践如下：

  1. 首先先判断传入的对象与自身是否为同一对象，如果是的话直接返回 true。这相当于一种性能优化，尤其是在各种比较操作代价高昂的时候，这种优化非常有效。
  2. 判断对象是否为正确的类型。若此方法接受子类，即子类判断等价的逻辑与父类相同，则可以用 instanceof 操作符；若逻辑不同，即仅接受当前类型，则可以用 getClass 方法获取 Class 对象来判断。注意使用 getClass 方法时必须保证非空，而用 instanceof 操作符则不用非空（null instanceof o 的值为 false）。
  3. 将对象转换为相应的类型：由于前面已经做过校验，因此这里做类型转换的时候不应当抛出 ClassCastException 异常。
  4. 进行对应的判断逻辑

几个注意事项：

  • 我们无法在扩展一个可实例化的类的同时，即增加新的成员变量，同时又保留原先的 equals 约定
  • 注意不要写错 equals 方法的参数类型，标准的应该是 public boolean equals(Object o)，若写错就变成重载而不是重写了
  • 不要让 equals 变得太“智能”而使其性能下降
  • 如果重写了 equals 方法，则一定要重写 hashCode 方法（具体见下面）

老生常谈的equals和==

上面提到过，equals方法用来判断 两个对象在逻辑上是否相等，而 == 用来判断两个引用对象是否指向同一个对象（是否为同一个对象）。

用烂了的例子，注意常量池：

1
2
3
4
5
6
7
8
9
10
11
12
String str1 = "Fucking Scala";
String str2 = new String("Fucking Scala");
String str3 = new String("Fucking Scala");
String str4 = "Fucking Scala";
System.out.println(str1 == str2); // false
System.out.println(str2 == str3); // false
System.out.println(str2.equals(str3)); // true
System.out.println(str1 == str4); // true
str4 = "Fuck again!";
String str5 = "Fuck again!";
System.out.println(str1 == str4); // false
System.out.println(str4 == str5); // true

hashCode 方法

如果重写了equals方法，则一定要重写hashCode方法。

重写 hashCode 方法的原则如下：

  • 在程序执行期间，只要equals方法的比较操作用到的信息没有被修改，那么对这同一个对象调用多次，hashCode方法必须始终如一地返回同一个整数
  • 如果两个对象通过equals方法比较得到的结果是相等的，那么对这两个对象进行hashCode得到的值应该相同
  • 两个不同的对象，hashCode的结果可能是相同的，这就是哈希表中的冲突。为了保证哈希表的效率，哈希算法应尽可能的避免冲突

关于相应的哈希算法，一个简单的算法如下:

  • 永远不要让哈希算法返回一个常值，这时哈希表将退化成链表，查找时间复杂度也从 $O(1)$ 退化到 $O(N)$
  • 如果参数是boolean型，计算(f ? 1 : 0)
  • 如果参数是byte, char, short或者int型，计算(int) f
  • 如果参数是long型，计算(int) (f ^ (f >>> 32))
  • 如果参数是float型，计算Float.floatToIntBits(f)
  • 如果参数是double型，计算Double.doubleToLongBits(f)得到long类型的值，再根据公式计算出相应的hash值
  • 如果参数是Object型，那么应计算其有用的成员变量的hash值，并按照下面的公式计算最终的hash值
  • 如果参数是个数组，那么把数组中的每个值都当做单独的值，分别按照上面的方法单独计算hash值，最后按照下面的公式计算最终的hash值

组合公式：result = 31 * result + c

比如，String 类的 hashCode 方法如下（JDK 1.8）：

1
2
3
4
5
6
7
8
9
10
11
12
public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;
            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

举个自定义类的 hashCode 例子：

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
27
28
29
30
31
32
33
34
35
class Baz {
    private int id;
    private String name;
    private double weight;
    private float height;
    private String note;
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Baz baz = (Baz) o;
        if (id != baz.id) return false;
        if (Double.compare(baz.weight, weight) != 0) return false;
        if (Float.compare(baz.height, height) != 0) return false;
        if (name != null ? !name.equals(baz.name) : baz.name != null) return false;
        return !(note != null ? !note.equals(baz.note) : baz.note != null);
    }
    @Override
    public int hashCode() {
        int result;
        long temp;
        result = id;
        result = 31 * result + (name != null ? name.hashCode() : 0);
        temp = Double.doubleToLongBits(weight);
        result = 31 * result + (int) (temp ^ (temp >>> 32));
        result = 31 * result + (height != +0.0f ? Float.floatToIntBits(height) : 0);
        result = 31 * result + (note != null ? note.hashCode() : 0);
        return result;
    }
}

想找到一个不冲突的哈希算法不是非常容易，具体的属于数据结构部分知识，这里就不再赘述了。

其他语言

C++

C++不像Java那样所有的类都继承一个共同的根基类，因此在写自定义的类时，需要自己写这两个方法。
在C++里，一般通过重载==运算符来实现判断两对象等价的逻辑，而实现计算散列值的函数则需要特化std::hash模板结构体，并且重载()运算符。

如果用不到散列数据结构的话，则无需定义对应的散列函数。

【2015-10 Update】C++ 示例可见 C++ STL之哈希表 | unordered_map。

参考资料

  • The Java Language Specification, Java SE 8 Edition
  • Effective Java (2nd Edition)
Java

Java 基础技术细节总结 | 语言规范

开发莫忘基础，写业务写多了很多基础内容容易忘。这里将寻根溯源，总结Java语言规范和基础类中的一些细节问题。所有关于 Java 语言规范的细节问题，都可以参考 The Java® Language Specification, Java SE 8 Edition (JLS8) .

本文将不断补充。。

小数化为整数

  • Math.floor(x) 返回小于等于 x 的最接近整数，返回类型为 double;
  • Math.round(x) 相当于四舍五入，返回值为 long 或 int;
  • Math.ceil(x) 返回大于等于 x 的最接近整数，返回类型为 double。

静态块与构造块

  • 静态块：用 static 申明，JVM 加载类时执行，仅执行一次且优先于 main 函数。
  • 构造块：类中直接用 {} 定义，每一次创建对象时执行，相当于往构造器最前面加上构造块的内容（很像往每个构造器那里插了内联函数，构造块就相当于内联函数）。

执行顺序优先级：静态块 > 构造块 > 构造方法。有继承关系时，执行顺序通常是：父类静态块→子类静态块→父类构造块→父类构造方法→子类构造块→子类构造方法。

测试：

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
27
28
29
30
31
32
33
34
public class test {
    public static void main(String[] args) {
        new Derived();
    }
}
class Base {
        static {
            System.out.println("fucking => Base::static");
        }
        {
            System.out.println("fucking => Base::before");
        }
        public Base() {
            System.out.println("Base::Base<init>");
        }
    }
    class Derived extends Base {
        static {
            System.out.println("fucking => Derived::static");
        }
        {
            System.out.println("fucking => Derived::before");
        }
        public Derived() {
            super();
            System.out.println("Derived::Derived<init>");
        }
    }

输出:

1
2
3
4
5
6
fucking => Base::static
fucking => Derived::static
fucking => Base::before
Base::Base<init>
fucking => Derived::before
Derived::Derived<init>

运算符规则 - 加法规则

代码片段：

1
2
3
4
5
byte b1 = 1, b2 = 2, b3, b6;
final byte b4 = 4, b5 = 6;
b6 = b4 + b5;
b3 = (b1 + b2);
System.out.println(b3 + b6);

结果：第四行编译错误。

表达式的数据类型自动提升, 关于类型的自动提升，注意下面的规则。

  1. 所有的byte,short,char型的值将被提升为int型
  2. 如果有一个操作数是long型，计算结果是long型
  3. 如果有一个操作数是float型，计算结果是float型
  4. 如果有一个操作数是double型，计算结果是double型

而声明为 final 的变量会被 JVM 优化，因此第三句在编译时就会优化为 b6 = 10，不会出现问题。

float x 与“零值”比较的if语句

1
if (fabs(x) < 0.00001f)

float类型的还有double类型的，这些小数类型在趋近于0的时候不会直接等于零，一般都是无限趋近于0。因此不能用==来判断。应该用|x-0| < err来判断，这里|x-0|表示绝对值，err表示限定误差，用程序表示就是fabs(x) < 0.00001f。

关于 try 和 finally

  1. 首先执行到 try 里的 return，但是有 finally 语句还要执行，于是先执行 return 后面的语句，例如（x++），把要返回的值保存到局部变量。
  2. 执行 finally 语句的内容，其中有 return 语句，这时就会忽略 try 中的 return，直接返回。

返回值问题。可以认为 try（或者catch）中的 return 语句的返回值放入线程栈的顶部：如果返回值是基本类型则顶部存放的就是值，如果返回值是引用类型，则顶部存放的是引用。finally中的 return 语句可以修改引用所对应的对象，无法修改基本类型。但不管是基本类型还是引用类型，都可以被 finally 返回的“具体值”具体值覆盖。

三目运算符的类型转换问题

三目运算符里的类型必须一致，比如下面的代码：

1
2
3
4
 int i = 40;
String s1 = String.valueOf(i < 50 ? 233 : 666);
String s2 = String.valueOf(i < 50 ? 233 : 666.0);
assertEquals(true, s1.equals(s2));

结果是测试不通过，这里就涉及到三元操作符的转换规则：

  1. 如果两个操作数无法转换，则不进行转换，返回 Object 对象
  2. 如果两个操作数是正常的类型，那么按照正常情况进行类型转换，比如int => long => float => double
  3. 如果两个操作数都是字面量数字，那么返回范围较大的类型

Java 中自增操作符的一些陷阱

观察下面的一段代码：

1
2
3
4
5
6
7
8
9
10
public class AutoIncTraps {
    public static void main(String[] args) {
        int count = 0;
        for(int i = 0; i < 10; i++) {
            count = count++;
        }
        System.out.println(count);
    }
}

这段代码的打印结果是0，也就是说自增在这里并没有什么卵用，这和C++是不一样的。反编译一下看一下字节码（main函数部分）：

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
27
28
29
30
31
32
public static main([Ljava/lang/String;)V
   L0
    LINENUMBER 6 L0
    ICONST_0
    ISTORE 1
   L1
    LINENUMBER 7 L1
    ICONST_0
    ISTORE 2
   L2
   FRAME APPEND [I I]
    ILOAD 2
    BIPUSH 10
    IF_ICMPGE L3
   L4
    LINENUMBER 8 L4
    ILOAD 1
    IINC 1 1
    ISTORE 1
   L5
    LINENUMBER 7 L5
    IINC 2 1
    GOTO L2
   L3
    LINENUMBER 10 L3
   FRAME CHOP 1
    GETSTATIC java/lang/System.out : Ljava/io/PrintStream;
    ILOAD 1
    INVOKEVIRTUAL java/io/PrintStream.println (I)V
   L6
    LINENUMBER 11 L6
    RETURN

这里相当于创建了一个局部变量存放count++，但没有返回，因此count相当于没变。看了字节码后可能没感觉，写一下编译器处理后的代码吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class AutoIncTraps {
    public AutoIncTraps() {
    }
    public static void main(String[] args) {
        byte count = 0;
        for(int i = 0; i < 10; ++i) {
            int var3 = count + 1;
            count = count;
        }
        System.out.println(count);
    }
}

总结一下这里count的处理流程：

  1. JVM把count值（其值是0）拷贝到临时变量区。
  2. count值加1，这时候count的值是1。
  3. 返回临时变量区的值，注意这个值是0，没有修改过。
  4. 返回值赋值给count，此时count值被重置成0。

单纯看这一个的字节码比较抽象，来看一下这三句的字节码，比较一下更容易理解：

1
2
3
count = ++count;
count = count++;
count++;

字节码：

1
2
3
4
5
6
7
8
9
10
11
12
13
 L4
 LINENUMBER 9 L4
 IINC 1 1
 ILOAD 1
 ISTORE 1
L5
 LINENUMBER 10 L5
 ILOAD 1
 IINC 1 1
 ISTORE 1
L6
 LINENUMBER 11 L6
 IINC 1 1

另外，自增操作不是原子操作，在后边总结并发编程的时候会涉及到。

instanceof 操作符的注意事项

instanceof 操作符左右两边的操作数必须有继承或派生关系，否则不会编译成功。因此，instanceof 操作符只能用于对象，不能用于基本类型（不会自动拆包）。

下面是一些典型的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class FuckingIOF {
    @Test
    public void test() {
        List<Object> list = new ArrayList<>();
        list.add("String" instanceof Object);
        list.add(new String() instanceof Object);
        list.add(new Object() instanceof String);
        //list.add('a' instanceof Character); //此句会编译错误
        list.add(null instanceof String);
        list.add((String)null instanceof String);
        list.add(null instanceof Object);
        list.add(new Generic<String>().isDataInstance(""));
        list.forEach(System.out::println);
    }
}
class Generic<T> {
    public boolean isDataInstance(T t) {
        return t instanceof Date;
    }
}

运行结果和分析：

1
2
3
4
5
6
7
true => String 是 Object 的子类
true => 同上
false => 同上
false => Java 语言规范规定 null instanceof ? 都是 false
false => 同上，无论怎么转换还是 null
false => 同上
false => 由于 Java 泛型在编译时会进行类型擦除，因此这里相当于 Object instanceof Date 了

诡异的 NaN 类型

根据 JLS8 4.2.3，对 NaN 有以下规定：

  • The numerical comparison operators < , <= , > , and >= return false if either or both operands are NaN (§15.20.1).
  • The equality operator == returns false if either operand is NaN.
  • In particular, (x=y) will be false if x or y is NaN.
  • The inequality operator != returns true if either operand is NaN (§15.21.1).
  • In particular, x!=x is true if and only if x is NaN.

注意到 Double.NaN == Double.NaN 返回 false，这其实是遵循了 IEEE 754 standard。NaN 代表一个非正常的数（比如除以 0 得到的数），其定义为：

1
2
3
4
5
6
/**
 * A constant holding a Not-a-Number (NaN) value of type
 * {@code double}. It is equivalent to the value returned by
 * {@code Double.longBitsToDouble(0x7ff8000000000000L)}.
 */
public static final double NaN = 0.0d / 0.0;

Integer 类的 valueOf 和 parseInt 的对比

这个问题是在 StackOverflow 上看到的。以下三个表达式：

1
2
3
System.out.println(Integer.valueOf("127") == Integer.valueOf("127"));
System.out.println(Integer.valueOf("128") == Integer.valueOf("128"));
System.out.println(Integer.parseInt("128") == Integer.valueOf("128"));

结果分别是：

1
2
3
true
false
true

为什么是这样的结果呢？我们看一下 valueOf 方法的源码：

1
2
3
4
5
6
7
8
9
public static Integer valueOf(String s) throws NumberFormatException {
    return Integer.valueOf(parseInt(s, 10));
}
public static Integer valueOf(int i) {
    if (i >= IntegerCache.low && i <= IntegerCache.high)
        return IntegerCache.cache[i + (-IntegerCache.low)];
    return new Integer(i);
}

可以看到 valueOf 方法是在 parseInt 方法的基础上加了一个读取缓存的过程。我们再看一下 IntegerCache 类的源码：

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * Cache to support the object identity semantics of autoboxing for values between
 * -128 and 127 (inclusive) as required by JLS.
 *
 * The cache is initialized on first usage.  The size of the cache
 * may be controlled by the {@code -XX:AutoBoxCacheMax=<size>} option.
 * During VM initialization, java.lang.Integer.IntegerCache.high property
 * may be set and saved in the private system properties in the
 * sun.misc.VM class.
 */
private static class IntegerCache {
    static final int low = -128;
    static final int high;
    static final Integer cache[];
    static {
        // high value may be configured by property
        int h = 127;
        String integerCacheHighPropValue =
            sun.misc.VM.getSavedProperty("java.lang.Integer.IntegerCache.high");
        if (integerCacheHighPropValue != null) {
            try {
                int i = parseInt(integerCacheHighPropValue);
                i = Math.max(i, 127);
                // Maximum array size is Integer.MAX_VALUE
                h = Math.min(i, Integer.MAX_VALUE - (-low) -1);
            } catch( NumberFormatException nfe) {
                // If the property cannot be parsed into an int, ignore it.
            }
        }
        high = h;
        cache = new Integer[(high - low) + 1];
        int j = low;
        for(int k = 0; k < cache.length; k++)
            cache[k] = new Integer(j++);
        // range [-128, 127] must be interned (JLS7 5.1.7)
        assert IntegerCache.high >= 127;
    }
    private IntegerCache() {}
}

原来 JVM 会缓存一部分的 Integer 对象（默认范围为 -128 - 127），在通过 valueOf 获取 Integer 对象时，如果是缓存范围内的就直接返回缓存的 Integer 对象，否则就会 new 一个 Integer 对象。返回的上限可通过 JVM 的参数 -XX:AutoBoxCacheMax=<size> 设置，而且不能小于 127（参照 JLS 5.1.7）。这样我们就可以解释 Integer.valueOf("127") == Integer.valueOf("127") 为什么是 true 了，因为它们获取的都是同一个缓存对象，而默认情况下 Integer.valueOf("128") == Integer.valueOf("128") 等效于 new Integer(128) == new Integer(128)，结果自然是 false。

我们再来看一下 parseInt 方法的原型，它返回一个原生 int 值：

1
public static int parseInt(String s) throws NumberFormatException

由于一个原生值与一个包装值比较时，包装类型会自动拆包，因此 Integer.parseInt("128") == Integer.valueOf("128") 就等效于 128 == 128，结果自然是 true。

Long 类型同样也有缓存。

Java

gdb 用法总结

以前写C++时，遇到需要调试的程序都是放在VS下进行debug，方便快捷。但是某些时候需要在Linux下进行debug，这时候显然不能用VS了，所以要祭出我们的法宝——gdb。
GDB是一个由GNU开源组织发布的、UNIX/LINUX操作系统下的、基于命令行的、功能强大的程序调试工具。
这里总结一下gdb的一些常用命令和简单使用方法，为以后调试Hotspot JVM以及Golang编译的程序做准备。（顺便吐槽一下Golang，都出到1.5版本了官方还不发布一个调试器，还得借助gdb。。）

放上一段简单的程序(klass.cpp):

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
#include <string>
using std::cout;
using std::endl;
using std::string;
template<typename T>
class Bean {
    private:
        T object;
        string name;
    public:
        explicit Bean() {};
        explicit Bean(T obj,string name);
        T& getObject();
        string& getName() {
            return this->name;
        }
        inline bool operator==(const Bean<T>& bean);
};
template<typename T>
class BeanFactory {
    private:
        Bean<T> bean;
    public:
        virtual Bean<T> getBean() = 0;
        virtual void debug(string s) = 0;
};
template<typename T>
class ApplicationContext : public BeanFactory<T> {
    private:
        Bean<T> bean;
    public:
        explicit ApplicationContext();
        explicit ApplicationContext(Bean<T> bean);
        ApplicationContext(const BeanFactory<T>& b) = delete;
        virtual Bean<T> getBean();
        virtual void debug(string s);
};
template<typename T>
Bean<T>::Bean(T obj,string name):object(obj),name(name){}
template<typename T>
T& Bean<T>::getObject() {
    return this->object;
}
template<typename T>
inline bool Bean<T>::operator==(const Bean<T>& bean) {
    return this->object == bean.getObject;
}
template<typename T>
ApplicationContext<T>::ApplicationContext() {
    this->bean = nullptr;
}
template<typename T>
ApplicationContext<T>::ApplicationContext(Bean<T> bean) {
    this->bean = bean;
}
template<typename T>
Bean<T> ApplicationContext<T>::getBean() {
    return this->bean;
}
template<typename T>
void ApplicationContext<T>::debug(string s) {
    cout<<"debug:"<<bean.getName()<<" + "<<s<<endl;
}
int main() {
    Bean<string> bean("Scala","fucking");
    BeanFactory<string> *context = new ApplicationContext<string>(bean);
    context->debug("hahaha");
    context->debug(bean.getObject());
    delete context;
    return 0;
}

编译：g++ klass.cpp -o klass -g -std=c++11
注意：需要调试的时候，最好在用g++编译的时候加上-g参数，以便将源代码信息编译到可执行文件中。当然玩逆向的话就看汇编代码吧→_→
进入gdb，然后使用file <filename>命令加载文件。
然后可使用r命令(run)执行可执行文件。若没下断点，则相当于正常执行：

1
2
debug:fucking + hahaha
debug:fucking + Scala

下面在main函数处下一个断点(Breakpoint)：b main
反馈：Breakpoint 1 at 0x400e61: file klass.cpp, line 75.表示断点地址在0x400e61处
然后我们再次使用r命令执行，程序将停在断点处：

1
2
Breakpoint 1, main () at klass.cpp:75
75      int main() {

此界面中可以查看汇编代码、表达式、历史记录、内存使用、寄存器值、源代码（如果有的话）、堆栈信息和线程信息

gdb

接着使用s命令(step into)步入执行下面的语句，遇到函数调用则步入此函数。在生成Bean对象实例的时候步入Bean的构造函数：

Bean的构造函数信息

顺着下去，可以观察完整的过程。这里只是总结gdb的使用，就不再阐述了。

下面是关于断点的一些用法：

命令 解释 示例
b <行号> 在此行号处下断点 b 75
b <函数名称> 在此函数处下断点 b service
b *<函数名称> 在此函数的入口点（prolog）处下断点 b *main
b *<函数地址> 在此函数地址处下断点 b *0x400e61
d <编号> 删除指定编号的断点或删除所有断点 d

查看某个变量可以用p <变量名>命令，比如查看bean的详细信息：

1
2
3
4
5
>>> p bean         
$1 = {             
  object = "Scala",
  name = "fucking"
}

继续执行可以用c命令，若下面还有断点则中断到下一个断点。
若需要看本行代码对应的汇编代码可用display /i $pc命令，这样就能在Outputs一栏显示出当前汇编代码，比如：

1
2
3
4
5
6
debug:fucking + hahaha
Breakpoint 4, main () at klass.cpp:79
79              context->debug(bean.getObject());
1: x/i $pc
=> 0x400f8f <main()+313>:       mov    -0x48(%rbp),%rax

若想逐行汇编代码步入执行，可以用si命令。
下面总结一下step命令：

命令 解释
s step into(单步跟踪进入）
n step over（单步跟踪）
si 逐行汇编代码步入
ni 逐行汇编代码步出

还有一个非常有用的命令就是i <信息>，用于显示对应信息，简单总结一下常用的：

命令 解释
i args 显示当前栈帧上的变量信息
i address <name> 显示对应对象、方法或变量name的地址
i breakpoints（缩写i b） 显示当前的所有断点
i variables 显示当前所有的静态变量和全局变量
i vtbl <object> 显示object对象的虚函数表(vtable)
i frame（缩写i f 显示栈帧信息
i registers(缩写i r） 显示寄存器信息

比如查看context对象的虚函数表：

1
2
3
4
5
>>> i vtbl context
warning: RTTI symbol not found for class 'ApplicationContext<std::string>'
vtable for 'BeanFactory<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >' @ 0x401530 (subobject @ 0x603070):
[0]: 0x40139a <ApplicationContext<std::string>::getBean()>
[1]: 0x4013c8 <ApplicationContext<std::string>::debug(std::string)>

最后退出当然是命令q咯~

后面将用gdb调试HotSpot JVM以便更深入地了解JVM的运行原理。

Develop

缓存算法（页面置换算法）总结

首先解释一下，缓存算法和内存页面置换算法（Page Replacement Algorithm）的核心思想是一样的，都是给定一个有限的空间，设计一个算法来更新和访问里面的数据，所以把它们放在一起讨论总结。下面提到缓存算法的同时，也指代页面置换算法。

常见的缓存算法有 FIFO、Least Recently Used (LRU)、Least Frequently Used (LFU)。

FIFO

FIFO 算法是一种比较容易实现的算法。它的思想是先进先出（FIFO，队列），这是最简单、最公平的一种思想，即如果一个数据是最先进入的，那么可以认为在将来它被访问的可能性很小。空间满的时候，最先进入的数据会被最早置换（淘汰）掉。

FIFO 算法的描述：设计一种缓存结构，该结构在构造时确定大小，假设大小为 K，并有两个功能：

  1. set(key,value)：将记录(key,value)插入该结构。当缓存满时，将最先进入缓存的数据置换掉。
  2. get(key)：返回key对应的value值。

实现：维护一个FIFO队列，按照时间顺序将各数据（已分配页面）链接起来组成队列，并将置换指针指向队列的队首。再进行置换时，只需把置换指针所指的数据（页面）顺次换出，并把新加入的数据插到队尾即可。

缺点：判断一个页面置换算法优劣的指标就是缺页率，而FIFO算法的一个显著的缺点是，在某些特定的时刻，缺页率反而会随着分配页面的增加而增加，这称为Belady现象。产生Belady现象现象的原因是，FIFO置换算法与进程访问内存的动态特征是不相容的，被置换的内存页面往往是被频繁访问的，或者没有给进程分配足够的页面，因此FIFO算法会使一些页面频繁地被替换和重新申请内存，从而导致缺页率增加。因此，现在不再使用FIFO算法。

LRU

LRU（The Least Recently Used，最近最久未使用算法）是一种常见的缓存算法，在很多分布式缓存系统（如Redis, Memcached）中都有广泛使用。

LRU算法的思想是：如果一个数据在最近一段时间没有被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最久没有访问的数据最先被置换（淘汰）。

LRU算法的描述： 设计一种缓存结构，该结构在构造时确定大小，假设大小为 K，并有两个功能：

  1. set(key,value)：将记录(key,value)插入该结构。当缓存满时，将最久未使用的数据置换掉。
  2. get(key)：返回key对应的value值。

实现：最朴素的思想就是用数组+时间戳的方式，不过这样做效率较低。因此，我们可以用双向链表（LinkedList）+哈希表（HashMap）实现（链表用来表示位置，哈希表用来存储和查找），在Java里有对应的数据结构LinkedHashMap。

LeetCode上有关于LRU的一道题（LeetCode #146）：

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

  • get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
  • set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

这里我用了双向链表+哈希表实现的。

C++ code(72 ms):

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#define DEFAULT_LIST_SIZE 10
class LRUCache {
    private:
        class Node {
            public:
                int key;
                int value;
                Node* pre;
                Node* next;
                Node(int key,int value,Node* pre,Node* next) {
                    this->key = key;
                    this->value = value;
                    this->pre = pre;
                    this->next = next;
                }
        };
        int count;
        int size;
        unordered_map<int,Node*> mp;
        Node* cacheHead;
        Node* cacheTail;
        void push_front(Node* cur) {
            if(count == 1 || cur == cacheHead) {
                return;
            }
            if(cur == cacheTail) {
                cacheTail = cur->pre;
            }
            cur->pre->next = cur->next;
            if(cur->next != nullptr) {
                cur->next->pre = cur->pre;
            }
            cur->next = cacheHead;
            cur->pre = nullptr;
            cacheHead->pre = cur;
            cacheHead = cur;
        }
    public:
        LRUCache() {
            this->size = DEFAULT_LIST_SIZE;
            this->count = 0;
            this->cacheHead = nullptr;
            this->cacheTail = nullptr;
        }
        LRUCache(int capacity):size(capacity) {
            this->count = 0;
            this->cacheHead = nullptr;
            this->cacheTail = nullptr;
        }
        void set(int key, int value) {
            if(cacheHead == nullptr) {
                cacheHead = new Node(key,value,nullptr,nullptr);
                mp[key] = cacheHead;
                cacheTail = cacheHead;
                count++;
            }
            else {
                unordered_map<int,Node*>::iterator it = mp.find(key);
                if(it == mp.end()) {
                    if(count == size) {
                        if(cacheHead == cacheTail && cacheHead != nullptr) {
                            mp.erase(cacheHead->key);
                            cacheHead->key = key;
                            cacheHead->value = value;
                            mp[key] = cacheHead;
                        }
                        else {
                            Node *p = cacheTail;
                            cacheTail->pre->next = cacheTail->next;
                            cacheTail = cacheTail->pre;
                            mp.erase(p->key);
                            p->key = key;
                            p->value = value;
                            p->next = cacheHead;
                            p->pre = cacheHead->pre;
                            cacheHead->pre = p;
                            cacheHead = p;
                            mp[cacheHead->key] = cacheHead;
                        }
                    }
                    else {
                        Node* p = new Node(key,value,nullptr,cacheHead);
                        cacheHead->pre = p;
                        cacheHead = p;
                        mp[cacheHead->key] = cacheHead;
                        count++;    
                    }
                }
                else {
                    Node *p = it->second;
                    p->value = value;
                    pushFront(p);
                }
            }
        }
        int get(int key) {
            if(cacheHead == nullptr)
                return -1;
            unordered_map<int,Node*>::iterator it = mp.find(key);
            if(it == mp.end()) {
                return -1;
            }
            else {
                Node* p = it->second;
                pushFront(p);
            }
            return cacheHead->value;
        }
};

LFU 算法

LFU（Least Frequently Used ，最近最少使用算法）也是一种常见的缓存算法。

顾名思义，LFU算法的思想是：如果一个数据在最近一段时间很少被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最小频率访问的数据最先被淘汰。

LFU 算法的描述：

设计一种缓存结构，该结构在构造时确定大小，假设大小为 K，并有两个功能：

  1. set(key,value)：将记录(key,value)插入该结构。当缓存满时，将访问频率最低的数据置换掉。
  2. get(key)：返回key对应的value值。

算法实现策略：考虑到 LFU 会淘汰访问频率最小的数据，我们需要一种合适的方法按大小顺序维护数据访问的频率。LFU 算法本质上可以看做是一个 top K 问题(K = 1)，即选出频率最小的元素，因此我们很容易想到可以用二项堆来选择频率最小的元素，这样的实现比较高效。最终实现策略为小顶堆+哈希表。

OPT算法

最佳页面置换算法（OPT，Bélády’s Algorithm）是一种理论上最佳的页面置换算法。它的思想是，试图淘汰掉以后永远也用不到的页面，如果没有则淘汰最久以后再用到的页面。因为这种算法必须知道进程访问页面的序列，而这是无法实现的，因此仅有理论意义。

Algorithm

Web开发笔记 - 前端总结 (性能篇)

从一个用户的角度来说，网站的性能就是用户在浏览器上访问网页的直观感受，加载网页的快慢，加载资源的快慢。通过对前端的性能优化，可以使浏览器尽快地显示内容，对用户更为友好。所以，为了给用户更好的体验，Web前端性能优化是非常有必要的。

CSS、JS代码优化

  • 避免使用CSS表达式，虽然功能强大但是效率低下。
  • 避免使用CSS3的@import，性能非常低。可以在Sass中使用@import，预编译后会将引用的文件合并到一个文件中，不会影响性能。
  • 使用前端构建工具（比如Grunt的grunt-contrib-unglify）压缩精简CSS、JS代码（混淆），消除重复、无用代码，并且合并代码，尽量减少HTTP请求次数。

减少DNS查询

DNS查询会消耗一定时间。使用 DNS缓存 可有效减少DNS查询（只要对应的解析地址不要常变动就好）。

使用CDN

CDN的本质也是缓存，并且由于CDN部署在网络运营商的机房，而这些机房又为用户提供网络服务。所以CDN是将数据缓存在离用户最近的地方，让用户以最快的速度获取资源。一般地，CDN用来缓存静态资源，如图片、CSS、JS脚本、静态网页等等的访问频率较高而变化频率低的静态资源。

使用浏览器缓存

对不经常变化的资源，在HTTP头中添加Expire或Cache-Control，可以设定浏览器缓存。

减少HTTP请求

  • 合并CSS、JS文件（用构建工具）
  • 合并图片文件（利用CSS Sprites），将几个相关的图片合成一张图片，使用的时候通过CSS偏移定位出图片的精确位置即可（比如小按钮）。注意响应式页面下图片的位置。

必要的时候启用压缩

在服务端进行压缩，在浏览器端进行解压缩，可以减少传输的数据量。对HTML、CSS、JS文件启用gzip压缩可达到较好的效果，但是注意压缩会消耗一定的服务器资源，在PV量大而服务器资源不充裕时应谨慎使用。

CSS与JS在网页中的位置

浏览器在获取完所有的CSS资源后才对整个页面进行渲染，因此将CSS放在页面的最上面是最合适的。

而加载JS有可能会阻塞整个页面（可以添加async来达到异步加载的效果），因此JS最好放在页面的底部。当然如果页面解析需要用到JS（比如用AngularJS开发的SPA），那么就应该放在相应的位置，确保页面正常加载。

Web

Web开发笔记 - 前端总结(开发篇)

终于从老家回来咯~有时间总结总结啦~这是Web前端开发篇~

此笔记会不断补充。部分不重要的就不放上来了。

CSS相关

CSS Position

四种定位：static, relative, absolute, fixed

  • static position是HTML元素的默认值，即没有定位，元素出现在正常的流中。静态定位的元素不会受到top, bottom, left, right影响。
  • fixed position是固定位置，常用于实现固定层效果。
  • relative position相对于其正常位置，而 absolute position的元素的位置相对于最近的已定位父元素。

CSS Float && The inline-block Value

CSS 的 Float（浮动），会使元素向左或向右移动，其周围的元素也会重新排列。常用于各区域的水平方向并排化。

横向导航栏也可用 inline-block，可以更好地解决图片的排列问题，或者元素需要多个display属性时。两者各有利弊，需要根据业务需求考虑。

元素显示与隐藏

元素显示与隐藏使用visibility或display属性控制。

顺便提一下display属性，其可以控制显示方式为块级元素和内联元素。区别显而易见，块级元素（如div）占用了全部宽度，在前后都是换行符，而内联元素（如span）相当于内嵌，不强制换行。

而inline-block兼具inline和block的特性，可占有全部宽度而不换行。比起float，inline-block不需要再为after指定clear。当需要控制元素的垂直对齐跟水平排列时，可以使用inline-block。（可代替float）

改变元素的明暗度

改变元素的明暗度可以通过设置一个遮罩层，并改变其透明度来实现。CSS3的opacity属性用来设置元素的不透明级别。

至于IE9 below。。。看着办吧。。

应用：毛玻璃效果（Login界面）、购物导航（hover辅助）、配合HTML5和JS的各种cool效果。

CSS Box Model

  • Margin - 清除边框区域。Margin没有背景颜色，它是完全透明的
  • Border - 边框周围的填充和内容。边框是受到盒子的背景颜色影响
  • Padding - 清除内容周围的区域。会受到框中填充的背景颜色影响
  • Content - 盒子的内容，显示文本和图像

CSS Box Model

超出元素的部分隐藏

使用overflow : hidden

CSS3 transition/transform

CSS 3可以直接写过渡(transition)而不需要JQuery等库的帮助，而transform则是做2D、3D转换。

用示例总结：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
div {
width: 233px;
height: 233px;
background: green;
transition:width 2s linear, height 2s;
-moz-transition:width 2s, height 2s, -moz-transform 2s; /* Firefox 4 */
-webkit-transition:width 2s, height 2s linear, -webkit-transform 2s; /* Safari and Chrome */
-o-transition:width 2s, height 2s, -o-transform 2s; /* Opera */
}
div:hover {
width:233px;
height:233px;
transform:rotate(180deg);  /*旋转180度*/
-moz-transform:rotate(180deg); /* Firefox 4 */
-webkit-transform:rotate(180deg); /* Safari and Chrome */
-o-transform:rotate(180deg); /* Opera */
}

PS:有些东西用JS比CSS 3方便很多，不过还是了解一下的好~况且CSS3动画性能应该比JS要高一些

CSS Enhancer

只用过Sass，Less.js木有用过不了解。
Sass是一个基于Ruby的CSS预处理器，相当于CSS的一个增强版吧。Compass则相当于一个Sass框架，提供了许多mixin的功能。
在Terminal里开compass watch可以实时编译sass/scss文件
总结一下Sass的特性

可定义变量

Sass中可以定义变量，方便统一修改和维护重复、相同的值。

模块化思想

Sass中可以导入其它sass/scss文件，但与CSS 3中的@import意义不同，Sass改写了@import的意义，Sass中的import在预编译时会将所有模块合并，因此性能优于CSS3的import。

1
2
3
4
5
6
7
$headline-font: 微软雅黑,Arial,sans-serif;
@import "compass/reset" //这一句用来覆盖掉浏览器的默认样式
.mian-sec {
    font-family: $headline-font;
}

嵌套

Sass中可以进行选择器的嵌套表示层级关系，更加简便、直观。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
nav {
  ul {
    margin: 0;
    padding: 0;
    list-style: none;
  }
  li { display: inline-block; }
  a {
    display: block;
    padding: 6px 12px;
    text-decoration: none;
  }
}

顺便再总结一下CSS3中的f4cking 组合选择符：

  • 后代选取器(以空格分隔)
  • 子元素选择器(以大于号分隔）
  • 相邻兄弟选择器（以加号分隔）
  • 普通兄弟选择器（以破折号分隔）

写的时候都能晕了有木有。。所以有Sass真是方便的多。

mixin

Sass中可用mixin定义一些代码片段（相当于function），且可传参数，方便日后根据需求调用，这使得写CSS3浏览器兼容时更加便捷。

1
2
3
4
5
6
7
8
9
@mixin box-sizing ($sizing) {
    -webkit-box-sizing:$sizing;     
       -moz-box-sizing:$sizing;
            box-sizing:$sizing;
}
.box-border{
    border:1px solid #ccc;
    @include box-sizing(2px);
}

扩展/继承

Sass可通过@extend来实现代码组合声明，使代码更加简洁优美。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
.message {
  border: 1px solid #ccc;
  padding: 10px;
  color: #333;
}
.success {
  @extend .message;
  border-color: green;
}
.error {
  @extend .message;
  border-color: red;
}

其它

Sass中可以进行简单的加减乘除运算。并且Sass提供了许多操作颜色的内建函数，让调色更方便。

Sass可以用命令行编译，也可以用GUI工具编译~用Sublime的话推荐配合使用神器Koala，鹅厂出品，非常方便。
用WebStorm的话都支持自动编译sass/scss文件的，还是InteliJ大法好！

Bootstrap相关

写UI个人比较喜欢用Bootstrap及其各种变种（比如Flat-UI），其实主要还是因为懒（总感觉Bootstrap特别适合给不熟悉前端设计的后端开发者使用。。）

重中之重-Bootstrap Grid System

Bootstrap采用移动设备优先的原则。

Bootstrap网格系统具有响应式的特点，可随着设备大小进行分栏，响应式网格系统随着屏幕或视口（viewport）尺寸的增加，系统会自动分为最多12列。12个总格位主要有112、26、8+4、34、121这几种分栏方式。

网格系统有四种尺寸:

  • xs (for phones <768px)
  • sm (for tablets >=768px)
  • md (for desktops >=992px)
  • lg(for larger desktops >=1200px)

可以一次使用多种尺寸来构建自适应的页面。

网格系统的结构：

First,create a row . Then, add the desired number of columns (tags with appropriate .col-- classes). Note that numbers in .col-- should always add up to 12 for each row.

1
2
3
<div class="row">
  <div class="col-*-*"></div>
</div>

比如分三栏：

1
2
3
4
5
<div class="row">
  <div class="col-sm-4">Fucking Scala</div>
  <div class="col-sm-4">Fucking Scala</div>
  <div class="col-sm-4">Fucking Scala</div>
</div>

另外需要注意响应式的列重置、偏移列及嵌套列问题。
别的暂时没什么好总结的了，查查手册应该就可以解决。重要的是响应式页面的设计。

JQuery相关

项目中用的比较多，内容太多，慢慢填坑。

MVC、MVVM框架

目前常用的MVC/MVP/MVVM/MVW框架主要有BackboneJS（第一代前端MVC框架，仅作了解），EmberJS（MVC框架，和AngularJS思想相似，仅作了解）以及目前特别常用的MVVM框架AngularJS。这里仅总结AngularJS（目前版本为1.4.4，为什么要写版本？因为这货不一定哪一次更新就会deprecate很多旧特性。。）

有的人不明白AngularJS的用途，认为“万事皆可用AngularJS”，这样就没有领悟AngularJS的精髓。AngularJS最适合开发RESTful风格的SPA（国内各种云服务的Dashboard以及Gmail、Twitter都应用了AngularJS)，而如果开发非应用型网站则要看业务需求，用AngularJS不一定是最佳选择。

这里内容也太多，先总结思想吧。

AngularJS的一大特点是bi-directional data binding，即数据双向绑定。它和JQuery的思维有着天壤之别。JQuery的思想是先构建好一个页面，再通过各种DOM操作编写动作；而用AngularJS写页面时，对DOM的直接操作是完全没有必要，也是不被提倡的。在AngularJS中用声明式的数据绑定就可以很好地实现JQuery中命令式的功能。并且，我们心中要对整个页面的结构有个把握，页面分成几个组件，每个组件由不同的控制器负责，数据模型应合理设计。有重复的逻辑是否可以抽象出来，提供一个统一的函数，配合回调达到功能的可扩展化。

总之，AngularJS提供了一种类似于后端的思考方式，可以更好地对网页组件进行解耦，方便日后的开发和维护。后面会详细总结AngularJS的开发。

模板引擎

主要是EJS和Jade。Jade的语法，只能说，诡异！！！所以用Node.js构建博客时页面模板引擎果断用了EJS（其实我也不知道哪个性能好些，反正EJS没有那么诡异。。）
待填坑 >_<

ReactJS

ReactJS是一个View层组件，专门负责View层的开发。很喜欢它的Virtual DOM的设计，优化了性能。（比原生DOM性能快，当然也不支持所有的DOM操作）

这个也没有太多实践（毕竟是View层），以后可以试试React Native构建Hybrid App，写个个人博客的管理器还是可以的~

构建工具

前端构建工具主要有流式构建工具Gulp.js及Grunt，用于压缩、合并依赖文件。前端构建工具貌似一直在改进，变化很快（后端也是，比如Java项目构建，从Maven到Gradle），不过万变不离其宗，核心流程是没有变的。
两者用起来比较接近，主要就是package.json + Gruntfile.js(gulp.js)的配置。
以Grunt为例，先npm init生成package.json文件，该文件主要配置项目基本信息及工具插件依赖，以让 Node.js 知道下载哪些插件，重点是devDependencies字段。
至于其使用，麻烦诶。。就简单用了用，不是专业写前端的话一般懒得用。。

依赖包管理

主要用过bower和npm，很方便。

Bower节省了时间，相当于建立了一个本地仓库（类似于Maven的.m2仓库），并且bower.json可以很容易地展现各种依赖关系。给依赖库升级也更加方便了，一句bower update <package-name>完事。Bower的优点是约束比较松散，使用很简单，缺点就是不提供构建工具，需要配合Glup.js或Grunt。

配合Grunt的一些插件

  • grunt-bower-concat
  • grunt-wiredep
  • grunt-bower-requirejs
  • grunt-bower-task
  • grunt-preen

配合Glup.js的一些插件

  • gulp-google-cdn（国内呵呵）
  • main-bower-files
  • preen
  • gulp-bower-normalize

npm 和Browserify配合相当于间接给浏览器提供了npm的功能（Browserify本身不是模块管理器，只是让服务器端的CommonJS格式的模块可以运行在浏览器端）。

Web

LeetCode | 链表相关算法总结

这里总结一下常见的与链表有关的算法。

链表成环的各种问题

判断一个单链表是否存在环

这个思路比较简单，用 两个指针代表快、慢指针，然后从头指针开始，快指针一次前进两个结点，慢指针一次前进一个结点，则如果两个指针相遇（相等），则一定有环。若两指针不相遇，则 fast 指针遇到空指针后便结束循环。

  • 扩展：这种快、慢指针的思路还可用于找到无环链表的中间元素，当快指针到尾部时，慢指针正好到中间元素的位置。可用于链表的归并排序。

  • 扩展：这种两个指针的思路还可以用于寻找链表的第k个结点，思路同上。

对应：LeetCode 141 - Linked List Cycle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;
        while(fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if(fast == slow)
                return true;
        }
        return false;
    }
};

若存在环，求环的长度

此处有定理I： 两指针（fast和slow）从第一次碰撞点出发到第二次碰撞所走的长度即为环的长度。

链表成环的情况

若存在环，求环的入口（连接点）

此处有定理II：第一次碰撞点到环的入口的距离，等于头指针到环的入口的距离。因此，分别从头指针和碰撞点遍历链表，第一次相遇的点即为换的入口（连接点）。

证明如下：
设单链表的总长度为L，头结点到环入口的距离为a，环入口到快慢指针相遇的结点距离为x，环的长度为r，慢指针总共走了s步，则快指针走了2s步。并且，快指针要追赶上慢指针，在环内的圈数n >= 1；因此我们可以列出式子：

$$s = a + x$$
$$2s = a + nr + x$$
$$=> a = nr - x = (n-1)r + y$$

由上式可知成立。
对应：LeetCode 142 - Linked List Cycle II

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
27
28
29
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;
        while(fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow) {
                ListNode *q = head;
                while(q != slow) {
                    q = q->next;
                    slow = slow->next;
                }
                return q;
            }
        }
        return nullptr;
    }
};

链表相交的各种问题

如何判断链表相交，若相交则找到第一个交点

Question：给出两个单向链表的头指针，而两个链表都可能带环，判断这两个链表是否相交，并且给出他们相交的第一个节点。

思路：

首先根据上边的算法判断链表是否成环。

第一种情况：两个链表都不成环
思路1：将其中一个链表首尾相连，判断另一个链表是否存在环，如果存在，则两个链表相交，且找出来的环入口点即为相交的第一个点。
思路2：若如果两个不成环的链表相交，那么两个链表从相交点到尾结点都是相同的结点。首先先遍历两个链表，记录下两个链表的长度（长链表a，短链表b）。然后先让长链表移动a-b长度，然后两链表开始同步前进，相遇的第一个点即为环的第一个交点。

    A:          a1 → a2
                       ↘
                         c1 → c2 → c3
                       ↗            
    B:     b1 → b2 → b3

对应：LeetCode 160 - Intersection of Two Linked Lists

第二种情况：两个链表都成环

不可能的情况：一个有环，一个没有环

很好想的，如果两个链表一个有环，一个无环的话，那么它们不可能相交。

Algorithm

深入探究 JVM | 类加载器与双亲委派模型

类的加载过程指通过一个类的全限定名来获取描述此类的二进制字节流，并将其转化为方法区的数据结构，进而生成一个java.lang.Class对象作为方法区这个类各种数据访问的入口。这个过程通过Java中的类加载器(ClassLoader)来完成。

类与类加载器

类加载器非常重要，因为每个类加载器都有一个独立的类名称空间。比如我们要加载两个类，如果要比较两个类是否相等（包括equals()方法、isAssignableFrom()方法、isInstance()方法），只有在这两个类被同一个类加载器加载的前提下，比较才有意义。否则，即使两个类来自同一个class文件，被同一个JVM加载，但是加载它们的类加载器不同，则这两个类就不相等。这就相当于两个命名空间中的等价类LoaderA::C和LoaderB::C。

类加载器的种类

从一般角度来分的话，ClassLoader分为根加载器（Bootstrap ClassLoader）和其它的加载器。其中Bootstrap ClassLoader负责加载Java的核心类，由JVM实现(C++)，而其它类加载器都由Java层实现并继承java.lang.ClassLoader。

更细分的话，ClassLoader分为：

  • Bootstrap ClassLoader（启动类加载器）负责将%JAVA_HOME%/lib目录中或-Xbootclasspath中参数指定的路径中的，并且是虚拟机识别的（按名称）类库加载到JVM中
  • Extension ClassLoader（扩展类加载器）负责加载%JAVA_HOME%/lib/ext中的所有类库
  • System ClassLoader（加载%CLASSPATH%路径的类库）以及其它自定义的ClassLoader

双亲委派模型

JVM中类加载的机制——双亲委派模型。这个模型要求除了Bootstrap ClassLoader外，其余的类加载器都要有自己的父加载器。子加载器通过组合来复用父加载器的代码，而不是使用继承。在某个类加载器加载class文件时，它首先委托父加载器去加载这个类，依次传递到顶层类加载器(Bootstrap)。如果顶层加载不了（它的搜索范围中找不到此类），子加载器才会尝试加载这个类。

双亲委派模型最大的好处就是让Java类同其类加载器一起具备了一种带优先级的层次关系。这句话可能不好理解，我们举个例子。比如我们要加载顶层的Java类——java.lang.Object类，无论我们用哪个类加载器去加载Object类，这个加载请求最终都会委托给Bootstrap ClassLoader，这样就保证了所有加载器加载的Object类都是同一个类。如果没有双亲委派模型，那就乱了套了，完全可以搞出Root::Object和L1::Object这样两个不同的Object类。

双亲委派模型的实现比较简单，在java.lang.ClassLoader的loadClass方法中：

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
27
28
29
30
31
32
33
34
35
36
37
protected Class<?> loadClass(String name, boolean resolve)
        throws ClassNotFoundException
    {
        synchronized (getClassLoadingLock(name)) {
            // First, check if the class has already been loaded
            Class<?> c = findLoadedClass(name);
            if (c == null) {
                long t0 = System.nanoTime();
                try {
                    if (parent != null) {
                        c = parent.loadClass(name, false);
                    } else {
                        c = findBootstrapClassOrNull(name);
                    }
                } catch (ClassNotFoundException e) {
                    // ClassNotFoundException thrown if class not found
                    // from the non-null parent class loader
                }
                if (c == null) {
                    // If still not found, then invoke findClass in order
                    // to find the class.
                    long t1 = System.nanoTime();
                    c = findClass(name);
                    // this is the defining class loader; record the stats
                    sun.misc.PerfCounter.getParentDelegationTime().addTime(t1 - t0);
                    sun.misc.PerfCounter.getFindClassTime().addElapsedTimeFrom(t1);
                    sun.misc.PerfCounter.getFindClasses().increment();
                }
            }
            if (resolve) {
                resolveClass(c);
            }
            return c;
        }
    }

注意JVM的双亲委派模型也会遭到破坏（Java自己就破坏好几次）。

Java

博客搬迁咯~

此文章仅为测试用

以前那个VPS真的太慢了。。旧博客系统一时脑残用了WordPress，对md的支持很不好，所以这次换了支持md比较好的博客系统Hexo。
说起来发现Hexo这个博客系统还真是偶然，当时是练习Dockerfile构建的时候看到了这个玩意，构建完后便试用了一下发现很方便，很好用，正好以前的VPS到期了，所以就趁着这个机会把博客迁移到Hexo上。
至于以前的文章，有意义的还会贴上来，有些比较麻烦不好转换成md的就先不贴了。
新的开始~
（PS：期末考试终于快结束啦哈哈哈！！！）

附赠薛定谔方程，测试一下LaTex引擎:
$$ i\hbar\frac{\partial \psi}{\partial t}
= \frac{-\hbar^2}{2m} \left(
\frac{\partial^2}{\partial x^2}+ \frac{\partial^2}{\partial y^2}+ \frac{\partial^2}{\partial z^2}
\right) \psi + V \psi $$

Life

深入探究 JVM | HotSpot JVM 的 GC 实现

HotSpot JVM中GC的实现主要有以下的几种：

  • Serial/Serial Old
  • ParNew
  • Parallel Scavenge/Parallel Old
  • Concurrent Mark Sweep(CMS)
  • Garbage First(G1)

分别简单总结一下。

Serial/Serial Old

Serial 收集器是最基本的、历史最悠久的收集器。从字面上就能看出，这是一个单线程的收集器，即在进行GC时必须STW。

Serial收集器在新生代采用复制算法，在老年代采用标记-清理-压缩算法(Serial Old)。

ParNew

ParNew收集器是Serial收集器的多线程版本，采用多线程进行收集，但一样要STW。

与Serial类似，ParNew收集器在新生代采用复制算法，在老年代采用标记-清理-压缩算法。

ParNew比较重要，因为它可以配合CMS收集器一起使用(Parallel Scavenge则不行)。ParNew是-XX:+UseConcMarkSweepGC选项下默认的新生代收集器。

Parallel Scavenge

Parallel Scavenge是一个新生代收集器，它与ParNew最主要的区别是它的目标是吞吐量优先而不是时间优先（注意这两个不能兼得）。所谓吞吐量就是CPU用于运行用户代码的时间与CPU运行总时间的比值。吞吐量优先适合在后台完成计算而不需要太多交互的业务，而时间优先适合需要交互和实时性的业务。
Parallel Scavenge可以精确控制吞吐量，通过两个参数：控制最大垃圾收集停顿时间的-XX:MaxGCPauseMillis参数及直接设置吞吐量大小的-XX:GCTimeRatio参数。它还可以通过打开-XX:+UseAdaptiveSizePolicy参数进行自适应调节(GC Ergonomics)，打开后JVM会根据当前运行状况收集监控信息并动态调整参数来提供最合适的吞吐量，配合前两个参数使用更好。

Parallel Old

Parallel Old是Parallel Scavenge对应的老年代版本，目标也是吞吐量优先，可以与Parallel Scavenge结合。

Concurrent Mark Sweep

CMS是真正意义上的并发收集器，作用于老年代。CMS的目标是时间优先（最短停顿时间），像服务器之类的就很适合跑在CMS收集器下，因为互联网服务重视服务的响应速度，希望系统延迟时间短。CMS通常与ParNew配合使用。

CMS的过程

CMS是基于标记-清除算法实现的，整个过程分几步：

  • 初始标记(initial-mark)：从GC Root开始，仅扫描与根节点直接关联的对象并标记，这个过程需要STW，但是GC Root数量有限，因此时间较短
  • 并发标记(concurrent-marking)：这个阶段在初始标记的基础上继续向下进行遍历标记。这个阶段与用户线程并发执行，因此不停顿
  • 并发预清理(concurrent-precleaning)：上一阶段执行期间，会出现一些刚刚晋升老年代的对象，该阶段通过重新扫描减少下一阶段的工作。该阶段并发执行，不停顿
  • 重新标记(remark)：重新标记阶段会对CMS堆上的对象进行扫描，以对并发标记阶段遭到破坏的对象引用关系进行修复，以保证执行清理之前对象引用关系是正确的。这一阶段需要STW，时间也比较短暂
  • 并发清理(concurrent-sweeping)：清理垃圾对象，这个过程与用户线程并发执行，不停顿
  • 并发重置(reset)：重置CMS收集器的数据结构，等待下一次GC

可以看到，整个过程中需要STW的阶段仅有初始标记和*重新标记阶段，所以可以说它的停顿时间比较短（当然吞吐量可能会受影响）。

CMS的缺陷

由于CMS是基于 标记-清理 算法的，因此会产生大量的内存碎片。这很可能会出现老年代虽然有大量不连续的空闲内存，但很难找到连续的内存空间来给对象分配，不得不提前触发一次Full GC的情况。针对这一点，CMS提供了一个-XX:+UseCMSCompactAtFullCollection开关（默认开启），用于在CMS要gg的时候进行内存碎片整理从而得到连续的内存空间。这样内存碎片的问题可以解决，但STW的时间也相应变长。

另外，CMS收集器无法处理 浮动垃圾（Floating Garbage），可能出现“Concurrent Mode Failure”失败而导致另一次Full GC的产生。由于CMS并发清理阶段用户线程还在运行着，伴随程序的运行自然还会有新的垃圾不断产生，这一部分垃圾出现在标记过程之后，CMS无法在本次收集中处理掉它们，只好留待下一次GC时再将其清理掉，这一部分垃圾就称为“浮动垃圾”。由于在垃圾收集阶段用户线程还需要运行，即还需要预留足够的内存空间给用户线程使用，因此CMS收集器不能像其他收集器那样等到老年代几乎完全被填满了再进行收集，需要预留一部分空间提供并发收集时的程序运作使用。在默认设置下，CMS收集器在老年代使用了92%的空间后就会被激活(JDK 1.6)。可以通过设置-XX:CMSInitiatingOccupancyFraction的值来改变这个阈值。注意一定要结合实际的运行情况，不要设的太大，假如内存真的太满，CMS要gg的时候就会临时召唤出Serial Old对老年代进行Full GC，停顿时间长，因此一定要合理设置这个参数的值。

日志分析

我们可以通过日志观察一次完整的CMS GC过程(参数：-XX:+UseConcMarkSweepGC -verbose:gc -XX:+PrintGCDetails -XX:+PrintGCTimeStamps)：

1
2
3
4
5
6
7
8
9
10
11
12
50.201: [GC (CMS Initial Mark) [1 CMS-initial-mark: 47452K(174784K)] 349898K(489344K), 0.0289564 secs] [Times: user=0.22 sys=0.00, real=0.03 secs]
50.230: [CMS-concurrent-mark-start]
50.265: [CMS-concurrent-mark: 0.035/0.035 secs] [Times: user=0.07 sys=0.00, real=0.03 secs]
50.265: [CMS-concurrent-preclean-start]
50.268: [CMS-concurrent-preclean: 0.003/0.003 secs] [Times: user=0.01 sys=0.00, real=0.01 secs]
50.268: [CMS-concurrent-abortable-preclean-start]
 CMS: abort preclean due to time 55.290: [CMS-concurrent-abortable-preclean: 1.618/5.022 secs] [Times: user=1.66 sys=0.02, real=5.02 secs]
55.290: [GC (CMS Final Remark) [YG occupancy: 302446 K (314560 K)]55.290: [Rescan (parallel) , 0.0252109 secs]55.315: [weak refs processing, 0.0000131 secs]55.315: [class unloading, 0.0122450 secs]55.327: [scrub symbol table, 0.0103126 secs]55.338: [scrub string table, 0.0007051 secs][1 CMS-remark: 47452K(174784K)] 349898K(489344K), 0.0503070 secs] [Times: user=0.22 sys=0.00, real=0.05 secs]
55.340: [CMS-concurrent-sweep-start]
55.356: [CMS-concurrent-sweep: 0.016/0.016 secs] [Times: user=0.02 sys=0.00, real=0.01 secs]
55.356: [CMS-concurrent-reset-start]
55.357: [CMS-concurrent-reset: 0.000/0.000 secs] [Times: user=0.00 sys=0.00, real=0.00 secs]

【关于CMS-concurrent-abortable-preclean】：从日志中我们还发现了一个细节叫做CMS-concurrent-abortable-preclean，这就要从Concurrent precleaning阶段说起了。Concurrent precleaning阶段的实际行为是：针对新生代做抽样，等待新生代在某个时间段（默认5秒，可以通过CMSMaxAbortablePrecleanTime参数设置）执行一次Minor GC，如果这个时间段内GC没有发生，那么就继续进行下一阶段（Remark）；如果时间段内触发了Minor GC，则可能会执行一些优化（具体可以参考https://blogs.oracle.com/jonthecollector/entry/did_you_know）

G1

G1(Garbage First)收集器是HotSpot JVM最新的垃圾收集器，它最大的特点就是将堆内存划分成多个连续的区域(region)，每个区域大小相等。因此在G1中新生代与老年代都是由若干个Region组成(不需要连续)。Region的大小是可以重新设置的。

G1的优点：可以非常精确地控制停顿；老年代采用标记-压缩算法，避免了内存碎片的问题。

G1会在内部维护一个优先列表，通过一个合理的模型，计算出每个Region的收集成本和收益期望并量化，这样每次进行GC时，G1总是会选择最适合的Region（通常垃圾比较多）进行回收，使GC时间满足设置的条件。

G1新生代GC过程

G1的新生代收集类似于ParNew，同样是基于复制的算法（英文叫evacuation），存活的对象会被移至Survivor区，空间不够则一些对象需要晋升至老年代。新生代收集同样会有STW。

每次GC中，Eden区和Survivor区的大小都会被重新计算来提供给下一次Minor GC（根据内部记录的一些信息以及设置的期望停顿时间）。


Remembered Set

G1通过引入Remembered Set来避免全堆扫描。Remembered Set用于跟踪对象引用。G1中每个Region都有对应的Remembered Set。当JVM发现内部的一个引用关系需要更新（对Reference类型进行写操作），则立即产生一个Write Barrier中断这个写操作，并检查Reference引用的对象是否处于不同的Region之间（用分代的思想，就是新生代和老年代之间的引用）。如果是，则通过CardTable通知G1，G1根据CardTable把相关引用信息记录到被引用对象所属的Region的Remembered Set中，并将Remembered Set加入GC Root。这样，在G1进行根节点枚举时就可以扫描到该对象而不会出现遗漏。

G1老年代GC过程

一共六步，直接放上官方的解释：

Initial Mark(STW)

This is a stop the world event. With G1, it is piggybacked on a normal young GC. Mark survivor regions (root regions) which may have references to objects in old generation.

Initial Marking Phase

Root Region Scanning

Scan survivor regions for references into the old generation. This happens while the application continues to run. The phase must be completed before a young GC can occur.

Concurrent Marking

Find live objects over the entire heap. This happens while the application is running. This phase can be interrupted by young generation garbage collections.

Remark(STW)

Completes the marking of live object in the heap. Uses an algorithm called snapshot-at-the-beginning (SATB) which is much faster than what was used in the CMS collector.

Cleanup(STW and concurrent)

  • Performs accounting on live objects and completely free regions. (Stop the world)
  • Scrubs the Remembered Sets. (Stop the world)
  • Reset the empty regions and return them to the free list. (Concurrent)

Copying(STW)

These are the stop the world pauses to evacuate or copy live objects to new unused regions. This can be done with young generation regions which are logged as [GC pause (young)]. Or both young and old generation regions which are logged as [GC Pause (mixed)].


总结

G1老年代收集的几个要点：

  • Concurrent Marking Phase
    • Liveness information is calculated concurrently while the application is running.
    • This liveness information identifies which regions will be best to reclaim during an evacuation pause.
    • There is no sweeping phase like in CMS.
  • Remark Phase
    • Uses the Snapshot-at-the-Beginning (SATB) algorithm which is much faster then what was used with CMS.
    • Completely empty regions are reclaimed.
  • Copying/Cleanup Phase
    • Young generation and old generation are reclaimed at the same time.
    • Old generation regions are selected based on their liveness.

日志分析

分析日志可以清晰地观察G1的收集阶段（JVM参数-XX:+UseG1GC -verbose:gc -XX:+PrintGCDetails -XX:+PrintGCTimeStamps）：

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
5.891: [GC pause (G1 Evacuation Pause) (young), 0.0288342 secs]
   [Parallel Time: 22.9 ms, GC Workers: 8]
      [GC Worker Start (ms): Min: 5891.4, Avg: 5891.4, Max: 5891.5, Diff: 0.1]
      [Ext Root Scanning (ms): Min: 1.1, Avg: 3.0, Max: 13.6, Diff: 12.5, Sum: 24.1]
      [Update RS (ms): Min: 0.0, Avg: 0.3, Max: 0.7, Diff: 0.7, Sum: 2.1]
         [Processed Buffers: Min: 0, Avg: 3.9, Max: 10, Diff: 10, Sum: 31]
      [Scan RS (ms): Min: 0.0, Avg: 0.5, Max: 0.8, Diff: 0.7, Sum: 3.8]
      [Code Root Scanning (ms): Min: 0.0, Avg: 0.1, Max: 0.4, Diff: 0.4, Sum: 1.0]
      [Object Copy (ms): Min: 3.3, Avg: 13.8, Max: 20.2, Diff: 16.9, Sum: 110.5]
      [Termination (ms): Min: 0.0, Avg: 5.1, Max: 5.8, Diff: 5.8, Sum: 40.8]
         [Termination Attempts: Min: 1, Avg: 1.0, Max: 1, Diff: 0, Sum: 8]
      [GC Worker Other (ms): Min: 0.0, Avg: 0.0, Max: 0.0, Diff: 0.0, Sum: 0.1]
      [GC Worker Total (ms): Min: 22.8, Avg: 22.8, Max: 22.8, Diff: 0.1, Sum: 182.4]
      [GC Worker End (ms): Min: 5914.2, Avg: 5914.2, Max: 5914.3, Diff: 0.0]
   [Code Root Fixup: 0.2 ms]
   [Code Root Purge: 0.0 ms]
   [Clear CT: 0.3 ms]
   [Other: 5.4 ms]
      [Choose CSet: 0.0 ms]
      [Ref Proc: 4.8 ms]
      [Ref Enq: 0.1 ms]
      [Redirty Cards: 0.2 ms]
      [Humongous Register: 0.0 ms]
      [Humongous Reclaim: 0.0 ms]
      [Free CSet: 0.2 ms]
   [Eden: 251.0M(251.0M)->0.0B(273.0M) Survivors: 14.0M->34.0M Heap: 286.6M(512.0M)->58.6M(512.0M)]
 [Times: user=0.18 sys=0.00, real=0.02 secs]
 8.119: [GC pause (Metadata GC Threshold) (young) (initial-mark), 0.0240591 secs]
   [Parallel Time: 14.9 ms, GC Workers: 8]
      [GC Worker Start (ms): Min: 8119.1, Avg: 8119.4, Max: 8120.3, Diff: 1.1]
      [Ext Root Scanning (ms): Min: 0.5, Avg: 2.3, Max: 9.7, Diff: 9.2, Sum: 18.2]
      [Update RS (ms): Min: 0.0, Avg: 0.2, Max: 0.4, Diff: 0.4, Sum: 1.2]
         [Processed Buffers: Min: 0, Avg: 2.5, Max: 6, Diff: 6, Sum: 20]
      [Scan RS (ms): Min: 0.0, Avg: 0.7, Max: 0.9, Diff: 0.9, Sum: 5.4]
      [Code Root Scanning (ms): Min: 0.0, Avg: 0.2, Max: 0.4, Diff: 0.4, Sum: 1.3]
      [Object Copy (ms): Min: 4.9, Avg: 11.1, Max: 12.4, Diff: 7.5, Sum: 89.2]
      [Termination (ms): Min: 0.0, Avg: 0.1, Max: 0.1, Diff: 0.1, Sum: 0.7]
         [Termination Attempts: Min: 1, Avg: 20.9, Max: 31, Diff: 30, Sum: 167]
      [GC Worker Other (ms): Min: 0.0, Avg: 0.0, Max: 0.0, Diff: 0.0, Sum: 0.1]
      [GC Worker Total (ms): Min: 13.7, Avg: 14.5, Max: 14.8, Diff: 1.1, Sum: 116.1]
      [GC Worker End (ms): Min: 8133.9, Avg: 8134.0, Max: 8134.0, Diff: 0.0]
   [Code Root Fixup: 0.3 ms]
   [Code Root Purge: 0.0 ms]
   [Clear CT: 0.2 ms]
   [Other: 8.6 ms]
      [Choose CSet: 0.0 ms]
      [Ref Proc: 8.2 ms]
      [Ref Enq: 0.0 ms]
      [Redirty Cards: 0.1 ms]
      [Humongous Register: 0.0 ms]
      [Humongous Reclaim: 0.0 ms]
      [Free CSet: 0.1 ms]
   [Eden: 159.0M(273.0M)->0.0B(291.0M) Survivors: 34.0M->16.0M Heap: 219.6M(512.0M)->68.1M(512.0M)]
 [Times: user=0.11 sys=0.00, real=0.03 secs]
8.143: [GC concurrent-root-region-scan-start]
8.151: [GC concurrent-root-region-scan-end, 0.0081611 secs]
8.151: [GC concurrent-mark-start]
8.191: [GC concurrent-mark-end, 0.0399863 secs]
8.192: [GC remark 8.192: [Finalize Marking, 0.0005544 secs] 8.192: [GC ref-proc, 0.0002680 secs] 8.192: [Unloading, 0.0068146 secs], 0.0079309 secs]
 [Times: user=0.04 sys=0.00, real=0.00 secs]
8.200: [GC cleanup 74M->66M(512M), 0.0005223 secs]
 [Times: user=0.00 sys=0.00, real=0.00 secs]
8.201: [GC concurrent-cleanup-start]
8.201: [GC concurrent-cleanup-end, 0.0000154 secs]

目前来说，大内存对G1支持的较好，其余的情况有待观察。是否将GC替换为G1还有待实验（何况很多公司还在用JDK 1.7）。有消息称JDK 9会把G1作为默认的GC。

其他的JVM GC实现

关于低延时的GC实现，Azul的C4: The Continuously Concurrent Compacting Collector做的挺好的，STW时间非常低，而且对超大堆支持的很好（据说能支持2T的内存。。），当然吞吐量会稍弱。

参考资料

Java