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

基于ArrayList常用方法的源码全面解析

程序员文章站 2023-12-16 13:09:52
我相信几乎所有的同学在大大小小的笔试、面试过程中都会被问及arraylist与linkedlist之间的异同点。稍有准备的人这些问题早已烂熟于心,前者基于数组实现,后者基于...

我相信几乎所有的同学在大大小小的笔试、面试过程中都会被问及arraylist与linkedlist之间的异同点。稍有准备的人这些问题早已烂熟于心,前者基于数组实现,后者基于链表实现;前者随机方法速度快删除和插入指定位置速度慢,后者随机访问速度慢删除和插入指定位置速度快;两者都是线程不安全的;列表与数组之间的区别等等。

列表与数组之间很大的一个区别就是:数组在其初始化就需要给它确定大小不能动态扩容,而列表则可以动态扩容。arraylist是基于数组实现的,那么它是如何实现的动态扩容呢?

对于arraylist的初始化有三种方式:

对于第一种默认的构造方法,arraylist并没有初始化容量大小,而是将列表的元素数据引用指向了一个空数组。

private transient object[] elementdata;
private static final object[] empty_elementdata = {};
//1.arraylist默认构造方法
public arraylist() {  
  super();
  this.elementdata = empty_elementdata;
}

与jdk1.6不同的是,jdk1.6即时是在调用默认的构造方法时,也会初始化容量大小,jdk1.7当然会带来一定的好处,如果初始化而不使用就白白浪费了存储空间,等到添加的时候再初始化容量大小即可。

与jdk1.6不同的是,jdk1.6即时是在调用默认的构造方法时,也会初始化容量大小,jdk1.7当然会带来一定的好处,如果初始化而不使用就白白浪费了存储空间,等到添加的时候再初始化容量大小即可。

//jdk1.6 arraylist
public arraylist() {
  this(10);
}  

对于第二种构造方法,则直接创建一个指定大小的数组,将列表的元素数组引用指向它。

//2.arraylist带有初始化大小的构造方法
public arraylist(int initialcapacity) {
  super();
  if (initialcapacity < 0)
    throw new illegalargumentexception("illegal capacity: "+
                      initialcapacity);
  this.elementdata = new object[initialcapacity];
}

第三种构造方法,能将一个集合作为参数传递,但集合中的元素必须继承自arraylist中的元素。

//3.可将一个集合作为arraylist的参数构造成arraylist
public arraylist(collection<? extends e> c) {
  elementdata = c.toarray();  //将集合转换为数组
  size = elementdata.length;  //集合中的元素大小
  // c.toarray might (incorrectly) not return object[] (see 6260652) 这里是个bug,参考http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652
  if (elementdata.getclass() != object[].class)
    elementdata = arrays.copyof(elementdata, size, object[].class);
}

上面提到了一个bug,也就是说将一个集合转换为数组的时候可能错误地不会返回object[],举例说明。

package com.algorithm.sort;

import java.util.arraylist;
import java.util.arrays;
import java.util.list;

/**
 * bug编号:6260652。toarray有可能不会返回object[]
 * created by yulinfeng on 2017/6/26.
 */
public class test {
  public static void main(string[] args) {
    correctly();
    incorrectly();
  }
  
  /**
   * 返回object[]
   */
  private static void correctly() {
    list<string> list = new arraylist<string>();
    list.add("test");
    system.out.println(list.getclass());
    object[] objarray = list.toarray();
    system.out.println(objarray.getclass());
  }
  /**
   * 不返回object[]
   */
  private static void incorrectly() {
    list<string> list = arrays.aslist("test");
    system.out.println(list.getclass());
    object[] objarray = list.toarray();
    system.out.println(objarray.getclass());
  }
}

运行结果:

基于ArrayList常用方法的源码全面解析

上面的这个例子就说明了toarray并不一定总是返回object[],返回的object[]时,object元素就不能插入,故jdk在“6260652”中修复了这个bug。

接下来看元素插入以及删除等其它方法。

//arraylist#add
public boolean add(e e) {
  ensurecapacityinternal(size + 1); //确保容量是否充足
  elementdata[size++] = e;  //将元素添加至数组
  return true;
}
//arraylist#ensurecapacityinternal
private void ensurecapacityinternal(int mincapacity) {
  if (elementdata == empty_elementdata) {
    mincapacity = math.max(default_capacity, mincapacity);   //如果此时还没有初始化列表容量大小,则对其初始化,默认容量为10
  }
  ensureexplicitcapacity(mincapacity); //检查容量是否充足
}
//arraylist#ensureecplicitcapacity
private void ensureexplicitcapacity(int mincapacity) {
  modcount++;  //注意此变量
  if (mincapacity - elementdata.length > 0)
    grow(mincapacity);  //容量不够则进行扩容
}

在ensureecplicitcapacity方法中有一个modcount(modify count)变量进行了自增。

protected transient int modcount = 0;

这个变量不仅在add方法中会自增,只要是在增加或者删除等对arraylist结构产生了变化都会记录加1,这样做的原因和多线程下iterator迭代器遍历有关。在abstractlist$itr中也有一个变量与之对应。

//abstractlist$itr
int expectedmodcount = modcount;

在abstractlist$itr#next中调用了checkforcomodification方法。

//abstractlist$itr#checkforcomodification
final void checkforcomodification() {
  if (modcount != expectedmodcount)
    throw new concurrentmodificationexception();
}

如果当前运行环境是单线程,不论对列表进行何种操作何时增加、修改、删除等,excpectedmodcount总是会等于modcount,但是如果当前运行环境是多线程,很有可能一个线程在迭代遍历,而另一个线程在对其进行新增或者修改等,jdk则不允许这么做,此时则会抛出concurrentmodificationexception异常,这就是modcount变量在此起的作用。

回到arraylist#add方法,当列表容量不足时,此时会调用grow方法进行扩容。

//arraylist#grow
private void grow(int mincapacity) {
  int oldcapacity = elementdata.length;
  int newcapacity = oldcapacity + (oldcapacity >> 1);  //扩容策略为,每次新增容量的大小为旧容量的一半。也就是说如果默认容量为10,则第一次扩容大小为10 / 2 = 5,第二次扩容大小为15 / 2 = 7。
  if (newcapacity - mincapacity < 0)
    newcapacity = mincapacity;  //扩容策略扩得太小
  if (newcapacity - max_array_size > 0)  //扩容策略扩得太大,大于最大数组大小时,最多等于integer.max_value
    newcapacity = hugecapacity(mincapacity);
  
  elementdata = arrays.copyof(elementdata, newcapacity);
}

arraylist获取指定索引位置的元素get方法。

public e get(int index) {
  rangecheck(index);  //检查索引是否越界
  return elementdata(index);
}

由于arraylist是由基于数组实现,故此方法较为简单,判断是否越界,没有则根据数组下标来索引返回元素即可。remove方法删除指定位置的元素。 

//arraylist#remove
public e remove(int index) {
  rangecheck(index);  //检查索引是否越界
  modcount++;  //记录modcount,上面已提及
  e oldvalue = elementdata(index);  //取出指定索引元素
  int nummoved = size - index - 1;  //移动的元素个数
  if (nummoved > 0)
    system.arraycopy(elementdata, index+1, elementdata, index, nummoved);
  elementdata[--size] = null; //将最后一个数组元素置为null,方便gc

  return oldvalue;
}

代码比较简单,同样也体现了基于数组实习的arraylist在删除指定元素时的效率问题。

以上这篇基于arraylist常用方法的源码全面解析就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持。

上一篇:

下一篇: