資訊專欄INFORMATION COLUMN
摘要：前面已經(jīng)講解集合中的并且也對其中使用的紅黑樹結(jié)構(gòu)做了對應(yīng)的說明，這次就來看下簡單一些的另一個集合類，也是日常經(jīng)常使用到的，整體來說，算是比較好理解的集合了，一起來看下前言版本類定義繼承了，實現(xiàn)了，提供對數(shù)組隊列的增刪改查操作實現(xiàn)接口，提供隨
前面已經(jīng)講解集合中的HashMap并且也對其中使用的紅黑樹結(jié)構(gòu)做了對應(yīng)的說明，這次就來看下簡單一些的另一個集合類，也是日常經(jīng)常使用到的ArrayList，整體來說，算是比較好理解的集合了，一起來看下
前言jdk版本：1.8類定義
public class ArrayListextends AbstractList implements List , RandomAccess, Cloneable, java.io.Serializable
繼承了AbstractList，實現(xiàn)了List，提供對數(shù)組隊列的增刪改查操作
實現(xiàn)RandomAccess接口，提供隨機訪問功能
實現(xiàn)Cloneable接口，提供克隆功能
實現(xiàn)Serializable接口，支持序列化，方便序列化傳輸
變量說明 private static final long serialVersionUID = 8683452581122892189L;
/**
* 默認的初始化容量
* 這里和HashMap初始容量不同，默認10
* 有些面試官可能問，雖然我感覺沒必要記這玩意
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 空集合，在構(gòu)造函數(shù)中看說明
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 默認容量大小的空集合，這里和上邊一樣，但是第一次添加的時候會自動擴容到默認容量，看構(gòu)造函數(shù)的說明
*/
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.
*
* 基于數(shù)組實現(xiàn)容量大小變化，上邊注釋也說了第一次添加元素時，將容量擴展到DEFAULT_CAPACITY
* 更詳細的接著往下看
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* 數(shù)組長度，即arraylist的長度
*/
private int size;
/**
* 最大數(shù)組長度限制
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
從上邊變量定義也能看出來ArrayList本質(zhì)上是基于Object[]實現(xiàn)，故方法上的操作都是基于數(shù)組來進行
構(gòu)造方法從構(gòu)造方法中能看出：
如果不設(shè)置初始化容量或者初始化賦值集合則elementData賦值為空數(shù)組而不是默認容量為10的數(shù)組
/**
* 無參構(gòu)造方法，初始化為默認空數(shù)組
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(Collection c) {
elementData = c.toArray();
// 原集合不為空，則進行復(fù)制
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
/**
* 官方bug
* c.toArray() 返回類型取決于其實際類型
* 查了下，應(yīng)該是調(diào)用子類的toArray（重寫）方法返回具體的類型
* 自己多想下也明白了，父類保存了子類的數(shù)組對象，這里需要調(diào)整成Object[]
* 不明白的自己Google下
*/
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 原集合為空，elementData賦值為空數(shù)組
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;
}
/**
* 修改次數(shù)記錄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方法實現(xiàn)拷貝
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
addAll
/**
* 先對集合容量進行檢查，記錄修改次數(shù)，調(diào)用arraycopy將舊數(shù)組元素拷貝到新數(shù)組元素中
*/
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;
}
/**
* 和上邊不同之處在于將數(shù)組拷貝到新數(shù)組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;
}
/**
* 返回元素在集合中的首個索引（從小到大）
* 主要是判空區(qū)分
*/
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的元素，先檢查索引值,再調(diào)用elementData方法
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
iterator
/**
* 返回迭代器 內(nèi)部類實現(xiàn)
*/
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，方便下次調(diào)用，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];
}
/**
* 移除當前l(fā)astRet對應(yīng)元素，cursor置為lastRet，修改次數(shù)修改
*/
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新增接口，調(diào)用accept接口對每個元素執(zhí)行動作
*/
@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;
}
/**
* 根據(jù)給定的元素刪除，這里看源碼也能發(fā)現(xiàn)，只刪除第一個匹配成功的元素即返回
*/
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
/**
* 移除所有和參數(shù)集合相同的元素
*/
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++)
//將保留的數(shù)據(jù)寫回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++)
//清理為空的數(shù)據(jù)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
set
/**
* 設(shè)置索引為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
/**
* 獲取子數(shù)組，內(nèi)部類實現(xiàn)，子數(shù)組只是引用了原來的數(shù)組，因此改變子數(shù)組，相當于改變了原來的數(shù)組
* 子數(shù)組不再詳細說明，ArrayList類相似，只是多了幾個成員變量，來限制范圍
* 源碼部分自行查看
*/
public List subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}
總結(jié)
整體來看ArrayList源碼還是比較簡單的，從源碼部分也能注意到幾個點：
ArrayList是基于數(shù)組實現(xiàn)的集合類
Object數(shù)組可以存放null
非線程安全，如需并發(fā)線程安全類需使用對應(yīng)的線程安全包裝類保證
如已經(jīng)確定容量大小，可以提前初始化設(shè)置好對應(yīng)容量以減少中間擴容帶來的損耗
總的來說，還是相對比較簡單了，希望對各位有所幫助，如有錯誤，歡迎指正，謝謝
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/77631.html
摘要：接下來就來說下我眼中的。鏈表轉(zhuǎn)換為樹的閾值，超過這個長度的鏈表會被轉(zhuǎn)換為紅黑樹，當然，不止這一個條件，在下面的源碼部分會看到。 源碼部分從HashMap說起是因為筆者看了很多遍這個類的源碼部分，同時感覺網(wǎng)上很多都是粗略的介紹，有些可能還不正確，最后只能自己看源碼來驗證理解，寫下這篇文章一方面是為了促使自己能深入，另一方面也是給一些新人一些指導(dǎo)，不求有功，但求無過。有錯誤的地方請在評論中...
摘要：前言版本以為例是因為之前的紅黑樹操作在文章省略了，這里進行一個解釋，其實源碼里并不是只有這個地方用紅黑樹結(jié)構(gòu)，但是總體上都大同小異，故只說明這一部分就好，舉一反三的能力相信各位都應(yīng)該擁有。紅黑樹類型遞歸左右子樹遍歷，直到值相等。 前面幾篇文章已經(jīng)講解過HashMap內(nèi)部實現(xiàn)以及紅黑樹的基礎(chǔ)知識，今天這篇文章就講解之前HashMap中未講解的紅黑樹操作部分，如果沒了解紅黑樹，請去閱讀前面...
摘要：上一篇文章已經(jīng)就進行了部分說明，介紹了其中涉及的常量和變量的含義，有些部分需要結(jié)合方法源碼來理解，今天這篇文章就繼續(xù)講解并發(fā)前言本文主要介紹中的一些重要方法，結(jié)合上篇文章中的講解部分進行更進一步的介紹回顧下上篇文章，我們應(yīng)該已經(jīng)知道的整體結(jié) 上一篇文章已經(jīng)就ConcurrentHashMap進行了部分說明，介紹了其中涉及的常量和變量的含義，有些部分需要結(jié)合方法源碼來理解，今天這篇文章就...
摘要：強調(diào)一下，紅黑樹中的葉子節(jié)點指的都是節(jié)點。故刪除之后紅黑樹平衡不用調(diào)整。將達到紅黑樹平衡。到此關(guān)于紅黑樹的基礎(chǔ)已經(jīng)介紹完畢，下一章我將就源碼中的進行講解說明，看一看紅黑樹是如何在源碼中實現(xiàn)的。 說到HashMap，就一定要說到紅黑樹，紅黑樹作為一種自平衡二叉查找樹，是一種用途較廣的數(shù)據(jù)結(jié)構(gòu)，在jdk1.8中使用紅黑樹提升HashMap的性能，今天就來說一說紅黑樹，上一講已經(jīng)給出插入平衡...
前面已經(jīng)說明了HashMap以及紅黑樹的一些基本知識，對JDK8的HashMap也有了一定的了解，本篇就開始看看并發(fā)包下的ConcurrentHashMap，說實話，還是比較復(fù)雜的，筆者在這里也不會過多深入，源碼層次上了解一些主要流程即可，清楚多線程環(huán)境下整個Map的運作過程就算是很大進步了，更細的底層部分需要時間和精力來研究，暫不深入 前言 jdk版本：1.8 JDK7中，ConcurrentH...
閱讀 2872·2023-04-25 22:15
閱讀 1890·2021-11-19 09:40
閱讀 2257·2021-09-30 09:48
閱讀 3320·2021-09-03 10:36
閱讀 2123·2021-08-30 09:48
閱讀 1953·2021-08-24 10:00
閱讀 2795·2019-08-30 15:54
閱讀 772·2019-08-30 15:54
