Java?集合常見問題總結示例詳解
ArrayList、LinkedList與Vector的區(qū)別？
這三個都是List接口的主要實現(xiàn)，
- ArrayList底層實現(xiàn)是數(shù)組，當超過原有大小的時候會按照原長度的1.5倍進行擴容，查詢性能比較高
- LinkedList底層實現(xiàn)是雙向鏈表，理論上可以無限長度，再增加和刪除的場景中性能比較好，但是查詢性能不高
- Vector底層實現(xiàn)和ArrayList類似，但是是線程安全的，原因就是里面的大部分方法都使用了synchronized進行修飾，此外就是擴容機制也不同，它是按照2倍進行擴容的
然后要注意LinkedList其實還實現(xiàn)了Deque（其內(nèi)部又繼承了Queue），所以比較全能一點，方法比較多
在使用上一般就是查找較多的場景以ArrayList為主，修改較多的場景通過LinkedList，而Vector是比較早期的，現(xiàn)階段一般用JUC包下的集合進行替代
對ArrayList的擴容機制了解嗎？
了解，在進行初始化的時候如果指定了合法的大小就是按照指定的大小創(chuàng)建數(shù)組，否則就是按照默認，默認大小是10
private static final int DEFAULT_CAPACITY = 10;
然后擴容的機制就是在執(zhí)行add的時候，判斷到當前個數(shù)已經(jīng)等于當前數(shù)組的長度，就會觸發(fā)擴容，擴容就是按原來的1.5倍進行擴容
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}擴容的具體邏輯就是先申請一個1.5倍大小的數(shù)組，將原數(shù)組進行復制，然后再將舊引用指向成新數(shù)組
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity >> 1 /* preferred growth */);
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}ArrayList的subList方法有什么需要注意的地方嗎？
subList() 方法其實就是用來對指定范圍內(nèi)的元素進行截取映射出來
public class Main {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>(1);
for (int i = 0; i < 100; i ++) list.add(i);
List<Integer> subList = list.subList(2, 7);
subList.add(1);
System.out.println(subList); // [2, 3, 4, 5, 6, 1]
}
}但是需要注意的就是底層其實并沒有創(chuàng)建一個新的ArrayList，而是直接創(chuàng)建一個內(nèi)部的SubList對象，可以理解為就是創(chuàng)建了一個視圖出來
SubList 是ArrayList的一個內(nèi)部類，不能轉化成ArrayList或是其它的，否則報錯
private static class SubList<E> extends AbstractList<E> implements RandomAccess {
private final ArrayList<E> root;
private final SubList<E> parent;
private final int offset;
private int size;
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList<>(this, fromIndex, toIndex);
}
}結構化修改：新增/刪除元素
非結構化修改：不改變數(shù)量，只改變原有元素的值
三個指標：
- 無論是對原來的ArrayList集合或是你subList進行非結構化修改，都會影響到另外一個
- 對subList進行結構化修改是可以的，且會影響到原來的ArrayList，但是反過來對原來的ArrayList進行結構化修改就不行，會直接報錯
此外就是你對subList視圖進行結構化修改會映射到原來的ArrayList，但是對原來的ArrayList修改則會報錯
public class Main {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>(1);
for (int i = 0; i < 100; i ++) list.add(i);
List<Integer> subList = list.subList(2, 7);
subList.remove(1);
// 可以發(fā)現(xiàn)3沒了
System.out.println(subList); // [2, 4, 5, 6]
System.out.println(list); // [0, 1, 2, 4, 5, 6, 7, 8, 9, 10……]
}
}public class Main {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>(1);
for (int i = 0; i < 100; i ++) list.add(i);
List<Integer> subList = list.subList(2, 7);
list.add(1);
System.out.println(subList);
}
}
Exception in thread "main" java.util.ConcurrentModificationException
at java.base/java.util.ArrayList$SubList.checkForComodification(ArrayList.java:1415)
at java.base/java.util.ArrayList$SubList.listIterator(ArrayList.java:1284)如果指向修改SubList，但是不想改變原有的list的話，就只能對SubList進行拷貝一份新的再去操作
結論：需要注意的地方主要是，SubList是ArrayList的一個內(nèi)部類，調(diào)用subList()方法時其實是創(chuàng)建了一個SubList對象給我們，底層并沒有創(chuàng)建新的ArrayList對象，而是直接復用，可以理解為給我們開了一個新的視圖，但是要注意無論是對這個視圖還是原來的ArrayList對象進行非結構化操作（不改變元素數(shù)量，只改變原有的值）或是對subList進行結構化操作（修改元素數(shù)量）都會影響到彼此，而對原來的ArrayList進行結構化操作會直接報錯
注意：是視圖，不是副本
ArrayList的序列化是怎么實現(xiàn)的？
首先ArrayList其實是一個動態(tài)Object數(shù)組，并且實現(xiàn)了Serializable接口，如果是按照這個來看似乎是直接使用jdk默認的序列化機制，但是實際上不是
transient Object[] elementData; // non-private to simplify nested class access
可以看到它的這個動態(tài)數(shù)組其實是被transient修飾了，這個關鍵字的作用就是忽略序列化，也就是有這個關鍵字，jdk的默認序列化方式就不會去序列化這個字段
此外，ArrayList重寫了Object的writeObject()和readObject()，這兩個方法就是Object默認序列化和反序列化時調(diào)用的方法，ArrayList重寫之后做了自己的序列化和反序列化邏輯
@java.io.Serial
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 behavioral 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();
}
}
@java.io.Serial
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// like clone(), allocate array based upon size not capacity
SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size);
Object[] elements = new Object[size];
// Read in all elements in the proper order.
for (int i = 0; i < size; i++) {
elements[i] = s.readObject();
}
elementData = elements;
} else if (size == 0) {
elementData = EMPTY_ELEMENTDATA;
} else {
throw new java.io.InvalidObjectException("Invalid size: " + size);
}
}那有一個問題：為什么ArrayList要大費周章的把這個元素數(shù)組標識成transient，然后自己控制序列化和反序列化的過程？
答案就是為了適配ArrayList的擴容機制，或者說ArrayList數(shù)組是不是每次申請的時候都是往大了申請，然后寫滿之后再申請更大的，然后數(shù)組又是聲明為Object類型，那么沒寫的空間就直接為null，要是使用默認序列化方式，假設數(shù)組大小是100，但是真實元素只有1個，這時候不就序列化了99個null，所以它自己控制序列化和反序列化的時候就是按照這個真實元素個數(shù)來進行序列化，避免造成資源浪費
總結一下：ArrayList的序列化方式就是先把真實存儲數(shù)據(jù)的數(shù)組聲明成transient，然后自己重寫序列化和反序列化方法實現(xiàn)對序列化流程的控制，序列化和反序列化的時候只處理真正的元素，而不是整個數(shù)組
ConcurrentHashMap是如何保證fail-safe的？
這兩種方式是并發(fā)過程中解決問題的策略
- fail-safe：安全失敗，迭代的時候遇到修改操作不會拋出異常，而是返回一個快照版本，可能會導致拿到的快照和實際有一定的不一致，例如ConcurrentHashMap
- fail-fast：快速失敗，迭代的時候遇到修改操作會直接拋出異常，例如ArrayList
那接下來我們就探討一下ConcurrentHashMap是如何實現(xiàn)安全失敗的，主要是兩個角度
- 移除來了HashMap的modCount比較，不會出現(xiàn)說modCount和期望的值不同的時候出現(xiàn)報錯的情況
- 此外就是table數(shù)組被volatile修飾了，并且當執(zhí)行修改操作的時候底層是通過synchronized + CAS進行修改的，也就是說當執(zhí)行put或是remove操作的時候首先會獲取一份最新的table數(shù)據(jù)，然后在自己的線程私有內(nèi)存中進行修改，修改完成就同步到主內(nèi)存，然后因為加了volatile，所以當它發(fā)生修改時，正在讀取的線程也能獲取到最新的數(shù)據(jù)
特點：可能讀取到修改前的數(shù)據(jù)，也可能讀取到修改后的數(shù)據(jù)，但是不會讀取到修改一半的數(shù)據(jù)
還有一個比較特殊的場景：要是是遍歷的時候剛好遇到擴容呢？
遍歷的時候如果遇到擴容，ConcurrentHashMap會在擴容之后桶如果發(fā)生遷移會用特殊的節(jié)點ForwardingNode進行標記
static final class ForwardingNode<K,V> extends Node<K,V> {
final Node<K,V>[] nextTable;
ForwardingNode(Node<K,V>[] tab) {
super(MOVED, null, null);
this.nextTable = tab;
}
}它里面會記錄新數(shù)組的位置，然后跳轉到新數(shù)組進行遍歷
遍歷的具體邏輯
final Node<K,V> advance() {
Node<K,V> e;
if ((e = next) != null)
e = e.next;
for (;;) {
Node<K,V>[] t; int i, n; // must use locals in checks
if (e != null)
return next = e;
if (baseIndex >= baseLimit || (t = tab) == null ||
(n = t.length) <= (i = index) || i < 0)
return next = null;
if ((e = tabAt(t, i)) != null && e.hash < 0) {
if (e instanceof ForwardingNode) {
tab = ((ForwardingNode<K,V>)e).nextTable;
e = null;
pushState(t, i, n);
continue;
}
else if (e instanceof TreeBin)
e = ((TreeBin<K,V>)e).first;
else
e = null;
}
if (stack != null)
recoverState(n);
else if ((index = i + baseSize) >= n)
index = ++baseIndex; // visit upper slots if present
}
}ConcurrentHashMap是如何保證線程安全的？
要回答這個問題得看jdk的版本，
如果是jdk1.7的話，存儲結構是數(shù)組+鏈表，主要使用的Segment分段鎖技術
這里的HashEntry就是一個一個的槽，每個槽存的就是一條鏈表（因為哈希沖突使用拉鏈法），然后引進了Segment的概念，就是規(guī)定哪幾個元素或是那一段元素屬于哪一個Segment，就這樣一個數(shù)組分成好幾段，每一段都用一個Segment進行管理，然后每次鎖的時候就是鎖一個Segment，也就是鎖一小段
jdk8開始就改了，首先是存儲結構變成了數(shù)組+鏈表+紅黑樹，同時也去掉了Segment的概念，直接對著每一個hash槽進行操作
由于現(xiàn)在改成要操作的時候直接操作哪一個槽就鎖哪一個，所以性能會大大提升，并發(fā)度也大大提高
然后它鎖的實現(xiàn)就是使用CAS+synchronized，具體什么時候用哪一種是分情況的
可以看源碼：
首先就是執(zhí)行put操作的時候
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh; K fk; V fv;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else if (onlyIfAbsent // check first node without acquiring lock
&& fh == hash
&& ((fk = f.key) == key || (fk != null && key.equals(fk)))
&& (fv = f.val) != null)
return fv;
else {
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key, value);
break;
}
}
}
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
else if (f instanceof ReservationNode)
throw new IllegalStateException("Recursive update");
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}具體的邏輯可以總結一下：
首先就是看一下ConcurrentHashMap數(shù)組（容器）是否為null，
- 如果為null的話就使用tab = initTable();去進行初始化
- 不為null就根據(jù)要put的key計算出來的hash值去找對應的槽，判斷槽中是否已經(jīng)有數(shù)據(jù)
- 沒有數(shù)據(jù)就說明當前操作的競爭不是很高，使用CAS去添加
- 有數(shù)據(jù)說明競爭比較激烈，使用synchronized去進行添加，添加的過程就是遍歷整個槽位的鏈表，判斷執(zhí)行新增操作或覆蓋操作；最后就是判斷一下是否要進行轉化成紅黑數(shù)，轉換的條件就是鏈表長度已經(jīng)大于等于8且hash槽個數(shù)已經(jīng)大于等于64個
還有一點要補充的：上面其實大家都看到當(fh = f.hash) == MOVED時說明這一個槽位正在擴容中，會調(diào)用helpTransfer() 方法協(xié)助擴容操作
CAS的具體邏輯
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
break; // no lock when adding to empty bin
}
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
return U.compareAndSetReference(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
public final native boolean compareAndSetReference(Object o, long offset,
Object expected,
Object x);其實進去會發(fā)現(xiàn)是一個native本地方法，這一塊更多是系統(tǒng)底層來幫我們實現(xiàn)
cas其實可以認為就是一個循環(huán)，它不加鎖，但是會不斷的進行比較，有點像你要買一件衣服，然后錢不夠，你就可以不停的問店員降價了嗎，直到降價到錢夠買的時候就買下
缺點就是需要多次比較，且失敗率會比較高
ConcurrentHashMap為什么在JDK1.8中廢棄分段鎖？
說白了就是jdk7的分段鎖粒度還是太大了，分段鎖說白了不就是鎖著一個哈希表（小哈希表）嗎，那可能有一種情況就是這一個哈希表里面就只有一個元素熱點比較高，那它會導致這一段一直鎖著，造成其他同段節(jié)點沒法處理
所以jdk8直接把鎖的粒度減少到哈希槽級別的，就是每次只鎖一個槽，最多就這個槽的鏈表上其他節(jié)點沒辦法操作，粒度大大降低
此外jdk8中對synchronized進行了底層的優(yōu)化，讓它在性能上不輸ReentrantLock，且是自動釋放的更加安全，可以說synchronized+CAS的性能和安全性都要更好
所以總結一下更換的原因，主要是從鎖粒度以及性能和安全性出發(fā)考慮的最終結果
ConcurrentHashMap為什么在JDK1.8中使用synchronized而不是ReentrantLock？
首先就是synchronized早在jdk1.6中就已經(jīng)被優(yōu)化了，不再是簡單的鎖全部，而是有升級的過程，其實看源碼也可以看到因為已經(jīng)分成多個槽位，所以并發(fā)壓力并不高，鎖升級也不會很頻繁，性能和ReentrantLock差不多
此外就是synchronized能自動釋放資源并且不需要喚醒等操作，實現(xiàn)起來也是比較方便清晰
而且synchronized的內(nèi)存占用是比ReentrantLock低的
這幾點放在并發(fā)編程里面再進行解釋
到此這篇關于Java 集合常見問題總結的文章就介紹到這了,更多相關java 集合常見問題內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
解決Maven項目idea找不到本地倉庫jar包問題以及使用mvn install:install-file
這篇文章主要介紹了解決Maven項目idea找不到本地倉庫jar包問題以及使用mvn install:install-file,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2025-04-04
IntelliJ IDEA 中編寫 Speak 程序的詳細步驟和指南
本文介紹了如何在IntelliJIDEA中編寫一個語音交互程序,包括環(huán)境準備、編寫代碼、運行和測試以及調(diào)試優(yōu)化,通過使用GoogleCloud的語音處理API,可以實現(xiàn)語音轉文本和文本轉語音功能,感興趣的朋友跟隨小編一起看看吧2026-01-01
logback輸出日志屏蔽quartz的debug等級日志方式
這篇文章主要介紹了logback輸出日志屏蔽quartz的debug等級日志方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-08-08
這篇文章主要給大家介紹了關于JAVA為什么要使用封裝及如何封裝的相關資料,封裝就是將屬性私有化,提供公有的方法訪問私有屬性,文中通過代碼介紹的非常詳細,需要的朋友可以參考下2023-10-10
SpringBoot使用@PathVariable進行數(shù)據(jù)校驗的流程步驟
在SpringBoot項目中，我們經(jīng)常需要從 URL 中獲取參數(shù)并進行相關的數(shù)據(jù)校驗，而@PathVariable注解就是一種非常方便的方式，可以讓我們在方法參數(shù)中直接獲取URL中的參數(shù)，并進行數(shù)據(jù)校驗，本文將介紹如何使用@PathVariable注解進行數(shù)據(jù)校驗2023-06-06
SpringSecurity是一個強大的可高度定制的認證和授權框架,對于Spring應用來說它是一套Web安全標準,下面這篇文章主要給大家介紹了關于Spring?Security+JWT簡述的相關資料,需要的朋友可以參考下2023-04-04
java字符串轉數(shù)字及各種數(shù)字轉字符串的3種方法
這篇文章主要介紹了java字符串轉數(shù)字及各種數(shù)字轉字符串的3種方法,本文通過實例代碼給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2023-09-09
這篇文章主要圍繞Java中的字符流進行介紹，包括字符輸入流、字符輸出流以及處理流異常的幾種方式。文中的示例代碼講解詳細，感興趣的可以了解一下2022-08-08
本文給大家分享IDEA中一個很有用的內(nèi)存調(diào)試插件，非常不錯，具有參考借鑒價值，需要的朋友參考下2018-02-02
這篇文章主要介紹了logback如何自定義日志存儲的操作，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-08-08