資訊專欄INFORMATION COLUMN
摘要：前面已經講解集合中的并且也對其中使用的紅黑樹結構做了對應的說明，這次就來看下簡單一些的另一個集合類，也是日常經常使用到的，整體來說，算是比較好理解的集合了，一起來看下前言版本類定義繼承了，實現了，提供對數組隊列的增刪改查操作實現接口，提供隨
前面已經講解集合中的HashMap并且也對其中使用的紅黑樹結構做了對應的說明，這次就來看下簡單一些的另一個集合類，也是日常經常使用到的ArrayList，整體來說，算是比較好理解的集合了，一起來看下
前言jdk版本：1.8類定義
public class ArrayListextends AbstractList implements List , RandomAccess, Cloneable, java.io.Serializable
繼承了AbstractList，實現了List，提供對數組隊列的增刪改查操作
實現RandomAccess接口，提供隨機訪問功能
實現Cloneable接口，提供克隆功能
實現Serializable接口，支持序列化，方便序列化傳輸
變量說明 private static final long serialVersionUID = 8683452581122892189L;
/**
* 默認的初始化容量
* 這里和HashMap初始容量不同，默認10
* 有些面試官可能問，雖然我感覺沒必要記這玩意
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 空集合，在構造函數中看說明
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 默認容量大小的空集合，這里和上邊一樣，但是第一次添加的時候會自動擴容到默認容量，看構造函數的說明
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*
* 基于數組實現容量大小變化，上邊注釋也說了第一次添加元素時，將容量擴展到DEFAULT_CAPACITY
* 更詳細的接著往下看
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* 數組長度，即arraylist的長度
*/
private int size;
/**
* 最大數組長度限制
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
從上邊變量定義也能看出來ArrayList本質上是基于Object[]實現，故方法上的操作都是基于數組來進行
構造方法從構造方法中能看出：
如果不設置初始化容量或者初始化賦值集合則elementData賦值為空數組而不是默認容量為10的數組
/**
* 無參構造方法，初始化為默認空數組
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(Collection c) {
elementData = c.toArray();
// 原集合不為空，則進行復制
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
/**
* 官方bug
* c.toArray() 返回類型取決于其實際類型
* 查了下，應該是調用子類的toArray（重寫）方法返回具體的類型
* 自己多想下也明白了，父類保存了子類的數組對象，這里需要調整成Object[]
* 不明白的自己Google下
*/
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 原集合為空，elementData賦值為空數組
this.elementData = EMPTY_ELEMENTDATA;
}
}
/**
* 初始化容量 代碼比較簡單
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
重要方法
add
每次增加元素時會通過ensureCapacityInternal進行容量大小的驗證，不滿足則進行擴容操作，通過grow方法進行擴容操作，在允許的范圍上擴容為原來的1.5倍
/**
* 增加元素
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
/**
* 確認容量
*/
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
/**
* 計算容量
* elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* 在這里進行了初始化判斷
* 最小容量為10
*/
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
/**
* 修改次數記錄modCount，容量是否擴容判斷
*/
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;
// 右移操作擴容為原來的1.5倍（位移操作，自己試下就明白）
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 比較最小值
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;
}
/**
* 將element插入index的位置
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
// native方法實現拷貝
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
addAll
/**
* 先對集合容量進行檢查，記錄修改次數，調用arraycopy將舊數組元素拷貝到新數組元素中
*/
public boolean addAll(Collection c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
/**
* 和上邊不同之處在于將數組拷貝到新數組index位置，其后元素依次排序
*/
public boolean addAll(int index, Collection c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
clear
/**
* 清空
*/
public void clear() {
modCount++;
// clear to let GC do its work
// 注釋上也寫明了原因，置空為了讓GC工作，回收空間
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
contains
/**
* 判斷某個元素是否在集合中
*/
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
/**
* 返回元素在集合中的首個索引（從小到大）
* 主要是判空區分
*/
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
get
/**
* 獲取索引為index的元素，先檢查索引值,再調用elementData方法
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
iterator
/**
* 返回迭代器 內部類實現
*/
public Iterator iterator() {
return new Itr();
}
private class Itr implements Iterator {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
Itr() {}
public boolean hasNext() {
return cursor != size;
}
/**
* 獲取索引為cursor的元素，并置cursor = cursor + 1，方便下次調用，lastRet記錄當前返回的元素索引
*/
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
/**
* 移除當前lastRet對應元素，cursor置為lastRet，修改次數修改
*/
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
/**
* jdk 1.8新增接口，調用accept接口對每個元素執行動作
*/
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
/**
* 檢查
*/
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
lastIndexOf
/**
* 返回匹配對象的首個索引（從大到小）
*/
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
remove
/**
* 刪除索引為index的元素
*/
public E remove(int index) {
rangeCheck(index);
//修改記錄+1
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
//使用arraycopy重新整理集合
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
/**
* 根據給定的元素刪除，這里看源碼也能發現，只刪除第一個匹配成功的元素即返回
*/
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
removeAll
/**
* 移除所有和參數集合相同的元素
*/
public boolean removeAll(Collection c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
private boolean batchRemove(Collection c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
//將保留的數據寫回elementData
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
//清理為空的數據
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
set
/**
* 設置索引為index的值為element
*/
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
toArray
/**
* 將list元素拷貝返回
*/
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
@SuppressWarnings("unchecked")
public T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a"s runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
subList
/**
* 獲取子數組，內部類實現，子數組只是引用了原來的數組，因此改變子數組，相當于改變了原來的數組
* 子數組不再詳細說明，ArrayList類相似，只是多了幾個成員變量，來限制范圍
* 源碼部分自行查看
*/
public List subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}
總結
整體來看ArrayList源碼還是比較簡單的，從源碼部分也能注意到幾個點：
ArrayList是基于數組實現的集合類
Object數組可以存放null
非線程安全，如需并發線程安全類需使用對應的線程安全包裝類保證
如已經確定容量大小，可以提前初始化設置好對應容量以減少中間擴容帶來的損耗
總的來說，還是相對比較簡單了，希望對各位有所幫助，如有錯誤，歡迎指正，謝謝
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/77631.html
摘要：接下來就來說下我眼中的。鏈表轉換為樹的閾值，超過這個長度的鏈表會被轉換為紅黑樹，當然，不止這一個條件，在下面的源碼部分會看到。 源碼部分從HashMap說起是因為筆者看了很多遍這個類的源碼部分，同時感覺網上很多都是粗略的介紹，有些可能還不正確，最后只能自己看源碼來驗證理解，寫下這篇文章一方面是為了促使自己能深入，另一方面也是給一些新人一些指導，不求有功，但求無過。有錯誤的地方請在評論中...
摘要：前言版本以為例是因為之前的紅黑樹操作在文章省略了，這里進行一個解釋，其實源碼里并不是只有這個地方用紅黑樹結構，但是總體上都大同小異，故只說明這一部分就好，舉一反三的能力相信各位都應該擁有。紅黑樹類型遞歸左右子樹遍歷，直到值相等。 前面幾篇文章已經講解過HashMap內部實現以及紅黑樹的基礎知識，今天這篇文章就講解之前HashMap中未講解的紅黑樹操作部分，如果沒了解紅黑樹，請去閱讀前面...
摘要：上一篇文章已經就進行了部分說明，介紹了其中涉及的常量和變量的含義，有些部分需要結合方法源碼來理解，今天這篇文章就繼續講解并發前言本文主要介紹中的一些重要方法，結合上篇文章中的講解部分進行更進一步的介紹回顧下上篇文章，我們應該已經知道的整體結 上一篇文章已經就ConcurrentHashMap進行了部分說明，介紹了其中涉及的常量和變量的含義，有些部分需要結合方法源碼來理解，今天這篇文章就...
摘要：強調一下，紅黑樹中的葉子節點指的都是節點。故刪除之后紅黑樹平衡不用調整。將達到紅黑樹平衡。到此關于紅黑樹的基礎已經介紹完畢，下一章我將就源碼中的進行講解說明，看一看紅黑樹是如何在源碼中實現的。 說到HashMap，就一定要說到紅黑樹，紅黑樹作為一種自平衡二叉查找樹，是一種用途較廣的數據結構，在jdk1.8中使用紅黑樹提升HashMap的性能，今天就來說一說紅黑樹，上一講已經給出插入平衡...
前面已經說明了HashMap以及紅黑樹的一些基本知識，對JDK8的HashMap也有了一定的了解，本篇就開始看看并發包下的ConcurrentHashMap，說實話，還是比較復雜的，筆者在這里也不會過多深入，源碼層次上了解一些主要流程即可，清楚多線程環境下整個Map的運作過程就算是很大進步了，更細的底層部分需要時間和精力來研究，暫不深入 前言 jdk版本：1.8 JDK7中，ConcurrentH...
閱讀 2723·2023-04-25 22:15
閱讀 1804·2021-11-19 09:40
閱讀 2149·2021-09-30 09:48
閱讀 3213·2021-09-03 10:36
閱讀 2026·2021-08-30 09:48
閱讀 1854·2021-08-24 10:00
閱讀 2725·2019-08-30 15:54
閱讀 699·2019-08-30 15:54
