Arraylist

最近觉得前一段时间好像又浮躁了，什么都看了，又好像什么都没看，这两天想静下来看看jdk6的源代码，集合类可以说是平时用的最频繁的类库了，于是从util包开始。

 

于是从Collecition List Set Map Queue这些顶级接口看起。

接着看各Abstract*类，比如

AbstractCollection AbstractList AbstractMap AbstractQueue AbstractSequentailList等等。

从这一级开始，已经能看得出设计者的一些是实现思路了。但是有的地方还是让我感觉有些不是很理解，比如AbstractCollection里面size方法和迭代器实现是抽象的，等待子类自己去实现，而add方法又抛出了一个UnsupportedOperationException，这样是否多此一举了，如果不确定子类的实现方式，就像前面两者一样留给子类去实现不就得了。

当然今天的主题还是ArrayList了。

它里面最重要的一个思想或者说是它的实现核心，就是底层定义的那个数组了。

private transient Object[] elementData;---底层数组

private int size;--ArrayList的size

初始化的时候如果不指定列表的大小，默认是10。不过有一点，ArrayList里面有一个size字段，但是初始化之后size仍然是0。这一点在刚开始看的时候被晃了一下。当原始数组空间不够的时候，数组会扩容，这就是为什么说如果使用ArrayList最好能对放入列表中的数据的数量有个预先的评估，这样就不用一次次的扩容了，每次扩容原则上是扩大数组空间至原来的1.5倍（一次性指定较大空间除外）

好了，一旦底层的结构弄清楚了，之后的各种方法的实现思路基本就可以浮出水面了，基于数据的插入，删除，替换等等，基本上是插入删除时间花费是O(n)，而根据数组位置查找替换等是固定时间，这就是为什么一直说ArrayList尽量做查找，尽量少做插入删除操作的原因。

还有两点需要额外的说一下。

1.一个是在各项操作之前，既然是数组，数组越界的问题就不可回避，这也是java强于c c++的地方，一旦越界抛出异常而不是默默的将内存数据搞错。这里就涉及到ArrayList检查底层数据的问题，个人觉得如果能用到aop的思想在这里也许更好，因为基本上都是在相关方法的开头进行这种安全性检查，当然作为底层的api，引入太多的东西未必是件好事，只是突然想到而已，那么检查的依据是什么，是size字段，而不是elementData的length。也就是说初始化后，elementData.length等于10，但是size仍然是0，如果在这个时候add了一个数据进去，那么elementData.length仍然是10，而size变成了1，这个时候如果执行了set(2,object)方法，那么会抛出数组原界的异常，实际上elementData指定的数组并没有越界，只是越了size的界而已。

2.modCount字段

相信很多人都遇到过ConcurrentModificationException，这就是因为我们边改集合类的底层数据边进行一些数据操作导致的，而如果不使用线程安全的类库（例如CopyOnWriteArrayList）或者明确的将集合类变成线程安全的（例如Collections.synchronizedList(list)），java本身会尽快的让用户知道底层数据已经修改的这种情况，api里面叫做“快速失败”，这是为了保证不再后面的使用中引入一些不确定的数据情况，但是api也提到了，只是尽最大努力的保证，无法做到严格的保证，如果想多线程的操作集合类，那么，用上面提到的两种方式吧。

而modCount就是用来记录elementData数组的结构到底被修改了多少次，如果在需要检查的方法中，那么在开始会检查一遍modCount是否和expectedModCount一致，例如在利用迭代器进行list迭代的时候，中间remove了一个元素，那么这个时候modCount就会加1，等到下次再检查modCount是否和expectedModCount一致时发现不一致了，就抛出了ConcurrentModificationException。但是有一个地方，迭代器本身进行remove操作的时候就没有这个问题，为什么

因为它重新将modCount赋给了expectedModCount，以保证不会出问题。

 

好了，今天先写到这。