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