Comparator中Long Cast Int引发的血案
先看代码
Collections.sort(list, new Comparator<Long>() {
@Override
public int compare(Long time1, Long time2) {
return (int) (time1 - time2);
}
});
这么短几行,看上去好像没什么问题?
组内Code Review也未发现问题,但是上线一段时间后收到很多异常!
Caused by: java.lang.IllegalArgumentException: Comparison method violates its general contract!
at java.util.TimSort.mergeHi(TimSort.java:899)
at java.util.TimSort.mergeAt(TimSort.java:516)
at java.util.TimSort.mergeCollapse(TimSort.java:441)
at java.util.TimSort.sort(TimSort.java:245)
at java.util.Arrays.sort(Arrays.java:1498)
at java.util.ArrayList.sort(ArrayList.java:1470)
at java.util.Collections.sort(Collections.java:201)
翻译过来
比较方法违反了其总合同!!!
合同在哪?
Comparator中compare有如下描述。
**
* Compares its two arguments for order. Returns a negative integer,
* zero, or a positive integer as the first argument is less than, equal
* to, or greater than the second.<p>
*
* In the foregoing description, the notation
* <tt>sgn(</tt><i>expression</i><tt>)</tt> designates the mathematical
* <i>signum</i> function, which is defined to return one of <tt>-1</tt>,
* <tt>0</tt>, or <tt>1</tt> according to whether the value of
* <i>expression</i> is negative, zero or positive.<p>
*
* The implementor must ensure that <tt>sgn(compare(x, y)) ==
* -sgn(compare(y, x))</tt> for all <tt>x</tt> and <tt>y</tt>. (This
* implies that <tt>compare(x, y)</tt> must throw an exception if and only
* if <tt>compare(y, x)</tt> throws an exception.)<p>
*
* The implementor must also ensure that the relation is transitive:
* <tt>((compare(x, y)>0) && (compare(y, z)>0))</tt> implies
* <tt>compare(x, z)>0</tt>.<p>
*
* Finally, the implementor must ensure that <tt>compare(x, y)==0</tt>
* implies that <tt>sgn(compare(x, z))==sgn(compare(y, z))</tt> for all
* <tt>z</tt>.<p>
*
* It is generally the case, but <i>not</i> strictly required that
* <tt>(compare(x, y)==0) == (x.equals(y))</tt>. Generally speaking,
* any comparator that violates this condition should clearly indicate
* this fact. The recommended language is "Note: this comparator
* imposes orderings that are inconsistent with equals."
大致意思就是,你必须保证自反性,传递性,有序性。
- 自反性:x,y 的比较结果和 y,x 的比较结果相反。
- 传递性:x>y,y>z,则 x>z。
- 对称性:x=y,则 x,z 比较结果和 y,z 比较结果相同。
那么我到底违反了那条合同了?
唯一能怀疑的也只有 long cast to int 了!
先看下两种类型取值范围
类型 | 最大值 | 最小值 |
---|---|---|
int | 2^31 - 1 = 2147483647 | -2^31 = -2147483648 |
long | 2^63 - 1 = 9223372036854775807 | -2^63 = -9223372036854775808 |
开始找茬游戏...
于是乎!
long x = 2147483648l, long y = 0
(int) (x - y) = (int) 2147483648l = -2147483648
(int) (y - x) = (int) -2147483648l = -2147483648
神奇的x < y && y < x 成立了!
合同第一条自反性违反!
再来
long x = 2147483648l, long y = 1l, long z = -1l
(int) (x - y) = (int) (2147483647l) = 2147483647
(int) (y - z) = (int) (2l) = 2l
(int) (x - z) = (int) (2147483649l) = -2147483647
神奇的x > y && y > z && x < z 也成立了!
合同第二条传递性违反!
轻轻松松就写了个弥天大bug!
找到问题就好解决了,不用cast就是了。
Long.compare(time1, time2);
Long.compare实现也很简单, 直接比较大小,返回对应int值即可。
public static int compare(long x, long y) {
return (x < y) ? -1 : ((x == y) ? 0 : 1);
}
总结
类型强转,精度丢失会惹祸!!!
类型强转需谨慎,谨慎,再谨慎!!!