`

ArrayList类源码分析

 
阅读更多

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. }  
分享到：
| LinkedList源代码分析
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    ArrayList源码分析(含jdk1.8).pdf

    在了解ArrayList的源码分析时，我们主要探讨其在Java Development Kit (JDK) 1.8中的实现。ArrayList是一个非常重要的集合框架，用于动态数组的实现，其功能类似于数组，但可以在运行时动态调整大小。它是一个非线程...

    ArrayList源码分析

    ### ArrayList源码分析 #### 一、概述 `ArrayList` 是 Java 集合框架中的一个重要的类，它实现了 `List` 接口，并且内部使用动态数组来存储元素。由于其灵活的特性（比如可以方便地增加或删除元素），`ArrayList` ...

    计算机后端-Java-Java核心基础-第24章 集合01 14. ArrayList的源码分析.avi

    计算机后端-Java-Java核心基础-第24章 集合01 14. ArrayList的源码分析.avi

    硬核ArrayList源码分析，答应我每天看一遍好么

    《硬核ArrayList源码分析——深入理解Java集合框架》 ArrayList是Java集合框架中的一个重要组成部分，它是基于动态数组实现的列表。在Java 1.8版本中，ArrayList的实现细节和内部工作原理对于理解其性能和行为至关...

    ArrayList源码分析.docx 等

    转换为其内部数组 `elementData`，然后根据转换后的数组长度设置 `size`。这里需要注意的是，如果 `c.toArray()` ...在面试中，深入理解 ArrayList 的源码和其与其他数据结构的区别是展示 Java 基础技能的重要方面。

    ArrayList的源码

    源码分析见我博文：http://blog.csdn.net/wabiaozia/article/details/50684556

    ArrayList源码.zip

    ArrayList是Java编程语言中最常用的集合...总之，这个“ArrayList源码.zip”文件是Java程序员学习和优化代码的宝贵资源，它揭示了ArrayList内部的工作机制，帮助我们提升编程技巧，更好地理解和利用这个强大的集合类。

    ArrayList源码分析_016.pdf

    ArrayList是Java集合框架中的一种重要实现，它是List接口的一个具体类，提供了动态数组的功能。ArrayList在内部使用一个Object类型的数组来存储元素，因此它支持快速的随机访问，这是由其实现了RandomAccess接口所...

    Java编程中ArrayList源码分析

    Java编程中ArrayList源码分析 Java编程中ArrayList源码分析是Java编程中一个重要的知识点，对于Java开发者来说，了解ArrayList的源码可以帮助他们更好地理解Java集合框架的实现机制，从而提高自己的编程水平。 ...

    Java中的ArrayList的底层源码解读、LinkedList、Vector的区别介绍

    能学到什么：ArrayList的源码分析，自动扩容和自动缩容的源码分析，相关参数的深度解析，从是什么，为什么，怎么做三个角度进行讲解，用通俗易懂的白话进行介绍，LinkedList和Vector以及ArrayList的区别以及使用场景...

    第二章 ArrayList源码解析1

    第二章 ArrayList源码解析 ArrayList是Java集合框架中的一种动态数组，它继承自AbstractList，并实现了List接口。ArrayList主要用于存储可变大小的对象列表，它的核心是通过一个Object类型的数组elementData来实现...

    ArrayList 源码深度解析

    ArrayList 源码深度解析 一、重新认识ArrayList 什么是ArrayList？ ArrayList是基于数组实现的List类，封装了一个动态再分配的Object数组，以达到可以动态增长和缩减的索引序列。 长啥样？ 如图，是一个长度为6，...

    Java集合框架ArrayList源码分析（一）

    《深入剖析Java集合框架ArrayList源码》 Java集合框架中的ArrayList是开发者常用的数据结构，它是一种基于动态数组实现的列表。ArrayList的特点在于它的内部结构、性能优化以及在并发环境下的处理方式。本文将深入...

    ArrayList扩容机制源码解析.md

    本资源根据个人学习和总结，主要介绍Java中ArrayList扩容机制源码的解析，主要包含文字和代码等内容，以源码的形式进行分析，详细介绍了ArrayList扩容机制的整个流程，特此将该资源分享

    关于 ArrayList get(0)的异常JDK源码跟进

    这篇博客主要探讨了当尝试通过`get(0)`获取ArrayList的第一个元素时可能出现的问题，并通过JDK源码分析了其原因。 首先，我们需要了解ArrayList的内部结构。ArrayList实际上是一个基于数组实现的列表，它维护了一个...

    Android+上百实例源码分析以及开源分析+集合打包3

    再者，"集合打包3"可能指的是针对Android中数据集合类的深度解析，包括ArrayList、LinkedList、HashMap、HashSet等。这些数据结构在Android应用中广泛使用，理解它们的底层实现原理和性能特性，能够帮助开发者选择最...

    Java源码分析Iterable.pdf

    Java源码分析Iterable Java源码分析Iterable是Java编程语言中一个基础组件的源码分析，Iterable是一个接口，它允许对象被迭代，例如foreach循环中的数组或集合。了解Iterable的源码，可以帮助开发者更好地理解Java...

Magicbox
Global site tag (gtag.js) - Google Analytics