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不共享,但是实际的元素还是共享的。 7、实现Serializable接口,可以被序列化。ArrayList"实现"了自定义序列化方法,这么做主要是为了节省空间 。对于占用空间的大头――元素list,仅仅序列化实际size大小的元素,同时不序列化对于新对象无用属性的――来自父类AbstractList的modCount。ArrayList的实际size不会超过底层数组的length,大多数情况下比底层数组length小,使用默认序列化的话,会直接序列化整个底层数组,序列化后字节流会变大,浪费空间。 二、构造方法 1、默认构造方法,ArrayList() 关于默认构造方法,你可能在别的地方看见过这种话:无参构造方法(默认构造方法)构造的ArrayList的底层数组elementData大小(容量)默认为10。这里告诉你,这不一定是对的。这句话在1.6版本中是对的(更之前的版本我没看),从1.7开始这句话就有问题了。下面我贴出了三个版本的代码: // 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。 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),虽然创建后底层内容和容量都一样,但是实际的行为有些细小的差别,那就是这两个在第一次自动扩容时策略不一样。不过这一点影响比较小,基本不影响使用。 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,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,Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; } } 关于中间这行注释,可以看下这篇博文 此构造方法会有和Array.copyOf/System.arraycopy一样的问题,那就是它只是新建一个elementData数组,数组的内容对应相等,但是不拷贝实际的元素,实际的元素占据的内存空间还是共享的。 三、确保容量方法(扩容方法):ensureCapacity/ensureCapacityInternal 提前声明下:这两个方法只是确保容量,不一定会扩容,但是为了好理解,下面的文字中所说的"扩容"指的就是这两个方法。 扩容方法四个位置用到:两个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型的两个不同的数a和b,有 所以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、使用这行代码 还有一个问题就是,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的) 在带初始容量的构造方法 public ArrayList(int initialCapacity) 中,并没有判断初始容量是否大于MAX_ARRAY_SIZE。个人觉得还是判断下好,不判断可能在扩容时会有点问题。下面给一组变量值大家试下,看下是不是真有问题。 初始数组长度 elementData.length = Integer.MAX_VALUE - 5 = 2147483642; 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 remove(int index):基本同上,会进行数组复制,这是数组实现的list避免不了的问题。注意下实现中的elementData[--size] = null; // clear to let GC do its work,这句让list不引用元素,让元素可以被回收(当然,还得其他地方都不引用元素),避免集合类“假删除”造成内存泄漏。 int indexOf(Object o):此方法和下面的lastIndexOf方法会进行null判断,o == null则在遍历时使用 == 进行比较,o != null则在遍历时使用equals方法进行比较,所以使用时请注意下元素的equals方法。 2、来自Collection(Iteratable)接口的方法 Iterator<E> iterator():返回一个内部的实现类,从jdk1.7开始该实现类使用数组的特性优化实现Iterator的几个方法,1.6返回的是父类AbstractList中定义的一个List接口通用的迭代器。 // 此方法就是一个简单的数组批量删除方法,并且删除后剩余的元素相对顺序不变,且全部往前移动 // 之所以使用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已经讲了。 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,a.getClass()); System.arraycopy(elementData,a,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,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,9,null,11,12,null] } } 五、独有的两个方法 六、几个jdk1.8新增的函数式、stream有关的方法 这里不说。集合类这部分要说,也放在以后一起说 简单总结下,jdk1.7版本对比1.6版本,三个改动: 以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持编程小技巧。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |