这一篇开始说arraylist
参考代码为jdk1.6_45 jdk1.7_80 jdk1.8_111中的源码，对比阅读，发现修改的问题以及改进点。
public class arraylist<e> extends abstractlist<e> implements list<e>, randomaccess, cloneable, java.io.serializable
一、基本性质
1、底层使用原生数组实现，实现randomaccess接口，可以随机访问，随机访问指的是下标索引操作index(i)的时间复杂度是o(1)。
size、isempty、get、set、iterator和listiterator操作在o(1)内完成，add(e)操作平均在o(1)内完成，即添加n个元素需要o(n)时间（这个是collection.add，是在尾部添加注意区分下list.add(index, e)）。其他操作基本都是o(n)内完成。arraylist与linkedlist实现相比，o(n)的各个方法的时间复杂度的常数因子更小。
2、因为底层数组 elementdata 的容量是不能改变的，所以容量不够时，需要把 elementdata 换成一个更大的数组，这个过程叫作扩容。实际的元素的数量size，总是不会超过底层数组的容量 elementdata.length，因为扩容需要申请更大的内存，并且需要原来数组的进行一次复制，所以扩容是个耗时的操作。在添加大量元素之前，使用者最好是预估一个大致的数量，手动调用ensurecapacity进行一次扩容操作，避免一个个添加导致频繁扩容影响性能。
3、arraylist是未同步的，多线程并发读写时需要外部同步，如果不外部同步，那么可以使用collections.synchronizedlist方法对arraylist的实例进行一次封装，或者使用vector。
4、对存储的元素无限制，允许null元素。
5、arraylist的iterator和listiterator方法返回的迭代器是快速失败的，也就是如果在创建迭代器之后的任何时间被结构性修改，除了通过迭代器自己的remove或add方法之外，迭代器将直接抛出一个concurrentmodificationexception，从而达到快速失败fail-fast的目的，尽量避免不确定的行为。
arraylist的迭代器的快速失败行为不能被严格保证，并发修改时它会尽量但不100%保证抛出concurrentmodificationexception。因此，依赖于此异常的代码的正确性是没有保障的，迭代器的快速失败行为应该仅用于检测bug。
6、实现clone接口，可以调用其clone方法（虽然clone()是object中的方法，但是它是protected，使用子类的clone()必须在子类中覆盖此方法）。clone方法复制一个arraylist，底层数组elementdata不共享，但是实际的元素还是共享的。
不过clone是arraylist中覆盖的，不属于list中的方法，因此常见的声明形式
list<string> strs = new arraylist<>()；
声明出来的变量不能直接使用clone方法，本身也用得极少。
7、实现serializable接口，可以被序列化。arraylist"实现"了自定义序列化方法，这么做主要是为了节省空间 。对于占用空间的大头——元素list，仅仅序列化实际size大小的元素，同时不序列化对于新对象无用属性的——来自父类abstractlist的modcount。arraylist的实际size不会超过底层数组的length，大多数情况下比底层数组length小，使用默认序列化的话，会直接序列化整个底层数组，序列化后字节流会变大，浪费空间。
二、构造方法
1、默认构造方法，arraylist()
关于默认构造方法，你可能在别的地方看见过这种话：无参构造方法（默认构造方法）构造的arraylist的底层数组elementdata大小（容量）默认为10。这里告诉你，这不一定是对的。这句话在1.6版本中是对的（更之前的版本我没看），从1.7开始这句话就有问题了。下面我贴出了三个版本的代码：
jdk1.6的，初始化成10个容量。
|
1
2
3
4
5
|
// jdk1.6的 /** constructs an empty list with an initial capacity of ten. */ public arraylist() { this(10); } |
jdk1.7的，相对1.6版本，引入了一个新的常量empty_elementdata，它是一个空数组，因此容量为0。
|
1
2
3
4
5
6
7
8
9
10
11
|
// jdk1.7的 /** shared empty array instance used for empty instances. */private static final object[] empty_elementdata = {}; ... /** constructs an empty list with an initial capacity of ten. */public arraylist() { super(); this.elementdata = empty_elementdata; } |
jdk1.8的，相对1.7版本，又引入了一个新的常量defaultcapacity_empty_elementdata ，它也是一个空数组，因此容量也为0。至于两个空数组有什么区别，看下面一点说的。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
/** shared empty array instance used for empty instances. */private static final object[] empty_elementdata = {}; /** * shared empty array instance used for default sized empty instances. we * distinguish this from empty_elementdata to know how much to inflate when * first element is added. */private static final object[] defaultcapacity_empty_elementdata = {}; ... /** constructs an empty list with an initial capacity of ten. */public arraylist() { this.elementdata = defaultcapacity_empty_elementdata; } |
对比下可以看出：jdk1.6的无参构造方法（默认构造方法）构造的arraylist的底层数组elementdata大小（容量）默认为10；从1.7开始，无参构造方法构造的arraylist的底层数组elementdata大小默认为0。
java集合类在jdk1.7版本基本上都有一种改动：懒初始化。懒初始化指的是默认构造方法构造的集合类，占据尽可能少的内存空间（对于arraylist来说，使用空数组来占据尽量少的空间，不使用null是为了避免null判断），在第一次进行包含有添加语义的操作时，才进行真正的初始化工作。
1.7开始的arraylist，默认构造方法构造的实例，底层数组是空数组，容量为0，在进行第一次add/addall等操作时才会真正给底层数组赋非empty的值。如果add/addall添加的元素小于10，则把elementdata数组扩容为10个元素大小，否则使用刚好合适的大小（例如，第一次addall添加6个，那么扩容为10个，第一次添加大于10个的，比如24个，扩容为24个，刚好合适）；1.8版本，默认构造的实例这个行为没有改变，只是用的数组名字变了。
顺便吐槽下：jdk这个类维护者，你能不能改下默认构造方法上的注释啊，默认构造方法的行为都改变了，你注释还是用之前的！！！
2、带初始容量的构造方法，public arraylist(int initialcapacity)
|
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
|
// 1.6 public arraylist(int initialcapacity) { super(); if (initialcapacity < 0) throw new illegalargumentexception("illegal capacity: "+ initialcapacity); this.elementdata = new object[initialcapacity]; } // 1.7 跟1.6的一样 public arraylist(int initialcapacity) { super(); if (initialcapacity < 0) throw new illegalargumentexception("illegal capacity: "+ initialcapacity); this.elementdata = new object[initialcapacity]; } // 1.8 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); } } |
678三个版本的这个构造方法的实际行为基本一致：如果initialcapacity >= 0，把底层数组elementdata赋值为一个大小为initialcapacity的数组，数组的所有元素都是默认值null。1.8稍微进行了一点优化，也是赋值为空数组，但是重用了常量对象。
下面写个简单的例子看一个细微的区别。
|
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
|
// jdk1.6，两个构造的区别很明显 public class testarraylist { public static void main(string[] args) { list<string> la = new arraylist<string>(0); // la.elementdata = new object[0], la.elementdata.length = 0 la.add("111"); // la.elementdate.length = 1，这里一次性扩容了1个，后续再按照通用扩容策略执行扩容操作 list<string> lb = new arraylist<string>(); // lb.elementdata = new object[10], lb.elementdata.length = 10 lb.add("111"); // lb.elementdate.length = 10，这里没有进行扩容，后续再按照通用扩容策略执行扩容操作 } } // jdk1.7，两个构造在第一次进行添加时才看得出区别 public class testarraylist { public static void main(string[] args) { list<string> la = new arraylist<>(0); // la.elementdata = new object[0], la.elementdata.length = 0 la.add("111"); // la.elementdate.length = 1，这里一次性扩容了1个，后续再按照通用扩容策略执行扩容操作 list<string> lb = new arraylist<>(); // lb.elementdata = empty_elementdata, lb.elementdata.length = 0 lb.add("111"); // lb.elementdate.length = 10，这里一次性扩容了10个，后续再按照通用扩容策略执行扩容操作 } } // jdk1.8，同1.7 public class testarraylist { public static void main(string[] args) { list<string> la = new arraylist<>(0); // la.elementdata = empty_elementdata, la.elementdata.length = 0 la.add("111"); // la.elementdate.length = 1，这里一次性扩容了1个，后续再按照通用扩容策略执行扩容操作 list<string> lb = new arraylist<>(); // lb.elementdata = defaultcapacity_empty_elementdata, lb.elementdata.length = 0 lb.add("111"); // lb.elementdate.length = 10，这里一次性扩容了10个，后续再按照通用扩容策略执行扩容操作 } } |
jdk1.6中new arraylist<?>()跟new arraylist<?>(10)的行为是一模一样的，所以跟new arraylist<?>(0)有很明显区别，这个好理解 。从1.7版本开始，new arraylist<>()和new arraylist<>(0)，虽然创建后底层内容和容量都一样，但是实际的行为有些细小的差别，那就是这两个在第一次自动扩容时策略不一样。不过这一点影响比较小，基本不影响使用。
1.8中使用两个空数组，正如注释所说的，是在优化（避免创建无用的空数组）的同时，保留其扩容初始策略区别。只用一个空数组就不能再优化的同时，继续保持这个小区别了。
3、collection拷贝构造方法，public arraylist(collection<? extends e> c)
678三个版本的关系和第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
|
// jdk 1.6 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); } // jdk 1.7 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); } // jdk 1.8 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; } } |
关于中间这行注释，可以看下这篇
此构造方法会有和array.copyof/system.arraycopy一样的问题，那就是它只是新建一个elementdata数组，数组的内容对应相等，但是不拷贝实际的元素，实际的元素占据的内存空间还是共享的。
三、确保容量方法（扩容方法）：ensurecapacity/ensurecapacityinternal
提前声明下：这两个方法只是确保容量，不一定会扩容，但是为了好理解，下面的文字中所说的"扩容"指的就是这两个方法。
因为原生的数组的容量不能改变，要改变数组的容量，只能是新建一个数组，并把原来数组的内容复制到新数组对应位置上去。数组拷贝使用的是arrays.copyof，底层用的是system.arraycopy，比循环赋值效率高。扩容示意图如下。
扩容方法四个位置用到：两个add方法，两个addall方法，一个反序列化方法，还有就是手动扩容方法ensurecapacity（称之为手动，是因为此方法是public的，可以外部手动调用）。在1.6版本是只有这个手动的方法，内部自动操作也是调用这个方法，1.7开始进行了区分，并且进一步改进了扩容操作。
下面的是jdk1.8的代码，1.7的和1.8的基本相同，唯一的一点区别就是1.8用两个空数组，导致这里的空数组的名字不一样，两个版本的代码可以看作是一样的。
|
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
41
42
43
44
45
46
47
48
49
50
51
52
|
// 手动扩容方法（可以外部调用，不过大多数情况都是list<?> = new arraylist<>()，这样是调用不到这个方法的） // 这个方法只是简单区别下list是不是通过 new arraylist() 来创建的，这一点前面说了 // 如果是，则尝试最小扩容10个，不是则尝试扩容指定个，具体也是通过内部扩容方法完成容量确保 public void ensurecapacity(int mincapacity) { int minexpand = (elementdata != defaultcapacity_empty_elementdata) // any size if not default element table ? 0 // larger than default for default empty table. it's already // supposed to be at default size. : default_capacity; if (mincapacity > minexpand) { ensureexplicitcapacity(mincapacity); } } // 下面是内部扩容相关的几个方法的代码 private void ensurecapacityinternal(int mincapacity) { if (elementdata == defaultcapacity_empty_elementdata) { mincapacity = math.max(default_capacity, mincapacity); } ensureexplicitcapacity(mincapacity); } private void ensureexplicitcapacity(int mincapacity) { modcount++; // overflow-conscious code 考虑int型溢出 if (mincapacity - elementdata.length > 0) grow(mincapacity); } private void grow(int mincapacity) { // overflow-conscious code 考虑int型溢出 int oldcapacity = elementdata.length; int newcapacity = oldcapacity + (oldcapacity >> 1); if (newcapacity - mincapacity < 0) newcapacity = mincapacity; if (newcapacity - max_array_size > 0) newcapacity = hugecapacity(mincapacity); // mincapacity is usually close to size, so this is a win: elementdata = arrays.copyof(elementdata, newcapacity); } private static int hugecapacity(int mincapacity) { if (mincapacity < 0) // overflow int型溢出，直接报错 throw new outofmemoryerror(); return (mincapacity > max_array_size) ? integer.max_value : max_array_size; } |
下面这是1.6的相关代码，可以对比看下：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
public void ensurecapacity(int mincapacity) { modcount++; int oldcapacity = elementdata.length; if (mincapacity > oldcapacity) { object olddata[] = elementdata; int newcapacity = (oldcapacity * 3)/2 + 1; if (newcapacity < mincapacity) newcapacity = mincapacity; // mincapacity is usually close to size, so this is a win: elementdata = arrays.copyof(elementdata, newcapacity); } } |
区别就是：1.6的方法只是简单进行了逻辑上的操作，没有过多考虑int型溢出的问题，从1.7（上面贴的是1.8的）开始对这个进行了完善。
先仔细看看1.6的问题，整体来说都是int型溢出的问题。
1、没考虑入参mincapacity可能因为int溢出变为负数。这个方法可以外部手动调用，手动扩容传入负数这个肯定是应该拦截掉的。但是自动扩容会因为int溢出产生负数，碰到这种情况时应该特殊处理，而不是什么都不做，等着后面抛出一个arrayindexoutofboundsexception。
2、就是这句代码不太好，过早溢出
int newcapacity = (oldcapacity * 3)/2 + 1;
虽然上面这行代码和1.7开始的oldcapacity + (oldcapacity >> 1) 看上去一样，都是相当于1.5倍，但实际上是有区别的。两个区别，第一个小区别是jdk1.6的那种乘除运算的数学结果比后面一个大1比如oldcapacity=10，1.6的算法得到16，1.7开始的算法得到15，这个影响不大；第二个区别就是两者在数字比较大是运算结果不一样，比如oldcapacity=10^9，这个数和integer.max_value位数一样，用1.6的算法得到的会是错误的-647483647，用1.7的则是正确的1500000000，这时候明明可以1.5倍扩容，但是jdk1.6却用的是按需扩容。
在计算机里面对于int型的两个不同的数a和b，有
a-b>0 不等价于 a>b
因为，a-b>0会被int溢出影响，a>b不会受int溢出影响。无符号的int型中a-b>0是一定成立的；有符号的int型，负数可以看成是正数的溢出，假设a = integer.max_value + 10，b = integer.max_value - 10，很明显a是负数，b是正数，运行一遍a>b得到false，再运行一遍a-b得到的是20，a-b>0得到true。因此对于int型，a>b和a-b>0在if判断中有不同的功能，前者是纯粹比较大小，正数一定大于负数；后者可以判断溢出，正数不一定大于负数。
所以1.7版本对上面两个问题做了修改。
1、从1.7开始将内部扩容和外部可以调用的扩容方法分开了，通过源码（上面贴的是1.8的代码，可以看出是一样的）可以看出：外部调用的手动扩容方法ensurecapacity要多一个判断条件 mincapacity > minexpand，这个判断条件拦截掉负数的mincapacity，这样调用内部扩容ensurecapacityinternal方法时，mincapacity一定是正数；内部扩容方法直接就用mincapacity - elementdata.length > 0判断，此条件可以检测出int型溢出，碰到溢出最后会抛出一个oom错误。jdk1.7用oom，这比jdk1.6用arrayindexoutofboundsexception更好，因为此时数组大小超出了虚拟机对数组的限制，虚拟机无法处理这种情况了，抛出一个error是合理的。
2、使用这行代码
newcapacity = oldcapacity + (oldcapacity >> 1);
这行不仅仅是是用位运算加快执行速度，上面说了，这种做法才是对的，是真正的1.5倍。不仅仅因为那一个大小的差别，更重要的是避免过早出现int溢出的情况，保证了内部自动扩容会尽量按规定的策略执行。同时整个扩容处理流程中多增加了几处if判断，对各种情况处理更加完善。
还有一个问题就是，max_array_size = integer.max_value - 8。这个是1.7开始才有的，注释说这个是因为在一些虚拟机的数组实现中，会有array header这个保留部分，所以数组最大长度并不是实际的integer.max_value。这个在1.8自带的hotspot上测试（环境win7 64位，java hotspot(tm) 64-bit server vm (build 25.111-b14, mixed mode)），准确值应该是integer.max_value -
2.比这个值大就会出现outofmemoryerror: requested array size exceeds vm limit。此error和hugecapacity中抛出的oom基本上差不多，这两个跟一般的oom还是有区别的。抛出这个异常时，一般是程序有问题，此时虚拟机看看数组大小，就知道了它是不能完成这样的内存分配的，跟剩余的内存空间大小没关系。
测试下实际max_array_size（都是64bit的）
jdk1.8 integer,max_value - 2，超过这个值（实际上也只有两个数可选，integer.max_value和integer.max_value - 1）就抛出outofmemoryerror: requested array size exceeds vm limit
jdk1.7 integer.max_value - 2
jdk1.6 integer.max_value，使用这个值能够成功创建数组（使用boolean数组）
在带初始容量的构造方法 public arraylist(int initialcapacity) 中，并没有判断初始容量是否大于max_array_size。个人觉得还是判断下好，不判断可能在扩容时会有点问题。下面给一组变量值大家试下，看下是不是真有问题。
初始数组长度 elementdata.length = integer.max_value - 5 = 2147483642；
还要继续添加的长度 expand = integer.max_value - 2 = 2147483645；
最小容量 mincapacity = expand + elementdata.length = -9；
ensureexplicitcapacity方法中 mincapacity - elementdata.length = 2147483645 > 0，会继续执行grow方法；
grow方法中 newcapacity = elementdata.length + (elementdata.length >> 1) = -1073741833；
grow方法中的第一个if，newcapacity - mincapacity = -1073741824 < 0，执行第一个if中的 newcapacity = mincapacity，newcapacity = -9；
grow方法中的第二个if，newcapacity - max_array_size = -2147483648 < 0，不执行第二个if中的语句；
执行最后的arrays.copyof，因为newcapacity = -9 < 0，会抛出异常negativearraysizeexception。
grow方法中第二个if，如果newcapacity是负数，只有是-9到-1这几个负数，才会不执行hugecapacity方法而是直接执行arrays.copyof抛出异常。如果构造方法中拦截判断下是否大于max_array_size，一开始的数组长度就限制在integer.max_value - 8，应该是无法通过一个正数的expand，使得mincapacity在[-9,-1]内。严格证明暂时给不出，实际运行中由于内存限制无法演示。
四、常用方法
arraylist提供的public方法的实现，基本上都有利用数组随机访问特性，以及system.arraycopy/arrays.copyof数组快速复制，进行加速。
1、来自list接口中的方法
e get(int index)：这个没啥说的。
e set(int index, e element)：这个没啥说的。
void add(int index, e element)：这个内部会进行数组复制，复制原来index开始的数组到 index+1 开始的位置，因此在arraylist中间add元素是比较慢的，平均下来是o(n)的时间。没必要时尽量不使用这个方法，而是直接使用 add(e) 添加到尾部，add(e) 平均下来只会耗费o(1)的时间，效率高很多。
简单画了个图，可以看下。
e remove(int index)：基本同上，会进行数组复制，这是数组实现的list避免不了的问题。注意下实现中的elementdata[--size] = null; // clear to let gc do its work，这句让list不引用元素，让元素可以被回收（当然，还得其他地方都不引用元素），避免集合类“假删除”造成内存泄漏。
remove示意图如下。
int indexof(object o)：此方法和下面的lastindexof方法会进行null判断，o == null则在遍历时使用 == 进行比较，o != null则在遍历时使用equals方法进行比较，所以使用时请注意下元素的equals方法。
int lastindexof(object o)：同上。
boolean addall(int index, collection<? extends e> c)：elementdata数组中插入c.toarray()数组，使用的system.arraycopy复制进去。
listiterator<e> listiterator(int index)：返回一个基于数组操作的listiterator，listiterator是iterator的增强实现。传统的iterator只能往一个方向迭代，并且只能在迭代中进行remove这一个写操作；listiterator能够双向迭代，支持迭代时获取下标，并且能够在迭代中进行add和set操作。不过list这一系的迭代器弄得比较乱，抽象类abstractlist中有一套，几个主要实现类arraylist、linkedlist、vector、copyonwritearraylist中又各自有一套。父类中那一套是通用的，各个具体的类中的那一套，一般都是优化过的，效率会提升一些，所以不用管父类的迭代器了，那些虽然通用，但是效率不高，差不多过时了。jdk1.6的arraylist是直接使用父类abstract中的通用的那一套，效率稍微低些。
listiterator<e> listiterator()：就是new listitr(0);
list<e> sublist(int fromindex, int toindex)：返回此list的某一段的视图，具体返回类型是java.util.arraylist$sublist这个内部类，arraylist.sublist是复用原arraylist的elementdata数组，操作原数组也会对sublist有影响。jdk1.6中是用父类的这个方法，返回一个通用的java.util.subllist，1.7开始使用的是java.util.arraylist.sublist，直接操作arraylist的数组，效率更高。虽然重写了一份功能几乎一样的代码，但是作为一个基层的类，效率还是很重要的。
2、来自collection(iteratable)接口的方法
iterator<e> iterator()：返回一个内部的实现类，从jdk1.7开始该实现类使用数组的特性优化实现iterator的几个方法，1.6返回的是父类abstractlist中定义的一个list接口通用的迭代器。
int size()：直接返回属性size
boolean isempty()：size == 0
boolean contains(object o)：使用的是indexof
boolean add(e e)：尾部添加，只用考虑是否扩容，不扩容时的插入不用考虑数组元素移动的问题，平均下来是o(1)的时间。这里可以简单证明下：初始a个容量，每次扩容后是1.5倍，设为c；那么扩容次数为x = o(logc(n))（c为底数）；扩容移动的元素个数，等比数列求和，为o(c^x) = o(n)；不扩容时每个元素为o(1)，不扩容总共消耗小于o(n)；总共耗时o(n)，平均耗时o(1)。
boolean remove(object o)：移除所有“相等”的元素，此处相等和indexof中的一样，null使用 ==，非null使用equals。移除时使用的fastremove(int index)跟remove(int index)行为一样，因为是内部使用，所以不用检查边界，而且返回void。
boolean containsall(collection<?> c)：继承使用abstractcollection中的方法，使用for-each挨个检验contains。对于iterable的实现类，for-each是用iterator实现的。在arraylist这种基于数组的实现中，传统for循环比iterator要快，iterator比直接数组下标取值要多不少步骤，在n次简单循环这种狂飙cpu的操作中，每个步骤都是花时间的，所以iterator（for-each循环）要慢。不够估计是此方法用的不多，在arraylist中没有用数组的特性进一步优化此方法。1.7以后arraylist中其余几个all方法都重写了，就这个all方法还是用的父类的。
boolean addall(collection<? extends e> c)：c.toarray，数组尾部追加数组，先确保容量，然后复制要add的数组就行。
boolean removeall(collection<?> c)：可以理解为差集操作，这个和下面的retainall一起讲，都是利用batchremove方法，只是判断是否删除一个元素时行为相反。1.8在调用batchremove进行了null判断，c == null会提前抛出npe，1.6的是重用父类abstractcollection中的实现。
|
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
|
// 此方法就是一个简单的数组批量删除方法，并且删除后剩余的元素相对顺序不变，且全部往前移动 // 之所以使用try-fianlly是因为c.contains可能会抛出异常(c == null，或者实现类中不允许null），导致arraylist没有能更新size以及对底层数组进行整理， // 使用finally可以保证保证这一点，并且与父类abstractcollection中已经实现的removeall/retainall方法的行为的一致性 // 通过finally中的代码可以看出，这些没有进行判断的元素会全部保留。 private boolean batchremove(collection<?> c, boolean complement) { final object[] elementdata = this.elementdata; int r = 0, w = 0; boolean modified = false; try { for (; r < size; r++) if (c.contains(elementdata[r]) == complement) elementdata[w++] = elementdata[r]; } finally { // preserve behavioral compatibility with abstractcollection, // even if c.contains() throws. if (r != size) { system.arraycopy(elementdata, r, elementdata, w, size - r); w += size - r; } if (w != size) { // clear to let gc do its work for (int i = w; i < size; i++) elementdata[i] = null; modcount += size - w; size = w; modified = true; } } return modified; } |
boolean retainall(collection<?> c)：交集操作，上面removeall已经讲了。
void clear()：for循环清空elementdata数组，并把size置为0，不改变容量。
boolean equals(object o)：继承使用父类abstractlist中的方法，算法和判断两个数组内容是否全等一样，就是用的是迭代器而不是传统for循环，此方法用得很少，所以没用数组特性进一步优化。
int hashcode()：同上，继承使用父类abstractlist中的方法，hashcode算法也不特殊，线性结构常用的hash = 31 * hash + e.hashcode。
object[] toarray()：直接使用arrays.copyof拷贝一份elementdata数组作为返回值，也就是数组不共享但是元素共享。
<t> t[] toarray(t[] a)：此方法说明下，觉得行为有些不太友好。
|
1
2
3
4
5
6
7
8
9
|
public <t> t[] toarray(t[] a) { if (a.length < size) // make a new array of a's runtime type, but my contents: return (t[]) arrays.copyof(elementdata, size, a.getclass()); system.arraycopy(elementdata, 0, a, 0, size); if (a.length > size) a[size] = null; return a; } |
此方法很简单，分3种情况处理：给定数组空间小了，新建一样大小数组并拷贝过去（新建操作是在arrays.copyof里面完成的）；刚好相等，直接拷贝就过去完事；给定数组大了，拷贝过去后，由于只覆盖了原数组的前面一部分，再把接下来的一个元素变为null。
觉得不友好的就是给定数组大了的这种情况，因为它会多覆盖掉一个值，注释中说这么做的原因是“当调用者知道列表不包含任何空元素时，这在确定列表的长度时非常有用”，这是个坑啊。下面的demo简单展示了这个坑。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public class testarraylist { public static void main(string[] args) { list<string> slist = arrays.aslist("0", "1", "2", "3", "4", "5", "6", "7", "8", "9"); // 推荐使用空数组 string[] s0 = {}; system.err.println("s0 = " + arrays.tostring(slist.toarray(s0))); // s0 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] // 也可以使用等长数组 string[] s10 = new string[slist.size()]; system.err.println("s10 = " + arrays.tostring(slist.toarray(s10))); // s10 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] // 除非你清楚，否则不要像下面这么做，因为s20[10]被此方法设置为null string[] s20 = new string[20]; s20[10] = "10"; s20[11] = "11"; s20[12] = "12"; system.err.println("s20 = " + arrays.tostring(slist.toarray(s20))); // s20 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, null, 11, 12, null, null, null, null, null, null, null] } } |
五、独有的两个方法
public void ensurecapacity(int mincapacity)：可以外部调用的手动扩容方法，在要添加大量元素之前，预估下容量，调用这个方法手动扩容，避免频繁自动扩容降低性能。
public void trimtosize()：节省空间，使得elementdata刚好容纳下所有元素。
六、几个jdk1.8新增的函数式、stream有关的方法
这里不说。集合类这部分要说，也放在以后一起说
简单总结下，jdk1.7版本对比1.6版本，三个改动：
1、懒初始化，因此默认构造方法创建的是空数组，不再是10个大小的数组；
2、扩容相关的完善；
3、一些方法不再直接使用父类的通用实现，改为利用数组特性的更有效率的实现。
对比着看更容易发现问题，也跟有收获。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：http://blog.csdn.net/u011392897/article/details/57105709
