`
yuyiming1986
  • 浏览: 63488 次
  • 性别: Icon_minigender_1
  • 来自: 成都
社区版块
存档分类
最新评论

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使用对象数组元素来作为内部实现的基础数据结构。

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


 
//默认情况下ArrayList实现依赖的数组长度为10
   public ArrayList() {
    	this(10);
   }

  

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



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

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

public void ensureCapacity(int minCapacity) {

	modCount++;
	int oldCapacity = elementData.length;
        
        //如果当前数组的实际容量(oldCapacity)比当前要求的容量要小(minCapacity)
        //就需要进行扩容,申请新的数组空间,大小为minCapacity,并将原来数组空间中的元素拷贝
        //到新的数组空间当中。        
	if (minCapacity > oldCapacity) {
	    Object oldData[] = elementData;
          
            //扩容因子为:1.5倍左右,每次需要扩容时,会将空间扩展为原来的1.5倍大小
	    int newCapacity = (oldCapacity * 3)/2 + 1;

            if (newCapacity < minCapacity)
		newCapacity = minCapacity;

	    elementData = (E[])new Object[newCapacity];
              
            //将数组元素转移到新申请的数组空间当中
	    System.arraycopy(oldData, 0, elementData, 0, size);
	}
}


  add(E)操作是向集合ArrayList中存储元素,在当前数组容器的尾部添加,不需要移动元素,返回true。
public boolean add(E o) {
        //调用ensureCapacity确保当前容量不小于(size + 1),size为容器中当前存储的实际元素个数.
	ensureCapacity(size + 1); 
        //将对象引用o保存到数组容器中,并++size.
	elementData[size++] = o;
	return true;
}


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

        //检测指定位置的合法性
	if (index > size || index < 0)
	    throw new IndexOutOfBoundsException(
		"Index: "+index+", Size: "+size);

	ensureCapacity(size+1);
        
        //将数组容器elementData中从index位置开始的元素,依次往后移动一个位置
        //也就是说经过arraycopy()后,index位置被空出来
	System.arraycopy(elementData, index, elementData, index + 1,
			 size - index);

        //将对象element存储到数组容器的index位置上
	elementData[index] = element;
	size++;
}




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

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

	RangeCheck(index);

	modCount++;

	E oldValue = elementData[index];
        //numMoved需要移动的元素个数,也就是index后面的所有的元素个数
	int numMoved = size - index - 1;

        //将index后面的所有元素全部往前依次移动一个位置
	if (numMoved > 0)
	    System.arraycopy(elementData, index+1, elementData, index,
			     numMoved);

        //经过arraycopy的移位,数组容器的最个位置被腾空,
        //但是仍然持有某个对象的引用,需要把这个多余的引用置为null.
      	elementData[--size] = null; // Let gc do its work

	return oldValue;
}

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

public boolean remove(Object o) {
	if (o == null) {
            for (int index = 0; index < size; index++)
		if (elementData[index] == null) {
		    fastRemove(index);
		    return true;
		}
	} else {
            //注意比较两个对象是否相等调用的是equals(),
            //如果此类对象没有重写equals()
            //比较的是是否引用同一个对象,如果有重写,将比较对象内部状态.
	    for (int index = 0; index < size; index++)
		if (o.equals(elementData[index])) {
		    fastRemove(index);
		    return true;
		}
        }
	return false;
    }


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

 private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index, 
                             numMoved);
        elementData[--size] = null; // Let gc do its work
  }



removeRange(int, int)用于删除数组容器中指定下标范围内的元素
 
    protected void removeRange(int fromIndex, int toIndex) {
	modCount++;
	int numMoved = size - toIndex;
        //将从toIndex开始的元素依次拷贝到fromIndex位置上。
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);

	// Let gc do its work
        //newSize为删除指定范围元素后,容器中所剩下的元素个数。
	int newSize = size - (toIndex-fromIndex);
        //将持有多余引用的元素位置(从size-1到newSize - 1)置为null,
        //让GC能够及时回收垃圾对象.
	while (size != newSize)
	    elementData[--size] = null;
    }


4.get(int)

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

public E get(int index) {

        //RangeCheck(index)用于检查index在数组元素中位置是否合法(必须index < size)
	RangeCheck(index);

	return elementData[index];
}

分享到:
评论

相关推荐

    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...

Global site tag (gtag.js) - Google Analytics