ArrayList--源码分析之理论结合实践

引子

 

最近在从事一些基于大数据做 “应用级产品”的架构设计和开发工作，比如 实时流量监控、实时热力图、注意力热图等。发现一些基础类的正确使用，对性能提升还是挺大的。记录下来，时刻提醒自己一定要开发中的注意细节。

 

“万丈高楼平地起”，在软件开发中如果不注重细节，会带来很大的性能问题，尤其是在大数据相关产品的开发中。本系列中会结合开发中遇到的实际情况，结合源码进行分析。首先来看看我们用得很多的ArrayList。

 

一个典型的场景：批量向hbase写入数据（数据量大的情况下尽量避免一条一条的插入）。一般的写法为：

//在大数据场景下，该方法会被循环调用

 

public void insert(List<DataObjet> datas){
…………省略代码…….
List<put> puts = new ArrayList<put>();
Put put = null;
For(DataObjet data; datas){//一般为for循环一个list的对象，大小为几十到几百不等
Put = new Put(data.getId().getBytes()); //设置rowkey
Put.add(xx,xx,xx); //添加每个column
…………省略代码…….
puts.add(put); //放入list
}
table.setAutoFlush(false);//table为habse表，关闭批量提交
…………省略代码…….
table.put(puts);
table.flushCommits();
}

 

 

咋一看没啥问题，但是在插入十万，百万，乃至亿级别的数据时，其实还是有优化空间的。

想必大家已经看出来，问题出现在这行List<put> puts = new ArrayList<put>()，没有指定数据大小。

 

ArrayList的三个构造方法

 

一起来重新认识下ArrayList（jdk1.8）：简单的说 是一个动态数组，其容量可可以自动增长的数组。

先看下三个构造方法：

 

1、默认构造方法：

 

/**
     * 初始化一个空数组，默认容量是10
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
   // 空数组
   private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
   //默认容量大小
   private static final int DEFAULT_CAPACITY = 10;

 

 

 

2、指定容量构造方法：

 

    /**
     * 指定容量大小
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                    initialCapacity);
        }
    }
 

 3、通过Collection创建：

 

public ArrayList(Collection<? extends E> c) {
    //先转换为数组
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
}

 

入参只要是实现了Collection接口的子孙类型（set、list），都可以作为参数。

我们经常用的是第一个无参默认构造方法。

 

再来看添加方法：

 

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 确保数组容量
        elementData[size++] = e;
        return true;
}
 
/**
* minCapacity 需要的最小容量
*/
private void ensureCapacityInternal(int minCapacity) {
//这个好理解，如果不够10，minCapacity改为10
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //根据情况改变数组长度，可变数组的核心方法
        ensureExplicitCapacity(minCapacity);
}
 
private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
 
        // 如果需要的最小容量超出数据长度，需要对数组进行扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
 
private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
// 扩容1.5倍、或者1.5倍减1。这里采用的位运算比老版本性能好些
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;//好理解
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 最终调用System.arraycopy方法，把老数组中的数据copy到新数组
        elementData = Arrays.copyOf(elementData, newCapacity);
}

 

 

 

Grow()方法

第一步：先按照老容量进行扩容，这个地方相对jdk1.6有改进，jdk1.6是按照1.5倍+1进行扩容（int newCapacity = (oldCapacity * 3)/2 + 1）。有没有注意到这个细节，老版本是用的除法，jdk1.8用的是位运算，性能肯定好些。看来大神们都很重视每一个细节。

 

第二步：判断扩容后的容量是否够用，并判断是否超过最大容量（一般会出现这种情况吧）。

 

第三步：调用System.arraycopy方法，把老数组中的数据copy到扩容后的新数组。

 

可以看到默认构造函数容量是10，在大量数据需要插入的情况下（比如批量插入hbase，假如一次批量是500），会进行多次自动扩容，以及多次数组copy。

平时数据量小，体现不出来。在大数据开发中，一次动则插入千万条记录。整体的性能消耗是非常恐怖的。

所以在能明确确认数组大小的情况下，请使用确定的容量进行ArrayList的创建，即第二构造函数。开篇场景中的代码可以改为：

 

public void insert(List<DataObjet> datas){
…………省略代码…….
List<put> puts = new ArrayList<put>(datas.size());//非空判断没写出来
…………省略代码…….
}

 

 

做个简单测试：

        List list = null;
        long s = System.currentTimeMillis();
        for(int j=0;j<100000;j++){
            list = new ArrayList<>();
            //list = new ArrayList<>(500);
            for (int i=0;i<500;i++){
                list.add(1);
            }
        }
        long e = System.currentTimeMillis();
        System.out.println(e-s);

 

直接运行结果大约是500+ms, 注释代码交互后运行结果大约是200+ms。可以看到提升还是挺多的。

 

说了这么多，就只改动了一个地方。其实就想表达，一定要注意细节。在平常开发，直接使用默认的构造函数，也许差别不大。比如你的容量基本都不会超过10，那就直接用默认构造函数也是最高效的做法。

 

subList()方法

 

ArrayList是实现了Serializable接口的，也就是说可以进行序列化和反序列化，可以在rpc框架（）中进行传输。我们经常用这个方法对ArrayList进行截取，但这个截取后的List是不能在某些rpc框架中进行传输的（如:淘宝dubbo，京东jsf）,主要原因就是这个List没有实现Serializable接口。看代码：

public List<E> subList(int fromIndex, int toIndex) {
        subListRangeCheck(fromIndex, toIndex, size); //是否越界判断
        return new SubList(this, 0, fromIndex, toIndex);
    }

 

       

其实是新建了一个Sublist，是ArrayList的私有类：

private class SubList extends AbstractList<E> implements RandomAccess

可以返现该类是没有实现Serializable接口接口的。

 

另外 也可以使用ArrayList的第三个构造方法，把Sublist转换成一个ArrayList。这样就可以在rpc框架中传输了。

      List list = new ArrayList<>();
              list.add(1);
              list.add(2);
              list.add(3);
              List slist = list.subList(0,1);
              List newList = new ArrayList<>(slist);

 

 

 

迭代子模式

 

在ArrayList里我们还可以学习下，23种常用设计模式中的迭代子模式(关于迭代子模式可以看下这篇文章：http://www.cnblogs.com/java-my-life/archive/2012/05/22/2511506.html) ,

ArrayList的iterator()方法实际上会生成一个ListItr类的实例对象。ListItr类继承至Itr类，Itr是AbstractList类的内部私有类，可以看出该类是AbstractList类的“内禀迭代子”。

只要是继承了AbstractList抽象类，都可以获得这个迭代子。

 

另外jdk1.8里，ArrayList新增了一个迭代子：ArrayListSpliterator，该类继承自Spliterator。后面抽时间在单独分析下Spliterator的实现类。

 

总结下：

1、大数据的场景下，说明了使用确定容量的ArrayList的重要性。

2、ArrayList是能序列化的，但是的sublist()生成的list却不能序列化。

3、迭代子模式在ArrayList中的使用。

 

就啰嗦这么多，ArrayList其他方法这里不再细讲。很多博客已经将的比较详细，感兴趣的同学可以把源码打开看看，还可以看下这篇文章（jdk1.8以前的版本）：http://www.cnblogs.com/ITtangtang/p/3948555.html