Ryuu 的个人博客

一个计算机初学者

发表于 更新于 分类于 本文字数： 5.6k 阅读时长 ≈ 20 分钟

覆盖 equals 方法看起来容易，但是许多的覆盖方式会导致错误，并且产严重后果。最容易避免这类问题的办法就是不覆盖 equals 方法，在这种情况下，类的每个实例都只与它自身相等。如果满足以下任何一个条件：

  1. 类的每个实例本质上都是唯一的。

    对于代表活动的实体，而不是值 (value) 的类来说的却如此，例如 Thread。

    Object 提供的 equals 实现对于这些类来说是正确的。

  2. 类没有必要提供 “逻辑相等” (logical equality) 的测试功能。

    例如，java.util.regex.Pattern 可以覆盖 equals，以检查两个 Pattern 实例是否代表同一个正则表达式，但是设计者并不认为客户需要或者期望这样的功能。

    在这类情况下，Object 继承得到的 equals 实现已经足够了。

  3. 超类已经覆盖了 equals，超类的行为对于这个类也是合适的。

    大多数的 Set 实现都从 AbstractSet 继承了 equals 实现， List 实现从 AbstractList 继承了 equals 实现，Map 实现从 AbstractMap 继承了 equals 实现。

那么什么时候应该覆盖 equals 方法呢？如果类具有自己的 “逻辑相等” (logical equality) 概念，而且超类还没有覆盖 equals。这通常属于 “值类” (value class) 的情况。值类仅仅是表示值的类，例如 Integer 或者 String。程序员在利用 equals 方法来比较值对象的引用时，希望知道它们逻辑上是否相等，而不是像了解它们是否指向同一个对象。为了满足要求，必须覆盖 equals 方法，这样做也使得这个类的实例可以被用作映射表的键和值，或者集合的元素，使映射或集合表现出预期的行为。

有一种值类不需要覆盖 equals 方法，即用实例受控 (见第1条) 确保 “每个值至多只存在一个对象”的类。枚举类型(见第34条)就属于这种类。对于这种类而言，逻辑相同与对象等同是一回事，此时 Object 的 equals 方法等同于逻辑意义上的 equals 方法。

在覆盖 equals 方法的时候，必须遵守它的通用约定。以下是约定内容，Object 的规范。

equals 方法实现了等价关系 (equivalence relation)，其属性如下：(Ryuu : 感觉自己回到了离散数学)

  • 自反性 (reflexive)

    对于任何非 null 的引用 x，x.equals(x) 必须返回 true。

  • 对称性 (symmetric)

    对于任意非 null 的引用 x，y。当且仅当 x.equals(y) 返回 true 时，y.equals(x) 必须返回 true。

  • 传递性 (transitive)

    对于任何非 null 的引用 x，y，z。如果 x.equals(y) 且 y.equals(z) 返回 true，x.equals(z) 也必须返回 true。

  • 一致性 (consistent)

    对于任何非 null 的引用 x，y，只要 equals 的比较操作在对象中所用的信息没有被修改，任意次对 x.equals(y) 的调用，一致返回 true 或一致返回 false。

  • 对于任何非 null 的引用值 x，x.equals(null) 必须返回 false。

除非你对数学特别感兴趣，否则这些规则看起来有点让人恐惧，但是不要忽视这些规则，如果违反了，程序很容易出错且很难找到错误根源。一个类的实例通常会被频繁的传递给另一个类的实例。许多类，包括所有的集合类 (collection class) 在内，都依赖于传递给它们的对象是否遵守了 equals 约定。

幸运的是，虽然这些约定看起来很吓人。实际上并不复杂。一旦了解了这些约定，要遵守它们并不困难。

自反性 (Reflexivity) —— 仅仅说明对象等于自身。假如违反，将该类的实例添加到集合中，调用集合的 contains 方法，将告知该集合不包含刚刚添加的元素。

对称性 (Symmetry) —— 任何两个对象对于 “它们是否等同” 的问题都必须保持一致。违反该条件的清醒不难想象。以下类实现了一个不区分大小写的字符串。字符串由 toString 保存，但在 equals 操作中被忽略。

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
// Broken - violates symmetry
public final class CaseInsensitiveString {
    private final String s;

    public CaseInsensitiveString(String s) {
        this.s = Objects.requireNonNull(s);
    }

    // Broken - violates symmetry
    @Override
    public boolean equals(Object o) {
        if (o instanceof CaseInsensitiveString)
            return s.equalsIgnoreCase(((CaseInsensitiveString) o).s);
        if (o instanceof String) // One-way interoperability!
            return s.equalsIgnoreCase((String) o);
        return false;
    }

    public static void main(String[] args) {
        CaseInsensitiveString cis = new CaseInsensitiveString("Polish");
        String s = "Polish";
        System.out.println(cis.equals(s)); // true
        System.out.println(s.equals(cis)); // false
    }
}

在该类中 equals 企图与普通字符串对象进行互操作。正如注释结果，问题在于 CaseInsensitiveString 类中的 equals 知道普通字符串对象，但 String 类中的 equals 方法却不知道 CaseInsensitiveString 。显然这违反了对称性。

若将 CaseInsensitiveString 的对象置入集合：

1
2
3
List<CaseInsensitiveString> list = new ArrayList<>();
list.add(cis);
System.out.println(list.contains(s)); // false

在当前的 OpenJDK list.contains(s) 返回的是 false，实际上根据实现的不同，可能会返回 true 或者抛出一个运行时异常。

一旦违反了 equals 约定，当其他对象面对你的对象时，你完全不知道这些对象的行为会怎么样。

为解决该问题，只需把企图与 String 互操作的这段代码从 equals 方法中去掉就可以了：

1
2
3
4
@Override
public boolean equals(Object o) {
    return o instanceof CaseInsensitiveString && ((CaseInsensitiveString) o).s.equalsIgnoreCase(s);
}

传递性 (Transitivity) —— 若一个对象等于第二个对象，第二个对象等于第三个对象，则第一个对象等于第三个对象。用子类举例，将一个新的值组件 (value component) 添加到了超类中。子类增加的信息会影响 equals 的比较结果。首先以一个不可变的二维整型 Point 类作为开始：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Point {
    private final int x;
    private final int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof Point p)) return false;
        return x == p.x && y == p.y;
    }
}

假如想要扩展这个类，为其添加颜色信息：

1
2
3
4
5
6
7
8
public class ColorPoint extends Point {
    private final Color color;

    public ColorPoint(int x, int y, Color color) {
        super(x, y);
        this.color = color;
    }
}

如果完全不提供 equals 方法，而是直接从 Point 继承过来，在 equals 做比较的时候颜色信息就被忽略了。虽然这不会违反 equals 约定，但很明显此方案是无法接受的。假设编写了一个 equals 方法，只有当它的参数是另一个有色点，并且具有相同的位置和颜色时，他才会返回 true：

1
2
3
4
5
6
// Broken - violates symmetry
@Override
public boolean equals(Object o) {
    if (!(o instanceof ColorPoint)) return false;
    return super.equals(o) && ((ColorPoint) o).color == color;
}

问题在于，比较普通点和有色点，以及相反的情况时，可能会得到不同的结果。前一种忽略了颜色信息，而后一种则总是返回 false，因为参数的类型不正确。

1
2
3
4
Point p = new Point(1, 2);
ColorPoint cp = new ColorPoint(1, 2, Color.RED);
System.out.println(p.equals(cp)); // true
System.out.println(cp.equals(p)); // false

可以做以下的尝试来修正上述问题，让 ColorPoint.equals 在进行 “混合比较” 时忽略颜色信息：

1
2
3
4
5
6
7
8
9
10
11
12
// Broken - violates transitivity!
@Override
public boolean equals(Object o) {
    if (!(o instanceof Point)) return false;

    // If o is a normal Point,do a color-blind comparison
    if (!(o instanceof ColorPoint))
        return o.equals(this);

    // o is a ColorPoint; do a full comparison
    return super.equals(o) && ((ColorPoint) o).color == color;
}

这种方法提供了对称性，但是牺牲了传递性：

1
2
3
4
5
6
ColorPoint p1 = new ColorPoint(1, 2, Color.RED);
Point p2 = new Point(1, 2);
ColorPoint p3 = new ColorPoint(1, 2, Color.BLUE);
System.out.println(p1.equals(p2)); // true
System.out.println(p2.equals(p3)); // true
System.out.println(p1.equals(p3)); // false

前两种是不考虑颜色的色盲比较，而第三种却考虑了颜色。

此外，该方法还可能导致无限的递归：假设 Point 有两个子类，ColorPoint 和 SmellPoint，它们各自都带有这种 equals 方法。那么对于 colorPoint.equals(smellpoint) 的调用将抛出 StackOverflowError 异常。

那么该如何解决呢？事实上，这是面向对象语言中关于等价关系的一个基本问题。无法在扩展可实例化的类的同时，既增加新的值组件，同时又保留 equals 约定，除非愿意放弃面向对象的抽象所带来的优势。

你可能听说过，在 equals 方法中用 getClass 测试代替 instanceof 测试，可以扩展可实例化的类和新增值组件，同时保留 equals 约定：

1
2
3
4
5
6
7
// Broken - violates Liskov substitution principle
@Override
public boolean equals(Object o) {
    if (o == null || getClass() != o.getClass()) return false;
    Point point = (Point) o;
    return x == point.x && y == point.y;
}

这段程序只有当对象具有相同的实现类事，才能使对象等同。但其结果是无法令人接受的：Point 子类的实例仍然是一个 Point，它仍然需要发挥作用，但是如果采用了这种方法，它将无法完成任务！

假设要编写一个方法，以检验某个点是否在单位圆中，以下是可采用的一种方法：

1
2
3
4
5
6
7
8
9
// Initialize unitCircle to contain all Points on the unit circle
private static final Set<Point> unitCircle = Set.of(
        new Point(1, 0), new Point(0, 1),
        new Point(-1, 0), new Point(0, -1)
);

public static boolean onUnitCircle(Point p) {
    return unitCircle.contains(p);
}

虽然这可能不是最好的方法，但是这是可行的。

但是，若通过某种不添加值组件的方法扩展 Point，例如让它的构造器记录创建了多少个实例：

1
2
3
4
5
6
7
8
9
10
11
12
public class CounterPoint extends Point {
    private static final AtomicInteger counter = new AtomicInteger();

    public CounterPoint(int x, int y) {
        super(x, y);
        counter.incrementAndGet();
    }

    public static int numberCreated() {
        return counter.get();
    }
}

里氏替换原则 (Liskov substitution principle) 认为，一个类型的任何重要属性也将适用于它的子类型。因此为该类型编写的任何方法，在他的子类型上也应该同样运行得很好 [Liskov 87]。若将 CounterPoint 实例传递给 onUnitCircle 方法。若在 Point 类中使用了基于 getClass 的 equals 方法，则返回 false。这是因为 onUnitCircle 方法所用的 HashSet 这样的集合，利用 equals 方法检验包含条件，没有任何 CounterPoint 实例与任何 Point 对应。但是，如果在 Point 上使用适当的基于 instanceof 的 equals 方法，当遇到 CounterPoint 时，相同的 onUnitCircle 方法就会工作得很好。遵从第18条 “复合优先于继承” 的建议。不再让 ColorPoint 扩展 Point，而是在 ColorPoint 中加入一个私有的 Point，以及一个公有的视图 (view) 方法 (见第6条)，此方法返回一个与该有色点处在相同位置的普通 Point 对象：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Add a value component without violating the equals contract
public class ColorPoint {
    private final Point point;
    private final Color color;

    public ColorPoint(Point point, Color color) {
        this.point = point;
        this.color = color;
    }

    /**
     * Returns the point-view of this color point.
     * @return point
     */
    public Point asPoint() {
        return point;
    }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof ColorPoint that)) return false;
        return that.point.equals(point) && that.color.equals(color);
    }
}

在 Java 平台类库中，有一些类扩展了可实例化类，添加了新的值组件。例如，java.sql.Timestamp 对 java.util.Date 进行扩展，并增加了 nanoseconds 域。Timestamp 的 equals 实现确实违反了对称性，如果 Timestamp 和 Date 对象用于同一个集合中，或者以其他的方式被混合在一起，则会引起不正确的行为。Timestamp 类有一个免责声明，告诫程序员不要混合使用 Date 和 Timestamp 对象。只要不把它们混合在一起就不会有麻烦。除此之外，没有其他的措施可以防止此问题，并且错误将很难调试。Timestamp 的这种行为是个错误，不值得效仿。

1
2
3
4
// java.util.Date * DON'T DO THIS!
public boolean equals(Object obj) {
    return obj instanceof Date && getTime() == ((Date) obj).getTime();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// java.sql.Timestamp extends java.util.Date * DON'T DO THIS!
public boolean equals(java.lang.Object ts) {
  if (ts instanceof Timestamp) {
    return this.equals((Timestamp)ts);
  } else {
    return false;
  }
}

public boolean equals(Timestamp ts) {
    if (super.equals(ts)) {
        if  (nanos == ts.nanos) {
            return true;
        } else {
            return false;
        }
    } else {
        return false;
    }
}

注意，你可以在一个抽象 (abstract) 类的子类中增加新的值组件且不违反 equals 约定。对于根据第23条建议而得到的那种类层次结构来说，这一点十分重要。例如，有一抽象类 Shape ，没有任何的值组件，Circle 子类添加了一个 radius 域，Rectangle 子类添加了 length 和 width 域。只要不能直接创造超类的实例，前面所述的种种问题都不会发生。

一致性 (Consistency) —— 如果两个对象相等，那么它们将始终保持相等，除非它们中有一个对象 (或者两个) 被修改了。换句话说，可变对象在不同的时候可以与不同的对象相等，而不可变对象则不会这样。当编写一个类时，应仔细考虑它是否应该是不可变的 (见第17条)。如果认为它应是不可变的，就必须保证 equals 方法满足这样的限制条件：相等的永远相等，不相等的永远不相等。

无论如何，不要使 equals 方法依赖于不可靠的资源。如果违反了这条禁令，想要满足一致性要求将十分困难。例如，java.net.URL 的 equals 方法依赖于对 URL 中主机 IP 地址的比较。随时间的推移，不能确保产生相同的结果，IP 地址有可能发生变化。这会违反 equals 约定，在实践中可能引发一些问题。URL equals 方法是一个大错误，不应该模仿。遗憾的是，因为兼容性的要求，这一行为无法被改变。为了避免发生这种问题，equals 方法应该对驻留在内存中的对象执行确定性的计算。

1
2
3
4
5
6
7
8
// java.net.URL * DON'T DO THIS!
transient URLStreamHandler handler;

public boolean equals(Object obj) {
    if (!(obj instanceof URL)) return false;
    URL u2 = (URL)obj;
    return handler.equals(this, u2);
}
1
2
3
4
// java.net.URLStreamHandler * DON'T DO THIS!
protected boolean equals(URL u1, URL u2) {
    return Objects.equals(u1.getRef(), u2.getRef()) && sameFile(u1, u2);
}

非空性 (Non-nullity) —— 暂且如此称呼。所有的对象都不能等于 null。尽管很难想象，在什么情况下 o.equals(null) 调用会意外地返回 true，但是意外抛出 NullPointerException 异常的情况不难想象。通用约定不允许抛出 NullPointerException 异常。许多类的 equals 方法都通过一个显式的 null 测试来防止该情况：

1
2
3
4
5
6
// Unnessasary!
@Override
public boolean equals(Object o) {
    if(o == null) return false;
    ...
}

然而这项测试是不必要的。为了测试其参数的等同性，equals 方法必须先把参数转换为适当的类型，以便可以调用它的访问方法，或者访问它的域。在进行转换之前， equals 方法必须使用 instanceof 操作符，检查其参数的类型是否正确：

1
2
3
4
5
6
@Override
public boolean equals(Object o) {
    if (!(o instanceof MyType)) return false;
    MyType mt = (MyType) o;
    ...
}

如果漏掉类型检查，并且传递给 equals 方法的参数又是错误的类型，那么equals 方法将会抛出 ClassCastException 异常，这违反了 equals 约定。但是，**如果 instanceof 操作符的第一个操作数为 null，那么，不管第二个操作数是哪种类型，instanceof 操作符都会指定应该返回的 false [JLS，15.20.2]**。因此如果把 null 传给 equals 方法，类型检查就会返回 false，所以不需要显示的 null 检查。

结合所有这些要求，得出了以下实现高质量 equals 方法的诀窍：

  1. 使用 == 操作符检查 “参数是否为这个对象的引用”。

    如果是，则返回 true。这只不过是一种性能优化，如果比较操作性能消耗过大，就值得这么做。

  2. 使用 instanceof 操作符检查 “参数是否为正确的类型”。

    如果不是，则返回 false。一般来说，”正确的类型”是指 equals 方法所在的类。某些情况下是指该类所实现的某个接口。如果类实现的接口改进了 equals 约定，允许了在实现了该接口的类之间进行比较，那么就使用接口。集合接口如Set、List、Map 和 Map.Entry 具有这样的特性。

  3. 把参数转换成正确的类型。

    因为转换之前进行过 instanceof 测试，所以确保会成功。

  4. 对于该类的每个 “关键” (significant) 域，检查参数中的域是否与该对象中对应的域相匹配。

    如果这些测试全部通过，返回 true；否则返回 false。

    如果第二步中的类型是接口，就必须通过接口方法访问参数中的域；

    如果该类型是类，也许就能直接访问其参数，这要取决于它们的可访问性。

对于对象引用域，可以递归地调用 equals 方法；

对于既不是 float 也不是 double 类型的基本类型域，可以使用 == 操作符进行比较；

对于 float 域，可以使用静态 Float.compare(float, float) 方法； 对于 double 域，使用 Double.compare(double, double)。对这两个域进行特殊处理是有必要的，因为存在着 Float.NaN、-0.0f 以及类似的 double 常量；详细信息请参考 JLS 15.21.1 或者 Float.equals 的文档。虽然可以用静态方法 Float.compare Double.compare 进行比较，但是每次比较都要进行自动装箱，这将导致性能下降。对于数组域，则要把以上这些指导原则应用到每一个元素上。如果数组域的每个元素都很重要，可以使用 Arrays.equals 方法。

有些对象引用域包含 null 可能是合法的，所以，为了避免可能导致 NullPointerException 异常，使用静态方法 Objects.equals(Object, Object) 来检查这些类域的等同性。

对于有些类，比如前面提到的CaseInsensitiveString类，域的比较要比简单的等同性测试复杂得多。如果是这种情况，可能希望保存该域的一个“范式”（canonical form），这样equals方法就可以根据这些范式进行低开销的精确比较，而不是高开销的非精确比较。这种方法对于不可变类（见第17条）是最为合适的；如果对象可能发生变化，就必须使其范式保持最新。

域的比较顺序可能会影响equals方法的性能。为了获得最佳的性能，应该最先比较最有可能不一致的域，或者是开销最低的域，最理想的情况是两个条件同时满足的域。不应该比较那些不属于对象逻辑状态的域，例如用于同步操作的 Lock 域。也不需要比较衍生域 (derived field)，因为这些域可以由 “关键域” (significant field)计算获得，但是这样做有可能提高 equals 方法的性能。如果衍生域代表了整个对象的综合描述，比较这个域可以节省在比较失败时去比较实际数据所需要的开销。例如，假设有一个 Polygon 类，缓存了其面积。若两个多边形面积不同，则没有必要去比较它们的边和顶点。

在编写完equals方法之后，应该问自己三个问题：它是否是对称的、传递的、一致的？并且不要只是自问，还要编写单元测试来检验这些特性，除非用AutoValue (后面会讲到) 生成 equals 方法，在这种情况下就可以放心地省略测试。如果答案是否定的，就要找出原因，再相应地修改 equals 方法。当然， equals 方法也必须满足其他两个特性 (自反性和非空性)，但是这两种特性通常会自动满足。

根据上面的诀窍构建 equals 方法的具体例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Class with a typical equals method
public final class PhoneNumber {
    private final short areaCode, prefix, lineNum;

    public PhoneNumber(int areaCode, int prefix, int lineNum) {
        this.areaCode = rangeCheck(areaCode, 999, "areaCode");
        this.prefix = rangeCheck(prefix, 999, "prefix");
        this.lineNum = rangeCheck(lineNum, 9999, "line num");
    }

    private static short rangeCheck(int val, int max, String arg) {
        if (val < 0 || val > max) throw new IllegalArgumentException(arg + " : " + val);
        return (short) val;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof PhoneNumber that)) return false;
        return areaCode == that.areaCode && prefix == that.prefix && lineNum == that.lineNum;
    }
}

下面是最后的一些告诫：

  • 覆盖 equals 时总要覆盖 hashCode

    为了让关注点在 equals 方法上，本条建议中都没有覆盖 hashCode，详情见第11条。

  • 不要企图让 equals 方法过于智能。

    如果只是简单地测试域中的值是否相等，则不难做到遵守 equals 约定。如果想过度地去寻求各种等价关系，则很容易陷入麻烦之中。把任何一种别名形式考虑到等价的范围内，往往不会是个好主意。例如，File类不应该试图把指向同一个文件的符号链接 (symbolic link) 当作相等的对象来看待。所幸 File 类没有这样做。

  • 不要将 equals 声明中的 Object 对象替换为其他的类型。

    程序员编写出下面这样的 equals 方法并不鲜见，这会使程序员花上数个小时都搞不清为什么它不能正常工作：

    1
    2
    3
    4
    5
    // DON'T DO THIS!
    @Override
    public boolean equals(MyClass o) {
    	...
    }

    问题在于，这个方法并没有 重写 (override) Object.equals，因为它的参数应该是 Object 类型，相反，它重载 (overload) 了 Object.equals (见52条)。在正常 equals 方法的基础上，再提供一个 “强类型” (strongly typed) 的 equals 方法，这是无法接受的，因为会导致子类中的 Override 注解产生错误的正值，带来错误的安全感。
    @Override 注解的用法一致，就如本条目中所示，可以防止犯这种错误 (见第40条)。这个equals方法不能编译，错误消息会告诉你到底哪里出了问题：

    1
    2
    3
    4
    5
    // Still broken, but won't compile
    @Override
    public boolean equals(MyClass o) {
        ...
    }

编写和测试 equals (及 hashCode) 方法都是十分烦琐的，得到的代码也很琐碎。代替手工编写和测试这些方法的最佳途径，是使用 Google 开源的 AutoValue 框架，它会自动替你生成这些方法，通过类中的单个注解就能触发。在大多数情况下，AutoValue 生成的方法本质上与你亲自编写的方法是一样的。

IDE 也有工具可以生成 equals 和 hashCode 方法，但得到的源代码比使用 Auto-Value 的更加冗长，可读性也更差，它无法自动追踪类中的变化，因此需要进行测试。也就是说，让 IDE 生成 equals (及 hashCode) 方法，通常优于手工实现它们，因为 IDE 不会犯粗心的错误，但是程序员会犯错。

总而言之，不要轻易重写 equals 方法，除非迫不得已。因为在许多情况下，从 Object 处继承的实现正是你想要的。如果覆盖 equals，一定要比较这个类的所有关键域，并且查看它们是否遵守 equals 约定的所有五个条款。

发表于 更新于 分类于 本文字数： 1k 阅读时长 ≈ 4 分钟

Java 类库中包括许多必须通过调用 close 方法来手工关闭的资源。例如 InputStream、OutputStream 和 java.sql.Connection。客户端经常会忽略资源的关闭。虽然这其中的许多资源都是用终结方法作为安全网，但是效果并不理想(见第8条)。

根据经验，try-finally 语句是确保资源会被适时关闭的最佳方法，就算发生异常或者返回也一样：

1
2
3
4
5
6
7
8
public static String firstLineOfFile(String path) throws IOException {
    BufferedReader br = new BufferedReader(new FileReader(path));
    try {
        return br.readLine();
    } finally {
        br.close();
    }
}

这看起来似乎没有什么问题，但如果再加入一个资源，就会变得糟糕了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void copy(String src, String dst) throws IOException {
    FileInputStream in = new FileInputStream(src);
    try {
        OutputStream out = new FileOutputStream(dst);
        try {
            byte[] buf = new byte[BUFFER_SIZE];
            int n;
            while ((n = in.read(buf)) >= 0)
                out.write(buf, 0, n);
        } finally {
            out.close();
        }
    } finally {
        in.close();
    }
}

这可能让人难以置信，不过就算优秀的程序员也经常犯这样的错误。Joshua Bloch (本书作者) 在《Java Puzzlers》[Bloch5] 第88页犯过该错误，时隔多年都无人发现。事实上，在 2007年，close 方法在 Java 类库中有 2/3 都用错了。

即使用 try-finally 语句正确地关闭了资源 (如前两段代码)，依然存在许多不足。因为在 try 块和 finally 块中的代码，都会抛出异常。例如，在 firstLineOfFile 中，如果因为物理设备损坏，那么调用 readLine、close 就会抛出异常。这种情况下第二个异常完全抹除了第一个异常。在异常堆栈轨迹中，完全没有第一个异常的记录，这会导致调试变得非常复杂，因为通常需要看到第一个异常才能诊断出问题何在，虽然可以通过编写代码来禁止第二个异常，保留第一个异常，但是实现起来太繁琐了。

当 Java 7 引入 try-with-resources 语句时 [JLS，14.20.3]，所有这些问题一下子就全部解决了。要使用这个构造的资源，必须先实现 AutoCloseable 接口，其中包括了单个返回 void 的 close 方法。Java 类库与第三方类库中的许多类和接口，现在都实现或扩展了 AutoCloseable 接口。如果编写了一个类，它代表的是必须被关闭的资源，那么这个类也应该实现 AutoCloseable。

以下是使用 try-with-resources 的两个范例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// try-with-resources - the best way to close resources!
public static String firstLineOfFile(String path) throws IOException {
    try (BufferedReader br = new BufferedReader(new FileReader(path))) {
        return br.readLine();
    }
}

// try-with-resources on multiple resources - short and sweet
public static void copy(String src, String dst) throws IOException {
    try (FileInputStream in = new FileInputStream(src); OutputStream out = new FileOutputStream(dst)) {
        byte[] buf = new byte[BUFFER_SIZE];
        int n;
        while ((n = in.read(buf)) >= 0)
            out.write(buf, 0, n);
    }
}

使用 try-with-resources 不仅使代码变得更简洁易懂，也更容易进行诊断。以 firstLineOfFile 为例，如果调用 readLine 和 (不可见的) close 方法都抛出异常，后一个异常就会被禁止，以保留第一个异常。事实上，为了保留你想看到的那个异常，即使是多个异常都可以被禁止。这些异常禁止并不是被简单的抛弃了，而是会被打印在堆栈轨迹中，并注明它们是被禁止的异常。通过编程调用 getSuppressed 方法可以访问到它们，getSuppressed 方法也已经添加在 Java 7 的 Throwalble 中了。

在 try-with-resources 语句中还可以使用 catch 子句，就像在平时的 try-finally 语句中一样。这样既可以处理异常，又不需要再套一层代码。

该 firstLineOfFile 方法没有抛出异常，但如果他无法打开文件，或者无法从中读取，就会返回一个默认值：

1
2
3
4
5
6
7
8
// try-with-resources with a catch clause
public static String firstLineOfFile(String path, String defaultVal) {
    try (BufferedReader br = new BufferedReader(new FileReader(path))) {
        return br.readLine();
    } catch (IOException e) {
        return defaultVal;
    }
}

在处理必须关闭的资源时，始终优先考虑 try-with-resources ，而不是用 try-finally。这样得到的代码将更加简洁、清晰。产生的异常也更有价值，这是 try-finally 不能做到的。

发表于 更新于 分类于 本文字数： 507 阅读时长 ≈ 2 分钟

Java 类库中包含了几种注解类型。一般来说，其中最重要的是 @Override 注解。该注解仅能用于方法声明，表示被注解的方法声明覆盖了超类中的一个方法声明。坚持使用该注解，可以防止一大类的非法错误。请看代码段

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
/**
 * Can you spot the bug?
 * result: 260
 */
public class Bigram {
    private final char first;
    private final char second;

    public Bigram(char first, char second) {
        this.first = first;
        this.second = second;
    }

    public boolean equals(Bigram b) {
        return first == b.first && second == b.second;
    }

    public int hashCode() {
        return 31 * first + second;
    }

    public static void main(String[] args) {
        Set<Bigram> s = new HashSet<>();
        for (int i = 0; i < 10; i++) {
            for (char ch = 'a'; ch <= 'z'; ch++) {
                s.add(new Bigram(ch, ch));
            }
        }
        System.out.println(s.size());
    }
}

该程序将反复的把 26 个双字母组合添加进集合中 (每个字母组合都由两个相同的小写字母组成)，随后打印该集合的大小。结果见注释，期望的结果是 26 ，因为存在重复添加相同字母组合的情况。

显然 Bigram 类的创建者原本想覆盖 equals 方法(见第10条)，同时还记得覆盖 hashCode。实际上 equals 没有被重写，而是被重载了。重写 Object.equals 必须定义一个参数为 Object 类型的 equals 方法，但Bigram 类中定义的是 Bigram 类型，因此 Bigram 类从Object 类继承了equals ，该 equals 比较对象的同一性 (identity)，就像 == 操作符一样。所以对于每一个 bigram 的重复添加，都被看做是不同的，这就是结果为 260 的原因。

幸运的是，编译器可以可以帮助你发现这个错误，但是需要告知编译器想要重写 Object.equals才行。用 @Override 标注Bigram.equals，如下

1
2
3
4
5
6
7
8
/**
* DON'T DO THIS!
* Error: Method does not override method from its superclass
*/
@Override
public boolean equals(Bigram b) {
    return first == b.first && second == b.second;
}

如果插入这个注解，会发现错误信息。将其改正为：

1
2
3
4
5
6
7
@Override
public boolean equals(Object o) {
    if (!(o instanceof Bigram))
        return false;
    Bigram b = (Bigram) o;
    return first == b.first && second == b.second;
}

因此，应在想要重写超类声明的每个方法中使用 Override 注解。

发表于 更新于 分类于 本文字数： 3.7k 阅读时长 ≈ 14 分钟

Java 是一门面向对象的程序语言，Java 具备面向对象的3个基本特征：封装、继承与多态。分派调用过程将会解释多态性特征的一些最基本的体现，如 Java 虚拟机如何实现 “重载” 和 “重写”。

静态分派

“分派” (Dispatch) 本身就带有动态性，一般不应用在静态语境中，在英文原版的 《Java 虚拟机规范》和《Java 语言规范》里的说法都是 “Method Overload Resolution”，实际应当归于 “解析”。但许多翻译的中文资料将其称为 “静态分派”。

为解释静态分派与重载 (Overload)，请看如下代码

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
/**
 * hello, guy!
 * hello, guy!
 */
public class StaticDispatch {
    public static void main(String[] args) {
        Human man = new Man();
        Human woman = new Woman();
        StaticDispatch sd = new StaticDispatch();
        sd.sayHello(man);
        sd.sayHello(woman);
    }

    static abstract class Human {
    }

    static class Man extends Human {
    }

    static class Woman extends Human {
    }

    private void sayHello(Human guy) {
        System.out.println("hello, guy!");
    }

    private void sayHello(Man guy) {
        System.out.println("hello, gentleman!");
    }

    private void sayHello(Woman guy) {
        System.out.println("hello, lady!");
    }
}

相信对 Java 稍有了解的程序员看完代码后都能判断出正确的结果。但为何虚拟机会选择执行参数为 Human 的重载呢？首先需要弄清两个关键概念：

1
Human man = new Man();

以上代码中的 “Human” 称为变量的 “静态类型” (Static Type)，或者叫做 “外观类型” (Apparent Type)，后面的 “Man” 则被称为变量的 “实际类型” (Actual Type) 或者叫 “运行时类型” (Runtime Type)。外观类型和实际类型在程序中都可能会发生变化，区别是外观类型的变化仅仅在使用时发生，变量本身的外观类型不会改变，并且最终的外观类型在编译期是可知的；而实际类型变化的结果在运行期才可以确定，编译器在编译程序的时候并不知道一个对象的实际类型是什么。

不妨通过以下代码解释

1
2
3
4
5
6
// 实际类型变化
Human human = new Random().nextBoolean() ? new Man() : new Woman();

// 外观类型变化
sd.sayHello((Man) human);
sd.sayHello((Woman) human);

human 的实际类型是可变的 (根据 nextBoolean() 的值决定)，编译期是不可知的，必须等到运行时才可以确定。human 的外观类型是 Human，可以在使用时临时改变类型，但这种改变在编译期是可知的，两次 sayHello 的调用，在编译期完全可以明确是 Man 还是 Women。

回到最先的代码 main 中两次调用 sd.sayHello ，此时调用哪个重载版本完全取决于传入参数的数据类型。代码中定义了两个实际类型不同，外观类型却相同的对象。虚拟机 (准确的来说是编译器) 重载时是通过参数的外观类型而不是实际类型作为判定依据的。外观类型在编译期可知，在编译阶段 Javac 编译器根据参数的外观类型决定了使用哪个重载版本，因此选择了 sayHello(Human) 作为调用的目标，并将这个方法的符号引用写到 main 里的两条invokevirtual 指令的参数中，如下反汇编的 26: 与 31:。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// javap -c 反汇编
public static void main(java.lang.String[]);
    Code:
       0: new           #7                  // class StaticDispatch$Man
       3: dup
       4: invokespecial #9                  // Method StaticDispatch$Man."<init>":()V
       7: astore_1
       8: new           #10                 // class StaticDispatch$Woman
      11: dup
      12: invokespecial #12                 // Method StaticDispatch$Woman."<init>":()V
      15: astore_2
      16: new           #13                 // class StaticDispatch
      19: dup
      20: invokespecial #15                 // Method "<init>":()V
      23: astore_3
      24: aload_3
      25: aload_1
      26: invokevirtual #16                 // Method sayHello:(LStaticDispatch$Human;)V
      29: aload_3
      30: aload_2
      31: invokevirtual #16                 // Method sayHello:(LStaticDispatch$Human;)V
      34: return

所有依赖外观类型来决定方法执行版本的分派动作，都称为静态分派。静态分派最典型的应用表现就是方法的重载。静态分派发生在编译阶段，因此确定静态分派的动作实际上不是由虚拟机来执行，这也是一些资料选择把静态分派归于 “解析” 而不是 “分派” 的原因。

(未完待续)

动态分派

动态分派与 Java 语言动态性的另一重要体现 —— 重写 (Override) 有着很密切的关联。请看如下代码段

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
/**
 * man say hello
 * woman say hello
 * woman say hello
 */
public class StaticDispatch {
    public static void main(String[] args) {
        Human man = new Man();
        Human woman = new Woman();
        man.sayHello();
        woman.sayHello();
        man = new Woman();
        man.sayHello();
    }

    static abstract class Human {
        protected abstract void sayHello();
    }

    static class Man extends Human {
        @Override
        public void sayHello() {
            System.out.println("man say hello");
        }
    }

    static class Woman extends Human {
        @Override
        protected void sayHello() {
            System.out.println("woman say hello");
        }
    }
}

对于习惯了面向对象的 Java 程序员来说，运行结果正如预期。但 Java 虚拟机是如何判断应该调用哪个方法的？

显然这里的选择调用的方法不可能再根据外观类型来决定。因为该实例的两个对象外观类型都是 Human 产生了不同的行为。man 在两次调用中还执行了两个不同的方法。原因很明显，因为这两个变量的实际类型不同。

Java 是如何根据实际类型来分派方法执行的版本的呢？请看如下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void main(java.lang.String[]);
    Code:
       0: new           #7                  // class dispatch/DynamicDispatch$Man
       3: dup
       4: invokespecial #9                  // Method dispatch/DynamicDispatch$Man."<init>":()V
       7: astore_1
       8: new           #10                 // class dispatch/DynamicDispatch$Woman
      11: dup
      12: invokespecial #12                 // Method dispatch/DynamicDispatch$Woman."<init>":()V
      15: astore_2
      16: aload_1
      17: invokevirtual #13                 // Method dispatch/DynamicDispatch$Human.sayHello:()V
      20: aload_2
      21: invokevirtual #13                 // Method dispatch/DynamicDispatch$Human.sayHello:()V
      24: new           #10                 // class dispatch/DynamicDispatch$Woman
      27: dup
      28: invokespecial #12                 // Method dispatch/DynamicDispatch$Woman."<init>":()V
      31: astore_1
      32: aload_1
      33: invokevirtual #13                 // Method dispatch/DynamicDispatch$Human.sayHello:()V
      36: return

0 ~ 15 行是准备动作，建立 man 和 woman 的内存空间、调用 Man 和 Woman 类型的实例构造器，将这个实例引用存放到第 1、2 个局部变量表的变量槽中，这些动作实际对应以下的 Java 源码：

1
2
Human man = new Man();
Human woman = new Woman();

16 ~ 21 的 aload 指令分别把刚刚创建的两个对象的引用压到栈顶，这两个对象是执行 sayHello 的所有者，称为接收者 (Receiver)；17 和 21 行是方法调用指令，这两条调用指令单从字节码角度来看，无论是指令(都是 invokevirtual) 还是参数 ( 都是常量池中第 22 项的常量，注释显示了这个常量是 Human.sayHello 的符号引用) 都完全一样，但是这两句指令最终执行的目标方法并不相同。解决问题的关键必须从 invokevirtual 指令本身入手，要弄清楚它是如何确定调用方法版本、如何实现多态查找来着手分析才行。

根据 《Java 虚拟机规范》，invokevirtual 指令的运行时解析过程大致分为以下几个部分：

  1. 找到操作数栈顶的第一个元素所指向的对象的实际类型，记作 C

  2. 如果在类型 C 中找到与常量中的描述符和简单名称都相符的方法，则进行访问权限校验，

    如果通过则返回这个方法的直接引用，查找过程结束；

    不通过则返回 java.lang.IllegalAccessError 异常。

  3. 否则，按继承关系自下而上依次对 C 的各个父类进行第二步的搜索及验证。

  4. 若始终没有合适的方法，抛出 java.lang.AbstractMethodError 异常。

正是因为 invokevirtual 指令执行的第一步就是在运行期确定接收者的实际类型，所以两次调用中的 invokevirtual 指令并不是把常量池中方法的符号引用解析到直接引用上就结束了，还会根据方法接收者的实际类型来选择方法版本，这个过程就是 Java 语言中方法重写的本质。这种在运行期根据实际类型确定方法执行版本的分派过程称为动态分派。

这种多态性的根源在于虚方法调用指令 invokevirtual 的执行逻辑，所以这只会对方法有效，对字段无效，因为字段不使用这条指令。在 Java 中只有虚方法存在，没有虚字段。字段永远不参与多态，哪个类的方法访问某个名字的的字段时，该名字指的就是这个类能看到的那个字段。当子类声明了与父类同名的字段时，虽然在子类的内存中两个字段都会存在，但子类的字段会遮蔽父类的同名字段。

请看如下代码

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
// DON'T DO THIS!
/**
 * I'm Son, I have $0
 * I'm Son, I have $4
 * This guy has $2
 */
public class FieldHasNoPolymorphic {
    public static void main(String[] args) {
        Father guy = new Son();
        System.out.println("This guy has $" + guy.money);
    }

    static class Father {
        public int money = 1;

        public Father() {
            money = 2;
            showMeTheMoney();
        }

        public void showMeTheMoney() {
            System.out.println("I'm Father, I have $" + money);
        }
    }

    static class Son extends Father {
        public int money = 1;

        public Son() {
            money = 4;
            showMeTheMoney();
        }

        public void showMeTheMoney() {
            System.out.println("I'm Son, I have $" + money);
        }
    }
}

输出的两句都是 “I’m Son”，因为 Son 类在创建的时候，首先隐式调用了 Father 的构造函数，而 Father 构造函数中对 showMeTheMoney 的调用是一次虚方法的调用，执行的版本是 Son::showMeTheMoney 方法，所以输出的是 “I’m Son”。虽然父类的 money 已经初始化成 2，但 Son::showMeTheMoney 方法中访问的是子类的 money，这里的结果是 0，因为它要到子类的构造函数执行时才会被初始化。之后子类构造方法执行输出 4，main 的最后一句通过外观类型访问到了父类中的 money，输出 2。

单分派与多分派

方法的接收者与方法的参数统称为方法的宗量，该定义最早出现在《Java 与模式》。根据分派基于多少种宗量，可将分派划分为单分派和多分派两种。单分派是根据一个宗量对目标方法进行选择，多分派则是根据多于一个宗量对目标方法进行选择。

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
/**
 * father choose 360
 * son choose qq
 */
public class Dispatch {
    public static void main(String[] args) {
        Father father = new Father();
        father.hardChoice(new _360());
        Father son = new Son();
        son.hardChoice(new QQ());
    }

    static class QQ {
        
    }

    static class _360 {
        
    }

    public static class Father {
        public void hardChoice(QQ arg) {
            System.out.println("father choose qq");
        }

        public void hardChoice(_360 arg) {
            System.out.println("father choose 360");
        }
    }

    public static class Son extends Father {
        public void hardChoice(QQ arg) {
            System.out.println("son choose qq");
        }

        public void hardChoice(_360 arg) {
            System.out.println("son choose 360");
        }
    }
}

这两次 hardChoice 的结果已在注释标注，重点是编译阶段中编译器的静态分派过程。选择目标方法的依据有两点：一是外观类型是 Father 还是 Son，二是方法参数是 QQ 还是 360.这次选择结果的最终产物是产生了两条 invokevirtual 指令，两条指令的参数分别为常量池中指向 Father::hardChoice(360) 及 Father::hardChoice(QQ) 方法的符号引用。因为是根据两个宗量进行选择，所以 Java 语言的静态分派属于多分派类型。

再看运行阶段中虚拟机的动态分派的过程。在执行 “son.hardChoice(new QQ());”，也就是指对应的 invokevirtual 指令时，由于编译期已经决定目标方法的签名必须为 hardChoice(QQ) ，虚拟机不管关心此时传递过来的参数到底是什么，因为其外观类型、实际类型都不会对选择构成任何影响，唯一可以影响虚拟机的该方法接受者的实际类型是 Father 还是 Son。因为只有一个宗量作为选择的依据，所以 Java 语言的动态分派属于单分派类型。

根据上述论证，如今的 Java 语言是一门静态多分派、动态单分派的语言。强调如今是因为这个结论未必会一直保持。 C# 3.0 及之前的版本与 Java 一样是动态单分派语言，但在 C# 4.0 加入dynamic 类型后，就可以很方便的实现多分派。JDK 10 时 Java 语言出现新关键字 var，但请不要将其与 C# dynamic 混淆，实际上 Java var 对应的是 C# var。它们与 dynamic 有本质区别：var 是在编译时根据声明语句的右侧表达式类型进行静态推断的，本质上这是一种语法糖(见 Effective-CSharp-1优先使用隐式类型的局部变量)；而 dynamic 在编译时完全不关心类型是什么，等到运行的时候再做类型判断。 与 C# dynamic 功能相近的是 JDK 9 时通过 JEP 276 引入的 jdk.dynalink 模块，使用 jdk.dynalink 可以实现在表达式中使用动态类型，Javac 编译器可以将其操作翻译为 invokedynamic 指令的调用点。

虚拟机动态分派实现

前文介绍的分派过程，作为对于 Java 虚拟机概念模型的解释已基本足够了，明确的解释了虚拟机在分派时会做什么这个问题。但要问 Java 虚拟机 “具体如何做到”，答案则可能因虚拟机的实现而不同而有差别。

动态分派是执行非常频繁的动作，且动态分派的方法版本选择过程需要运行时在接收者类型的方法元数据中搜索合适的目标方法。因此， Java 虚拟机实现基于执行性能的顾虑，真正运行时一般不会如此频繁地去反复搜索类型元数据，面对这种情况，一种基础且常见的优化手段是为类型在方注区中建立一个虚方法表（Virtual Method Table，也称为 vtable，与此对应的、在 invokeinterface 执行时也会用到接口方法表 —— Interface Method Table，简称 itable)，使用虚方法表索引代替元数据查找以提高性能。

虚方法表中存放着各个方法的实际入口地址。如果某个方法在子类中没有被重写，子类的虚方法表中的地址入口将与父类相同方法的入口地址一致，都是指向父类的实现入口。如果子类重写了这个方法，子类虚方法表中的地址则会被替换为指向子类实现版本的入口地址。

为了程序实现方便，拥有相同签名的方法，在父类、子类的虚方法表中都应当具有一样的索引序号，这样当类型变换时，仅需要变更查找的虚方法表，就可以从不同的虚方法表中按索引转换出所需的入口地址。虚方法表一般在类加载的连接阶段进行初始化，准备了类的变量初始值后，虚拟机会把该类的虚方法表也一同初始化完毕。

上述的查虚方法表是分派调用的一种优化手段，由于 Java 对象里面的方法默认 (即不使用 final) 就是虚方法，虚拟机除了使用虚方法表之外，为了进一步提高性能，还会用类型继承关系分析 (Class Hierarchy Analysis，CHA)、守护内联 (Guarded Inlining)、内存缓存 (Inline Cache) 等多种非稳定的激进优化来争取更大的性能空间。

发表于 更新于 分类于 本文字数： 198 阅读时长 ≈ 1 分钟

Cpu 对于可能被多次访的内存区域，会将其复制到 cache 中，之后访问不再从主存中获取，提升效率。从 ram 到 cache 的复制过程(Block Transfer)，复制单位为 linesize ，此处为 64 byte。

请看如下代码段，1 与 2 所需时间差不多，甚至 2 有时时间比 1 还长 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// int : 4 byte
// cache line : 64 byte
int[] arr = new int[1 << 26];

// 1
long t1 = System.currentTimeMillis();
for (int i = 0; i < arr.length; i++) arr[i] *= 3;
System.out.println(System.currentTimeMillis() - t1 + " ms");

// 2
long t2 = System.currentTimeMillis();
for (int i = 0; i < arr.length; i += 2) arr[i] *= 3;
System.out.println(System.currentTimeMillis() - t2 + " ms");


// 3
long t3 = System.currentTimeMillis();
for (int i = 0; i < arr.length; i += 32) arr[i] *= 3;
System.out.println(System.currentTimeMillis() - t3 + " ms");

1 与 2 Block transfer 次数相同，时间不会差太多

3 相比于 1 和 2 Block transfer 少了一倍，时间与其相差略小于一倍

发表于 更新于 分类于 本文字数： 1.1k 阅读时长 ≈ 4 分钟

冒泡排序

外层循环次数为集合元素数 - 1 (两两比较)

内层循环每次 -1 (每次循环确定最末尾数)

1
2
3
4
5
6
7
8
9
10
11
public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int idx = 0; idx < arr.length - 1 - i; idx++) {
            if (arr[idx] > arr[idx + 1]) {
                int temp = arr[idx + 1];
                arr[idx + 1] = arr[idx];
                arr[idx] = temp;
            }
        }
    }
}

选择排序

默认首位数为最小，遍历后续元素，确定最小索引，交换数据

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void selectSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int minIdx = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        int tmp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = tmp;
    }
}

插入排序

默认从二号元素开始，左侧元素为有序列

遍历时若较左侧小的数，进行移动(类冒泡)，否则直接进入下次外循环 (较左侧最近数大，则较有序列所有数大)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void insertionSort(int[] a) {
    int cur = 0;
    int len = a.length;
    while (++cur < len) {
        if (a[cur] < a[cur - 1]) {
            int val = a[cur];
            int idx = cur;
            while (--idx >= 0 && val < a[idx]) {
                a[idx + 1] = a[idx];
            }
            a[idx + 1] = val;
        }
    }
}

希尔排序

一种改进的插入排序

最外层循环为步长

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void shellSort(int[] arr) {
    for (int step = arr.length >>> 1; step > 0; step >>>= 1) {
        for (int j = step; j < arr.length; j++) {
            for (int idx = j; idx > 0 && idx - step >= 0; idx -= step) {
                if (arr[idx] < arr[idx - step]) {
                    int temp = arr[idx - step];
                    arr[idx - step] = arr[idx];
                    arr[idx] = temp;
                } else {
                    break;
                }
            }
        }
    }
}

快速排序

首先确定一个基数，将大于/小于他的数置于其两侧，再对左右两侧集合进行递归

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 static void quickSort(int[] arr, int start, int end) {
    if (start + 1 > end) {
        return;
    }
    boolean isStartWithEnd = true;
    int left = start;
    int right = end;
    int meanVal = arr[start];
    while (true) {
        if (isStartWithEnd) {
            if (arr[end] >= meanVal) {
                end--;
            } else if (arr[end] < meanVal) {
                arr[start] = arr[end];
                start++;
                isStartWithEnd = false;
            }
        } else /* if (!isStartWithHigh) */ {
            if (arr[start] <= meanVal) {
                start++;
            } else if (arr[start] > meanVal) {
                arr[end] = arr[start];
                end--;
                isStartWithEnd = true;
            }
        }
        if (start == end) {
            arr[start] = meanVal;
            break;
        }
    }
    quickSort(arr, left, start - 1);
    quickSort(arr, start + 1, right);
}

归并排序

先进行递归，将列表进行拆分，首先从最小的切分集合进行排序，之后进行合并排序，最终合并排序为一个有序表

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
public static void mergeSort(int[] arr, int start, int end) {
    if (end <= start) {
        return;
    }
    int mid = (start + end) >>> 1;
    mergeSort(arr, start, mid);
    mergeSort(arr, mid + 1, end);
    int left = start;
    int right = mid + 1;
    int idx = 0;
    int[] resArr = new int[end - start + 1];
    while (left <= mid && right <= end) {
        if (arr[left] <= arr[right]) {
            resArr[idx] = arr[left];
            left++;
        } else /* arr[left] > arr[right] */ {
            resArr[idx] = arr[right];
            right++;
        }
        idx++;
    }
    while (left <= mid || right <= end) {
        if (left <= mid) {
            resArr[idx] = arr[left];
            left++;
        } else /* right <= end */ {
            resArr[idx] = arr[right];
            right++;
        }
        idx++;
    }
    if (end - start + 1 >= 0) {
        System.arraycopy(resArr, 0, arr, start, end - start + 1);
    }
}

堆排序

构建堆 (此处是升序排序，所以选择大顶堆)

  1. 从第一个非叶子结点从下至上，从右至左调整，将大数置于根节点 (根节点 > 子节点)
  2. 调整堆结构，持续交换堆顶元素与末尾元素，从尾部向头部逐渐递归出一个有序表
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
class HeapSort {
    public static void sort(int[] arr) {
        for (int i = arr.length >>> 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        for (int j = arr.length - 1; j > 0; j--) {
            int tmp = arr[0];
            arr[0] = arr[j];
            arr[j] = tmp;
            adjustHeap(arr, 0, j);
        }
    }

    private static void adjustHeap(int[] arr, int cur, int len) {
        int tmp = arr[cur];
        // 若调整根节点，子节点需再调整 (idx = idx * 2 + 1)
        for (int idx = cur * 2 + 1; idx < len; idx = idx * 2 + 1) {
            // 判断 左/右子节点 中的最大子节点
            if (idx + 1 < len && arr[idx + 1] > arr[idx]) {
                idx++;
            }
            if (arr[idx] > tmp) {
                arr[cur] = arr[idx];
                cur = idx;
            } else {
                break;
            }
        }
        arr[cur] = tmp;
    }
}

基数排序

此处是最低位优先 (Least Significant Digit first，LSD) 法，从个位开始，对数组进行排序

  1. 将对应位元素出现的次数存储在 buckets 中

  2. buckets[i] += buckets[i - 1] 将 bucket 的值变为对应最后一个元素的索引 (此时buckets 为一个有序索引桶)，每确定一个索引的元素将对应 bucket 的值 -1，将 bucket 存储的索引移动到对应的下一个索引

    (实际上是索引 + 1，因为默认没有元素的 bucket 的值为 0，之后从 bucket 中取得索引需要 -1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static void radixSort(int[] arr) {
    int max = arr[0];
    int exp;
    for (int num : arr) {
        if (num > max) {
            max = num;
        }
    }
    for (exp = 1; max / exp > 0; exp *= 10) {
        int[] tmpArr = new int[arr.length];
        int[] buckets = new int[10]; // 0 ~ 9
        for (int value : arr) {
            buckets[(value / exp) % 10]++;
        }
        for (int i = 1; i < 10; i++) {
            buckets[i] += buckets[i - 1];
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            tmpArr[buckets[(arr[i] / exp) % 10] - 1] = arr[i];
            buckets[(arr[i] / exp) % 10]--;
        }
        System.arraycopy(tmpArr, 0, arr, 0, arr.length);
    }
}

发表于 更新于 分类于 本文字数： 3.9k 阅读时长 ≈ 14 分钟

简述

Java 选择的泛型实现方式是”类型擦除式泛型”(Type Erasure Generics)，而 C# 选择的泛型实现方式是”具体化式泛型”(Reified Generics)。具现化、偏特化这些名词最初都是源于C++ 模板语法中的概念，可以不必纠结其概念定义。C# 里面泛型无论在程序源码、编译后的中间语言(IL，这时泛型是一个占位符)，或是运行时期的CLR里面都是切实存在的，List 与 List 就是两个不同的类型，他们由系统在运行期生成，有自己独立的虚方法表和类型数据。而 Java 语言中的泛型则只在程序源码中存在，在编译后的字节码文件中，全部泛型都被替换为原来的裸类型(Raw Type)，并且在相应的位置插入了强制转换代码，对于运行期 的 Java 语言而言，ArrayList 和 ArrayList 其实是同一个类型。

如果是 C# 开发者，很难想象以下的 Java 代码是不合法的

1
2
3
T t = new T();
T[] array = new T[10];
List<T>[] listArray = new ArrayList<T>[10];

上述示例仅是 Java 泛型在编码阶段的不良影响，这个阶段的问题还能通过其他方法弥补 (多写几行代码，方法中多加一两个类型参数)，然而，在性能上的差距则是难以用编码弥补的。自 C# 2.0 引入了泛型后，带来的显著优势之一便是对比起 Java 在执行性能上的的提高，在使用平台提供的容器类型(例如 List Dictionary<TKey, TValue>)时，无需像 Java 那样不厌其烦的拆装箱，如果在 Java 中想避免这种性能损失，需要构造一个与数据类型相关的容器类(例如 IntFloatHashMap)。显然，这样除了引入了更多的代码，复杂度提高，复用性降低外，丧失了泛型本身的存在价值。

Java 的类型擦除式泛型无论是在使用效果上还是运行效率上，几乎是全面落后于 C# 的具现化式泛型，而它的唯一优势是在于实现这种泛型的影响范围上：擦除式泛型的实现几乎只需要在 Javac 编译器上做出改进即可，不需要改动字节码、不需要改动 Java 虚拟机，也保证了以前没用使用泛型的库，可以直接运行在 Java 5.0 之上。但这种听起来节省工作量甚至可以说是有偷工减料嫌疑的优势就显得非常短视。但这种方法确实在 Java 当年实现泛型的利弊权衡中胜出了。我们必须在当时的泛型历史背景中，考虑不同的实现方式带来的代价。

关于泛型

泛型的思想早在 C++ 语言的模板 (Template) 功能中就开始生根发芽了，而在 Java 语言中加入泛型的首次尝试出现在1996年。Martin Odersky (后来Scala语言的缔造者）当时是德国卡尔斯鲁厄编程理论的教授，他想设计一门能够支持函数式编程的程序语言，又不想从头把编程语言的所有功能都再做一遍。所以就注意到了刚刚发布一年的 Java，并在它上面实现了函数式编程的3大特性；泛型、高阶函数和模式匹配，形成了 Scala 语言的前身 Pizza 语言。后来，Java 的开发团队找到了 Martin Odersky，表示对 Pizza 语言的泛型功能很感兴趣，他们就一起建立了一个叫作 “Generic Java” 的新项目，且标是把 Pizza 语言的泛型单独移植到Java 语言上，其最终成果就是 Java 5.0 中的那个泛型实现，但是移植的过程并不是一开始就朝着类型擦除式泛型去的。事实上 Pizza 语言中的泛型更接近于现在 C# 的泛型，Martin Odersky 自已在采访自述中提到，进行 Generic Java 项目的过程中受到了重重约束，甚至多次让他感到沮丧，最紧、最难的约束来源于被迫要完全向后兼容无泛型 Java，即保证”二进制向后兼容性”(Binary Backwards Compatibility)。二进制向后兼容性是明确写入《Java 语言规范》中的对Java 使用者的严肃承诺，譬如一个在 JDK 1.2 中编译出来的 Class 文件，必须保证能够在 JDK 12 乃至以后的版本中也能够正常运行。

Java 到1.4.2版之前都没有支持过泛型，而到 Java 5.0 突然要支持泛型，还要让以以前编译的程序在新版本的虚拟机还能正常运行，就意味着以前没有的限制不能突然冒出来。

举个例子，在没有泛型的时代，由于 Java 中的数组是支持协变（Covariant)的，对应的集合类也可以存入不同类型的元素。类似于如下代码尽管不提倡，但是是完全可以正常编译成 Class 文件。

1
2
3
4
5
6
7
// 编译通过、运行时报错
Object[] array = new String[10];
array[0] = 10;
// 编译、运行都不会报错
ArrayList list = new ArrayList();
list.add(Integer.valueOf(10));
list.add("hello world");

为了保证这些编译出来的 Class 文件可以在 Java 5.0 引入泛型之后继续运行，设计者大体上有两种选择：

  1. 需要泛型化的类型(主要是容器类型)，以前有的就保持不变，然后平行地加一套泛型化版本的新类型。
  2. 直接把已有的类型泛型化，即让所有需要泛型化的已有类型都原地泛型化，不添加任何平行于已有类型的泛型版。

C# 选择第一条，添加了一组 System.Collections.Generic 的新容器，以前的 System.Collections 以及 System.Collections.Specialized 依然存在。C# 的开发人员很快就接受了新的容器，唯一的问题大概是许多 .NET 自身的标准库已经把老容器类型当作方法的返回值或者参数使用，这些方法至今还保持者原来的老样子。

但如果相同的选择出现在 Java 中，很有可能不会是相同的结果，当时的 .NET 才问世两年，而 Java 已经快有十年的历史了，再加上各自的流行程度，两者遗留代码的规模根本不在一个数量级上。而且更大的问题是 Java 并不是没有做过第一条那样的技术决策，在 JDK 1.2 时，遗留代码规模尚小，Java 就引入过新的集合类，并且保留了旧集合类不动。这就导致了直到现在，标准库中还有 Vector(老) ArrayList(新)、Hashtable(老) HashMap(新) 等两套容器代码并存，如果再整出像 Vector(老) ArrayList(新)、Vector(老但有泛型) ArrayList(新且有泛型) 这样的容器，可能会被骂的更狠。

如果当时有足够的时间来好好设计和实现，完全有可能做出更好的泛型系统，如今的 Valhalla 项目正在还以前泛型实现偷懒留下的技术债。

Java 类型擦除

由于 Java 选择了第二条，直接把已有的类型泛型化。要让所有需要泛型化的已有类型都原地泛型化。如 ArrayList，原地泛型化后变成了 ArrayList ，需要保证以前直接用 ArrayList 的代码泛型的新版本中还能使用这同一个容器，这就必须让所有泛型化的实例类型，如 ArrayList ArrayList 这些全部自动成为 ArrayList 的子类型才行，否则类型转换将是不安全的。由此引出了裸类型(Raw Type)的概念，**裸类型应是所有该类型泛型化实例的共同父类型(Super Type)**，只有这样，如下的复制才是被系统允许的，从子类到父类的安全转型。

1
2
3
4
5
ArrayList<Integer> iList = new ArrayList<>();
ArrayList<String> sList = new ArrayList<>();
ArrayList list; // Raw use of parameterized class 'ArrayList'
list = iList;
list = sList;

接下来的问题是如何实现裸类型。这又出现了两种选择：

  1. 运行期由 JVM 自动地、真实地构造出 ArrayList 这样的类型，自动实现从 ArrayList 派生自 ArrayList 的继承关系来满足裸类型的定义。
  2. 简单粗暴地直接在编译时把 ArrayList 还原成 ArrayList ，只在元素访问、修改时自动插入一些强制类型转换和检查指令。

当然结果大家都知道了，Java 选择了第二种。将第一段代码编译成 Class 文件，再用字节码反编译工具进行反编译后，将会发现泛型都不见了，程序又变回了 Java 泛型出现以前的代码，类型变为了裸类型，只是在元素访问的时候插入了从 Object 到 String 的强制转型代码，如第二段代码所示。

1
2
3
4
5
6
// 泛型擦除前
Map<String, String> map = new HashMap<>();
map.put("hello", "你好");
map.put("how are you", "你好吗");
System.out.println(map.get("hello"));
System.out.println(map.get("how are you"));
1
2
3
4
5
6
// 泛型擦除后
Map map = new HashMap<>();
map.put("hello", "你好");
map.put("how are you", "你好吗");
System.out.println((String) map.get("hello"));
System.out.println((String) map.get("how are you"));

缺陷

  1. 使用泛型擦除实现导致了对原始类(Primitive Type) 数据的支持成了新麻烦。

    1
    2
    3
    4
    5
    ArrayList<int> iList = new ArrayList<>();
    ArrayList<long> lList = new ArrayList<>();
    ArrayList list;
    list = iList;
    list = lList;

    上述代码是不合法的，因为，这种情况下，一旦把泛型信息擦除后，到要插入强制转型代码的地方就没有办法做下去了，因为不支持 int long 与 Object 之间的强制转换。Java 当时给出的方法一如既往的简单粗暴：没办法做，那就索性不用原生类型的泛型了，都用包装类，反正都做了自动的强制类型转换，遇到原生类型时把装拆箱也做了。这个决定导致了无数构造包装类和装箱、拆箱的开销，成为 Java 泛型慢的重要原因，也成为了如今 Valhalla 项目要重点解决的问题之一。

  2. 运行期无法取到泛型类型信息。使得一些代码变得极其繁琐，例如本文第一段代码的几种 Java 不支持的泛型用法，都是由于运行期 JVM 无法取得泛型类型而导致的。

    1
    2
    3
    4
    public static <T> T[] convert(List<T> list, Class<T> componentType) {
        T[] array = (T[]) Array.newInstance(componentType, list.size());
        ...
    }

    上述代码，写一个从泛型版本的从 List 到数组的转换方法，由于不能从 List 中取得参数化类型 T，所以不得不从另一个额外参数中再传一个数组的组件类型进去，实属无奈。

  3. 通过擦除实现泛型，还丧失了一些面向对象应有的优雅，带来了一些模糊情况。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    // 'method(List<String>)' clashes with 'method(List<Integer>)'
    // both methods have same erasure
    public static void method(List<String> list) {
        System.out.println("invoke method(List<String> list)");
    }

    public static void method(List<Integer> list) {
        System.out.println("invoke method(List<Integer> list)");
    }

    上述代码是不能被编译的，因为 List List 编译之后都被擦除了，变成了同一裸类型 List。类型擦除导致这两个方法的特征签名一模一样。但实际上这仅该方法是无法重载的一部分原因。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    public static String method(List<String> list) {
        System.out.println("invoke method(List<String> list)");
        return "";
    }

    public static int method(List<Integer> list) {
        System.out.println("invoke method(List<Integer> list)");
        return 1;
    }

    上述的代码竟然是可以正常使用的(在一些 JVM 中，例如 JDK 6)。为两个方法指定不同的返回值，方法的重载竟然成功了，简直是打破了我们对于 Java 语言中返回值不参与重载选择的基本认知。

    实际上这当然不是根据返回值来确定的，能编译和执行成功，是因为两个 method() 方法加入了不同的返回值后才能共存在一个 Class 文件中。方法重载要求方法具备不同的特征签名，返回值并不包含在方法的特征签名中，所以返回值不参与重载选择，但是在 Class 文件格式之中，只要描述符不是完全一致的两个方法，就可以共存。

    由于 Java 泛型的引入，各种场景（虚拟机解析、反射等）下的方法调用都可能对原有的基础产生影响并带来新的需求，如在泛型类中如何获取传入的参数化类型等。所以 JCP 组织对《Java 虚拟机规范》做出了相应的修改，引入了诸如 Signature LocalVariableTypeTable 等新的属性用于解决伴随泛型而来的参数类型的识别问题，Signature 是其中最重要的一项属性，它的作用就是存储一个方法在字节码层面的特征整签名，这个属性中保存的参数类型并不是原生类型，而是包括了参数化类型的信息。修改后的虚拟机规范P要求所有能识别 49.0 以上版本的 Class 文件的虚拟机都要能正确地识别 Signature 参数。

    从上面的例子中可以看到擦除法对实际编码带来的不良影响，由于 List 和 List 擦除后是同一个类型，我们只能添加两个并不需要的返回值才能完成重载，这是一种毫无优雅和美感可言的解决方案，并且存在一定语意上的混乱，例如上文中提到的，用 JDK 6的 Javac 才能编译成功，其他版本或者是 ECJ 编译器都有可能拒绝编译。

    另外，从 Signature 属性的出现我们还可以得出结论，擦除法所谓的擦除，仅仅是对方法的 Code 属性中的字节码进行擦除，实际上元数据中还是保留了泛型信息，这也是我们在编码时能通过反射手段取得参数化类型的根本依据。

值类型

目前比较明确的是未来的 Java 应该会提供 “值类型” (Value Type) 的语言层面的支持。

说到值类型，这也是 C# 用户攻讦 Java 语言的常用武器之一

C# 并没有 Java 意义上的原生数据类型，在 C# 中使用的 int、bool、double关键字其实是对应了一系列在 .NET 中来中预定义好的结构体(Struct)，如 Int32、 Boolean、 Double 等。在 C# 中开发人员也可以定义自己值类型，只要继承于 ValueType 类型即可，而 ValueType 也是统一基类 Object 的子类，所以并不会遇到 Java 那样 int 不自动装箱就无法转型为 Object 的尴尬。

值类型可以与引用类型一样，具有构造函数，方法或是属性字段，等等，而它与引用类型的区别在于它在赋值的时候通常是整体复制，而不是像引用类型那样传递引用的。更为关键的是，值类型的实例很容易在方法的调用栈上实现分配，这意味着值类型会随着当前方法的退出而自动释放，不会给垃圾收集于系统带来任何压力。

发表于 更新于 本文字数： 366 阅读时长 ≈ 1 分钟

事务是一组原子性的SQL查询，一个独立的工作单元。如果数据库引擎能够成功对数据库应用该组查询的全部语句，那么就执行该组查询。如果其中任何一条因为崩溃或其他原因无法执行，那么所有的语句都不会被执行。事务内的语句，要么全部执行成功，要么全部执行失败。

  1. 原子性(atomicity)

    一个事务必须被视为一个不可分割的最小单元。

    整个事务中所有的操作要么全部提交(成功)，要么全部回滚(失败)。

    对于单一事务而言，不可能只执行其中的一部分操作。

  2. 一致性(consistency)

    总是从一个一致的状态转换到另一个一致的状态。

    若在事务执行过程中系统崩溃，因事务的修改还未提交，事务的修改不会被保存。

  3. 隔离性(isolation)

    一个事务所做的修改在提交前，对于其他的事务是不可见的。

    是否可见与**隔离级别(Isolation level)**相关。

  4. 持久性(durability)

    一旦事务提交，修改将永久保存。即使系统崩溃修改的数据也不会丢失。

    持久性的表现与持久性级别相关。

实现以上特性能提供更高的安全性，但也会需要数据库做更多的额外工作。

发表于 更新于 分类于 本文字数： 362 阅读时长 ≈ 1 分钟

将null而不是0长度的数组或集合返回是不合常理的，这使得客户端中必须得有额外代码以处理null的代码。编写客户端程序的程序员有可能忘记写代码来处理null，这样的错误可能很久都不会被发现。返回null也会使得其实现代码更加复杂。

有时候会有人认为: null返回值会比零长度集合或数组更好，因为它避免了分配长度容器所需的开销。这种观点是站不住脚的，原因有二:

  1. 在这个级别上担心性能问题是不明智的，除非分析表明这个方法正是造成性能问题的原因(见67条)。
  2. 不需要分配零长度的集合或者数组，也可以返回他们。

如果切实造存在性2能问题，可以通过重复返回一个不可变的零长度集合(例如 Collections.emptyList() Collections.emptyMap() )，避免即时分配，因为不可变类可以被自由的共享(见17条)。这仅是一个优化，几乎用不上。如果您认为确实有必要，请在行动前后进行性能测试。

简而言之，返回一个零长度的数组或集合，而不是null。如果返回null，那样会使得API更加难用，也更容易出错，且没有任何的性能优势。

发表于 更新于 分类于 本文字数： 185 阅读时长 ≈ 1 分钟

  1. 单一职责原则(Single Responsibility Principle)

    单一类承担单一职责。

  2. 开放封闭原则（Open close Principle)

    对扩展开放，对修改封闭。

  3. 里氏替换原则（Liskov Substitution Principle）

    父类具有的功能，子类必须具有。

  4. 接口隔离原则（Interface Segregation Principle）

    依赖应当建立在最小的接口。 (而不是聚合的单一接口)

  5. 依赖倒置原则（Dependency Inversion Principle）

    依赖不基于实体类，而是基于接口 。(依赖不基于具体，而是基于抽象)

国内有设计模式六大原则的说法，多出一个：

  1. 迪米特法则 (Law of Demeter) 又称 最少知道原则 (Least Knowledge Principle)

    模块不应了解所操作对象的内部情况。

0%