JDK 完全向下兼容吗?JDK1.7 新的内置排序算法 TimSort 引发的异常

从 1997 年 JDK1.1 面世,20 年间 Java 已经发布了 10 多个版本,而我们都知道 Java 的兼容性很强,低版本编译的项目可以运行在高版本的 Java 上,平时工程项目升级 Java 版本时无需任何顾虑。
但是真的是这样吗。我们来看下面一段代码:

public static void main(String[] args) {
    int[] sample = new int[]
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 1, 0, -2, 0, 0, 0, 0};
    List<Integer> list = new ArrayList<Integer>();
    for (int i : sample)
        list.add(i);
    Collections.sort(list, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o1 > o2 ? 1 : -1;
        }
    });
    System.out.println(list);
}

这段代码是调用 Java 内置排序方法 Collections.sort() 来排序一个数组,用 JDK1.6 版本运行没问题,但如果用 JDK1.7 就会抛出异常。


原因有两点

  1. JDK1.7 将内置排序算法改为了 TimSort。
  2. 我们 Comparator 接口的实现并不规范。

Comparator

我们先来看一下源代码中 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.
In the foregoing description, the notation sgn(expression) designates the mathematical signum function, which is defined to return one of -1, 0, or 1 according to whether the value of expression is negative, zero or positive.
The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y. (This implies that compare(x, y) must throw an exception if and only if compare(y, x) throws an exception.)
The implementor must also ensure that the relation is transitive: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0.
Finally, the implementor must ensure that compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z.
It is generally the case, but not strictly required that (compare(x, y)==0) == (x.equals(y)). 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."

简单总结一下就是实现这个方法要保证以下几点:

  • compare(x,y) 和 compare(y,x) 的正负相反;
  • 如果 compare(x,y)>0,并且 compare(y,z)>0,那么 compare(x,z)>0;
  • 如果 compare(x,y)==0,那么 compare(x,z) 和 compare(y,z) 正负相同

我们上面代码实现的 compare 方法中,如果传入的两个对象相等,compare(x,y) 和 compare(y,x) 都会返回 -1,没有保证上面说的第一点。其实一般的排序算法并不需要严格保证 compare 方法,只需要两个对象简单比较一下。比如 JDK1.6 内置排序算法 Collections.sort() 使用的是归并排序(JDK1.7 保留了这个算法),并在元素个数小于 INSERTIONSORT_THRESHOLD(默认值 7) 时优化为使用简单的冒泡排序:

if (length < INSERTIONSORT_THRESHOLD) {
    for (int i=low; i<high; i++)
        for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)
            swap(dest, j, j-1);
    return;
}

我们实现的 compare 在这些排序中完全适用,但 JDK1.7 中默认排序算法改为了 TimeSort,就让我们来深入了解一下这种排序算法。

TimSort

TimSort 的起源和历史我就不多说了,最早应用在 python 的内置排序中。TimSort 的核心就是 归并排序+二分查找插入排序,并进行大量优化,主要思路如下:

  1. 划分 run(对原序列分块,每个块称之为 run)
  2. 排序 run
  3. 合并 run

网络上有关介绍这种算法的文章很多,我就不多赘述了,我们来看一下 JDK1.7 中的具体实现

代码总览

首先进入排序逻辑会先判断一个 jvm 启动参数,选择使用旧的归并排序(元素个数小于 7 时用冒泡排序),还是使用 TimeSort 进行排序。默认为使用 TimSort。

if (LegacyMergeSort.userRequested)
    legacyMergeSort(a, c);
else
    TimSort.sort(a, c);

进入 TimSort 代码后会进行一些校验和判断,比如判断元素个数少于 MIN_MERGE(默认值 32) 则会通过一个“迷你-TimSort” 进行排序。这是将整个序列看做一个 run,省略了划分 run 和合并 run 两个步骤,直接进行排序 run。

// If array is small, do a "mini-TimSort" with no merges
if (nRemaining < MIN_MERGE) {
    int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
    binarySort(a, lo, hi, lo + initRunLen, c);
    return;
}

我们来看一下核心的算法流程代码,后面会详细讲解每个步骤:

//栈结构,用于保存以及合并 run
TimSort<T> ts = new TimSort<>(a, c);
//确定每个 run 的最小长度
int minRun = minRunLength(nRemaining);
do {
    //划分、排序 run
    // Identify next run
    int runLen = countRunAndMakeAscending(a, lo, hi, c);

    // If run is short, extend to min(minRun, nRemaining)
    if (runLen < minRun) {
        int force = nRemaining <= minRun ? nRemaining : minRun;
        binarySort(a, lo, lo + force, lo + runLen, c);
        runLen = force;
    }

    //保存、合并 run
    // Push run onto pending-run stack, and maybe merge
    ts.pushRun(lo, runLen);
    ts.mergeCollapse();

    // Advance to find next run
    lo += runLen;
    nRemaining -= runLen;
} while (nRemaining != 0);

// Merge all remaining runs to complete sort
assert lo == hi;
ts.mergeForceCollapse();
assert ts.stackSize == 1;

1.划分 run

划分 run 和排序 run 密不可分,TimSort 算法优化的点之一就是尽可能利用原序列的单调子序列。countRunAndMakeAscending() 方法寻找原始元素数组 a 中从 lo 位置开始的最长单调递增或递减序列(递减序列会被反转)。这样,这部分元素相当于排好序了,我们可以直接把它当做一个排序好的 run。但问题随之而来,如果这样的序列很短,会产生很多 run,后续归并的代价就很大,所以我们要控制 run 的长度。下面这段代码规定 run 的最小长度:

private static int minRunLength(int n) {
    assert n >= 0;
    int r = 0;      // Becomes 1 if any 1 bits are shifted off
    while (n >= MIN_MERGE) {
        r |= (n & 1);
        n >>= 1;
    }
    return n + r;
}

n 为整个序列的长度,TimSort 算法优化点之一是通过控制 run 的长度,使 run 的数量保持在 2 的 n 次方,这样在归并的时候,就像二叉树一样进行归并,不会到最后出现非常大的 run 与非常小的 run 归并。代码中 MIN_MERGE 为 32,最后计算出的最小 run 长度介于 16 和 32 之间。

2.排序 run

// Identify next run
int runLen = countRunAndMakeAscending(a, lo, hi, c);
// If run is short, extend to min(minRun, nRemaining)
if (runLen < minRun) {
    int force = nRemaining <= minRun ? nRemaining : minRun;
    binarySort(a, lo, lo + force, lo + runLen, c);
    runLen = force;
}

随后在循环中根据计算出的最短 run 长度和剩余序列单调子序列来划分 run,先取出剩余序列开头的单调子序列,如果长度不够规定的最短长度,则用 binarySort() 方法将其后的元素一个个通过二分查找插入到这个找出的单调递增数组中,直到长度达到规定的最短长度(或到剩余序列结尾),从而将整个序列划分多个 run,并确保每个 run 都是排好序的。

private static <T> void binarySort(T[] a, int lo, int hi, int start,
                                   Comparator<? super T> c) {
    assert lo <= start && start <= hi;
    if (start == lo)
        start++;
    for ( ; start < hi; start++) {
        T pivot = a[start];
        // Set left (and right) to the index where a[start] (pivot) belongs
        int left = lo;
        int right = start;
        assert left <= right;
        /*
         * Invariants:
         *   pivot >= all in [lo, left).
         *   pivot <  all in [right, start).
         */
        while (left < right) {
            int mid = (left + right) >>> 1;
            if (c.compare(pivot, a[mid]) < 0)
                right = mid;
            else
                left = mid + 1;
        }
        assert left == right;
        /*
         * The invariants still hold: pivot >= all in [lo, left) and
         * pivot < all in [left, start), so pivot belongs at left.  Note
         * that if there are elements equal to pivot, left points to the
         * first slot after them -- that's why this sort is stable.
         * Slide elements over to make room for pivot.
         */
        int n = start - left;  // The number of elements to move
        // Switch is just an optimization for arraycopy in default case
        switch (n) {
            case 2:  a[left + 2] = a[left + 1];
            case 1:  a[left + 1] = a[left];
                     break;
            default: System.arraycopy(a, left, a, left + 1, n);
        }
        a[left] = pivot;
    }
}

上面代码首先二分查找出插入点 assert left == right,插入点及其后元素后移,通过 a[left] = pivot,将目标元素插入。可以看到,这里也有很多优化,比如计算需要后移的元素个数,如果是 1,则直接交换目标元素和插入点元素即可(目标元素本来在数组最后一格)。

3.合并 run

将 run 压入栈,执行合并,之后便是在循环中寻找下一个 run,入栈的时候会记录当前 run 的起点在整个序列的位置(所有 run 都在原数组里,不占用额外空间)以及 run 长度:

// Push run onto pending-run stack, and maybe merge
ts.pushRun(lo, runLen);
ts.mergeCollapse();

// Advance to find next run
lo += runLen;
nRemaining -= runLen;

我们来看一下具体合并流程,首先是合并的条件,我们要保证所有的 run 类似二叉树方式进行合并,防止出现非常大的 run 与非常小的 run 进行合并,每个 run 入栈时都会调动这个方法,假设栈顶位置为 i,那么我们要保证栈里的 run 符合以下条件 stack[i-2].length > stack[i-1].length + stack[i].length,并且 stack[i-1].length > stack[i].length。如果不符合,则需要合并。

private void mergeCollapse() {
    while (stackSize > 1) {
        int n = stackSize - 2;
        if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {
            if (runLen[n - 1] < runLen[n + 1])
                n--;
            mergeAt(n);
        } else if (runLen[n] <= runLen[n + 1]) {
            mergeAt(n);
        } else {
            break; // Invariant is established
        }
    }
}

因为我们的 run 都在原数组中,通过记录起点坐标和长度来划分,没有占用额外空间,所以我们合并的时候合并相邻两个 run,排序完成后,修改记录的起点坐标和长度来实现合并。在合并时也有优化,run1 和 run2 相邻,run1 在前,run2 在后。那么 run1 中比 run2 最小(第一个)元素小的那些元素其实相当于已经在正确的位置了,不需要考虑,同理 run2 中比 run1 最大的元素大的那些元素也是这样。举个例子:[1,2,3,4][3,4,4,4,5,6] -> [1,2,[3,4][3,4,4],5,6] -> [1,2,3,3,4,4,4,5,6],数组 9 个连续位置,两个相邻 run,其中 [1,2,-,-,-,-,-,5,6] 相当于排好序了,只需要合并剩余的 [3,4][3,4,4],代码如下:

/*
 * Find where the first element of run2 goes in run1. Prior elements
 * in run1 can be ignored (because they're already in place).
 */
int k = gallopRight(a[base2], a, base1, len1, 0, c);
assert k >= 0;
base1 += k;
len1 -= k;
if (len1 == 0)
    return;

/*
 * Find where the last element of run1 goes in run2. Subsequent elements
 * in run2 can be ignored (because they're already in place).
 */
len2 = gallopLeft(a[base1 + len1 - 1], a, base2, len2, len2 - 1, c);
assert len2 >= 0;
if (len2 == 0)
    return;

// Merge remaining runs, using tmp array with min(len1, len2) elements
if (len1 <= len2)
    mergeLo(base1, len1, base2, len2);
else
    mergeHi(base1, len1, base2, len2);

可以看到,即使合并剩余部分,依然通过判断两者长度来进行算法优化。

在循环结束后,会尝试最后的合并,确保栈里只剩一个 run,即排序好的整个序列。

// Merge all remaining runs to complete sort
assert lo == hi;
ts.mergeForceCollapse();
assert ts.stackSize == 1;

具体合并算法非常复杂,我看的也是一知半解,总之在合并过程中,遇到一些特殊情况,会抛出一个异常,提醒开发者所实现的 compare() 并不符合规约。

if (len1 == 1) {
    assert len2 > 0;
    System.arraycopy(a, cursor2, a, dest, len2);
    a[dest + len2] = tmp[cursor1]; //  Last elt of run 1 to end of merge
} else if (len1 == 0) {
    throw new IllegalArgumentException(
        "Comparison method violates its general contract!");
} else {
    assert len2 == 0;
    assert len1 > 1;
    System.arraycopy(tmp, cursor1, a, dest, len1);
}

结论

我们只能确定低版本编译的代码可以运行在高版本的 Java,但却无法保证运行的行为和结果与低版本一致。

我们看到代码入口会通过一个启动参数来判断选择内置排序算法,所以我们可以通过添加 jvm 启动参数 -Djava.util.Arrays.useLegacyMergeSort=true,来使用传统归并排序,保证两个版本的排序行为一致。

Java7 及之前版本中 Date 类设计缺陷

Java 程序猿普遍对 Date 这个类感触深刻,诟病已久,因为它存在太多问题,用起来十分不方便。下面说说主要问题。

多个 Date

在 java.util 和 java.sql 的包中都有一个名为 Date 的日期类。但 java.util.Date 同时包含日期和时间,而 java.sql.Date 仅包含日期,java.sql.Time 包含时间。按照英文语义来说,Date 指日期,Time 指时间,而且还有重名类,因此 java.util.Date 命名定义就有问题。

常用操作

作为开发者,尤其是初学者,一定会对 java.util.Date 类的格式化印象深刻,因为感觉冗余和繁琐,还需要引入其他类。用于格式化和解析的类在 java.text 包中定义,对于格式化和解析的需求,我们有 java.text.DateFormat 抽象类,一般写代码时,我们习惯用 SimpleDateFormat。

Date date = new Date();
SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String dateString = dateFormat.format(date);

另外 java.util.Date 没有提供直接对日期时间的加减操作方法,在修改时间十分不方便。

局限性

java.util.Date 类并不提供国际化,没有时区支持,开发相关业务时还要引入 java.util.Calendar 和 java.util.TimeZone 类,业务开发时增加了代码复杂度。

可变

java.util.Date 类最大的缺陷就是可变性。可变性会在开发中带来很多问题,比如在多线程环境中不可靠,再比如下面的代码执行不符合预期。

Date d = new Date();
Scheduler.scheduleTask(task1, d);
d.setTime(d.getTime() + ONE_DAY);
Scheduler.scheduleTask(task2, d);

task1 和 task2 都会在一天后执行

解决方案

在 Java7 及之前的版本中用第三方时间库,比如 Jode-Time,相信大多数程序猿对这个库十分熟悉。
Java8 引入了新的时间库,java.time 包,其中有关日期时间的类解决了上面这些问题,十分好用。

Spring Mybatis 动态数据源

Annotation 和 Enum

我们首先需要一个注解和枚举类来标识和定义数据源

@Retention(RetentionPolicy.RUNTIME)
@Target({ElementType.METHOD})
public @interface DataSource {
    DataSourceEnum value() default DataSourceEnum.MASTER;
}
public enum DataSourceEnum {
    MASTER, SLAVE
}

DynamicDataSourceAspect

然后监听 service 层接口,获取数据源标识,切点前执行 before() 方法,切点后执行 after() 方法。(xml配置省略)

public class DynamicDataSourceAspect {

    public void before(JoinPoint point) {
        Method targetMethod = ((MethodSignature) point.getSignature()).getMethod();
        DataSource dataSource = targetMethod.getAnnotation(DataSource.class);
        if (dataSource != null) {
            DynamicDataSourceHolder.putDataSource(dataSource.value());
        } else {
            DynamicDataSourceHolder.putDataSource(DataSourceEnum.MASTER);
        }
    }

    public void after(JoinPoint point) {
        DynamicDataSourceHolder.clearDataSource();
    }
}

DynamicDataSourceHolder

我们需要一个 ThreadLocal 来保存当前取到的数据源,这里我们用了一个 Stack,因为可能 A 方法调用了 B 方法,执行完 B 方法后上下文要还原到 A 的数据源来继续执行 A 方法后续语句。因此需要一个先进先出的数据结构来存放数据源。

public class DynamicDataSourceHolder {

    private static final ThreadLocal<Stack<DataSourceEnum>> holder = new ThreadLocal<>();

    public static void putDataSource(DataSourceEnum dataSource) {
        Stack<DataSourceEnum> dataSourceEnums = holder.get();
        if (null == dataSourceEnums) {
            dataSourceEnums = new Stack<>();
            holder.set(dataSourceEnums);
        }

        dataSourceEnums.push(dataSource);
    }

    public static DataSourceEnum getDataSource() {
        Stack<DataSourceEnum> dataSourceEnums = holder.get();
        if (null == dataSourceEnums || dataSourceEnums.isEmpty()) {
            return null;
        }
        return dataSourceEnums.peek();
    }

    public static void clearDataSource() {
        Stack<DataSourceEnum> dataSourceEnums = holder.get();
        if (null == dataSourceEnums || dataSourceEnums.isEmpty()) {
            return;
        }
        dataSourceEnums.pop();
    }
}

DynamicDataSource

Spring 提供 AbstractDataSource 这个抽象类,我们继承这个类实现自己的动态 DataSource,我们我们先看看这个类的主要代码

//有 set 和 get 方法
private Map<Object, Object> targetDataSources;
//有 set 和 get 方法
private Object defaultTargetDataSource;
//在 afterPropertiesSet() 方法中复制自 targetDataSources
private Map<Object, DataSource> resolvedDataSources;
//在 afterPropertiesSet() 方法中复制自 defaultTargetDataSource
private DataSource resolvedDefaultDataSource;

@Override
public void afterPropertiesSet() {
    //复制 targetDataSources -> resolvedDataSources
    //复制 defaultTargetDataSource -> resolvedDefaultDataSource
}

//获取 DataSource 连接
@Override
public Connection getConnection() throws SQLException {
    return determineTargetDataSource().getConnection();
}

//根据 Key 获取指定 DataSource
protected DataSource determineTargetDataSource() {
    Assert.notNull(this.resolvedDataSources, "DataSource router not initialized");
    Object lookupKey = determineCurrentLookupKey();
    DataSource dataSource = this.resolvedDataSources.get(lookupKey);
    if (dataSource == null && (this.lenientFallback || lookupKey == null)) {
        dataSource = this.resolvedDefaultDataSource;
    }
    if (dataSource == null) {
        throw new IllegalStateException("Cannot determine target DataSource for lookup key [" + lookupKey + "]");
    }
    return dataSource;
}

//重写此方法,动态选择 Key
protected abstract Object determineCurrentLookupKey();

上面方法最后三个方法是重点,调用顺序 getConnection() -> determineTargetDataSource() -> determineCurrentLookupKey(),从一个 Map 中根据 key 来获取对应的 DataSource,最后这个抽象方法是需要我们重写的。

public class DynamicDataSource extends AbstractRoutingDataSource {

    @Setter
    private Object writeDataSource; //写数据源
    @Setter
    private Object readDataSources; //读数据源

    @Override
    public void afterPropertiesSet() {
        if (this.writeDataSource == null) {
            throw new IllegalArgumentException("Property 'writeDataSource' is required");
        }
        setDefaultTargetDataSource(writeDataSource);
        Map<Object, Object> targetDataSources = new HashMap<>();
        targetDataSources.put(DataSourceEnum.MASTER.name(), writeDataSource);
        targetDataSources.put(DataSourceEnum.SLAVE.name(), readDataSources);
        setTargetDataSources(targetDataSources);
        super.afterPropertiesSet();
    }

    @Override
    protected Object determineCurrentLookupKey() {
        DataSourceEnum dataSourceEnum = DynamicDataSourceHolder.getDataSource();
        if (dataSourceEnum == null) {
            return DataSourceEnum.MASTER.name();
        } else {
            return dataSourceEnum.name();
        }
    }
}

DynamicDataSource 的配置文件如下

<bean id="masterDataSource" class="org.apache.commons.dbcp.BasicDataSource">...</bean>
<bean id="slaveDataSource" class="org.apache.commons.dbcp.BasicDataSource">...</bean>
<bean id="dataSource" class="me.snowhere.datasource.DynamicDataSource">
    <property name="writeDataSource" ref="masterDataSource"/>
    <property name="readDataSources" ref="slaveDataSource"/>
    <property name="defaultTargetDataSource" ref="masterDataSource"/>
</bean>
<bean id="sqlSessionFactory" class="org.mybatis.spring.SqlSessionFactoryBean">
    <property name="dataSource" ref="dataSource"/>
</bean>

其他

上面只是实现了一个最简单的,可以工作的动态数据源,并不适合放到工程中,因为还有很多地方需要扩展:
1. 切面和注解。除了注解方法,我们还可以设置注解到类上以及接口上,并在 DynamicDataSourceAspect 中按照优先级依次寻找方法、类、接口上的注解,确定数据源标识。
2. 动态数据源。在 DynamicDataSource 中,我们只有一个主数据源和从数据源,我们可以把从数据源改为 List,在 targetDataSources.put() 时的 key 为 DataSourceEnum.SLAVE.name() + index,并设置一个属性来标识选择从库的策略,比如随机或轮询,来确定 index 的值选择具体从库。实现一主多从的架构。

另外还有一些其他需要注意的问题:
1. 直接用 this 调用当前对象的方法不会被切面拦截,配置的数据源标识也就无效
2. 事务不能跨数据源

从 Date 和 Timestamp 看 Java 继承特性和 equals() 方法约定间的冲突

Java 的继承是面向对象最显著的一个特性。Date 和 Timestamp 是 Java 中的两个和时间有关的类。Timestamp 继承自 Date。

equals() 方法是 Java 中最常用的方法之一,在 Object 中定义,任何对象都有的方法,我们在自定义类的时候,一般都会重写此方法。

equals() 方法的约定

首先讲一讲重写 equals() 方法时要注意的约定

  1. 自反性(reflexive),对于任何非 null 的引用值 x,x.equals(x)必须返回true。
  2. 对称性(symmetric),对于任何非 null 的引用值 x 和 y,当且仅当y.equals(x)返回true时,x.equals(y)必须返回true。
  3. 传递性(transitive),对于任何非 null 的引用值 x、y 和 z,如果 x.equals(y) 返回 true,并且 y.equals(z) 也返回 true,那么 x.equals(z) 也必须返回 true。
  4. 一致性(consistent),对于任何非 null 的引用值 x 和 y,只要 equals 的比较操作在对象中所有的信息没有被修改,多次调用 x.equals(y) 就会一致地返回 true,或者一致地返回 false。
  5. 对于任意非 null 的引用值 x,x.equals(null) 必须返回false。

这几条简单易懂。一般我们重写 equals() 方法会先判断类型是否一致,然后根据类中的成员域来判断。比如下面这个简化的 Date 类。

public class Date{
    private transient long fastTime;
    public Date(long date) {
        fastTime = date;
    }
    public long getTime() {
        return fastTime;
    }
    public boolean equals(Object obj) {
        return obj instanceof Date && getTime() == ((Date) obj).getTime();
    }
}

equals 方法首先判断是否是 Date 类型,然后判断 fastTime 字段值是否一致。

继承

我们再来看一下简化的 Timestamp 类

public class Timestamp extends Date {
    private int nanos;
    public Timestamp(long time) {
        super((time/1000)*1000);
        nanos = (int)((time%1000) * 1000000);
    }
    public boolean equals(Object ts) {
        if (ts instanceof Timestamp) {
            if (super.equals(ts)) {
                if  (nanos == ts.nanos) {
                    return true;
                } 
            } 
        } 
        return false;
    }
}

Timestamp 在 Date 的基础上增加了一个 nanos 字段。所以它的 equals 方法首先判断是否是 Timestamp 类型,然后调用父类 equals 方法判断 fastTime 字段,最后判断 nanos 字段。

我们看下面一段代码。

继承破坏约定

Date date = new Date(1000);
Timestamp timestamp1 = new Timestamp(1000);
timestamp1.setNanos(1);
Timestamp timestamp2 = new Timestamp(1000);
timestamp2.setNanos(2);
System.out.println(date.equals(timestamp1));//true
System.out.println(date.equals(timestamp2));//true
System.out.println(timestamp1.equals(date));//false
System.out.println(timestamp1.equals(timestamp2));//false

很明显,正是因为继承关系,导致 equals 方法的对称性和传递性遭到破坏。事实上,Java 源码中 Timestamp 的注释里已经提到了这个问题。

Note: This type is a composite of a java.util.Date and a separate nanoseconds value. Only integral seconds are stored in the java.util.Date component. The fractional seconds – the nanos – are separate. The Timestamp.equals(Object) method never returns true when passed an object that isn’t an instance of java.sql.Timestamp, because the nanos component of a date is unknown. As a result, the Timestamp.equals(Object) method is not symmetric with respect to the java.util.Date.equals(Object) method. Also, the hashCode method uses the underlying java.util.Date implementation and therefore does not include nanos in its computation.
Due to the differences between the Timestamp class and the java.util.Date class mentioned above, it is recommended that code not view Timestamp values generically as an instance of java.util.Date. The inheritance relationship between Timestamp and java.util.Date really denotes implementation inheritance, and not type inheritance.

重点在最后一句。不建议把 Timestamp 实例当做 Date 的实例。它们这种继承关系只是实现层面上的继承,并非类型层面上的继承。

当我们感觉到问题的时候,就应该开始思考如何解决了。

getClass()

首先想到的就是 instanceof 来判断类型时无法识别继承关系,而用 getClass() 方法可以准确获知类型。
我们用这种思路实现一个 equals() 方法。

public boolean equals(Object obj) {
     if(obj == null || obj.getClass() != this.getClass()){
        return false;
     }
     //other conditions
}

这个 equals 能够很刻薄地判断两个对象是否相等,并能够严格遵守 equals 的各项约定。但是它却违背了面向对象思想的一项很重要的原则,里氏替换原则。

里氏替换原则(Liskov Substitution Principle LSP)面向对象设计的基本原则之一。 里氏替换原则中说,任何基类可以出现的地方,子类一定可以出现。 LSP是继承复用的基石,只有当衍生类可以替换掉基类,软件单位的功能不受到影响时,基类才能真正被复用,而衍生类也能够在基类的基础上增加新的行为。

这种 equals 方法显然使得子类替换父类受影响,这种行为和继承的思想理念相违背。

用组合而不是继承

还有另一种方法,便是放弃继承。
再设计模式中,常常被人提及的就是“组合优先于继承”
上面例子中我们可以把 Date 当做 Timestamp 的一个域,就解决了 equals 的问题。

public class Timestamp{
    private int nanos;
    private Date date;
    public Timestamp(long time) {
        date = new Date(time);
        nanos = (int)((time%1000) * 1000000);
    }
    public boolean equals(Object ts) {
        if (ts instanceof Timestamp) {
            if  (nanos == ((Timestamp)ts).nanos && date.equals(((Timestamp)ts).date)) {
                return true;
            } 
        } else {
            return false;
        }
    }
}

总结

我们并没有完美的解决方案调和 Java 的继承特性和 equals 方法约定,它们之间的冲突依然还在。

参考《Effective Java》

简单的依赖注入与Bean工厂

我们在写代码时,经常需要在多个controller中引用多个service,比如下面这样。

public class UserController {
    UserService userService = new UserService();
    UserValidate userValidate = new UserValidate();
}
public class CodeController {
    UserService userService = new UserService();
}

这时候我才意识到依赖注入的好处,每个service只需要生成一个实例,然后注入到各个controller。
所以我想实现下面这样自动注入的效果

public class UserController {
    @DI
    UserService userService;
    @DI
    UserValidate userValidate;
}

我们梳理一下思路,首先我们需要有一个Map来存储已经实例化的Bean,这样在注入到多个地方的时候,不需重复创建新实例。
其次我们需要标注需要注入的位置,可以在需要注入的字段上用一个注解,比如@DI
最后,我们需要获取字段的类型并创建实例,然后注入到这个字段,这并不复杂,用反射可以搞定。
值得注意的是,有可能有多个层次的注入,比如除了service注入到controller外,service也可能互相注入,我们可以用递归解决。

1.首先建立Map

private ConcurrentHashMap<String, Object> map = new ConcurrentHashMap<>();

其中key保存类的名字,value保存类的实例

2.声明注解

@Target(ElementType.FIELD)
@Retention(RetentionPolicy.RUNTIME)
public @interface DI {
}

Target设置的是FIELD,表示只能用在类的变量上。

3.向一个实例中有注解的地方注入

private <T> void inject(T bean) throws IllegalAccessException {
    Class claz = bean.getClass();
    //遍历声明的变量
    for (Field field : claz.getDeclaredFields()) {
        //找到有@DI注解的变量
        if (field.getAnnotation(DI.class) != null) {
            //获取变量的实例(getBean方法后面有提到)
            Object o = getBean(field.getType());
            if (!field.isAccessible()) {
                field.setAccessible(true);
            }
            //利用反射注入
            field.set(bean,o);
        }
    }
}

4.用Map管理众多实例,以及递归注入

public <T> T getBean(Class<T> claz) {
    //查看map中是否有该bean的实例
    Object bean = map.get(claz.getName());
    try {
        //如果没有,创建实例,调用刚刚写的inject方法其,注入所需字段
        if (bean == null) {
            bean = claz.newInstance();
            map.put(claz.getName(), bean);
            inject(bean);
        }
    } catch (Exception e) {
        e.printStackTrace();
    }
    return (T)bean;
}

上面两个方法inject()getBean()相互调用,最终递归完成多层次的注入工作。
当我们需要一个bean的时候只需要用getBean()方法,上面的代码可以整合成一个简单的Bean工厂

public class BeanFactory {
    private ConcurrentHashMap<String, Object> map = new ConcurrentHashMap<>();
    private static BeanFactory instance = new BeanFactory();

    public static BeanFactory getInstance() {
        return instance;
    }

    public <T> T getBean(Class<T> claz) {
        Object bean = map.get(claz.getName());
        try {
            if (bean == null) {
                bean = claz.newInstance();
                map.put(claz.getName(), bean);
                inject(bean);
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
        return (T) bean;
    }

    private <T> void inject(T bean) throws IllegalAccessException {
        Class claz = bean.getClass();
        for (Field field : claz.getDeclaredFields()) {
            if (field.getAnnotation(DI.class) != null) {
                Object o = getBean(field.getType());
                if (!field.isAccessible()) {
                    field.setAccessible(true);
                }
                field.set(bean, o);
            }
        }
    }
}

通过BeanFactory.getInstance().getBean()来获取一个Bean。

最近在用jFinal框架。似乎里面并没有这种依赖注入的功能,所以写这么一个简单的注入。然后我想办法在框架实例化各个controller的时候,使用这个方法。一直没想出来怎么把这段代码嵌入这个框架,最后发现原来不需要这么复杂。

public abstract class BaseController extends Controller {

    protected Log log = Log.getLog(this.getClass());

    public BaseController() {
        for (Field field : this.getClass().getDeclaredFields()) {
            if (field.getAnnotation(DI.class) != null) {
                Object o = BeanFactory.getInstance().getBean(field.getType());
                if (!field.isAccessible()) {
                    field.setAccessible(true);
                }
                try {
                    field.set(this, o);
                } catch (IllegalAccessException e) {
                    log.error(this.getClass().getName() + " inject fail: " + field.getName());
                }
            }
        }
    }
}

定义一个基类集成 jFinal 的 Controller,构造方法中实现注入,然后其他 Controller 继承这个 BaseController 就ok了。

最后说一下,这个依赖注入代码灵活性和可伸缩性并不高,使用条件很单一,只能用于这种无参的构造方法,不过对于我来说足够了。

Keep Coding … Stay Cool …

java.lang.Object

混沌开天地.万物始于Object
来看这条注释@since JDK1.0
从Java这门语言诞生之初,Object类如同基石般在那里。
public class Object
12个方法
1个private,2个protected,9个public
7个native
6个final
下面我大概说一下这些方法,其中private和native以及final修饰的方法我就不说太多,这些关键字修饰的方法都是稳固的方法

public class Object
//这个就不说了
private static native void registerNatives();
static {
    registerNatives();
}
//子类不能重写的获取类型的方法,运行期得到对象类型信息
public final native Class<?> getClass();
//常用,默认返回和对象内存地址有关内容。建议重写,比如Interger类就返回value值;
public native int hashCode();
//常用,默认比较对象是否指向同一位置。建议重写,比如String类比较字符是否相同
public boolean equals(Object obj) {
    return (this == obj);
}
/*这个克隆方法是个大坑,首先The method clone for class Object performs a specific cloning operation. First, if the class of this object does not implement the interface Cloneable, then a CloneNotSupportedException is thrown. 其次对于数组this method performs a "shallow copy" of this object, not a "deep copy" operation. */
protected native Object clone() throws CloneNotSupportedException;
//常用,默认返回Class名+@+十六进制hashCode。建议重写
public String toString() {
    return getClass().getName() + "@" + Integer.toHexString(hashCode());
}
//下面5个方法涉及线程等待和唤醒      
public final native void notify();

public final native void notifyAll();

public final native void wait(long timeout) throws InterruptedException;

public final void wait(long timeout, int nanos) throws InterruptedException {
    if (timeout < 0) {
        throw new IllegalArgumentException("timeout value is negative");
    }
    if (nanos < 0 || nanos > 999999) {
        throw new IllegalArgumentException("nanosecond timeout value out of range");
    }
    if (nanos >= 500000 || (nanos != 0 && timeout == 0)) {
        timeout++;
    }
    wait(timeout);
}

public final void wait() throws InterruptedException {
    wait(0);
}
//垃圾回收时调用的方法,一般不需要关注。
protected void finalize() throws Throwable { }

Java的回调

Java回调

一般意义上的回调是这样的:
回调函数就是一个通过函数指针调用的函数。如果你把函数的指针(地址)作为参数传递给另一个函数,当这个指针被用来调用其所指向的函数时,我们就说这是回调函数。
比如JavaScript里可以把函数当做参数进行传递。

function a(callback){
    //Do something else
    callback();
}
function b(){
    alert('回调');
}
a(b);

函数b显示hello字符串。而调用a函数时将b函数传递进去,由a函数自己在内部合适的时候调用b函数。这就是回调。

但是Java中不能将方法作为参数传递给其他方法(jdk1.7及之前)。在Java中对回调这个概念有自己的实现方式。
就是A类中调用B类中的某个方法do(),而方法do()中反过来调用A类中的方法callBack(),callBack()这个方法就叫回调方法。效果就是最终调用A的方法callBack(),但经历了B类中一些其他流程。回调的前提就是A对象中有一个B的实例

class B{
    public void do(A a){
        //Do something else
        a.callBack();
    }
}
class A{
    private B b = new B();
    public void callBack(){
        System.out.print("回调");
    }
    public void execute(){
        b.do(this);
    }
}

A a = new A();
a.execute("hello");

省略大部分代码。如果使用线程,就是异步回调。

这种模型在Java中最简单的体现就是观察者设计模式。在java.util包中有具体的实现,Observable类和Observer接口。

自己动手实现ArrayList

我们用的最多的就是ArrayList类了。
Java提供ArrayList类作为数据结构中数组的实现,其内部无非是封装了原始的数组。
先不看jdk里的源代码,我们自己试着实现一下吧。
pubic class MyArrayList
首先我们需要一个原始的数组作为成员变量Object[];
然后我们开始定义需要提供的操作。无外乎是增删改查,其中增删改都是传入指定位置下标进行操作,我们也可以额外提供不指定位置的增加操作,默认在尾部增加。
当然我们还要对各种非法操作进行判断并抛出异常,比如数组大小为5,访问第10个位置的操作就为非法操作。
最后我们可以试着实现Iterable接口

public class MyArrayList {

    private Object[] elements;

    /**
     * 默认的构造函数,初始化内部数组,默认大小为0
     */
    public MyArrayList() {
        elements = new Object[0];
    }

    /**
     * 根据下标获取元素
     */
    public E get(int index) {
        return (E) elements[index];
    }

    /**
     * 根据下标设置元素的值
     */
    public void set(int index, E element) {
        elements[index] = element;
    }

    /**
     * 根据下标移除元素,数组需要变小
     */
    public E remove(int index) {
        E element = get(index);
        Object[] oldElements = elements;
        elements = new Object[oldElements.length - 1];
        for (int i = 0; i < index; i++) {
            elements[i] = oldElements[i];
        }
        // 下标之后的所有元素向前移位
        for (int i = index; i < elements.length; i++) {
            elements[i] = oldElements[i + 1];
        }
        return element;
    }

    /**
     * 在队尾插入元素,数组需要扩容
     */
    public void add(E element) {
        Object[] oldElements = elements;
        // 建立新的更大的数组
        elements = new Object[oldElements.length + 1];
        // 拷贝
        for (int i = 0; i < oldElements.length; i++) {
            elements[i] = oldElements[i];
        }
        elements[oldElements.length] = element;
    }

    public void add(int index, E element) {
        Object[] oldElements = elements;
        elements = new Object[oldElements.length + 1];
        for (int i = 0; i < index; i++) {
            elements[i] = oldElements[i];
        }
        elements[index] = element;
        for (int i = index + 1; i <= oldElements.length; i++) {
            elements[i] = oldElements[i - 1];
        }
    }
}

上面的代码写的太粗糙,可以称得上是一个最差实践。这些代码只提供一个思路,没有任何越界判断和校检数据,也没有垃圾回收意识,实际工程中千万不要这样写。

写上面这些代码主要是深化思想上的一些东西,我们的ArrayList目的是封装对一个数组的操作,所有提供的方法间接的操纵数组,当然一些方法需要生成新的数组,将原有数据和新数据复制进去,从而达到对数组扩容的目的,而使用者并不需要关心内部变化。

从设计到编写这些代码,充分体现了Java这门语言的封装特性。我们也明白那些复杂和庞大的东西细化之后内部总是最简单的。

由于我代码写的很不严谨和完善,之后实现Iterable接口的工作已经没有动力做下去了。可以看看我的这篇博客。
Iterable和Iterator

协变数组covariant array

协变数组covariant array

来看两行Java代码

Object[] list = new Integer[10];
list[0] = "A"; 

这两行代码编译不会报错,运行会抛出一个错误java.lang.ArrayStoreException
我们从头来了解这里面的奥妙。
许多语言支持子类,Java也不例外。
举个例子,Cat是Animal的子类,那么Animal声明可以引用Cat对象,比如表达式中用Cat对象Animal,返回值中用Cat替换Animal。

public Animal get(){
    Animal a = new Cat();
    Cat b = new Cat();
    return b;
}

上面这些代码我们都不陌生,这是子类对象和父类对象之间is-a的关系,Cat is an Animal。
但是Cat[]与Animal[]之间的关系是怎样的呢。于是编程语言的设计者要考虑和决定由此衍生的问题,比如数组、继承、泛型等等。
一般出现4种定义

协变 covariant a Cat[] is an Animal[]
逆变 contravariant an Animal[] is a Cat[]
双变 bivariant an Animal[] is a Cat[] and a Cat[] is an Animal[]
不变 invariant an Animal[] is not a Cat[] and a Cat[] is not an Animal[]

拿”协变 covariant”举个例子,如果Cat和Dog都是Animal子类,Cat[]可以作为Animal[]对待,我们可以把Dog放到Animal[]里,但我们知道不能把Dog放到Cat[]里,所以存放有问题。
再说说”逆变 contravariant “,如果Cat和Dog都是Animal子类,Animal[]可以作为Cat[]对待,我们从Cat[]中期待只能取到Cat,但Animal[]可能存有Dog被我们取到。

由此可见,如果我们为了保证对数组的读和写都不会有类型错误,最安全的做法是选择”不变 invariant”
即规定这样的声明是错误的 Animal[] list = new Cat[];
但是Java中并没有这样做,而是选择了”协变 covariant “。为什么呢。
这是有历史原因,Java 1.2版本中才引入了泛型,而最初为了让ArrayList等一系列类可以正常工作,只能这样选择。
ArrayList内部保存一个Object[],封装了一系列的对数组的操作。Object是所有类型的父类,如果不是协变的,我们无法存取它的子类,比如我们创建一个ArrayList却不能存放String类型,这将是多大的不便。
当然为了正确处理异常,定义了java.lang.ArrayStoreException

不过,协变引起的问题不仅仅是这一点。
如果你看过ArrayList的源码,会在其中一个构造方法中看到这样一行注释

public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
}

仔细想想就能明白其中原因。我就不多说了。
在官网上根据编号查看这个bug的详细信息时,有个很有意思的回复,[bug是2005-04-25提交的]
http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652

10 years later, I still believe this is “just” a bug that should be fixed.

2015-06-26

参考https://en.wikipedia.org/wiki/Covariance_and_contravariance_(computer_science)

java.lang.Iterable 和 java.util.Iterator 和 java.util.Enumeration

这三个接口都为泛型接口,定义简单
先来看一看Iterable接口,@since 1.5。
而Iterable存在的目的就是使实现它的类可以使用foreach循环

public interface Iterable {
    Iterator iterator();
}

里面只有一个方法,就是返回一个Iterator,用于迭代。
我们马上来看一看Iterator接口

public interface Iterator {
    boolean hasNext();  
    E next();
    void remove();
}

也很简单,三个方法,一个判断是否有后续元素,一个获取后续元素,一个删除当前元素。
这里要注意remove方法,因为是删除当前元素,所以调用remove方法前,至少要调用一次next方法。
一般实现时通过一个标识变量,在next方法中修改为可remove状态,在remove方法中先判断标识,然后remove,最后变量改为不可remove状态。
我们来写一些非常简单的代码试一试。

public class MyList implements Iterable {

    // 定义一个数组
    private String[] list = { "A", "B", "C" };

    // 实现Iterable接口
    public Iterator iterator() {
        return new MyIterator();
    }

    // 实现Iterator接口
    public class MyIterator implements Iterator {

        private int i = 0;

        public boolean hasNext() {
            return i < 3;
        }

        public String next() {
            return list[i++];
        }

        public void remove() {
            // TODO 我比较懒,这里和我要测的foreach关系不大,就不写了。
        }
    }

    public static void main(String args[]) {
        MyList list = new MyList();
        for (String var : list) {
            System.out.println(var);
        }
    }
}

输出结果
A
B
C

Iterable定义在1.5版本,Itertor定义在1.2版本。
而定义在最初的1.0版本用于枚举和迭代的,是Enumeration接口。
Itertor是作为Enumeration的替代,为了向下兼容,Enumeration并没有标注弃用

public interface Enumeration {
    boolean hasMoreElements();
    E nextElement();
}

Itertor相比Enumeration有两点改进
1.增加了remove方法
2.简化了方法名。