神刀安全网

深入Java基础(三)–集合(2)ArrayList和其继承树源码解析以及其注意事项


好了,我们继续开始这个系列,今天我们来深入ArrayList吧!

本系列以前的文章:

(1) 深入Java基础(一)——基本数据类型及其包装类

(2)深入Java基础(二)——字符串家族

(3) 深入Java基础(三)–集合(1)集合父类以及父接口源码及理解


文章结构:(1).ArrayList概述以及基本了解;(2).ArrayList源码分析;(3).ArrayList的使用以及相关注意点。


一、ArrayList概述以及基本用法:

(1)概述:ArrayList是基于数组实现的,是一个动态数组,其容量能自动增长,类似于C语言中的动态申请内存,动态增长内存。

但是,和Vector不同,ArrayList中的操作不是线程安全的!所以,建议在单线程中才使用ArrayList,而在多线程中可以选择Vector或者CopyOnWriteArrayList。

每个ArrayList实例都有一个容量,该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList中不断添加元素,其容量也自动增长。自动增长会带来数据向新数组的重新拷贝,因此,如果可预知数据量的多少,可在构造ArrayList时指定其容量。在添加大量元素前,应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量,这可以减少递增式再分配的数量。

特点:1.随机访问速度快,插入和移除性能较差(数组的特点);2.支持null元素;3.有顺序;4.元素可以重复;5.线程不安全;

(2)基本了解:

先看看API:

// Collection中定义的API(此API总结是参考别的博客的,我们只需了解它的api由多少部分组成就好) boolean             add(E object) boolean             addAll(Collection<? extends E> collection) void                clear() boolean             contains(Object object) boolean             containsAll(Collection<?> collection) boolean             equals(Object object) int                 hashCode() boolean             isEmpty() Iterator<E>         iterator() boolean             remove(Object object) boolean             removeAll(Collection<?> collection) boolean             retainAll(Collection<?> collection) int                 size() <T> T[]             toArray(T[] array) Object[]            toArray() // AbstractCollection中定义的API void                add(int location, E object) boolean             addAll(int location, Collection<? extends E> collection) E                   get(int location) int                 indexOf(Object object) int                 lastIndexOf(Object object) ListIterator<E>     listIterator(int location) ListIterator<E>     listIterator() E                   remove(int location) E                   set(int location, E object) List<E>             subList(int start, int end) // ArrayList新增的API Object               clone() void                 ensureCapacity(int minimumCapacity) void                 trimToSize() void                 removeRange(int fromIndex, int toIndex)

二、ArrayList源码分析

分析前我们来看下类图:此图来源百度图库!!

深入Java基础(三)--集合(2)ArrayList和其继承树源码解析以及其注意事项

这里写图片描述

每当看一份源码,我都喜欢分析它的继承树,从而扩大自己的知识面。可以很清晰看到,实线就是继承,虚线就是接口。

关于ArrayList前面的继承,可以阅读我的上一篇博客:深入Java基础(三)–集合(1)集合父类以及父接口源码及理解

阅读源码才是根本:

先来看下它的父类AbstractList:

一个抽象类,主要实现了迭代器功能和定义了一系列顺序线性表容器的操作接口。关注一个 ListIterator实现,允许对容器中的元素进行双向遍历。以及关注一个关键设计,并发检查设计,快速失败。

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {     protected AbstractList() {     }     //说过不支持单个添加,要子类去实现     public boolean add(E e) {         add(size(), e);         return true;     }     //顺序线性表嘛,肯定要直接根据下标拿数据啦     abstract public E get(int index);     //更新index位置元素,让想做的话子类实现。这里丢给上一层。     public E set(int index, E element) {         throw new UnsupportedOperationException();     }     //index位置插入元素,同样交由子类去实现     public void add(int index, E element) {         throw new UnsupportedOperationException();     }     //删除inde位置元素,同样交由子类去实现     public E remove(int index) {         throw new UnsupportedOperationException();     }     //利用迭代器,查找元素首次出现的下标 ,不存在返回-1     public int indexOf(Object o) {         ListIterator<E> it = listIterator();//一会详解这个特殊迭代器         if (o==null) {             while (it.hasNext())                 if (it.next()==null)                     return it.previousIndex();         } else {             while (it.hasNext())                 if (o.equals(it.next()))                     return it.previousIndex();         }         return -1;     }     //利用迭代器,查找到元素最后一次出现的下标,不存在返回-1     public int lastIndexOf(Object o) {         ListIterator<E> it = listIterator(size());         if (o==null) {             while (it.hasPrevious())// 向前查找                 if (it.previous()==null)                     return it.nextIndex();         } else {             while (it.hasPrevious())                 if (o.equals(it.previous()))                     return it.nextIndex();         }         return -1;     }     //清空元素     public void clear() {         removeRange(0, size());     }     //从集合c中index位置开始,讲元素插入到当前集合中     public boolean addAll(int index, Collection<? extends E> c) {         rangeCheckForAdd(index);         boolean modified = false;         for (E e : c) {             add(index++, e);             modified = true;         }         return modified;     }     //获取普通迭代器     public Iterator<E> iterator() {         return new Itr();     }     //获取双向迭代器     public ListIterator<E> listIterator() {         return listIterator(0);     }     //指定index开始获取双向迭代器,减少迭代无用元素     public ListIterator<E> listIterator(final int index) {         rangeCheckForAdd(index);          return new ListItr(index);     }     //内部类,实现Iterator迭代器     private class Itr implements Iterator<E> {         //当前运行的位置,当然一开始表示数组元素的第一个下标。就是当前的位置嘛         int cursor = 0;         //如果这个元素不存在或者被删除,那么这个值就是-1.          int lastRet = -1;         //修改次数         int expectedModCount = modCount;         // 是否结束或继承遍历下一个         public boolean hasNext() {             return cursor != size();         }         // 返回当前元素值          public E next() {             checkForComodification();// 检查是否合法id             try {                 int i = cursor;                 E next = get(i);                 lastRet = i;                 cursor = i + 1;                 return next;             } catch (IndexOutOfBoundsException e) {                 checkForComodification();                 throw new NoSuchElementException();             }         }         // 删除当前元素         public void remove() {             if (lastRet < 0)                 throw new IllegalStateException();             checkForComodification();              try {                 AbstractList.this.remove(lastRet);                 if (lastRet < cursor)                     cursor--;                 lastRet = -1;                 expectedModCount = modCount;             } catch (IndexOutOfBoundsException e) {                 throw new ConcurrentModificationException();             }         }         //迭代器最重要的一个方法:检查并发修改的内容。检查了从迭代器构造完成后数组的容量和迭代以后数组的容量是否相等,如果不相等,说明有其他线程修改了数组长度,这里会抛出一个ConcurrentModificationException同步修改异常,也就是经常说的快速失败(fast fail)。         //设计只是善意提醒了这个容器存在多线程操作,因为这个容器目前只支持单线程操作。         final void checkForComodification() {             if (modCount != expectedModCount)                 throw new ConcurrentModificationException();         }     }     //ListItr 继承Itr 实现ListIterator ,增加前驱遍历。也就是说它能前提的前提是继承了父类的后驱遍历迭代嘛。     private class ListItr extends Itr implements ListIterator<E> {     // 从当前index开始构建迭代器         ListItr(int index) {             cursor = index;         }       // 是否有前驱         public boolean hasPrevious() {             return cursor != 0;         }         // 返回前驱节点值         public E previous() {             checkForComodification();             try {                 int i = cursor - 1;// 更新更新-1                  E previous = get(i);                 lastRet = cursor = i;                 return previous;             } catch (IndexOutOfBoundsException e) {                 checkForComodification();                 throw new NoSuchElementException();             }         }         // 后继下标         public int nextIndex() {             return cursor;         }          // 前驱下标         public int previousIndex() {             return cursor-1;         }         // 尾部更新元素         public void set(E e) {             if (lastRet < 0)                 throw new IllegalStateException();             checkForComodification();              try {                 AbstractList.this.set(lastRet, e);                 expectedModCount = modCount;             } catch (IndexOutOfBoundsException ex) {                 throw new ConcurrentModificationException();             }         }         // 当前位置更新元素数据         public void add(E e) {             checkForComodification();              try {                 int i = cursor;                 AbstractList.this.add(i, e);                 lastRet = -1;                 cursor = i + 1;                 expectedModCount = modCount;             } catch (IndexOutOfBoundsException ex) {                 throw new ConcurrentModificationException();             }         }     }     //剩下很多不常用的方法和一些以及讲过的基础代码了,,讲点此顺序线性表有趣点的东西吧。     public boolean equals(Object o) {         if (o == this)// 当前对象             return true;         if (!(o instanceof List))// 不是子对象             return false;          ListIterator<E> e1 = listIterator();// 构建两个迭代器         ListIterator<?> e2 = ((List<?>) o).listIterator();         while (e1.hasNext() && e2.hasNext()) {//用两个迭代器遍历,一起执行             E o1 = e1.next();             Object o2 = e2.next();// 比较每个元素             if (!(o1==null ? o2==null : o1.equals(o2)))                 return false;         }         return !(e1.hasNext() || e2.hasNext());     }     //下标检查的标志,跟迭代器的expectedModCount 比较。用于检测元素数组是否被修改的判断。如果数组在迭代过程中增加或删除,则可以直接检查出来,导致快速失败。      //AbstractList的一个自身属性      protected transient int modCount = 0;

ArrayList源码:

//实现了Serializable接口,因此它支持序列化,能够通过序列化传输,实现了RandomAccess接口,支持快速随机访问,实际上就是通过下标序号进行快速访问。实现了Cloneable接口,能被克隆。 /*     这里解析下Cloneable这个标记性接口。     为什么要clone?设计模式里有一个模式为原型模式,用原型实例指定创建对象的种类,并且通过拷贝这些原型创建新的对象,clone一个对象实例。使得clone出来的copy和原有的对象一模一样。     应对的情况:如果一个对象内部有可变对象实例的话,public API不应该直接返回该对象的引用,以防调用方的code改变该对象的内部状态。这个时候可以返回该对象的clone。     至于克隆原理以及优缺分析和使用,请关注我不久会写的系列深入设计模式。     还有这里需要理解浅拷贝跟深拷贝:http://blog.csdn.net/feitianxuxue/article/details/9275979 */ //List接口就不讲了吧,就是一个规范,规定所有线性表必须有的方法嘛。 public class ArrayList<E> extends AbstractList<E>         implements List<E>, RandomAccess, Cloneable, java.io.Serializable {      // 序列版本号     private static final long serialVersionUID = 8683452581122892189L;      //默认的初始容量为10     private static final int DEFAULT_CAPACITY = 10;     //!!!悬念:为什么是Object数组,以及配合泛型来玩???     //空数组     private static final Object[] EMPTY_ELEMENTDATA = {};     private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};     // ArrayList基于该数组实现,用该数组保存数据  ,并且标记为不参与序列化过程     //为什么标记不参与序列化?因为这是一个缓存数组,我们知道ArrayList它是一个动态数组,所以经常会扩容。极大地方便。除了writeObject方法中手动将其序列化,并且只序列化了实际存储的那些元素,而不是整个数组。     transient Object[] elementData;     //表示它包含的元素的数量     private int size;     //三个构造器     //带容量的构造器     public ArrayList(int initialCapacity) {         if (initialCapacity > 0) {             this.elementData = new Object[initialCapacity];//初始容量大于0,实例化数组         } else if (initialCapacity == 0) {             this.elementData = EMPTY_ELEMENTDATA;//初始化等于0,将空数组赋给elementData         } else {//初始容量小于0,抛异常             throw new IllegalArgumentException("Illegal Capacity: "+                                                initialCapacity);         }     }     //默认构造器,默认容量为10     public ArrayList() {         this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;     }     //创建一个包含collection的ArrayList     public ArrayList(Collection<? extends E> c) {         elementData = c.toArray();//返回一个包含c所有元素的数组给一个object数组         if ((size = elementData.length) != 0) {             // c.toArray might (incorrectly) not return Object[] (see 6260652)             //翻译下:c.toArray可能不会返回一个Object数组。这也涉及上面的悬念,为什么一定要Object?传进来一般是一个子类集合,它父类是Object,这个一会会详细解析此处。             if (elementData.getClass() != Object[].class)                 elementData = Arrays.copyOf(elementData, size, Object[].class);//复制指定数组         } else {         //c中没有元素,就用空数组赋给elementData咯             // replace with empty array.             this.elementData = EMPTY_ELEMENTDATA;         }     }     //将当前容量值设为当前实际元素大小,操作的对象还是缓存数组elementData     public void trimToSize() {         modCount++;         if (size < elementData.length) {             elementData = (size == 0)               ? EMPTY_ELEMENTDATA               : Arrays.copyOf(elementData, size);         }     }     //三大容量改变方法(扩容方法):在添加大量元素前,应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量,这可以减少递增式再分配的数量。       //将集合的capacit增加minCapacity     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);         }     }     //首先是判断现在的ArrayList是不是空的,如果是空的,minCapacity就取默认的容量和传入的参数minCapacity中的大值     private void ensureCapacityInternal(int minCapacity) {         if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {             minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);         }         //再调用此方法         ensureExplicitCapacity(minCapacity);     }     //     private void ensureExplicitCapacity(int minCapacity) {     //同理父类AbstractList,有一个快速失败机制,来检测并发安全。     //modCount是fail fast机制,在jdk1.6之前都是有volatile来修饰的,尽可能的让并发访问非安全的集合对象时尽快的失败抛出异常,让程序员修改代码。因为没有必要为非线程安全集合浪费效率,所以6之后就改了。         modCount++;          // overflow-conscious code         if (minCapacity - elementData.length > 0)             grow(minCapacity);     }     //最大的阀值     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;     //真正扩容在此!!!     private void grow(int minCapacity) {         // overflow-conscious code         int oldCapacity = elementData.length;//先拿到缓存数组的长度         //左移1位,相当于除以2,就是容量提高50%,就是变成原来*1.5的容量嘛         int newCapacity = oldCapacity + (oldCapacity >> 1);         //如果还不够,则直接将minCapacity设置为当前容量          if (newCapacity - minCapacity < 0)             newCapacity = minCapacity;             //再不够就给最大的阀值MAX_ARRAY_SIZE         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);     } //比较minCapacity和 MAX_ARRAY_SIZE,如果minCapacity大于最大容量,则新容量则为ArrayList定义的最大容量,否则,新容量大小则为 minCapacity。     private static int hugeCapacity(int minCapacity) {         if (minCapacity < 0) // overflow             throw new OutOfMemoryError();         return (minCapacity > MAX_ARRAY_SIZE) ?             Integer.MAX_VALUE :             MAX_ARRAY_SIZE;     }     //这几个方法就不说了吧。。。     public int size() {         return size;     }     public boolean isEmpty() {         return size == 0;     }     public boolean contains(Object o) {         return indexOf(o) >= 0;     }     //正向查找,返回ArrayList中元素Object(o)的索引位置     public int indexOf(Object o) {         if (o == null) {             for (int i = 0; i < size; i++)                 if (elementData[i]==null)                     return i;         } else {             for (int i = 0; i < size; i++)                 if (o.equals(elementData[i]))                     return i;         }         return -1;     }      //逆向查找,返回返回ArrayList中元素Object(o)的索引位置     public int lastIndexOf(Object o) {         if (o == null) {             for (int i = size-1; i >= 0; i--)                 if (elementData[i]==null)                     return i;         } else {             for (int i = size-1; i >= 0; i--)                 if (o.equals(elementData[i]))                     return i;         }         return -1;     }     //返回此 ArrayList实例的浅拷贝。     public Object clone() {         try {             ArrayList<?> v = (ArrayList<?>) super.clone();             v.elementData = Arrays.copyOf(elementData, size);             v.modCount = 0;             return v;         } catch (CloneNotSupportedException e) {             // this shouldn't happen, since we are Cloneable             throw new InternalError(e);         }     }     //返回一个包含ArrayList中所有元素的数组,而这里下面第一个返回异常,因为java在向下转型是有风险的,而这里的设计直接杜绝了它。     public Object[] toArray() {         return Arrays.copyOf(elementData, size);     }     //这里则是对应类型的转换     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;     }     //这不就是些数组功能吗???     E elementData(int index) {         return (E) elementData[index];     }     //返回至指定索引的值     public E get(int index) {         rangeCheck(index);          return elementData(index);     }     //将指定索引上的值替换为新值,并返回旧值     public E set(int index, E element) {         rangeCheck(index);          E oldValue = elementData(index);         elementData[index] = element;         return oldValue;     }     //将指定的元素添加到此列表的尾部     public boolean add(E e) {         ensureCapacityInternal(size + 1);  // Increments modCount!!         elementData[size++] = e;         return true;     }     // 将element添加到ArrayList的指定位置        public void add(int index, E element) {         rangeCheckForAdd(index);         //确定要不要扩容         ensureCapacityInternal(size + 1);  // Increments modCount!!         /*         从指定源数组中复制一个数组,复制从指定的位置开始,到目标数组的指定位置结束。         arraycopy(被复制的数组, 从第几个元素开始复制, 要复制到的数组, 从第几个元素开始粘贴。详细查看方法参数         即在数组elementData从index位置开始,复制到index+1位置,共复制size-index个元素。         */         //还不清晰arraycopy方法的请看:http://blog.csdn.net/kesalin/article/details/566354         System.arraycopy(elementData, index, elementData, index + 1,                          size - index);         elementData[index] = element;         size++;     }     //根据索引删除ArrayList指定位置的元素 ,并返回该元素      public E remove(int index) {         rangeCheck(index);          modCount++;         E oldValue = elementData(index);         int numMoved = size - index - 1;         if (numMoved > 0)         //拷贝数组,将后面的所有元素都向前移动一位             System.arraycopy(elementData, index+1, elementData, index,                              numMoved);           //将原数组最后一个位置置为null,将最后一位赋值为null以便垃圾回收器回收         elementData[--size] = null; // clear to let GC do its work         return oldValue;     }      //移除ArrayList中首次出现的指定元素(如果存在)。但是只返回成功与失败标志     public boolean remove(Object o) {         if (o == null) {             for (int index = 0; index < size; index++)                 if (elementData[index] == null) {                     fastRemove(index);                     return true;                 }         } else {             for (int index = 0; index < size; index++)                 if (o.equals(elementData[index])) {                     fastRemove(index);                     return true;                 }         }         return false;     }     // 快速删除第index个元素     private void fastRemove(int index) {         modCount++;         int numMoved = size - index - 1;         // 从"index+1"开始,用后面的元素替换前面的元素。          if (numMoved > 0)         //将后面的所有元素都向前移动一位             System.arraycopy(elementData, index+1, elementData, index,                              numMoved);         // 将最后一个元素设为null,将最后一位赋值为null以便垃圾回收器回收         elementData[--size] = null; // clear to let GC do its work     }     //清空ArrayList,将全部的元素设为null     public void clear() {         modCount++;          // clear to let GC do its work         for (int i = 0; i < size; i++)             elementData[i] = null;          size = 0;     }      //从指定位置index开始,将指定c中的所有元素插入到此列表中,其中使用c的迭代器     public boolean addAll(int index, Collection<? extends E> c) {         rangeCheckForAdd(index);          Object[] a = c.toArray();         int numNew = a.length;         ensureCapacityInternal(size + numNew);  // Increments modCount          int numMoved = size - index;         if (numMoved > 0)         //先将ArrayList中从index开始的numMoved个元素移动到起始位置为index+numNew的后面去             System.arraycopy(elementData, index, elementData, index + numNew,                              numMoved);  //再将c中的numNew个元素复制到起始位置为index的存储空间中去         System.arraycopy(a, 0, elementData, index, numNew);         size += numNew;         return numNew != 0;     }     //至于剩下的一些方法,其实差不多了,主要是理解arraycopy方法去复制数组,然后调用了父类的一些模板方法或者集合的一些模板方法了。     //下面讲得特殊的点:      //检查索引是否越界      //这个是普通的,查询时候使用的异常检测     private void rangeCheck(int index) {         if (index >= size)             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));     }     //这个是添加时,使用的异常检测     private void rangeCheckForAdd(int index) {         if (index > size || index < 0)             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));     }     //具体到哪一位越界     private String outOfBoundsMsg(int index) {         return "Index: "+index+", Size: "+size;     }     //它的两个流操作:     //将ArrayList的“容量,所有的元素值”都写入到输出流中      //虽然elementData被transient修饰,不能被序列化,但是我们可以将它的值取出来,然后将该值写入输出流     private void writeObject(java.io.ObjectOutputStream s)         throws java.io.IOException{         // Write out element count, and any hidden stuff         int expectedModCount = modCount;         //这个对比下面的writeInt,wtiteObject是一个很深奥的序列化机制问题:(我们先看官方解释)我翻译了下:         /*             1.defaultWriteObject它读取和写入类的所有非瞬态字段。             2.这些方法也有助于落后和未来的兼容性。             如果将来你添加一些非瞬态场的类,你要反序列化的类然后defaultreadobject()方法旧版本会忽略新加入的领域,             同样如果你反序列化序列化对象的旧的新版本,那么新的域将从JVM采取默认值         */         s.defaultWriteObject();          // Write out size as capacity for behavioural compatibility with clone()          //写入数组大小         s.writeInt(size);          // Write out all elements in the proper order.          //写入所有数组的元素         for (int i=0; i<size; i++) {             s.writeObject(elementData[i]);//传值时,是将实参elementData[i]赋给s.writeObject()的形参         }          if (modCount != expectedModCount) {             throw new ConcurrentModificationException();         }     }     //先将ArrayList的“大小”读出,然后将“所有的元素值”读出     private void readObject(java.io.ObjectInputStream s)         throws java.io.IOException, ClassNotFoundException {         elementData = EMPTY_ELEMENTDATA;          // Read in size, and any hidden stuff         s.defaultReadObject();          // Read in capacity         s.readInt(); // ignored          if (size > 0) {             // be like clone(), allocate array based upon size not capacity             ensureCapacityInternal(size);              Object[] a = elementData;             // Read in all elements in the proper order.             for (int i=0; i<size; i++) {                 a[i] = s.readObject();             }         }     }     //然后就有一堆迭代机制了,跟我们上面的abstractList中的迭代器一样(我也不太懂arraylist再写多了一遍,如懂此问题,请在下面评论指导下我,谢谢!) }

三、ArrayList的使用以及相关注意点:

(1)遍历方式:ArrayList支持3种遍历方式

第一种,通过迭代器遍历。即通过Iterator去遍历。

第二种,随机访问,通过索引值去遍历。由于ArrayList实现了RandomAccess接口,它支持通过索引值去随机访问元素。

第三种,for循环遍历。

关于它们的效率问题百度一下就知道了。遍历ArrayList时,使用随机访问(即,通过索引序号访问)效率最高,而使用迭代器的效率最低!


(2)Object数组的设计:(补充下:初始大小是10,所以使用时要注意!!)

1.设计成Object原因是想List装任何类型嘛,你存什么类型的都可以保存在里面嘛

2.从一般的意义来说,它和数组没有本质的差别,甚至于ArrayList的许多方法,如Index、IndexOf、Contains、Sort等都是在内部数组的基础上直接调用Array的对应方法。

3.往ArrayList里面添加和修改元素,都会引起装箱和拆箱的操作,频繁的操作可能会影响一部分效率。 而使用Object就可保证完全装入这些元素。当然不可避免的还是效率问题会出现。

补充: toArray() 方法和toArray(T[] contents) 方法:

调用 toArray() 函数会抛出“java.lang.ClassCastException”异常,但是调用 toArray(T[] contents) 能正常返回 T[]。toArray() 会抛出异常是因为 toArray() 返回的是 Object[] 数组,将 Object[] 转换为其它类型(如如,将Object[]转换为的Integer[])则会抛出“java.lang.ClassCastException”异常,因为Java不支持向下转型。具体的可以参考前面ArrayList.java的源码介绍部分的toArray()。

这也是为什么源码设计都采用了泛型去设计!!!!当我们初始化时也采用泛型,则会避免很多转换的风险,并且可以以最大效率去实现各功能。

//最常用的方式 public static Integer[] vectorToArray2(ArrayList<Integer> v) {     Integer[] newText = (Integer[])v.toArray(new Integer[0]);     return newText; }

(3)拷贝线性表的两个方法:Arrays.copyof()和System.arraycopy()方法:

//最后一个参数指明要转换的数据的类型 public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {  //创建了一个长度为newlength的数组         @SuppressWarnings("unchecked")         T[] copy = ((Object)newType == (Object)Object[].class)             ? (T[]) new Object[newLength]                : (T[]) Array.newInstance(newType.getComponentType(), newLength);             //调用System.arraycopy()方法,将原来数组中的元素复制到了新的数组中。         System.arraycopy(original, 0, copy, 0,                          Math.min(original.length, newLength));         return copy;     }
/*     (此段摘自一篇博客)     被标记了native,调用了系统的C/C++代码,在JDK中是看不到的,但在openJDK中可以看到其源码。该函数实际上最终调用了C语   言的memmove()函数,因此它可以保证同一个数组内元素的正确复制和移动,比一般的复制方法的实现效率要高很多,很适合用来批量处理数组。Java强烈推荐在复制大量数组元素时用该方法,以取得更高的效率。 */ public static native void arraycopy(Object src,  int  srcPos,                                         Object dest, int destPos,                                         int length);

(4)效率问题

频繁的调用IndexOf、Contains等方法(Sort、BinarySearch等方法经过优化,不在此列)引起的效率损失。首先,我们要明确一点,ArrayList是动态数组,它不包括通过Key或者Value快速访问的算法,所以实际上调用IndexOf、Contains等方法是执行的简单的循环来查找元素,所以频繁的调用此类方法并不比你自己写循环并且稍作优化来的快,如果有这方面的要求,建议使用Hashtable或SortedList等键值对的集合。

ArrayList基于数组实现,可以通过下标索引直接查找到指定位置的元素,因此查找效率高,但每次插入或删除元素,就要大量地移动元素,插入删除元素的效率低。

(5)值问题:

在查找给定元素索引值等的方法中,源码都将该元素的值分为null和不为null两种情况处理,ArrayList中允许元素为null。

(6)线程安全问题:

public class ArrayListTest {     public static Example example = new Example();      public static void main(String[] args) throws InterruptedException {          final List<Integer> list = new ArrayList<>();//只是声明了不可变,但是没有进行线程封闭,实现监视器模式          for (int i = 0; i < 10; i++) {             new Thread() {                 public void run() {                     for (int j = 0; j < 1000; j++) {                         list.add(1000 * j + j);  // 线程情况出现在这里                         example.increment();                         String threadName = Thread.currentThread().getName();                         System.out.println(threadName);                     }                 }             }.start();         }         try {             Thread.sleep(3000);         } catch (InterruptedException e) {             e.printStackTrace();         }         System.out.println("list size: " + list.size());         System.out.println("Example: " + example.getValue());     } } class Example {     private int value;     //一个单纯的线程锁,但基本保证并发     public synchronized int getValue() {         return value;     }      public synchronized int increment() {         return ++value;     } }
//经常输出: Thread-0 Thread-4 Thread-2 Thread-1 Thread-5 Thread-8 Thread-6 Thread-9 Thread-7 Thread-3 list size: 9994 Example: 10000 //为什么不相等呢??

ArrayList的add源码:

 public boolean add(E e) {  //判断是否需要扩容??!!!ensureCapacityInternal方法主要是判断需要的容量(size+1)是否大于 ArrayList的容量(elementData.length),如果大于 根据规则增加ArrayList的容量,否则 直接返回。         ensureCapacityInternal(size + 1);  // Increments modCount!!         elementData[size++] = e;         return true; }
//首先是判断现在的ArrayList是不是空的,如果是空的,minCapacity就取默认的容量和传入的参数minCapacity中的大值     private void ensureCapacityInternal(int minCapacity) {         if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {             minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);         }         //再调用此方法         ensureExplicitCapacity(minCapacity);     }

由于ArrayList.add()没有同步锁,所以多线程调用这个方法的时候,有可能多个线程拿到相同的size值去与ArrayList的容量做比较,而执行到elemntData[size++] = e;时却是有序的,这时,由于ensureCapacityInternal()没有适当的扩大ArrayList的容量,从而导致插入数据的长度大于ArrayList的剩余容量,于是也就抛出了越界的异常(java.lang.ArrayIndexOutOfBoundsException).


深入Java基础(三)–集合(2)ArrayList和其继承树源码解析以及其注意事项讲完了。本博客是这个系列的第四篇,深入了下ArrayList的源码。另外,这个系列会根据大家的点评以及我学习的深度,把一些问题摆出来给大家,分享经验给大家。欢迎在下面指出错误,共同学习!!你的点赞是对我最好的支持!!

更多内容,可以访问JackFrost的博客

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » 深入Java基础(三)–集合(2)ArrayList和其继承树源码解析以及其注意事项

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址