欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java集合框架ArrayList源码分析(一)

程序员文章站 2024-03-13 13:28:09
arraylist底层维护的是一个动态数组,每个arraylist实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向 arrayli...

arraylist底层维护的是一个动态数组,每个arraylist实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向 arraylist 中不断添加元素,其容量也自动增长。

 arraylist不是同步的(也就是说不是线程安全的),如果多个线程同时访问一个arraylist实例,而其中至少一个线程从结构上修改了列表,那么它必须保持外部同步,在多线程环境下,可以使用collections.synchronizedlist方法声明一个线程安全的arraylist,例如:
list arraylist = collections.synchronizedlist(new arraylist());
下面通过arraylist的源码来分析其原理。
1、arraylist的构造方法:arraylist提供了三种不同的构造方法
1) arraylist(),构造一个初始容量为 10 的空列表。
2) arraylist(int initialcapacity),构造一个具有指定初始容量的空列表。
3) arraylist(collection<? extends e> c),构造一个包含指定 collection 的元素的列表,这些元素是按照该 collection 的迭代器返回它们的顺序排列的。

源码如下: 

private transient object[] elementdata;

public arraylist(int initialcapacity) {

  super();

  if (initialcapacity < 0)

    throw new illegalargumentexception("illegal capacity: "+ initialcapacity);

  this.elementdata = new object[initialcapacity]; //生成一个长度为10的object类型的数组

 }

 

 

 public arraylist() {

  this(10); //调用arraylist(int i)

 }<br><br>

 public arraylist(collection<? extends e> c) {

    elementdata = c.toarray();  //返回包含此 collection 中所有元素的数组

  size = elementdata.length;

  // c.toarray might (incorrectly) not return object[] (see 6260652)

  if (elementdata.getclass() != object[].class)

   elementdata = arrays.copyof(elementdata, size, object[].class); //复制指定的数组,返回包含相同元素和长度的object类型的数组

 }

当采用不带参数的构造方法arraylist()生成一个集合对象时,其实是在底层调用arraylist(int initialcapacity)这一构造方法生产一个长度为10的object类型的数组。当采用带有集合类型参数的构造方法时,在底层生成一个包含相同的元素和长度的object类型的数组。 

2、add方法:arraylist提供了两种添加元素的add方法
1) add(e e),将指定的元素添加到此列表的尾部。
2) add(int index, e e),将指定的元素插入此列表中的指定位置。向右移动当前位于该位置的元素(如果有)以及所有后续元素(将其索引加 1)private int size;

public boolean add(e e) {

  ensurecapacity(size + 1); // 扩大数组容量

  elementdata[size++] = e;  //将元素e添加到下标为size的object数组中,并且执行size++

  return true;

  }

 

 public void add(int index, e element) {

  if (index > size || index < 0) //如果指定要插入的数组下标超过数组容量或者指定的下标小于0,抛异常

    throw new indexoutofboundsexception("index: "+index+", size: "+size);

 

  ensurecapacity(size+1); // 扩大数组容量

  system.arraycopy(elementdata, index, elementdata, index + 1,size - index); //从指定源数组中复制一个数组,复制从指定的位置开始,到目标数组的指定位置结束。<br>                                          // elementdata --- 源数组  index --- 源数组中的起始位置  <br>                                          // elementdata --- 目标数组 index+1 --- 目标数组中的起始位置<br>                                          // size - index --- 要复制的数组元素的数量

  elementdata[index] = element; //将要添加的元素放到指定的数组下标处

  size++;

  }

public void ensurecapacity(int mincapacity) {

  modcount++;

  int oldcapacity = elementdata.length; //原数组的容量

  if (mincapacity > oldcapacity) {

    object olddata[] = elementdata;

    int newcapacity = (oldcapacity * 3)/2 + 1; //定义新数组的容量,为原数组容量的1.5倍+1

      if (newcapacity < mincapacity)

    newcapacity = mincapacity;

      // mincapacity is usually close to size, so this is a win:

      elementdata = arrays.copyof(elementdata, newcapacity); //复制指定的数组,返回新数组的容量为newcapacity

  }

  }

如果集合中添加的元素超过了10个,那么arraylist底层会新生成一个数组,长度为原数组的1.5倍+1,并将原数组中的元素copy到新数组中,并且后续添加的元素都会放在新数组中,当新数组的长度无法容纳新添加的元素时,重复该过程。这就是集合添加元素的实现原理。

3、get方法:
 1) get(int index),返回此列表中指定位置上的元素。

public e get(int index) {
  rangecheck(index); //检查传入的指定下标是否合法
 
  return (e) elementdata[index]; //返回数组下标为index的数组元素

  }
private void rangecheck(int index) {
  if (index >= size) //如果传入的下标大于或等于集合的容量,抛异常
    throw new indexoutofboundsexception(
    "index: "+index+", size: "+size);

  }

4、remove方法:
1) e remove(int index),移除此列表中指定位置上的元素。向左移动所有后续元素(将其索引减 1)。
2) boolean remove(object o),移除此列表中首次出现的指定元素(如果存在)。如果列表不包含此元素,则列表不做改动,返回boolean值。 

public e remove(int index) {

  rangecheck(index); //检查指定的下标是否合法

 

  modcount++;

  e oldvalue = (e) elementdata[index]; //获取指定下标的数组元素

 

  int nummoved = size - index - 1; //要移动的元素个数

  if (nummoved > 0)

    system.arraycopy(elementdata, index+1, elementdata, index, nummoved); //移动数组元素

  elementdata[--size] = null; // let gc do its work

 

  return oldvalue;

  }

 

 public boolean remove(object o) {

  if (o == null) { //如果传入的参数为null

      for (int index = 0; index < size; index++)

    if (elementdata[index] == null) { //移除首次出现的null

      fastremove(index);

      return true;

    }

  } else {

    for (int index = 0; index < size; index++)

    if (o.equals(elementdata[index])) {

      fastremove(index);

      return true;

    }

    }

  return false;

  }

 

private void fastremove(int index) { //移除指定位置的元素,实现方法类似remove(int i)

    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

  }

5、clone方法:
1) object clone(),返回此arraylist实例的浅表副本(不复制这些元素本身) 。

public object clone() {
  try {
    arraylist<e> v = (arraylist<e>) super.clone(); //调用object类的clone方法返回一个arraylist对象
    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();

  }

  }

以上通过对arraylist部分关键源码的分析,知道了arraylist底层的实现原理,关于arraylist源码有以下几点几点总结:
 1) arraylist 底层是基于数组来实现的,可以通过下标准确的找到目标元素,因此查找的效率高;但是添加或删除元素会涉及到大量元素的位置移动,效率低。
 2) arraylist提供了三种不同的构造方法,无参数的构造方法默认在底层生成一个长度为10的object类型的数组,当集合中添加的元素个数大于10,数组会自动进行扩容,即生成一个新的数组,并将原数组的元素放到新数组中。
3) ensurecapacity方法对数组进行扩容,它会生成一个新数组,长度是原数组的1.5倍+1,随着向arraylist中不断添加元素,当数组长度无法满足需要时,重复该过程。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。