注册 登录
> 编程技术

ArrayList类源码分析

系统 1595 0

ArrayList源码分析  

   ArrayList是以数组为基础实现的一个动态数组容器，通过以下的代码分析可知，一方面在ArrayList中添加或者删除元素(除了在数组容器末尾添加或者删除元素)，是需要移动大量元素的借助System.arraycopy()来实现拷贝移动，另一方面，由于数组实现基础，可依靠数组下标，可以实现随机访问，当然查找具体的元素，还是需要循环去查找的，再者ArrayList不是thread-safe的，在代码中无论是add,remove，get，都没有任何同步措施，在多线程环境下需要自己确保thread-safe。由此可知ArrayList适用于在任意位置添加，删除元素不多，要求随机访问的应用场景。  

  代码分析主要罗列：ArrayList构造函数，remove(), add(), get()  

1.ArrayList构造函数  

   private transient E[] elementData;ArrayList使用对象数组元素来作为内部实现的基础数据结构。  

Java代码    
  1. //ArrayList是以数组为基础实现的，采用的泛型编程，数组元素都是Object类型   
  2. //初始化时主要是构造指定大小的数组，用于存储对象元素   
  3. public  ArrayList( int  initialCapacity){  
  4.        super ();  
  5.        if  (initialCapacity <  0 )  
  6.            throw   new  IllegalArgumentException( "Illegal Capacity: " +  
  7.                                              initialCapacity);  
  8.        this .elementData = (E[]) new  Object[initialCapacity];  
  9. }  
Java代码     收藏代码
  1. //ArrayList是以数组为基础实现的，采用的泛型编程，数组元素都是Object类型   
  2. //初始化时主要是构造指定大小的数组，用于存储对象元素   
  3. public  ArrayList( int  initialCapacity){  
  4.        super ();  
  5.        if  (initialCapacity <  0 )  
  6.            throw   new  IllegalArgumentException( "Illegal Capacity: " +  
  7.                                              initialCapacity);  
  8.        this .elementData = (E[]) new  Object[initialCapacity];  
  9. }  



 

Java代码    
  1. //默认情况下ArrayList实现依赖的数组长度为10   
  2.     public  ArrayList() {  
  3.          this ( 10 );  
  4.    }  
Java代码     收藏代码
  1. //默认情况下ArrayList实现依赖的数组长度为10   
  2.     public  ArrayList() {  
  3.          this ( 10 );  
  4.    }  


    

 

Java代码    
  1. //使用另一个集合中的元素来初始化当前的List   
  2.   public  ArrayList(Collection<?  extends  E> c) {  
  3.       size = c.size();  
  4.        // Allow 10% room for growth   
  5.       elementData = (E[]) new  Object[  
  6.                     ( int )Math.min((size*110L)/ 100 ,Integer.MAX_VALUE)];   
  7.       c.toArray(elementData);  
  8.   }  
Java代码     收藏代码
  1. //使用另一个集合中的元素来初始化当前的List   
  2.   public  ArrayList(Collection<?  extends  E> c) {  
  3.       size = c.size();  
  4.        // Allow 10% room for growth   
  5.       elementData = (E[]) new  Object[  
  6.                     ( int )Math.min((size*110L)/ 100 ,Integer.MAX_VALUE)];   
  7.       c.toArray(elementData);  
  8.   }  




2. ensureCapaciyt(int) | add(E) | add(int, E)分析  

   ensureCapacity主要用来实现数组的动态扩容,每次扩容为原来大小的1.5倍，在add操作前调用，以确保数组容量够用。  

Java代码    
  1. public   void  ensureCapacity( int  minCapacity) {  
  2.   
  3.     modCount++;  
  4.      int  oldCapacity = elementData.length;  
  5.           
  6.          //如果当前数组的实际容量(oldCapacity)比当前要求的容量要小(minCapacity)   
  7.          //就需要进行扩容，申请新的数组空间，大小为minCapacity,并将原来数组空间中的元素拷贝   
  8.          //到新的数组空间当中。           
  9.      if  (minCapacity > oldCapacity) {  
  10.         Object oldData[] = elementData;  
  11.             
  12.              //扩容因子为:1.5倍左右，每次需要扩容时，会将空间扩展为原来的1.5倍大小   
  13.          int  newCapacity = (oldCapacity *  3 )/ 2  +  1 ;  
  14.   
  15.              if  (newCapacity < minCapacity)  
  16.         newCapacity = minCapacity;  
  17.   
  18.         elementData = (E[]) new  Object[newCapacity];  
  19.                 
  20.              //将数组元素转移到新申请的数组空间当中   
  21.         System.arraycopy(oldData,  0 , elementData,  0 , size);  
  22.     }  
  23. }  
Java代码     收藏代码
  1. public   void  ensureCapacity( int  minCapacity) {  
  2.   
  3.     modCount++;  
  4.      int  oldCapacity = elementData.length;  
  5.           
  6.          //如果当前数组的实际容量(oldCapacity)比当前要求的容量要小(minCapacity)   
  7.          //就需要进行扩容，申请新的数组空间，大小为minCapacity,并将原来数组空间中的元素拷贝   
  8.          //到新的数组空间当中。           
  9.      if  (minCapacity > oldCapacity) {  
  10.         Object oldData[] = elementData;  
  11.             
  12.              //扩容因子为:1.5倍左右，每次需要扩容时，会将空间扩展为原来的1.5倍大小   
  13.          int  newCapacity = (oldCapacity *  3 )/ 2  +  1 ;  
  14.   
  15.              if  (newCapacity < minCapacity)  
  16.         newCapacity = minCapacity;  
  17.   
  18.         elementData = (E[]) new  Object[newCapacity];  
  19.                 
  20.              //将数组元素转移到新申请的数组空间当中   
  21.         System.arraycopy(oldData,  0 , elementData,  0 , size);  
  22.     }  
  23. }  



  add(E)操作是向集合ArrayList中存储元素，在当前数组容器的尾部添加，不需要移动元素,返回true。  

Java代码    
  1. public   boolean  add(E o) {  
  2.          //调用ensureCapacity确保当前容量不小于(size + 1),size为容器中当前存储的实际元素个数.   
  3.     ensureCapacity(size +  1 );   
  4.          //将对象引用o保存到数组容器中，并++size.   
  5.     elementData[size++] = o;  
  6.      return   true ;  
  7. }  
Java代码     收藏代码
  1. public   boolean  add(E o) {  
  2.          //调用ensureCapacity确保当前容量不小于(size + 1),size为容器中当前存储的实际元素个数.   
  3.     ensureCapacity(size +  1 );   
  4.          //将对象引用o保存到数组容器中，并++size.   
  5.     elementData[size++] = o;  
  6.      return   true ;  
  7. }  



add(int , E)在ArrayList中的指定位置index，保存对象element.  

Java代码    
  1. public   void  add( int  index, E element) {  
  2.   
  3.          //检测指定位置的合法性   
  4.      if  (index > size || index <  0 )  
  5.          throw   new  IndexOutOfBoundsException(  
  6.          "Index: " +index+ ", Size: " +size);  
  7.   
  8.     ensureCapacity(size+ 1 );  
  9.           
  10.          //将数组容器elementData中从index位置开始的元素，依次往后移动一个位置   
  11.          //也就是说经过arraycopy()后，index位置被空出来   
  12.     System.arraycopy(elementData, index, elementData, index +  1 ,  
  13.              size - index);  
  14.   
  15.          //将对象element存储到数组容器的index位置上   
  16.     elementData[index] = element;  
  17.     size++;  
  18. }  
Java代码     收藏代码
  1. public   void  add( int  index, E element) {  
  2.   
  3.          //检测指定位置的合法性   
  4.      if  (index > size || index <  0 )  
  5.          throw   new  IndexOutOfBoundsException(  
  6.          "Index: " +index+ ", Size: " +size);  
  7.   
  8.     ensureCapacity(size+ 1 );  
  9.           
  10.          //将数组容器elementData中从index位置开始的元素，依次往后移动一个位置   
  11.          //也就是说经过arraycopy()后，index位置被空出来   
  12.     System.arraycopy(elementData, index, elementData, index +  1 ,  
  13.              size - index);  
  14.   
  15.          //将对象element存储到数组容器的index位置上   
  16.     elementData[index] = element;  
  17.     size++;  
  18. }  





3. remove(int) | remove(Object) | fastRemove(int) | removeRange(int,int)分析  

  remove(int)用于删除ArrayList数组容器中指定位置int上的元素，并返回此元素.  

Java代码    
  1. public  E remove( int  index) {  
  2.   
  3.     RangeCheck(index);  
  4.   
  5.     modCount++;  
  6.   
  7.     E oldValue = elementData[index];  
  8.          //numMoved需要移动的元素个数，也就是index后面的所有的元素个数   
  9.      int  numMoved = size - index -  1 ;  
  10.   
  11.          //将index后面的所有元素全部往前依次移动一个位置   
  12.      if  (numMoved >  0 )  
  13.         System.arraycopy(elementData, index+ 1 , elementData, index,  
  14.                  numMoved);  
  15.   
  16.          //经过arraycopy的移位，数组容器的最个位置被腾空，   
  17.          //但是仍然持有某个对象的引用，需要把这个多余的引用置为null.   
  18.         elementData[--size] =  null ;  // Let gc do its work   
  19.   
  20.      return  oldValue;  
  21. }  
Java代码     收藏代码
  1. public  E remove( int  index) {  
  2.   
  3.     RangeCheck(index);  
  4.   
  5.     modCount++;  
  6.   
  7.     E oldValue = elementData[index];  
  8.          //numMoved需要移动的元素个数，也就是index后面的所有的元素个数   
  9.      int  numMoved = size - index -  1 ;  
  10.   
  11.          //将index后面的所有元素全部往前依次移动一个位置   
  12.      if  (numMoved >  0 )  
  13.         System.arraycopy(elementData, index+ 1 , elementData, index,  
  14.                  numMoved);  
  15.   
  16.          //经过arraycopy的移位，数组容器的最个位置被腾空，   
  17.          //但是仍然持有某个对象的引用，需要把这个多余的引用置为null.   
  18.         elementData[--size] =  null ;  // Let gc do its work   
  19.   
  20.      return  oldValue;  
  21. }  


remove(Object)删除指定的对象Object，在数组容器中，需要特别处理null对象，过程都是，首先在数组容器中循环查找某个对象，如果查找到则调用fastRemove()进行删除。  

Java代码    
  1. public   boolean  remove(Object o) {  
  2.      if  (o ==  null ) {  
  3.              for  ( int  index =  0 ; index < size; index++)  
  4.          if  (elementData[index] ==  null ) {  
  5.             fastRemove(index);  
  6.              return   true ;  
  7.         }  
  8.     }  else  {  
  9.              //注意比较两个对象是否相等调用的是equals()，   
  10.              //如果此类对象没有重写equals（)   
  11.              //比较的是是否引用同一个对象，如果有重写，将比较对象内部状态.   
  12.          for  ( int  index =  0 ; index < size; index++)  
  13.          if  (o.equals(elementData[index])) {  
  14.             fastRemove(index);  
  15.              return   true ;  
  16.         }  
  17.         }  
  18.      return   false ;  
  19.     }  
Java代码     收藏代码
  1. public   boolean  remove(Object o) {  
  2.      if  (o ==  null ) {  
  3.              for  ( int  index =  0 ; index < size; index++)  
  4.          if  (elementData[index] ==  null ) {  
  5.             fastRemove(index);  
  6.              return   true ;  
  7.         }  
  8.     }  else  {  
  9.              //注意比较两个对象是否相等调用的是equals()，   
  10.              //如果此类对象没有重写equals（)   
  11.              //比较的是是否引用同一个对象，如果有重写，将比较对象内部状态.   
  12.          for  ( int  index =  0 ; index < size; index++)  
  13.          if  (o.equals(elementData[index])) {  
  14.             fastRemove(index);  
  15.              return   true ;  
  16.         }  
  17.         }  
  18.      return   false ;  
  19.     }  



fastRemove(int index)是相对于remove(int index)来说的，因为不需要进行index合法性检查和返回被删除的元素，所以它可以称为fast remove.fastRemove是private不能被外界访问，只是在remove(Object o)中被调用，因为remove(Object o)在调用fastRemove()时候已经确定了此对象的确存在才进行fastRemove()，所以是安全的，不需要检查。  

Java代码    
  1. private   void  fastRemove( int  index) {  
  2.        modCount++;  
  3.         int  numMoved = size - index -  1 ;  
  4.         if  (numMoved >  0 )  
  5.            System.arraycopy(elementData, index+ 1 , elementData, index,   
  6.                             numMoved);  
  7.        elementData[--size] =  null ;  // Let gc do its work   
  8.  }  
Java代码     收藏代码
  1. private   void  fastRemove( int  index) {  
  2.        modCount++;  
  3.         int  numMoved = size - index -  1 ;  
  4.         if  (numMoved >  0 )  
  5.            System.arraycopy(elementData, index+ 1 , elementData, index,   
  6.                             numMoved);  
  7.        elementData[--size] =  null ;  // Let gc do its work   
  8.  }  




removeRange(int, int)用于删除数组容器中指定下标范围内的元素  

Java代码    
  1.     protected   void  removeRange( int  fromIndex,  int  toIndex) {  
  2. modCount++;  
  3. int  numMoved = size - toIndex;  
  4.         //将从toIndex开始的元素依次拷贝到fromIndex位置上。   
  5.        System.arraycopy(elementData, toIndex, elementData, fromIndex,  
  6.                         numMoved);  
  7.   
  8. // Let gc do its work   
  9.         //newSize为删除指定范围元素后，容器中所剩下的元素个数。   
  10. int  newSize = size - (toIndex-fromIndex);  
  11.         //将持有多余引用的元素位置(从size-1到newSize - 1)置为null，   
  12.         //让GC能够及时回收垃圾对象.   
  13. while  (size != newSize)  
  14.     elementData[--size] =  null ;  
  15.    }  
Java代码     收藏代码
  1.     protected   void  removeRange( int  fromIndex,  int  toIndex) {  
  2. modCount++;  
  3. int  numMoved = size - toIndex;  
  4.         //将从toIndex开始的元素依次拷贝到fromIndex位置上。   
  5.        System.arraycopy(elementData, toIndex, elementData, fromIndex,  
  6.                         numMoved);  
  7.   
  8. // Let gc do its work   
  9.         //newSize为删除指定范围元素后，容器中所剩下的元素个数。   
  10. int  newSize = size - (toIndex-fromIndex);  
  11.         //将持有多余引用的元素位置(从size-1到newSize - 1)置为null，   
  12.         //让GC能够及时回收垃圾对象.   
  13. while  (size != newSize)  
  14.     elementData[--size] =  null ;  
  15.    }  



4. get(int)  

get(int)用于获取ArrayList指定位置的元素，就是从数组中指定位置上取元素。  

Java代码    
  1. public  E get( int  index) {  
  2.   
  3.          //RangeCheck(index)用于检查index在数组元素中位置是否合法(必须index < size)   
  4.     RangeCheck(index);  
  5.   
  6.      return  elementData[index];  
  7. }  
Java代码     收藏代码
  1. public  E get( int  index) {  
  2.   
  3.          //RangeCheck(index)用于检查index在数组元素中位置是否合法(必须index < size)   
  4.     RangeCheck(index);  
  5.   
  6.      return  elementData[index];  
  7. }  

ArrayList类源码分析


更多文章、技术交流、商务合作、联系博主

微信扫码或搜索：z360901061

微信扫一扫加我为好友

QQ号联系： 360901061

您的支持是博主写作最大的动力，如果您喜欢我的文章，感觉我的文章对您有帮助，请用微信扫描下面二维码支持博主2元、5元、10元、20元等您想捐的金额吧，狠狠点击下面给点支持吧，站长非常感激您！手机微信长按不能支付解决办法：请将微信支付二维码保存到相册，切换到微信，然后点击微信右上角扫一扫功能，选择支付二维码完成支付。

【本文对您有帮助就好】元

您的支持是博主写作最大的动力，如果您喜欢我的文章，感觉我的文章对您有帮助，请用微信扫描上面二维码支持博主2元、5元、10元、自定义金额等您想捐的金额吧，站长会非常 感谢您的哦！！！

发表我的评论
最新评论 总共0条评论