JDK容器類List和Set及Queue源碼怎么編寫
JDK容器類List和Set及Queue源碼怎么編寫，針對這個問題，這篇文章詳細介紹了相對應(yīng)的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。
10年積累的成都做網(wǎng)站、網(wǎng)站制作經(jīng)驗，可以快速應(yīng)對客戶對網(wǎng)站的新想法和需求。提供各種問題對應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認識你，你也不認識我。但先網(wǎng)站設(shè)計后付款的網(wǎng)站建設(shè)流程，更有淳安免費網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。
List，Set，Queue都是繼承Collection接口的單列集合接口。List常用的實現(xiàn)主要有ArrayList，LinkedList，List中的數(shù)據(jù)是有序可重復(fù)的。Set常用的實現(xiàn)主要是HashSet，Set中的數(shù)據(jù)是無序不可重復(fù)的。Queue常用的實現(xiàn)主要有ArrayBlockingQueue，LinkedBlockingQueue，Queue是一個保持先進先出的順序隊列，不允許隨機訪問隊列中的元素。
ArrayList核心源碼解讀
ArrayList是一個底層用數(shù)組實現(xiàn)的集合，數(shù)組元素類型為Object類型，支持隨機訪問，元素有序且可以重復(fù)，它繼承于AbstractList，實現(xiàn)了List, RandomAccess, Cloneable, java.io.Serializable這些接口。
當(dāng)通過 ArrayList() 構(gòu)造一個是集合，它是構(gòu)造了一個空數(shù)組，初始長度為0。當(dāng)?shù)?次添加元素時，會創(chuàng)建一個長度為10的數(shù)組，并將該元素賦值到數(shù)組的第一個位置，當(dāng)添加的元素大于10的時候，數(shù)組會進行第一次擴容。擴容1.5倍，長度變?yōu)?5。
ArrayList在遍歷的時候時不能修改的，即遍歷的時候不能增加或者刪除元素，否則會拋ConcurrentModificationException
ArrayList是線程不安全的。
ArrayList源碼中的主要字段
// 默認數(shù)組的大小
private static final int DEFAULT_CAPACITY = 10;
// 默認空數(shù)組
private static final Object[] EMPTY_ELEMENTDATA = {};
// 實際存放數(shù)據(jù)的數(shù)組
private transient Object[] elementData;ArrayList源碼中的構(gòu)造器
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity]; //將自定義的容量大小當(dāng)成初始化elementData的大小
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}ArrayList源碼中的add方法
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); //添加元素之前，首先要確定集合的大小
elementData[size++] = e; //在數(shù)據(jù)中正確的位置上放上元素e，并且size++
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 如果為空數(shù)組
return Math.max(DEFAULT_CAPACITY, minCapacity); // 返回默認的我數(shù)組長度
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // 修改次數(shù)+1，相當(dāng)于版本號
// overflow-conscious code
if (minCapacity - elementData.length > 0) // 如果實際容量小于需要容量
grow(minCapacity); // 擴容
}
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length; // 拿到數(shù)組的當(dāng)前長度
int newCapacity = oldCapacity + (oldCapacity >> 1); //新數(shù)組的長度等于原數(shù)組長度的1.5倍
if (newCapacity - minCapacity < 0) //當(dāng)新數(shù)組長度仍然比minCapacity小，則為保證最小長度，新數(shù)組等于minCapacity
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0) //當(dāng)?shù)玫降男聰?shù)組長度比 MAX_ARRAY_SIZE大時，調(diào)用 hugeCapacity 處理大數(shù)組
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity); //調(diào)用 Arrays.copyOf將原數(shù)組拷貝到一個大小為newCapacity的新數(shù)組（拷貝引用）
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE; // 數(shù)組的最大長度為Integer.MAX_VALUE
}ArrayList源碼中的get方法
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
rangeCheck(index); //判斷索引合法性
return elementData(index);
}線程安全的ArrayList--CopyOnWriteArrayList
CopyOnWriteArrayList是基于寫時復(fù)制（copy-on-write）思想來實現(xiàn)的一個線程安全的ArrayList集合類。它實現(xiàn)了List接口，內(nèi)部持有一個ReentrantLock來給寫上鎖，底層是用volatile transient聲明的數(shù)組array，它是讀寫分離的，寫入數(shù)據(jù)時會復(fù)制出一個新的數(shù)組并加上ReentrantLock鎖，完成寫入后將新數(shù)組賦值給當(dāng)前array，而讀操作不需要獲得鎖，支持并發(fā)。
CopyOnWriteArrayList的寫時復(fù)制導(dǎo)致了數(shù)據(jù)并不是實時的，有一定的延遲性，同時由于數(shù)據(jù)的復(fù)制，當(dāng)數(shù)據(jù)量非常大的時候會占用很大的內(nèi)存。
CopyOnWriteArrayList是適合讀多寫少的場景。
CopyOnWriteArrayList核心源碼解讀
// 存放數(shù)據(jù)的數(shù)組
private transient volatile Object[] array;
/**
* 添加數(shù)據(jù)方法
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock(); // 加鎖，保證數(shù)據(jù)安全
try {
Object[] elements = getArray(); // 拿到數(shù)組
int len = elements.length; // 獲取數(shù)組長度
Object[] newElements = Arrays.copyOf(elements, len + 1); // 拷貝數(shù)組到新數(shù)組
newElements[len] = e; // 將元素賦值到新數(shù)組的末尾
setArray(newElements); //設(shè)置新數(shù)組為當(dāng)前數(shù)組
return true;
} finally {
lock.unlock(); // 解鎖
}
}HashSet源碼解讀
HashSet是最常用的Set實現(xiàn)，它繼承了AbstractSet抽象類，實現(xiàn)了Set，Cloneable和java.io.Serializable接口。 HashSet中存儲的是無序不可重復(fù)的數(shù)據(jù)，他的底層的數(shù)據(jù)存儲是通過HashMap實現(xiàn)的，HashSet將數(shù)據(jù)存儲在HashMap的key中，將HashMap的value設(shè)為一個Object引用。
HashSet核心源碼解讀
// 實際存儲數(shù)據(jù)的HashMap
private transient HashMap<E,Object> map;
// HashMap的value引用
private static final Object PRESENT = new Object();
/**
* Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
* default initial capacity (16) and load factor (0.75).
*/
public HashSet() {
map = new HashMap<>(); //new一個 HashMap 對象出來，采用無參的 HashMap 構(gòu)造函數(shù)，具有默認初始容量（16）和加載因子（0.75）。
}
/**
* Adds the specified element to this set if it is not already present.
* More formally, adds the specified element <tt>e</tt> to this set if
* this set contains no element <tt>e2</tt> such that
* <tt>(e==null ? e2==null : e.equals(e2))</tt>.
* If this set already contains the element, the call leaves the set
* unchanged and returns <tt>false</tt>.
*
* @param e element to be added to this set
* @return <tt>true</tt> if this set did not already contain the specified
* element
*/
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}線程安全的HashSet--CopyOnWriteArraySet
CopyOnWriteArraySet是一個線程安全的HashSet，它底層是通過CopyOnWriteArrayList實現(xiàn)的，它是通過在添加數(shù)據(jù)的時候如果數(shù)據(jù)不存在才進行添加來實現(xiàn)了數(shù)據(jù)的不可重復(fù)
CopyOnWriteArraySet 核心源碼解讀
// 實際存放數(shù)據(jù)
private final CopyOnWriteArrayList<E> al;
/**
* Adds the specified element to this set if it is not already present.
* More formally, adds the specified element {@code e} to this set if
* the set contains no element {@code e2} such that
* <tt>(e==null ? e2==null : e.equals(e2))</tt>.
* If this set already contains the element, the call leaves the set
* unchanged and returns {@code false}.
*
* @param e element to be added to this set
* @return {@code true} if this set did not already contain the specified
* element
*/
public boolean add(E e) {
return al.addIfAbsent(e); // 如果不存在則添加
}Queue詳細分析
Queue是先入先出（FIFO）的一個隊列數(shù)據(jù)結(jié)構(gòu)，可以分為阻塞隊列和非阻塞隊列，Queue接口與List、Set同一級別，都是繼承了Collection接口。
Queue API
| 方法 | 作用 | 描述 |
|---|---|---|
| add | 增加一個元素 | 如果隊列已滿，則拋出一個IIIegaISlabEepeplian異常 |
| remove | 移除并返回隊列頭部的元素 | 如果隊列為空，則拋出一個NoSuchElementException異常 |
| element | 返回隊列頭部的元素 | 如果隊列為空，則拋出一個NoSuchElementException異常 |
| offer | 添加一個元素并返回true | 如果隊列已滿，則返回false |
| poll | 移除并返問隊列頭部的元素 | 如果隊列為空，則返回null |
| peek | 返回隊列頭部的元素 | 如果隊列為空，則返回null |
| put | 添加一個元素 | 如果隊列滿，則阻塞 |
| take | 移除并返回隊列頭部的元素 | 如果隊列為空，則阻塞 |
ArrayBlockingQueue源碼解讀
ArrayBlockingQueue是數(shù)組實現(xiàn)的線程安全的有界的阻塞隊列。
// 存放數(shù)據(jù)的數(shù)組
final Object[] items;
// 取數(shù)據(jù)索引
int takeIndex;
// 放數(shù)據(jù)索引
int putIndex;
// 數(shù)據(jù)量
int count;
// 鎖
final ReentrantLock lock;
/** Condition for waiting takes */
private final Condition notEmpty;
/** Condition for waiting puts */
private final Condition notFull;
/** items index for next put, offer, or add */
int putIndex;
/**
* Inserts the specified element at the tail of this queue if it is
* possible to do so immediately without exceeding the queue's capacity,
* returning {@code true} upon success and {@code false} if this queue
* is full. This method is generally preferable to method {@link #add},
* which can fail to insert an element only by throwing an exception.
*
* @throws NullPointerException if the specified element is null
*/
public boolean offer(E e) { // offer方法是非阻塞
checkNotNull(e);
final ReentrantLock lock = this.lock; // offer的時候加鎖
lock.lock();
try {
if (count == items.length) // 如果沒有空間， 返回false
return false;
else {
enqueue(e); // 如果有空間，入隊列
return true;
}
} finally {
lock.unlock();
}
}
/**
* Inserts the specified element at the tail of this queue, waiting
* for space to become available if the queue is full.
*
* @throws InterruptedException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
*/
public void put(E e) throws InterruptedException {
checkNotNull(e);
final ReentrantLock lock = this.lock; // 加鎖
lock.lockInterruptibly();
try {
while (count == items.length) // queue的容量已滿
notFull.await(); // 阻塞
enqueue(e);
} finally {
lock.unlock();
}
}
public E take() throws InterruptedException {
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
while (count == 0)
notEmpty.await(); //隊列為空時，將使這個線程進入阻塞狀態(tài),直到被其他線程喚醒時取出元素
return dequeue(); //消費對頭中的元素
} finally {
lock.unlock();
}
}LinkedBlockingQueue源碼解讀
LinkedBlockingQueue底層是采用鏈表實現(xiàn)的一個阻塞的線程安全的隊列。 LinkedBlockingQueue構(gòu)造的時候若沒有指定大小，則默認大小為Integer.MAX_VALUE，當(dāng)然也可以在構(gòu)造函數(shù)的參數(shù)中指定大小。 LinkedBlockingQueue中采用兩把鎖，取數(shù)據(jù)的時候加takeLock，放數(shù)據(jù)的時候加putLock。
// 容量
private final int capacity;
// 元素數(shù)量
private final AtomicInteger count = new AtomicInteger();
// 鏈表頭
transient Node<E> head;
// 鏈表尾
private transient Node<E> last;
// take鎖
private final ReentrantLock takeLock = new ReentrantLock();
// 當(dāng)隊列無元素時，take鎖會阻塞在notEmpty條件上，等待其它線程喚醒
private final Condition notEmpty = takeLock.newCondition();
// 放鎖
private final ReentrantLock putLock = new ReentrantLock();
// 當(dāng)隊列滿了時，put鎖會會阻塞在notFull上，等待其它線程喚醒
private final Condition notFull = putLock.newCondition();
/**
* Creates a {@code LinkedBlockingQueue} with a capacity of
* {@link Integer#MAX_VALUE}.
*/
public LinkedBlockingQueue() {
this(Integer.MAX_VALUE); // 如果沒傳容量，就使用最大int值初始化其容量
}
/**
* Inserts the specified element at the tail of this queue, waiting if
* necessary for space to become available.
*
* @throws InterruptedException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
*/
public void put(E e) throws InterruptedException {
if (e == null) throw new NullPointerException();
// Note: convention in all put/take/etc is to preset local var
// holding count negative to indicate failure unless set.
int c = -1;
Node<E> node = new Node<E>(e);
final ReentrantLock putLock = this.putLock; // 使用putLock鎖加鎖
final AtomicInteger count = this.count;
putLock.lockInterruptibly();
try {
/*
* Note that count is used in wait guard even though it is
* not protected by lock. This works because count can
* only decrease at this point (all other puts are shut
* out by lock), and we (or some other waiting put) are
* signalled if it ever changes from capacity. Similarly
* for all other uses of count in other wait guards.
*/
while (count.get() == capacity) { // 如果隊列滿了，就阻塞在notFull條件上
notFull.await(); // 等待被其它線程喚醒
}
enqueue(node); // 隊列不滿了，就入隊
c = count.getAndIncrement();
if (c + 1 < capacity)
notFull.signal();
} finally {
putLock.unlock();
}
if (c == 0)
signalNotEmpty();
}
public E take() throws InterruptedException {
E x;
int c = -1;
final AtomicInteger count = this.count;
final ReentrantLock takeLock = this.takeLock; // 使用takeLock加鎖
takeLock.lockInterruptibly();
try {
while (count.get() == 0) { // 如果隊列無元素，則阻塞在notEmpty條件上
notEmpty.await();
}
x = dequeue();
c = count.getAndDecrement();
if (c > 1)
notEmpty.signal();
} finally {
takeLock.unlock();
}
if (c == capacity)
signalNotFull();
return x;
}ConcurrentLinkedQueue源碼解讀
ConcurrentLinkedQueue是線程安全的無界非阻塞隊列，其底層數(shù)據(jù)結(jié)構(gòu)是使用單向鏈表實現(xiàn)，入隊和出隊操作是使用我們經(jīng)常提到的CAS來保證線程安全的。 ConcurrentLinkedQueue不允許插入的元素為null。
private transient volatile Node<E> head;
private transient volatile Node<E> tail;
private static final sun.misc.Unsafe UNSAFE;
private static final long headOffset;
private static final long tailOffset;
/**
* Inserts the specified element at the tail of this queue.
* As the queue is unbounded, this method will never return {@code false}.
*
* @return {@code true} (as specified by {@link Queue#offer})
* @throws NullPointerException if the specified element is null
*/
public boolean offer(E e) {
checkNotNull(e); // 為null則拋出空指針異常
final Node<E> newNode = new Node<E>(e);
for (Node<E> t = tail, p = t;;) { // 自旋
Node<E> q = p.next;
if (q == null) { // 如果q==null說明p是尾節(jié)點，則執(zhí)行插入
// p is last node
if (p.casNext(null, newNode)) { // 使用CAS設(shè)置p節(jié)點的next節(jié)點
// Successful CAS is the linearization point
// for e to become an element of this queue,
// and for newNode to become "live".
if (p != t) // hop two nodes at a time
casTail(t, newNode); // Failure is OK.
return true;
}
// Lost CAS race to another thread; re-read next
}
else if (p == q)
// We have fallen off list. If tail is unchanged, it
// will also be off-list, in which case we need to
// jump to head, from which all live nodes are always
// reachable. Else the new tail is a better bet.
p = (t != (t = tail)) ? t : head;
else
// Check for tail updates after two hops.
p = (p != t && t != (t = tail)) ? t : q;
}
}關(guān)于JDK容器類List和Set及Queue源碼怎么編寫問題的解答就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道了解更多相關(guān)知識。
本文題目：JDK容器類List和Set及Queue源碼怎么編寫
網(wǎng)頁鏈接：http://bm7419.com/article2/jdecic.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站收錄、品牌網(wǎng)站建設(shè)、外貿(mào)建站、網(wǎng)站營銷、微信小程序、網(wǎng)站內(nèi)鏈
聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)
- 成都網(wǎng)站建設(shè)公司淺談移動網(wǎng)站建設(shè)的那些要點分析 2016-11-08
- 移動網(wǎng)站建設(shè)切忌忽視客戶的期望 2015-01-19
- 什么是鄭州網(wǎng)站設(shè)計公司移動網(wǎng)站建設(shè)流程 2023-03-18
- 百度移動搜索：移動網(wǎng)站建設(shè)常見問題集錦 2022-02-22
- 成都移動網(wǎng)站建設(shè)中長滾動頁面的優(yōu)勢 2020-08-22
- 移動網(wǎng)站建設(shè)體驗決定成敗 2021-12-12
- 做移動網(wǎng)站建設(shè)應(yīng)注意哪幾點？經(jīng)驗種草 2022-08-07
- 移動網(wǎng)站建設(shè)時的哪些要點一定要謹記 2021-03-06
- 淺析移動網(wǎng)站建設(shè)的發(fā)展趨勢 2023-03-27
- 移動網(wǎng)站建設(shè)應(yīng)注意的問題有哪些 2014-12-08
- 移動網(wǎng)站建設(shè)容易進入的誤區(qū) 2021-12-10
- 中小企業(yè)網(wǎng)站移動網(wǎng)站建設(shè)有哪些好處？ 2016-11-27