前言

本文主要給大家介紹了關(guān)于Java中Arraylist動(dòng)態(tài)擴(kuò)容的相關(guān)內(nèi)容，分享出來供大家參考學(xué)習(xí)，下面話不多說了，來一起看看詳細(xì)的介紹吧。

ArrayList 概述

ArrayList是基于數(shù)組實(shí)現(xiàn)的，是一個(gè)動(dòng)態(tài)數(shù)組，其容量能自動(dòng)增長。ArrayList不是線程安全的，只能用在單線程環(huán)境下。實(shí)現(xiàn)了Serializable接口，因此它支持序列化，能夠通過序列化傳輸；實(shí)現(xiàn)了RandomAccess接口，支持快速隨機(jī)訪問，實(shí)際上就是通過下標(biāo)序號(hào)進(jìn)行快速訪問；實(shí)現(xiàn)了Cloneable接口，能被克隆。

動(dòng)態(tài)擴(kuò)容

一 初始化

首先有三種方式來初始化：

public ArrayList();

默認(rèn)的構(gòu)造器，將會(huì)以默認(rèn)的大小來初始化內(nèi)部的數(shù)組

public ArrayList(Collection<? extends E> c)

用一個(gè)ICollection對(duì)象來構(gòu)造，并將該集合的元素添加到ArrayList

public ArrayList(int initialCapacity) 

用指定的大小來初始化內(nèi)部的數(shù)組

后兩種方式都可以理解，通過創(chuàng)造對(duì)象，或指定大小來初始化內(nèi)部數(shù)據(jù)即可。

那我們來重點(diǎn)關(guān)注一下無參數(shù)構(gòu)造器的實(shí)現(xiàn)過程：

/**
  * Constructs an empty list with an initial capacity of ten.
  */
 public ArrayList() {
  // DEFAULTCAPACITY_EMPTY_ELEMENTDATA是空數(shù)組
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
 }

 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

可以看出它的默認(rèn)數(shù)組為長度為0。而在之前JDK1,6中，無參數(shù)構(gòu)造器代碼是初始長度為10。

JDK6代碼這樣的：

public ArrayList() {
 this(10);
 }
 public ArrayList(int initialCapacity) {
 super();
  if (initialCapacity < 0)
   throw new IllegalArgumentException("Illegal Capacity: "+
            initialCapacity);
 this.elementData = new Object[initialCapacity];
 }

接下來，要擴(kuò)容的話，肯定是在ArrayList.add 方法中。我們來看一下具體實(shí)現(xiàn)。

二  確保內(nèi)部容量

我們以無參數(shù)構(gòu)造為例， 初始化時(shí)，數(shù)組長度為0. 那我現(xiàn)在要添加數(shù)據(jù)了，數(shù)組的長度是怎么變化的？

 public boolean add(E e) {
  //確保內(nèi)部容量(通過判斷，如果夠則不進(jìn)行操作；容量不夠就擴(kuò)容來確保內(nèi)部容量)
  ensureCapacityInternal(size + 1); // ①Increments modCount!!
  elementData[size++] = e;//②
  return true;
 }

① ensureCapacityInternal方法名的英文大致是“確保內(nèi)部容量”，size表示的是執(zhí)行添加之前的元素個(gè)數(shù)，并非ArrayList的容量，容量應(yīng)該是數(shù)組elementData的長度。ensureCapacityInternal該方法通過將現(xiàn)有的元素個(gè)數(shù)數(shù)組的容量比較?？慈绻枰獢U(kuò)容，則擴(kuò)容。

②是將要添加的元素放置到相應(yīng)的數(shù)組中。

下面具體看 ensureCapacityInternal(size + 1);

// ① 是如何判斷和擴(kuò)容的。private void ensureCapacityInternal(int minCapacity) {
  //如果實(shí)際存儲(chǔ)數(shù)組 是空數(shù)組，則最小需要容量就是默認(rèn)容量
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
   minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  }

  ensureExplicitCapacity(minCapacity);
 }

 private void ensureExplicitCapacity(int minCapacity) {
  modCount++;
  //如果數(shù)組（elementData)的長度小于最小需要的容量（minCapacity）就擴(kuò)容
  if (minCapacity - elementData.length > 0)
   grow(minCapacity);
 }
 /**
  * Default initial capacity.
  */
 private static final int DEFAULT_CAPACITY = 10;

以上，elementData是用來存儲(chǔ)實(shí)際內(nèi)容的數(shù)組。minExpand 是最小擴(kuò)充容量。DEFAULTCAPACITY_EMPTY_ELEMENTDATA共享的空數(shù)組實(shí)例用于默認(rèn)大小的空實(shí)例。根據(jù)傳入的最小需要容量minCapacity來和數(shù)組的容量長度對(duì)比，若minCapactity大于或等于數(shù)組容量，則需要進(jìn)行擴(kuò)容。

三 擴(kuò)容

/*
 *增加容量，以確保它至少能容納
 *由最小容量參數(shù)指定的元素?cái)?shù)。
 * @param mincapacity所需的最小容量
 */
 private void grow(int minCapacity) {
  // overflow-conscious code
  int oldCapacity = elementData.length;
  //>>位運(yùn)算，右移動(dòng)一位。 整體相當(dāng)于newCapacity =oldCapacity + 0.5 * oldCapacity 
  // jdk1.7采用位運(yùn)算比以前的計(jì)算方式更快
  int newCapacity = oldCapacity + (oldCapacity >> 1);
  if (newCapacity - minCapacity < 0)
   newCapacity = minCapacity;
  //jdk1.7這里增加了對(duì)元素個(gè)數(shù)的最大個(gè)數(shù)判斷,jdk1.7以前是沒有最大值判斷的，MAX_ARRAY_SIZE 為int最大值減去8（不清楚為什么用這個(gè)值做比較）
  if (newCapacity - MAX_ARRAY_SIZE > 0)
   newCapacity = hugeCapacity(minCapacity);
  // 最重要的復(fù)制元素方法
  elementData = Arrays.copyOf(elementData, newCapacity);
 }

綜上所述，ArrayList相當(dāng)于在沒指定initialCapacity時(shí)就是會(huì)使用延遲分配對(duì)象數(shù)組空間，當(dāng)?shù)谝淮尾迦朐貢r(shí)才分配10（默認(rèn)）個(gè)對(duì)象空間。假如有20個(gè)數(shù)據(jù)需要添加，那么會(huì)分別在第一次的時(shí)候，將ArrayList的容量變?yōu)?0 (如下圖一)；之后擴(kuò)容會(huì)按照1.5倍增長。也就是當(dāng)添加第11個(gè)數(shù)據(jù)的時(shí)候，Arraylist繼續(xù)擴(kuò)容變?yōu)?0*1.5=15(如下圖二)；當(dāng)添加第16個(gè)數(shù)據(jù)時(shí)，繼續(xù)擴(kuò)容變?yōu)?5 * 1.5 =22個(gè)(如下圖四)。：

向數(shù)組中添加第一個(gè)元素時(shí)，數(shù)組容量為10.

向數(shù)組中添加到第10個(gè)元素時(shí)，數(shù)組容量仍為10.

向數(shù)組中添加到第11個(gè)元素時(shí)，數(shù)組容量擴(kuò)為15.

向數(shù)組中添加到第16個(gè)元素時(shí)，數(shù)組容量擴(kuò)為22.

每次擴(kuò)容都是通過Arrays.copyOf(elementData, newCapacity) 這樣的方式實(shí)現(xiàn)的。

對(duì)比和總結(jié)：

本文介紹了 ArrayList動(dòng)態(tài)擴(kuò)容的全過程。如果通過無參構(gòu)造的話，初始數(shù)組容量為0，當(dāng)真正對(duì)數(shù)組進(jìn)行添加時(shí)，才真正分配容量。每次按照1.5倍（位運(yùn)算）的比率通過copeOf的方式擴(kuò)容。 在JKD1.6中實(shí)現(xiàn)是，如果通過無參構(gòu)造的話，初始數(shù)組容量為10，每次通過copeOf的方式擴(kuò)容后容量為原來的1.5倍，以上就是動(dòng)態(tài)擴(kuò)容的原理。

好了，以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作能帶來一定的幫助，如果有疑問大家可以留言交流，謝謝大家對(duì)腳本之家的支持。

參考資料：http://blog.csdn.net/u010176014/article/details/52073339

最新評(píng)論