JDK1.8、JDK1.7、JDK1.6区别看这里

这一篇开始说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个容量。

// jdk1.6的
/** Constructs an empty list with an initial capacity of ten. */
 public ArrayList() {
 this(10);
}

jdk1.7的,相对1.6版本,引入了一个新的常量EMPTY_ELEMENTDATA,它是一个空数组,因此容量为0。

// 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。至于两个空数组有什么区别,看下面一点说的。

/** 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.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稍微进行了一点优化,也是赋值为空数组,但是重用了常量对象。
下面写个简单的例子看一个细微的区别。

// 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点一样。

// 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用两个空数组,导致这里的空数组的名字不一样,两个版本的代码可以看作是一样的。

// 手动扩容方法(可以外部调用,不过大多数情况都是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的相关代码,可以对比看下:

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中的实现。

// 此方法就是一个简单的数组批量删除方法,并且删除后剩余的元素相对顺序不变,且全部往前移动
// 之所以使用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):此方法说明下,觉得行为有些不太友好。

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简单展示了这个坑。

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、一些方法不再直接使用父类的通用实现,改为利用数组特性的更有效率的实现。
对比着看更容易发现问题,也跟有收获。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • JAVA帮助文档全系列 JDK1.5 JDK1.6 JDK1.7 官方中英完整版整理

    JDK(Java Development Kit,Java开发包,Java开发工具)是一个写Java的applet和应用程序的程序开发环境.它由一个处于操作系统层之上的运行环境还有开发者编译,调试和运行用Java语言写的applet和应用程序所需的工具组成. JDK(Java Development Kit)是Sun Microsystems针对Java开发员的产品.自从Java推出以来,JDK已经成为使用最广泛的Java SDK(Software development kit). JDK包含

  • Jdk1.8 HashMap实现原理详细介绍

    HashMap概述 HashMap是基于哈希表的Map接口的非同步实现.此实现提供所有可选的映射操作,并允许使用null值和null键.此类不保证映射的顺序,特别是它不保证该顺序恒久不变. HashMap的数据结构 在Java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的,HashMap也不例外.HashMap实际上是一个"链表散列"的数据结构,即数组和链表的结构,但是在jdk1.8里 加入了红黑树的实现,当链表的

  • 使用Linux安装JDK1.7教程详解

    1. 准备材料 2. 创建 /usr/local/java 目录,并将JDK安装文件放入其中 mkdir /usr/local/java 3. 解压JDK到当前目录 tar -zxvf jdk-7u79-linux-x64.tar.gz 得到文件夹 jdk1.7.0_79 4. 编辑配置文件,配置环境变量 vim /etc/profile 输入i在文件底部添加jdk配置信息 # Java Path JAVA_HOME=/usr/local/java/jdk1.7.0_79 CLASSPATH=$

  • Debian配置JDK1.7 与Linux Java Helloworld

    其实JAVA的原生平台是Linux的,只是它可以跨平台运行而已.在Linux中甚至就有了原生的JDK,但是这些JDK难免不完整,因此最好自己配置一个JDK1,7,为以后的Tomcat,安卓等做好准备.下面以JDK1.7在Debian的配置为例子,讲解在Linux中如何配置JDK. 一.JDK1.7的下载与安装 1.首先,与在Windows配置JDK一样,打开Java的官网(点击打开链接)同意了协议之后,下载Linux版的JDK,下载那个压缩版的.tar.gz.记得同意协议,否则永远不让下载.I3

  • myEclipse配置jdk1.7教程

    本文实例为大家分享了jdk1.7配置教程,供大家参考,具体内容如下 第一步:下载jdk1.7 下载地址:链接 密码: wrmf 第二步:安装jdk1.7 将下载的压缩包进行解压,得到一个jdk-7u17-windows-x64.exe的文件,直接双击运行,安装完成. 第三步:在项目上右键->properties,选择Java Build Path,点击JRE System Library选项,点击Edit按钮. 第四步:点击Installed JREs按钮. 第五步:点击Add按钮. 第六步:单

  • 基于Fedora14下自带jdk1.6版本 安装jdk1.7不识别的解决方法

    安装jdk1.7.0_04后,同时设置环境变量,并且source.可是java -version查看后,还是只能查看到jdk1.6和jdk1.5一共两个版本,这两个版本都是fedora自带的. 解决方法: #:  alternatives --install /usr/bin/java java /usr/local/android/jdk1.7.0_04/bin/java 500 注意:/usr/local/android/jdk1.7.0_04/ 是我的jdk安装路径. 然后: altern

  • Ubuntu 15下安装JDK1.8教程

    一.下载安装包 官网下载地址:http://www.oracle.com/technetwork/java/javase/downloads/index-jsp-138363.html 点击同意.然后选择相应的版本.进行下载 二.安装JDK 下载下来之后,通过命令解包 sudo tar zxvf jdk-8u111-linux-x64.tar.gz 解包之后 创建一个目录/usr/lib/jvm以便于把下载解压后的包放到这个目录下. sudo mkdir -p /usr/lib/jvm 把解压后

  • Java编程之jdk1.4,jdk1.5和jdk1.6的区别分析(经典)

    本文结合实例详细分析了Java编程之jdk1.4,jdk1.5和jdk1.6的区别.分享给大家供大家参考,具体如下: 简单说:1.4和1.5最大的区别有两个,一个是1.5有泛型,另一个1.5可以自动封装八大基本数据类型的封装数据类型,即,Integer a = 4这个1.4是不可以的.1.5和1.6的区别不大.1.6我觉得最多的变化,我觉得最大的部分是在GUI上面,提供了很多方便的布局管理和扩展. 这段时间进了一家电子政务公司,都用weblogic8,那咱就用jdk1.4吧,eclipse一改j

  • JDK1.8、JDK1.7、JDK1.6区别看这里

    这一篇开始说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接口,可以随机访问,随机

  • RHEL6.5下JDK1.8安装教程

    RHEL6.5环境中安装JDK1.8,供大家参考,具体内容如下 注: 1.本文安装的是jdk1.8,采用rpm包的方式安装. 2.rpm安装方式默认会把jdk安装到/usr/java/jdk1.8xxx 路径上,若想将JDK安装到特定路径,需以源码方式安装. 步骤: 1.官网下载JDK1.8的rpm文件,并上传到linux服务器(任意目录) 2.使用rpm命令安装 [root@localhost ~]#rpm -ivh jdk-8u151-linux-x64.rpm 3.设置环境变量(我这里修改

  • JDK1.8新特性Stream流式操作的具体使用

    一. 前言 随着Java的发展,越来越多的企业开始使用JDK1.8 版本.JDK1.8 是自 JDK1.5之后最重要的版本,这个版本包含语言.编译器.库.工具.JVM等方面的十多个新特性.本次文章将着重学习Stream. Stream 是JDK1.8 中处理集合的关键抽象概念,Lambda 和 Stream 是JDK1.8新增的函数式编程最有亮点的特性了,它可以指定你希望对集合进行的操作,可以执行非常复杂的查找.过滤和映射数据等操作.使用Stream API 对集合数据进行操作,就类似于使用SQ

  • Java之String、StringBuffer、StringBuilder的区别分析

    相信大家对 String 和 StringBuffer 的区别也已经很了解了,但是估计还是会有很多同志对这两个类的工作原理有些不清楚的地方,今天我在这里重新把这个概念给大家复习一下,顺便牵出 J2SE 5.0 里面带来的一个新的字符操作的类-- StringBuilder .那么这个 StringBuilder 和 StringBuffer 以及我们最早遇见的 String 类有那些区别呢?在不同的场合下我们应该用哪个呢?我讲讲自己对这几个类的一点看法,也希望大家提出意见,每个人都有错的地方,在

  • 深入理解关于javascript中apply()和call()方法的区别

    如果没接触过动态语言,以编译型语言的思维方式去理解javaScript将会有种神奇而怪异的感觉,因为意识上往往不可能的事偏偏就发生了,甚至觉得不可理喻.如果在学JavaScript这自由而变幻无穷的语言过程中遇到这种感觉,那么就从现在形始,请放下的您的"偏见",因为这对您来说绝对是一片新大陆,让JavaScrip慢慢融化以前一套凝固的编程意识,注入新的生机! 好,言归正传,先理解JavaScrtipt动态变换运行时上下文特性,这种特性主要就体现在apply, call两个方法的运用上.

  • 理清apply(),call()的区别和关系

    如果在学JavaScript这自由而变幻无穷的语言过程中遇到这种感觉,那么就从现在形始,请放下的您的"偏见",因为这对您来说绝对是一片新大陆,让JavaScrip慢慢融化以前一套凝固的编程意识,注入新的生机! 好,言归正传,先理解JavaScrtipt动态变换运行时上下文特性,这种特性主要就体现在apply, call两个方法的运用上. 区分apply,call就一句话, 复制代码 代码如下: foo.call(this, arg1,arg2,arg3) == foo.apply(th

  • jQuery之DOM对象和jQuery对象的转换与区别分析

    本文实例分析了DOM对象和jQuery对象的转换与区别.分享给大家供大家参考.具体分析如下: jQuery Hello World程序: <script type="text/javascript" src="xxx//jquery-x.y.z.js"> 引入jQuery.存在两个版本,jquery-x.y.z.min.js是精简压缩版,不带min的是开发版,代码中的注释和缩进等都被保留了. 注意路径中的"/"需要转义,即用"

  • java中String与StringBuilder的区别

    相信大家对 String 和 StringBuffer 的区别也已经很了解了,但是估计还是会有很多同志对这两个类的工作原理有些不清楚的地方,今天我在这里重新把这个概念给大家复习一下,顺便牵出 J2SE 5.0 里面带来的一个新的字符操作的类-- StringBuilder (先别忙着扔我砖头,我还算清醒,我这里说的不是 C #, Java 也有 StringBuilder 类).那么这个 StringBuilder 和 StringBuffer 以及我们最早遇见的 String 类有那些区别呢?

随机推荐