WEB开发网
开发学院软件开发Java 集合类库(三):揭秘 ArrayList 容量的动态增加 阅读

集合类库(三):揭秘 ArrayList 容量的动态增加

 2009-09-18 00:00:00 来源:WEB开发网   
核心提示:ArrayList 和数组几乎没有区别,唯一的不同就在与ArrayList的容量可以根据添加的元素数量自动的增加,集合类库(三):揭秘 ArrayList 容量的动态增加, 做到这一点的原因就在于ArrayList封装了一个动态分配的对象数组: Java代码//ArrayList的内部数组publicclassArra

ArrayList 和数组几乎没有区别,唯一的不同就在与ArrayList的容量可以根据添加的元素数量自动的增加。

做到这一点的原因就在于ArrayList封装了一个动态分配的对象数组:

Java代码  

//ArrayList的内部数组 
public class ArrayList<E>{ 
     private transient E[] elementData; //存储数据的数组 
    ...... 
}

当我们初始化一个ArrayList的时候,其实内部的数组elementData就已经默认开辟了10个单位的空间。

Java代码   

//ArrayList的初始化 
public class ArrayList<E>{ 
    public ArrayList() { 
    this(10); //默认大小10个单位 
    } 
    public ArrayList(int initialCapacity) { 
       super(); 
       if (initialCapacity < 0) 
           throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); 
       this.elementData = (E[])new Object[initialCapacity];//开辟10个单位的数组空间 
    } 
}

虽然内部默认的数组已经有10个单位空间,但是这个时候的ArrayList.size()仍然为0。size()函数返回的是ArrayList类的私有数据size,而且没有赋初值,那么Java会给予默认的初值0。

Java代码   

//ArrayList的容量大小 
public class ArrayList<E>{ 
   private int size; //默认的值为0 
   public int size() { //返回容量的大小 
  return size; 
   } 
}

现在我们正式揭秘这个内部自动增加的秘密:

(1) 首先用ensureCapacity方法来确保新加入一个数据后(size+1)内部数组容量够用,其核心过程是:

第一步:如果内部数组原容量够用,则不另外增加内部数组容量,用原内部数组继续存储数据。否则扩大容量至原容量的1.5倍,如果此时新扩大的容量还是小于最小需求的容量,则将容量扩大到最小需求量。

第二步:如果新容量扩大以后,则根据新容量来重新创建新数组。

第三步:按顺序把原来数组中的数据拷贝进新数组

(2) 存储新数据,并记录新容量(size++)。

Java代码   

//ArrayList的自动增加 
public boolean add(E o) { 
 ensureCapacity(size + 1); //确保添加一个新数据的容量足够(如果容量不够,则开辟新数组空间) 
 elementData[size++] = o;//扩大容量后,添加新数据并将原容量+1 
 return true; 
} 
//如有必要,增加此 ArrayList 实例的容量,以确保它至少能够容纳最小容量参数所指定的元素数。 
public void ensureCapacity(int minCapacity) { 
 modCount++; 
 int oldCapacity = elementData.length; 
 //扩大容量的核心逻辑 
    if (minCapacity > oldCapacity) { 
   Object oldData[] = elementData; //记录原始数组,便于后面的数据转移操作。 
   int newCapacity = (oldCapacity * 3)/2 + 1; 
     if (newCapacity < minCapacity) 
        newCapacity = minCapacity; 
   //按照新容量,重新开辟elementData 的连续内存空间,并拷贝原始数据 
      elementData = (E[])new Object[newCapacity]; 
   System.arraycopy(oldData, 0, elementData, 0, size); 
 } 
  }

好了,一个动态增加的过程就是这样了,这些大师写的东西太棒了。

Tags:集合 揭秘 ArrayList

编辑录入:爽爽 [复制链接] [打 印]
赞助商链接