ArrayList 源碼解析(JDK1.7)
ps: 我思考了一下…想要不要發這篇部落格… 感覺作為一個初學者…發這種源碼解析… 尤其當做學習記錄這樣的東西來做…感覺沒有任何的重點可言… 不過思考了一下…反正估計也沒人看 (狗頭) 就發了吧
純屬個人 … emmm 萌新的學習經曆- -
大夥湊着看看吧…如果有錯 , 請指出…
快速導航
-
-
- ArrayList 源碼解析(JDK1.7)
-
- ArrayList的層次結構
-
- 接口
-
- Iterable (可疊代的)
- Collection (集合)
- List (清單)
- Cloneable (可拷貝的)
- Serializable (可序列化的)
- RandomAccess (随機通路)
- 抽象類
-
- AbstractCollection(抽象的集合)
- AbstractList (抽象的清單)
- 正餐 ArrayList (正主)
-
- 成員變量
- 執行個體方法
- 重要方法
- 内部的疊代器
- SubList
- 結束! ....
-
ArrayList的層次結構
接口
Iterable (可疊代的)
public interface Iterable<T> {
//沒啥好說的..獲得一個疊代器
Iterator<T> iterator();
}
Collection (集合)
public interface Collection<E> extends Iterable<E> {
int size(); //獲得集合大小
boolean isEmpty(); //判斷是否為空
boolean contains(Object o); //判斷集合内是否包含元素
Iterator<E> iterator(); //獲得集合的疊代器
Object[] toArray(); //将集合轉為Object數組
<T> T[] toArray(T[] a); //将結合轉為T數組
boolean add(E e); //添加一個元素
boolean containsAll(Collection<?> c); //是否包括了另外一個集合
boolean addAll(Collection<? extends E> c); //添加另外一個集合的所有元素
boolean retainAll(Collection<?> c); //保留c集合中的所有元素
void clear(); //将集合清空
// Object的方法 重寫
boolean equals(Object o);
int hashCode();
}
List (清單)
public interface List<E> extends Collection<E> {
//省略了從Collection 擴充的一些接口
//....
boolean addAll(int index, Collection<? extends E> c); //從index的位置處 插入一個集合
E get(int index); //通過index獲得值
E set(int index, E element); //設定值(修改)
void add(int index, E element); //在某個位置插入一個值
E remove(int index); //移除index位置的值
int indexOf(Object o); //查找o元素在清單中的位置
int lastIndexOf(Object o); //查找最後一個o出現的位置
ListIterator<E> listIterator(); //獲得清單的疊代器
ListIterator<E> listIterator(int index); //獲得從index開始的清單
List<E> subList(int fromIndex, int toIndex); //截取一個小的清單
}
Cloneable (可拷貝的)
public interface Cloneable { //是個用于标記的接口
//隻有實作了這個接口的類..才可以使用Object.Clone() 方法(動态方法) 對象.clone()
}
Serializable (可序列化的)
public interface Serializable {
//也是用于标記的接口..簽名
//實作了這個接口的類, 可序列化
}
RandomAccess (随機通路)
public interface RandomAccess {
//也是一個标記接口...用于加速随機通路..
//用于底層的優化..
}
抽象類
AbstractCollection(抽象的集合)
public abstract class AbstractCollection<E> implements Collection<E> {
//抽象類 ...沒啥好說的感覺... 主要是實作了 Collection的絕大部分方法..除了 iterator 和 size 方法沒實作
//這裡就分析一下它的private方法相關的東西 (以及 調用了這些方法的方法)
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; //注意..清單的容量最大值是不允許超過 Integer.MAX_VALUE - 8 ...原因是 說 有些VM 中會在清單裡面加入一些header work..可能會占用一些..
public Object[] toArray() {
// Estimate size of array; be prepared to see more or fewer elements
Object[] r = new Object[size()];
// 設計這個的時候...設計者的想法可能 size() 得到的是估計值..不是絕對的精确..
Iterator<E> it = iterator();
for (int i = 0; i < r.length; i++) {
if (! it.hasNext()) // fewer elements than expected
return Arrays.copyOf(r, i);
r[i] = it.next();
}
//走到這裡的條件是 r的大小 >= 清單的大小
//如果r的大小等于清單的大小..就會傳回r
//否則就是傳回 finishToArray方法.
return it.hasNext() ? finishToArray(r, it) : r;
}
public <T> T[] toArray(T[] a) {
// Estimate size of array; be prepared to see more or fewer elements
int size = size();
T[] r = a.length >= size ? a :
(T[])java.lang.reflect.Array
.newInstance(a.getClass().getComponentType(), size);
//這邊也是類似上面的方法.. 首先判斷 a元素大小夠不夠..如果不夠 先擴容
Iterator<E> it = iterator();
/**
如果 a 是 [1,2,3,4,5,6]
清單是 [2,3]
最後的傳回值 就是 a 為[2,3,null,4,5,6]...感覺好怪異
總的來說..調用這個方法之後, 信任傳回值比較好..傳入值有時改有時不會改
**/
for (int i = 0; i < r.length; i++) {
if (! it.hasNext()) { // 如果清單的值 是 數組小...
if (a == r) { //a原本就比估計的要大
r[i] = null; //最後一個元素設定為null...
} else if (a.length < i) { //r是調用反射生成的.. a的大小 < 清單的大小元素大小
return Arrays.copyOf(r, i); //壓縮掉r的大小
} else { //我覺得這種情況就很怪異
//r 是通過反射生成的..r的大小應該就是清單大小...能到這裡, 就說明了 清單的大小 < r的大小
//這個分支是 a的大小 >= 清單元素大小
//總結起來就是 : 調用的時候 a的大小 < 清單元素大小
//中間發生了未知的情況造成 清單元素瘋狂下降..下降到 a的大小 > 清單元素大小
System.arraycopy(r, 0, a, 0, i);
if (a.length > i) {
a[i] = null;
}
}
return a;
}
r[i] = (T)it.next();
}
//與上一個方法同理...
return it.hasNext() ? finishToArray(r, it) : r;
}
/*
進入這個方法的原因是 清單的實際元素數量 比 r要大
首先保留i 也就是index 下标..從r的第i個元素開始填充
然後将r進行擴容...遵照list的擴容方式.. 1.5倍的擴容
**/
private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
int i = r.length;
while (it.hasNext()) {
int cap = r.length;
if (i == cap) {
int newCap = cap + (cap >> 1) + 1;
// overflow-conscious code
if (newCap - MAX_ARRAY_SIZE > 0)
newCap = hugeCapacity(cap + 1);
r = Arrays.copyOf(r, newCap);
}
r[i++] = (T)it.next();
}
// trim if overallocated
return (i == r.length) ? r : Arrays.copyOf(r, i);
}
//防止擴容過大..
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError
("Required array size too large");
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
}
AbstractList (抽象的清單)
//開始慢慢複雜
//在抽象集合中沒有實作的2個方法 . 在這裡類中 實作了 具體的獲得疊代器的方法
// list 接口中的 get(int index) 方法沒有實作
// 當然 在這個類中. 其他的一些增删改(list接口中)的操作 都是 抛出UnsupportedOperationException的 , 隻能get..雖然沒有實作
//但是 它新加了自己的一些remove方法...
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
//已經被實作的方法..這裡都不介紹了 . 具體抽出一些新加入的東西
protected transient int modCount = 0; // 這個屬性 記錄着 集合的修改次數..主要用于 疊代器在周遊的時候 檢測集合是否發生過修改...
/**
這個方法的意思麼 就是移除這個區間裡的元素.. 主要的關注點在于它的 疊代器的實作
**/
protected void removeRange(int fromIndex, int toIndex) {
ListIterator<E> it = listIterator(fromIndex);
for (int i=0, n=toIndex-fromIndex; i<n; i++) {
it.next();
it.remove();
}
}
//這倆方法都是擷取該集合的疊代器
public ListIterator<E> listIterator() {
return listIterator(0);
}
public ListIterator<E> listIterator(final int index) {
rangeCheckForAdd(index);
return new ListItr(index);
}
//實作了可疊代器的接口..具有疊代的能力
private class Itr implements Iterator<E> {
int cursor = 0; //遊标..标記着 下一個周遊的元素下标
//在代碼中也能看出..記錄着 cursor的上一值
int lastRet = -1; //最後一次調用 next 或者 previous 傳回的下标 如果發生了remove 這個值又會變成-1
int expectedModCount = modCount; //用來檢測集合是否發生了值的變化.. 保證了在集合疊代的過程中不會發生改變
public boolean hasNext() { //是否有下一個..元素
return cursor != size();
}
public E next() { //獲得下一個元素前
checkForComodification(); //要檢測一下集合是否發現了改變
try {
int i = cursor;
E next = get(i);
lastRet = i;
cursor = i + 1;
return next;
} catch (IndexOutOfBoundsException e) { //後檢測..通過抛出異常來檢測是否越界
checkForComodification();
throw new NoSuchElementException();
}
}
//移除元素 ...雖然最後還是調用的 AbstractList的remove 方法
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
AbstractList.this.remove(lastRet);
if (lastRet < cursor)
cursor--;
lastRet = -1; // 這裡也就意味着 不能連續2次 remove
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() { //集合是否發生了修改
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
/**
清單的疊代器實作.. 看這裡繼承了一個 叫做Itr的類
這個類 也是其中一個内部類..就在上方
在能夠疊代的基礎上 還實作了 清單的疊代器..這個疊代器..又能向後 又能向前
還能夠支援 set 和 add方法
**/
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
cursor = index;
}
public boolean hasPrevious() {
return cursor != 0;
}
public E previous() {
checkForComodification();
try {
int i = cursor - 1;
E previous = get(i);
lastRet = cursor = i;
return previous;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor-1;
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
AbstractList.this.set(lastRet, e);
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
AbstractList.this.add(i, e);
lastRet = -1;
cursor = i + 1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
//這個方法也是來自 list接口的 獲得一段 子清單.. 裡面涉及了2個類 (下面2個)
public List<E> subList(int fromIndex, int toIndex) {
return (this instanceof RandomAccess ?
new RandomAccessSubList<>(this, fromIndex, toIndex) :
new SubList<>(this, fromIndex, toIndex));
}
}
//普通的子清單
/**
大局浏覽一下代碼...
發現并沒有真實的再去取一段清單
而是使用了源清單之後, 限定了一段區間...
擷取方式 使用 index + 偏移量的形式擷取
*/
class SubList<E> extends AbstractList<E> {
private final AbstractList<E> l;
private final int offset;
private int size;
SubList(AbstractList<E> list, int fromIndex, int toIndex) {
if (fromIndex < 0)
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
if (toIndex > list.size())
throw new IndexOutOfBoundsException("toIndex = " + toIndex);
if (fromIndex > toIndex)
throw new IllegalArgumentException("fromIndex(" + fromIndex +
") > toIndex(" + toIndex + ")");
l = list;
offset = fromIndex;
size = toIndex - fromIndex;
this.modCount = l.modCount;
}
public E set(int index, E element) {
rangeCheck(index);
checkForComodification();
return l.set(index+offset, element);
}
public E get(int index) {
rangeCheck(index);
checkForComodification();
return l.get(index+offset);
}
public int size() {
checkForComodification();
return size;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
checkForComodification();
l.add(index+offset, element);
this.modCount = l.modCount;
size++;
}
public E remove(int index) {
rangeCheck(index);
checkForComodification();
E result = l.remove(index+offset);
this.modCount = l.modCount;
size--;
return result;
}
protected void removeRange(int fromIndex, int toIndex) {
checkForComodification();
l.removeRange(fromIndex+offset, toIndex+offset);
this.modCount = l.modCount;
size -= (toIndex-fromIndex);
}
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
int cSize = c.size();
if (cSize==0)
return false;
checkForComodification();
l.addAll(offset+index, c);
this.modCount = l.modCount;
size += cSize;
return true;
}
public Iterator<E> iterator() {
return listIterator();
}
public ListIterator<E> listIterator(final int index) {
checkForComodification();
rangeCheckForAdd(index);
return new ListIterator<E>() {
private final ListIterator<E> i = l.listIterator(index+offset);
public boolean hasNext() {
return nextIndex() < size;
}
public E next() {
if (hasNext())
return i.next();
else
throw new NoSuchElementException();
}
public boolean hasPrevious() {
return previousIndex() >= 0;
}
public E previous() {
if (hasPrevious())
return i.previous();
else
throw new NoSuchElementException();
}
public int nextIndex() {
return i.nextIndex() - offset;
}
public int previousIndex() {
return i.previousIndex() - offset;
}
public void remove() {
i.remove();
SubList.this.modCount = l.modCount;
size--;
}
public void set(E e) {
i.set(e);
}
public void add(E e) {
i.add(e);
SubList.this.modCount = l.modCount;
size++;
}
};
}
public List<E> subList(int fromIndex, int toIndex) {
return new SubList<>(this, fromIndex, toIndex);
}
private void rangeCheck(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private void rangeCheckForAdd(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
private void checkForComodification() {
if (this.modCount != l.modCount)
throw new ConcurrentModificationException();
}
}
//實作方式與 子清單相同....就是再次擷取 子清單稍微不一樣
class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
super(list, fromIndex, toIndex);
}
public List<E> subList(int fromIndex, int toIndex) {
return new RandomAccessSubList<>(this, fromIndex, toIndex);
}
}
正餐 ArrayList (正主)
這裡就不把整個類代碼抓起來逐行看了…(代碼比較長)…
對于一個類…我喜歡先從成員變量…屬性…來看… 假設一些成員變量的作用…方法裡使用到之後就能确定是否正确
成員變量
讓我們先來看 它的成員變量
private static final int DEFAULT_CAPACITY = 10; //預設的容量大小
private static final Object[] EMPTY_ELEMENTDATA = {}; //可能
private transient Object[] elementData; //底層使用的是 Object[] 數組來存儲元素
private int size; //元素的大小
//這裡 -8的原因 在上文中提到了...根據源碼的解釋..是說VM裡面要在清單這個類型中 加入 header word..
//ps : 具體啥情況- -我也不知道..
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; //數組最大的長度.
執行個體方法
public ArrayList(int initialCapacity) { //如果指定一個值進行初始化...就會直接進行初始化
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
public ArrayList() {
super();
//注意這裡! 如果使用預設的話...不會先初始化!!!!! 會先使用一個空的數組進行标記..然後在第一次add的時候,擴容
this.elementData = EMPTY_ELEMENTDATA;
}
public ArrayList(Collection<? extends E> c) { //可以帶一個集合進來
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
如果把每個方法都拿出來分析…就有些備援了…
重要方法
// add
public boolean add(E e) {
ensureCapacityInternal(size + 1); //主要是這個方法... 涉及了擴容機制
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) { //如果使用預設方法構造..第一次會進入這裡
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
//明确是否要擴容 參數傳入是 add之後的容量大小
private void ensureExplicitCapacity(int minCapacity) {
modCount++; //可能會涉及數組的結構變化...是以要改變目前的修改值..如果有疊代器正在周遊..
//疊代器将會抛出錯誤
// overflow-conscious code
if (minCapacity - elementData.length > 0) // 如果目前容量不滿足了..就需要發生擴容
grow(minCapacity);
}
//擴容
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); //這裡也是重要的地方.以原來1.5倍的大小進行擴容
if (newCapacity - minCapacity < 0) //如果擴容之後還是不滿足數量的增長..就增長到 需要的數量
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0) //如果擴容超過了最大值..
newCapacity = hugeCapacity(minCapacity); //嘗試容量能否下降下來..不能就爆了
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
// 可以讓使用者主動 更改 清單的容量的2個方法
trimTosize
和
ensureCapacity(int)
//沒啥好說的..主動擴容到 minCapacity 加上一點點小判斷.
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != EMPTY_ELEMENTDATA)
? 0
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
//主動減少容量
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = Arrays.copyOf(elementData, size);
}
}
// 用于 對象流的
writeObject
和
readObject
這倆東西 我當時看的也是很蒙的… 發現沒有方法調用這倆方法… 又是private的…
一番百度才知道…這是 使用在 對象流裡面的… 對象流 會自動通過反射 調用這兩個類…
出現這倆個類的原因是 : 存儲資料的
private transient Object[] elementData;
是 transient關鍵字
不會被序列化… 當然不會被序列化也是考慮過的…因為 這個東西的大小通常比實際資料要大的多…
為了空間不被浪費
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
s.defaultReadObject();
s.readInt();
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
//
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
内部的疊代器
和AbstractList中的疊代器實作方式 幾乎相同 . 這裡就不說了
SubList
因為ArrayList 是實作RandomAccess的 , 是以 和 AbstractList 比起來 預設就是 RandomAccess型
結束! …
又是摸魚的一天 唉 苦逼
![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)