上難度了！社招三年了，我要跳槽了！
Java
HashMap底層實現(xiàn)原理
- 在 JDK 1.7 版本之前， HashMap 數(shù)據(jù)結(jié)構(gòu)是數(shù)組和鏈表，HashMap通過哈希算法將元素的鍵（Key）映射到數(shù)組中的槽位（Bucket）。如果多個鍵映射到同一個槽位，它們會以鏈表的形式存儲在同一個槽位上，因為鏈表的查詢時間是O(n)，所以沖突很嚴(yán)重，一個索引上的鏈表非常長，效率就很低了。
圖片
- 所以在 JDK 1.8 版本的時候做了優(yōu)化，當(dāng)一個鏈表的長度超過8的時候就轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)，不再使用鏈表存儲，而是使用紅黑樹，查找時使用紅黑樹，時間復(fù)雜度O（log n），可以提高查詢性能，但是在數(shù)量較少時，即數(shù)量小于6時，會將紅黑樹轉(zhuǎn)換回鏈表。
圖片
介紹一下ConcurrentHashMap；
- 在 JDK 1.7 中它使用的是數(shù)組加鏈表的形式實現(xiàn)的，而數(shù)組又分為：大數(shù)組 Segment 和小數(shù)組 HashEntry。Segment 是一種可重入鎖（ReentrantLock），在 ConcurrentHashMap 里扮演鎖的角色；HashEntry 則用于存儲鍵值對數(shù)據(jù)。一個 ConcurrentHashMap 里包含一個 Segment 數(shù)組，一個 Segment 里包含一個 HashEntry 數(shù)組，每個 HashEntry 是一個鏈表結(jié)構(gòu)的元素。簡單理解就是，ConcurrentHashMap 是一個 Segment 數(shù)組，Segment 通過繼承 ReentrantLock 來進(jìn)行加鎖，所以每次需要加鎖的操作鎖住的是一個 segment，這樣只要保證每個 Segment 是線程安全的，也就實現(xiàn)了全局的線程安全。
圖片
- JDK 1.8 也引入了紅黑樹，優(yōu)化了之前的固定鏈表，那么當(dāng)數(shù)據(jù)量比較大的時候，查詢性能也得到了很大的提升，從之前的 O(n) 優(yōu)化到了 O(logn) 的時間復(fù)雜度。ConcurrentHashMap 主要通過 volatile + CAS 或者 synchronized 來實現(xiàn)的線程安全的，ConcurrentHashMap通過對頭結(jié)點(diǎn)加鎖來保證線程安全的，鎖的粒度相比 Segment 來說更小了，發(fā)生沖突和加鎖的頻率降低了，并發(fā)操作的性能就提高了。
圖片
ThreadLocal的key是什么
為了有個宏觀的認(rèn)識，我們先來看下ThreadLocal的內(nèi)存結(jié)構(gòu)圖
圖片
從內(nèi)存結(jié)構(gòu)圖，我們可以看到：
- Thread類中，有個ThreadLocal.ThreadLocalMap 的成員變量。
- ThreadLocalMap內(nèi)部維護(hù)了Entry數(shù)組，每個Entry代表一個完整的對象，key是ThreadLocal本身，value是ThreadLocal的泛型對象值。
關(guān)鍵源碼分析
對照著幾段關(guān)鍵源碼來看，更容易理解一點(diǎn)哈~我們回到Thread類源碼，可以看到成員變量ThreadLocalMap的初始值是為null
public class Thread implements Runnable {
//ThreadLocal.ThreadLocalMap是Thread的屬性
ThreadLocal.ThreadLocalMap threadLocals = null;
}ThreadLocalMap的關(guān)鍵源碼如下：
static class ThreadLocalMap {
static class Entry extends WeakReference<ThreadLocal<?>> {
/** The value associated with this ThreadLocal. */
Object value;
Entry(ThreadLocal<?> k, Object v) {
super(k);
value = v;
}
}
//Entry數(shù)組
private Entry[] table;
// ThreadLocalMap的構(gòu)造器，ThreadLocal作為key
ThreadLocalMap(ThreadLocal<?> firstKey, Object firstValue) {
table = new Entry[INITIAL_CAPACITY];
int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1);
table[i] = new Entry(firstKey, firstValue);
size = 1;
setThreshold(INITIAL_CAPACITY);
}
}ThreadLocal類中的關(guān)鍵set()方法：
public void set(T value) {
Thread t = Thread.currentThread(); //獲取當(dāng)前線程t
ThreadLocalMap map = getMap(t); //根據(jù)當(dāng)前線程獲取到ThreadLocalMap
if (map != null) //如果獲取的ThreadLocalMap對象不為空
map.set(this, value); //K，V設(shè)置到ThreadLocalMap中
else
createMap(t, value); //創(chuàng)建一個新的ThreadLocalMap
}
ThreadLocalMap getMap(Thread t) {
return t.threadLocals; //返回Thread對象的ThreadLocalMap屬性
}
void createMap(Thread t, T firstValue) { //調(diào)用ThreadLocalMap的構(gòu)造函數(shù)
t.threadLocals = new ThreadLocalMap(this, firstValue); this表示當(dāng)前類ThreadLocal
}ThreadLocal類中的關(guān)鍵get()方法：
public T get() {
Thread t = Thread.currentThread();//獲取當(dāng)前線程t
ThreadLocalMap map = getMap(t);//根據(jù)當(dāng)前線程獲取到ThreadLocalMap
if (map != null) { //如果獲取的ThreadLocalMap對象不為空
//由this（即ThreadLoca對象）得到對應(yīng)的Value，即ThreadLocal的泛型值
ThreadLocalMap.Entry e = map.getEntry(this);
if (e != null) {
@SuppressWarnings("unchecked")
T result = (T)e.value;
return result;
}
}
return setInitialValue(); //初始化threadLocals成員變量的值
}
private T setInitialValue() {
T value = initialValue(); //初始化value的值
Thread t = Thread.currentThread();
ThreadLocalMap map = getMap(t); //以當(dāng)前線程為key，獲取threadLocals成員變量，它是一個ThreadLocalMap
if (map != null)
map.set(this, value); //K，V設(shè)置到ThreadLocalMap中
else
createMap(t, value); //實例化threadLocals成員變量
return value;
}綜上所述：
- Thread線程類有一個類型為ThreadLocal.ThreadLocalMap的實例變量threadLocals，即每個線程都有一個屬于自己的ThreadLocalMap。
- ThreadLocalMap內(nèi)部維護(hù)著Entry數(shù)組，每個Entry代表一個完整的對象，key是ThreadLocal本身，value是ThreadLocal的泛型值。
- 并發(fā)多線程場景下，每個線程Thread，在往ThreadLocal里設(shè)置值的時候，都是往自己的ThreadLocalMap里存，讀也是以某個ThreadLocal作為引用，在自己的map里找對應(yīng)的key，從而可以實現(xiàn)了線程隔離。
Reentranlock，公平鎖/非公平鎖的實現(xiàn)
公平鎖和非公平鎖的實現(xiàn)都是基于AbstractQueuedSynchronizer（AQS），這是Java并發(fā)框架中用于構(gòu)建鎖和同步器的基礎(chǔ)框架。ReentrantLock內(nèi)部通過繼承AbstractQueuedSynchronizer（AQS）來實現(xiàn)鎖的機(jī)制。AQS使用一個volatile int state字段來表示鎖的狀態(tài)，以及一個內(nèi)部類Node來維護(hù)等待隊列。
AQS的核心方法
- getState(): 獲取state的值。
- setState(): 設(shè)置state的值。
- compareAndSetState(expected, update): 原子地更新state的值。
ReentrantLock的實現(xiàn)
在ReentrantLock的構(gòu)造函數(shù)中，你可以選擇創(chuàng)建公平鎖或非公平鎖。默認(rèn)情況下，不帶參數(shù)的構(gòu)造函數(shù)創(chuàng)建非公平鎖。
public ReentrantLock() {
sync = new NonfairSync();
}
public ReentrantLock(boolean fair) {
sync = fair ? new FairSync() : new NonfairSync();
}NonfairSync和FairSync分別擴(kuò)展了AbstractQueuedSynchronizer，并重寫了tryAcquire()方法。
非公平鎖（默認(rèn)）
非公平鎖試圖在獲取鎖時立即進(jìn)行CAS操作，即使已經(jīng)有其他線程在等待。
這意味著它可能會讓新來的線程“插隊”，這在理論上是不公平的，但在實踐中往往能提供更好的性能，因為減少了線程的等待時間。
在非公平鎖中，tryAcquire()方法首先嘗試獲取鎖，而不考慮是否有線程在等待隊列中。
protected final boolean nonfairTryAcquire(int acquires) {
final Thread current = Thread.currentThread();
int c = getState();
if (c == 0) {
// 直接嘗試獲取鎖
if (compareAndSetState(0, acquires)) {
setExclusiveOwnerThread(current);
return true;
}
} else if (current == getExclusiveOwnerThread()) {
// 可重入
int nextc = c + acquires;
if (nextc < 0)
throw new Error("Maximum lock count exceeded");
setState(nextc);
return true;
}
return false;
}公平鎖
公平鎖則會保證鎖的分配順序，即后來的線程必須等待前面的線程釋放鎖才能獲取。
這樣雖然理論上更公平，但可能增加線程等待的時間，從而影響性能。 在公平鎖中，tryAcquire()方法會檢查等待隊列中是否有線程在等待，如果有，則不會嘗試獲取鎖，除非隊列為空或當(dāng)前線程已經(jīng)是隊列的頭部。
protected final boolean tryAcquire(int acquires) {
final Thread current = Thread.currentThread();
int c = getState();
if (c == 0) {
// 檢查隊列中是否有等待線程
if (!hasQueuedPredecessors() &&
compareAndSetState(0, acquires)) {
setExclusiveOwnerThread(current);
return true;
}
} else if (current == getExclusiveOwnerThread()) {
// 可重入
int nextc = c + acquires;
if (nextc < 0)
throw new Error("Maximum lock count exceeded");
setState(nextc);
return true;
}
return false;
}synchronize鎖升級過程
synchronized關(guān)鍵字在Java中用于控制多線程對共享資源的訪問，確保同一時刻只有一個線程能夠執(zhí)行臨界區(qū)代碼。鎖升級機(jī)制允許鎖從一種成本較低的狀態(tài)升級到成本較高的狀態(tài)，具體包括以下幾種鎖狀態(tài)：
- 無鎖： 在沒有線程訪問同步塊的情況下，對象頭中的Mark Word中不包含鎖信息。
- 偏向鎖: 就是指一個線程多次重復(fù)訪問同一段同步代碼塊時，會在對象頭和棧幀中的鎖記里面添加偏向的線程ID，以后在該線程進(jìn)入和退出同步塊時不需要進(jìn)行CAS操作來加鎖和解鎖，只需要簡單地比對一下對象頭的markword里面是否存儲著指向當(dāng)前線程的偏向鎖。減少CAS加鎖帶來的開銷。
- 輕量級鎖：如果一個線程擁有偏向鎖，此時另一個線程嘗試使用CAS將對象頭的markword的鎖指針指向自己。如果失敗了，那么他會自旋嘗試獲取鎖。此時為輕量級鎖的狀態(tài)。
- 重量級鎖：當(dāng)自旋次數(shù)達(dá)到閾值，或者來了第三個線程爭奪鎖時，輕量級鎖就會升級為重量級鎖。
鎖升級過程是單向的，意味著一旦鎖升級到更重的級別，它就不會降級回到更輕的級別。這種機(jī)制可以避免不必要的鎖膨脹和收縮帶來的開銷，特別是在鎖競爭較少的情況下，可以顯著提高程序的執(zhí)行效率。同時，在對象的Mark Word中記錄了鎖的當(dāng)前狀態(tài)。
Mark Word是對象頭的一部分，它包含對象的元數(shù)據(jù)信息，如哈希碼、GC分代年齡、鎖狀態(tài)標(biāo)志、線程ID等。當(dāng)鎖升級時，Mark Word中的信息也會相應(yīng)地改變，以反映新的鎖狀態(tài)。
多個任務(wù)，同時達(dá)到臨界點(diǎn)，主線程執(zhí)行，怎么實現(xiàn)
在Java中，要實現(xiàn)多個任務(wù)同時達(dá)到某個臨界點(diǎn)后由主線程執(zhí)行某些操作，可以使用CountDownLatch或者CyclicBarrier這兩個工具類，它們都位于java.util.concurrent包下。
下面分別介紹這兩種方式的使用方法：
使用CountDownLatch
CountDownLatch是一個同步輔助類，它允許一個或多個線程等待直到其他線程完成了操作。它通過一個計數(shù)器來實現(xiàn)這一功能，每當(dāng)一個線程完成了操作，計數(shù)器減一；當(dāng)計數(shù)器到達(dá)零時，所有因為計數(shù)器未到達(dá)零而在await()方法上等待的線程都將被釋放。
import java.util.concurrent.CountDownLatch;
public class CountDownLatchExample {
public static void main(String[] args) throws InterruptedException {
final int threadCount = 5;
final CountDownLatch latch = new CountDownLatch(threadCount);
for (int i = 0; i < threadCount; i++) {
new Thread(() -> {
// 執(zhí)行一些操作...
System.out.println(Thread.currentThread().getName() + " is ready.");
latch.countDown();
}).start();
}
// 等待所有線程完成它們的操作
latch.await();
System.out.println("All threads have reached the critical point. Main thread continues...");
// 主線程繼續(xù)執(zhí)行...
}
}使用CyclicBarrier
CyclicBarrier與CountDownLatch類似，也允許一組線程互相等待直到到達(dá)某個公共屏障點(diǎn)（barrier）。但是CyclicBarrier支持在屏障點(diǎn)執(zhí)行一個回調(diào)操作，并且在每次所有參與線程都到達(dá)屏障點(diǎn)后，它可以被重用。
import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.CyclicBarrier;
public class CyclicBarrierExample {
public static void main(String[] args) {
final int threadCount = 5;
final CyclicBarrier barrier = new CyclicBarrier(threadCount, () -> {
System.out.println("All threads have reached the critical point. Main thread executes callback...");
// 主線程在這里執(zhí)行回調(diào)操作
});
for (int i = 0; i < threadCount; i++) {
new Thread(() -> {
// 執(zhí)行一些操作...
System.out.println(Thread.currentThread().getName() + " is ready.");
try {
barrier.await(); // 等待所有線程到達(dá)屏障點(diǎn)
} catch (InterruptedException | BrokenBarrierException e) {
e.printStackTrace();
}
}).start();
}
}
}在這兩個例子中，多個線程各自執(zhí)行一些操作，當(dāng)它們都到達(dá)臨界點(diǎn)時，主線程才繼續(xù)執(zhí)行后續(xù)的操作。根據(jù)具體的應(yīng)用場景，你可以選擇使用CountDownLatch或CyclicBarrier。如果只需要一次性觸發(fā)事件，可以選擇CountDownLatch；如果需要多次循環(huán)等待所有線程到達(dá)，CyclicBarrier可能更加合適。
CyclicBarrier的實現(xiàn)
方法解析
圖片
- CyclicBarrier(int parties, Runnable barrierAction) 創(chuàng)建一個CyclicBarrier實例，parties指定參與相互等待的線程數(shù)，barrierAction指定當(dāng)所有線程到達(dá)屏障點(diǎn)之后，首先執(zhí)行的操作，該操作由最后一個進(jìn)入屏障點(diǎn)的線程執(zhí)行。
- CyclicBarrier(int parties) 創(chuàng)建一個CyclicBarrier實例，parties指定參與相互等待的線程數(shù)。
- getParties() 返回參與相互等待的線程數(shù)。
- await() 該方法被調(diào)用時表示當(dāng)前線程已經(jīng)到達(dá)屏障點(diǎn)，當(dāng)前線程阻塞進(jìn)入休眠狀態(tài)，直到所有線程都到達(dá)屏障點(diǎn)，當(dāng)前線程才會被喚醒。
- await(long timeout, TimeUnit unit) 該方法被調(diào)用時表示當(dāng)前線程已經(jīng)到達(dá)屏障點(diǎn)，當(dāng)前線程阻塞進(jìn)入休眠狀態(tài)，在timeout指定的超時時間內(nèi)，等待其他參與線程到達(dá)屏障點(diǎn)；如果超出指定的等待時間，則拋出TimeoutException異常，如果該時間小于等于零，則此方法根本不會等待。
- isBroken() 判斷此屏障是否處于中斷狀態(tài)。如果因為構(gòu)造或最后一次重置而導(dǎo)致中斷或超時，從而使一個或多個參與者擺脫此屏障點(diǎn)，或者因為異常而導(dǎo)致某個屏障操作失敗，則返回true；否則返回false。
- reset() 將屏障重置為其初始狀態(tài)。
- getNumberWaiting() 返回當(dāng)前在屏障處等待的參與者數(shù)目，此方法主要用于調(diào)試和斷言。
源碼解析
CyclicBarrier(int parties, Runnable barrierAction)和await()方法是CyclicBarrier的核心，本篇重點(diǎn)分析這兩個方法的背后實現(xiàn)原理。 首先，看一下CyclicBarrier內(nèi)聲明的一些屬性信息：
//用于保護(hù)屏障入口的鎖
private final ReentrantLock lock = new ReentrantLock();
//線程等待條件
private final Condition trip = lock.newCondition();
//記錄參與等待的線程數(shù)
private final int parties;
//當(dāng)所有線程到達(dá)屏障點(diǎn)之后，首先執(zhí)行的命令
private final Runnable barrierCommand;
private Generation generation = new Generation();
//實際中仍在等待的線程數(shù)，每當(dāng)有一個線程到達(dá)屏障點(diǎn)，count值就會減一；當(dāng)一次新的運(yùn)算開始后，count的值被重置為parties
private int count;其中，Generation是CyclicBarrier的一個靜態(tài)內(nèi)部類，它只有一個boolean類型的屬性，具體代碼如下：
private static class Generation {
boolean broken = false;
}當(dāng)使用構(gòu)造方法創(chuàng)建CyclicBarrier實例的時候，就是給上面這些屬性賦值，
//創(chuàng)建一個CyclicBarrier實例，parties指定參與相互等待的線程數(shù)，
//barrierAction指定當(dāng)所有線程到達(dá)屏障點(diǎn)之后，首先執(zhí)行的操作，該操作由最后一個進(jìn)入屏障點(diǎn)的線程執(zhí)行。
public CyclicBarrier(int parties, Runnable barrierAction) {
if (parties <= 0) throw new IllegalArgumentException();
this.parties = parties;
this.count = parties;
this.barrierCommand = barrierAction;
}
//創(chuàng)建一個CyclicBarrier實例，parties指定參與相互等待的線程數(shù)
public CyclicBarrier(int parties) {
this(parties, null);
}當(dāng)調(diào)用await()方法時，當(dāng)前線程已經(jīng)到達(dá)屏障點(diǎn)，當(dāng)前線程阻塞進(jìn)入休眠狀態(tài)，
//該方法被調(diào)用時表示當(dāng)前線程已經(jīng)到達(dá)屏障點(diǎn)，當(dāng)前線程阻塞進(jìn)入休眠狀態(tài)
//直到所有線程都到達(dá)屏障點(diǎn)，當(dāng)前線程才會被喚醒
public int await() throws InterruptedException, BrokenBarrierException {
try {
return dowait(false, 0L);
} catch (TimeoutException toe) {
throw new Error(toe); // cannot happen;
}
}
//該方法被調(diào)用時表示當(dāng)前線程已經(jīng)到達(dá)屏障點(diǎn)，當(dāng)前線程阻塞進(jìn)入休眠狀態(tài)
//在timeout指定的超時時間內(nèi)，等待其他參與線程到達(dá)屏障點(diǎn)
//如果超出指定的等待時間，則拋出TimeoutException異常，如果該時間小于等于零，則此方法根本不會等待
public int await(long timeout, TimeUnit unit)
throws InterruptedException,
BrokenBarrierException,
TimeoutException {
return dowait(true, unit.toNanos(timeout));
}
private int dowait(boolean timed, long nanos)
throws InterruptedException, BrokenBarrierException,
TimeoutException {
//使用獨(dú)占資源鎖控制多線程并發(fā)進(jìn)入這段代碼
final ReentrantLock lock = this.lock;
//獨(dú)占鎖控制線程并發(fā)訪問
lock.lock();
try {
final Generation g = generation;
if (g.broken)
throw new BrokenBarrierException();
//如果線程中斷，則喚醒所有等待線程
if (Thread.interrupted()) {
breakBarrier();
throw new InterruptedException();
}
//每調(diào)用一次await()方法，計數(shù)器就減一
int index = --count;
//當(dāng)計數(shù)器值等于0的時
if (index == 0) { // tripped
boolean ranAction = false;
try {
final Runnable command = barrierCommand;
//如果在創(chuàng)建CyclicBarrier實例時設(shè)置了barrierAction，則先執(zhí)行barrierAction
if (command != null)
command.run();
ranAction = true;
//當(dāng)所有參與的線程都到達(dá)屏障點(diǎn)，為喚醒所有處于休眠狀態(tài)的線程做準(zhǔn)備工作
//需要注意的是，喚醒所有阻塞線程不是在這里
nextGeneration();
return 0;
} finally {
if (!ranAction)
breakBarrier();
}
}
// loop until tripped, broken, interrupted, or timed out
for (;;) {
try {
if (!timed)
//讓當(dāng)前執(zhí)行的線程阻塞，處于休眠狀態(tài)
trip.await();
else if (nanos > 0L)
//讓當(dāng)前執(zhí)行的線程阻塞，在超時時間內(nèi)處于休眠狀態(tài)
nanos = trip.awaitNanos(nanos);
} catch (InterruptedException ie) {
if (g == generation && ! g.broken) {
breakBarrier();
throw ie;
} else {
// We're about to finish waiting even if we had not
// been interrupted, so this interrupt is deemed to
// "belong" to subsequent execution.
Thread.currentThread().interrupt();
}
}
if (g.broken)
throw new BrokenBarrierException();
if (g != generation)
return index;
if (timed && nanos <= 0L) {
breakBarrier();
throw new TimeoutException();
}
}
} finally {
//釋放獨(dú)占鎖
lock.unlock();
}
}
private void nextGeneration() {
//為喚醒所有處于休眠狀態(tài)的線程做準(zhǔn)備工作
trip.signalAll();
//重置count值為parties
count = parties;
//重置中斷狀態(tài)為false
generation = new Generation();
}
private void breakBarrier() {
//重置中斷狀態(tài)為true
generation.broken = true;
//重置count值為parties
count = parties;
//為喚醒所有處于休眠狀態(tài)的線程做準(zhǔn)備工作
trip.signalAll();
}到這里CyclicBarrier的實現(xiàn)原理基本已經(jīng)都清楚了，下面來深入源碼分析一下線程阻塞代碼trip.await()和線程喚醒trip.signalAll()的實現(xiàn)。
//await()是AQS內(nèi)部類ConditionObject中的方法
public final void await() throws InterruptedException {
//如果線程中斷拋異常
if (Thread.interrupted())
throw new InterruptedException();
//新建Node節(jié)點(diǎn)，并將新節(jié)點(diǎn)加入到Condition等待隊列中
//Condition等待隊列是AQS內(nèi)部類ConditionObject實現(xiàn)的，ConditionObject有兩個屬性，分別是firstWaiter和lastWaiter，都是Node類型
//firstWaiter和lastWaiter分別用于代表Condition等待隊列的頭結(jié)點(diǎn)和尾節(jié)點(diǎn)
Node node = addConditionWaiter();
//釋放獨(dú)占鎖，讓其它線程可以獲取到dowait()方法中的獨(dú)占鎖
int savedState = fullyRelease(node);
int interruptMode = 0;
//檢測此節(jié)點(diǎn)是否在資源等待隊列(AQS同步隊列)中，
//如果不在，說明此線程還沒有競爭資源鎖的權(quán)利，此線程繼續(xù)阻塞，直到檢測到此節(jié)點(diǎn)在資源等待隊列上(AQS同步隊列)中
//這里出現(xiàn)了兩個等待隊列，分別是Condition等待隊列和AQS資源鎖等待隊列(或者說是同步隊列)
//Condition等待隊列是等待被喚醒的線程隊列，AQS資源鎖等待隊列是等待獲取資源鎖的隊列
while (!isOnSyncQueue(node)) {
//阻塞當(dāng)前線程，當(dāng)前線程進(jìn)入休眠狀態(tài)，可以看到這里使用LockSupport.park阻塞當(dāng)前線程
LockSupport.park(this);
if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
break;
}
if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
interruptMode = REINTERRUPT;
if (node.nextWaiter != null) // clean up if cancelled
unlinkCancelledWaiters();
if (interruptMode != 0)
reportInterruptAfterWait(interruptMode);
}
//addConditionWaiter()是AQS內(nèi)部類ConditionObject中的方法
private Node addConditionWaiter() {
Node t = lastWaiter;
// 將condition等待隊列中，節(jié)點(diǎn)狀態(tài)不是CONDITION的節(jié)點(diǎn)，從condition等待隊列中移除
if (t != null && t.waitStatus != Node.CONDITION) {
unlinkCancelledWaiters();
t = lastWaiter;
}
//以下操作是用此線程構(gòu)造一個節(jié)點(diǎn)，并將之加入到condition等待隊列尾部
Node node = new Node(Thread.currentThread(), Node.CONDITION);
if (t == null)
firstWaiter = node;
else
t.nextWaiter = node;
lastWaiter = node;
return node;
}
//signalAll是AQS內(nèi)部類ConditionObject中的方法
public final void signalAll() {
if (!isHeldExclusively())
throw new IllegalMonitorStateException();
//Condition等待隊列的頭結(jié)點(diǎn)
Node first = firstWaiter;
if (first != null)
doSignalAll(first);
}
private void doSignalAll(Node first) {
lastWaiter = firstWaiter = null;
do {
Node next = first.nextWaiter;
first.nextWaiter = null;
//將Condition等待隊列中的Node節(jié)點(diǎn)按之前順序都轉(zhuǎn)移到了AQS同步隊列中
transferForSignal(first);
first = next;
} while (first != null);
}
final boolean transferForSignal(Node node) {
if (!compareAndSetWaitStatus(node, Node.CONDITION, 0))
return false;
//這里將Condition等待隊列中的Node節(jié)點(diǎn)插入到AQS同步隊列的尾部
Node p = enq(node);
int ws = p.waitStatus;
if (ws > 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL))
LockSupport.unpark(node.thread);
return true;
}
//ReentrantLock#unlock()方法
public void unlock() {
//Sync是ReentrantLock的內(nèi)部類，繼承自AbstractQueuedSynchronizer，它是ReentrantLock中公平鎖和非公平鎖的基礎(chǔ)實現(xiàn)
sync.release(1);
}
public final boolean release(int arg) {
//釋放鎖
if (tryRelease(arg)) {
//AQS同步隊列頭結(jié)點(diǎn)
Node h = head;
if (h != null && h.waitStatus != 0)
//喚醒節(jié)點(diǎn)中的線程
unparkSuccessor(h);
return true;
}
return false;
}
private void unparkSuccessor(Node node) {
int ws = node.waitStatus;
if (ws < 0)
compareAndSetWaitStatus(node, ws, 0);
Node s = node.next;
if (s == null || s.waitStatus > 0) {
s = null;
for (Node t = tail; t != null && t != node; t = t.prev)
if (t.waitStatus <= 0)
s = t;
}
if (s != null)
//喚醒阻塞線程
LockSupport.unpark(s.thread);
}原理總結(jié)
CyclicBarrier簡單使用樣例
public class CyclicBarrierDemo {
@Test
public void test() {
final CyclicBarrier barrier = new CyclicBarrier(2, myThread);
new Thread(new Runnable() {
@Override
public void run() {
try {
System.out.println(Thread.currentThread().getName());
barrier.await();
System.out.println(Thread.currentThread().getName());
} catch (Exception e) {
e.printStackTrace();
}
}
}, "thread1").start();
new Thread(new Runnable() {
@Override
public void run() {
try {
System.out.println(Thread.currentThread().getName());
barrier.await();
System.out.println(Thread.currentThread().getName());
} catch (Exception e) {
e.printStackTrace();
}
}
}, "thread2").start();
}
Thread myThread = new Thread(new Runnable() {
@Override
public void run() {
System.out.println("myThread");
}
}, "thread3");
}結(jié)果輸出：
thread1
thread2
myThread
thread2
thread1用上面的示例總結(jié)一下CyclicBarrier的await方法實現(xiàn)。
假設(shè)線程thread1和線程thread2都執(zhí)行到CyclicBarrier的await()，都進(jìn)入dowait(boolean timed, long nanos)，thread1先獲取到獨(dú)占鎖，執(zhí)行到 --count 的時，index等于1，所以進(jìn)入下面的for循環(huán)，接著執(zhí)行trip.await()，進(jìn)入await()方法，執(zhí)行Node node = addConditionWaiter() 將當(dāng)前線程構(gòu)造成Node節(jié)點(diǎn)并加入到 Condition 等待隊列中，然后釋放獲取到的獨(dú)占鎖，當(dāng)前線程進(jìn)入阻塞狀態(tài)。
此時，線程thread2可以獲取獨(dú)占鎖，繼續(xù)執(zhí)行--count，index等于0，所以先執(zhí)行command.run()，輸出myThread，然后執(zhí)行nextGeneration()，nextGeneration()中 trip.signalAll() 只是將Condition等待隊列中的Node節(jié)點(diǎn)按之前順序都轉(zhuǎn)移到了AQS同步隊列中，這里也就是將thread1對應(yīng)的Node節(jié)點(diǎn)轉(zhuǎn)移到了AQS同步隊列中，thread2執(zhí)行完nextGeneration()，返回return 0之前，細(xì)看代碼還需要執(zhí)行l(wèi)ock.unlock()，這里會執(zhí)行到ReentrantLock的unlock()方法，最終執(zhí)行到AQS的unparkSuccessor(Node node)方法，從AQS同步隊列中的頭結(jié)點(diǎn)開始釋放節(jié)點(diǎn)，喚醒節(jié)點(diǎn)對應(yīng)的線程，即thread1恢復(fù)執(zhí)行。
如果有三個線程thread1、thread2和thread3，假設(shè)線程執(zhí)行順序是thread1、thread2、thread3，那么thread1、thread2對應(yīng)的Node節(jié)點(diǎn)會被加入到Condition等待隊列中。
當(dāng)thread3執(zhí)行的時候，會將thread1、thread2對應(yīng)的Node節(jié)點(diǎn)按thread1、thread2順序轉(zhuǎn)移到AQS同步隊列中，thread3執(zhí)行l(wèi)ock.unlock()的時候，會先喚醒thread1，thread1恢復(fù)繼續(xù)執(zhí)行，thread1執(zhí)行到lock.unlock()的時候會喚醒thread2恢復(fù)執(zhí)行。
CountdownLatch和CyclicBarrier，哪個可以復(fù)用，為什么
CyclicBarrier可以復(fù)用。
CyclicBarrier設(shè)計成可復(fù)用是因為它內(nèi)部維護(hù)了一個“generation”計數(shù)器，這使得即使所有線程通過了一次屏障，CyclicBarrier也可以準(zhǔn)備下一次的屏障。
如果在某個時刻線程因為異常或其他原因沒有成功通過屏障，CyclicBarrier可以通過調(diào)用reset()方法重置狀態(tài)，這會清除所有等待線程的狀態(tài)，并允許新的線程組再次使用同一個CyclicBarrier實例。
源碼部分
public void reset() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
breakBarrier(); // break the current generation
nextGeneration(); // start a new generation
} finally {
lock.unlock();
}
}
private void breakBarrier() {
generation.broken = true;
count = parties;
trip.signalAll();
}
private void nextGeneration() {
// signal completion of last generation
trip.signalAll();
// set up next generation
count = parties;
generation = new Generation();
}多線程在實際應(yīng)用的場景
- 并發(fā)處理和并行計算：在Web服務(wù)器、數(shù)據(jù)庫服務(wù)器或任何網(wǎng)絡(luò)服務(wù)器中，多線程可以同時處理多個客戶端的請求，提高服務(wù)器的吞吐量和響應(yīng)能力。并且，在執(zhí)行大量的獨(dú)立任務(wù)時，如圖像處理、數(shù)據(jù)清洗、報表生成等，可以將任務(wù)分解并分配給多個線程并行處理，加速處理過程。
- 異步操作和事件驅(qū)動：在圖形用戶界面中，多線程可以用來處理耗時的后臺任務(wù)，如文件讀寫、網(wǎng)絡(luò)請求等，以避免阻塞UI線程，確保界面的響應(yīng)性。并且，使用多線程處理網(wǎng)絡(luò)請求和響應(yīng)，可以實現(xiàn)非阻塞I/O，提高網(wǎng)絡(luò)應(yīng)用的效率。
- 定時任務(wù)和后臺服務(wù)：使用多線程實現(xiàn)定時任務(wù)，如定期備份、日志輪轉(zhuǎn)、系統(tǒng)監(jiān)控等?；蛘咦鋈玎]件發(fā)送、日志記錄、數(shù)據(jù)分析等長時間運(yùn)行的服務(wù)，可以獨(dú)立于主程序線程執(zhí)行。
- 分布式計算和云計算：在大數(shù)據(jù)處理中，多線程或多進(jìn)程可以并行執(zhí)行Map和Reduce操作，提高數(shù)據(jù)處理速度。在微服務(wù)架構(gòu)中，每個服務(wù)可以獨(dú)立運(yùn)行在自己的線程或進(jìn)程中，提高系統(tǒng)的并發(fā)能力和容錯性。
寫過SpringBoot starter嗎
步驟1: 創(chuàng)建Maven項目
首先，需要創(chuàng)建一個新的Maven項目。在pom.xml中添加Spring Boot的starter parent和一些必要的依賴。例如：
<parent>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-starter-parent</artifactId>
<version>2.7.0</version>
<relativePath/> <!-- lookup parent from repository -->
</parent>
<dependencies>
<dependency>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-starter-web</artifactId>
</dependency>
</dependencies>步驟2: 添加自動配置
在src/main/resources/META-INF/spring.factories中添加自動配置的元數(shù)據(jù)。例如：
org.springframework.boot.autoconfigure.EnableAutoConfiguration = com.example.starter.MyAutoConfiguration然后，創(chuàng)建MyAutoConfiguration類，該類需要@Configuration和@EnableConfigurationProperties注解。@EnableConfigurationProperties用于啟用你定義的配置屬性類。
@Configuration
@EnableConfigurationProperties(MyProperties.class)
public class MyAutoConfiguration {
@Autowired
private MyProperties properties;
@Bean
public MyService myService() {
return new MyServiceImpl(properties);
}
}步驟3: 創(chuàng)建配置屬性類
創(chuàng)建一個配置屬性類，使用@ConfigurationProperties注解來綁定配置文件中的屬性。
@ConfigurationProperties(prefix = "my")
public class MyProperties {
private String name;
// getters and setters
}步驟4: 創(chuàng)建服務(wù)和控制器
創(chuàng)建一個服務(wù)類和服務(wù)實現(xiàn)類，以及一個控制器來展示你的starter的功能。
@Service
public interface MyService {
String getName();
}
@Service
public class MyServiceImpl implements MyService {
private final MyProperties properties;
public MyServiceImpl(MyProperties properties) {
this.properties = properties;
}
@Override
public String getName() {
return properties.getName();
}
}
@RestController
public class MyController {
private final MyService myService;
public MyController(MyService myService) {
this.myService = myService;
}
@GetMapping("/name")
public String getName() {
return myService.getName();
}
}步驟5: 發(fā)布Starter
將你的starter發(fā)布到Maven倉庫，無論是私有的還是公共的，如Nexus或Maven Central。
步驟6: 使用Starter
在你的主應(yīng)用的pom.xml中添加你的starter依賴，然后在application.yml或application.properties中配置你的屬性。
my:
name: Hello WorldBean的生命周期
圖片
- Spring啟動，查找并加載需要被Spring管理的bean，進(jìn)行Bean的實例化
- Bean實例化后對將Bean的引入和值注入到Bean的屬性中
- 如果Bean實現(xiàn)了BeanNameAware接口的話，Spring將Bean的Id傳遞給setBeanName()方法
- 如果Bean實現(xiàn)了BeanFactoryAware接口的話，Spring將調(diào)用setBeanFactory()方法，將BeanFactory容器實例傳入
- 如果Bean實現(xiàn)了ApplicationContextAware接口的話，Spring將調(diào)用Bean的setApplicationContext()方法，將bean所在應(yīng)用上下文引用傳入進(jìn)來。
- 如果Bean實現(xiàn)了BeanPostProcessor接口，Spring就將調(diào)用他們的postProcessBeforeInitialization()方法。
- 如果Bean 實現(xiàn)了InitializingBean接口，Spring將調(diào)用他們的afterPropertiesSet()方法。類似的，如果bean使用init-method聲明了初始化方法，該方法也會被調(diào)用
- 如果Bean 實現(xiàn)了BeanPostProcessor接口，Spring就將調(diào)用他們的postProcessAfterInitialization()方法。
- 此時，Bean已經(jīng)準(zhǔn)備就緒，可以被應(yīng)用程序使用了。他們將一直駐留在應(yīng)用上下文中，直到應(yīng)用上下文被銷毀。
- 如果bean實現(xiàn)了DisposableBean接口，Spring將調(diào)用它的destory()接口方法，同樣，如果bean使用了destory-method 聲明銷毀方法，該方法也會被調(diào)用。
MySQL
MySQL索引什么時候回表
在MySQL中，回表是指在使用非聚集索引（也稱為二級索引或輔助索引）進(jìn)行查詢時，需要額外訪問主鍵索引（聚集索引）以獲取完整的行數(shù)據(jù)的過程。這是因為非聚集索引中通常只存儲了索引列的值和指向主鍵的引用，而不包含完整的行數(shù)據(jù)。
回表通常在以下情況發(fā)生：
- 非覆蓋索引查詢：當(dāng)查詢語句所請求的數(shù)據(jù)列不在非聚集索引中，而是需要從主鍵索引中獲取時，就會發(fā)生回表。例如，如果查詢SELECT * FROM table WHERE column1 = value;，且column1是非聚集索引，那么為了返回所有列，MySQL需要根據(jù)column1索引中的主鍵引用回到主鍵索引中獲取完整的行數(shù)據(jù)。
- 索引列不完全匹配查詢條件：如果查詢條件涉及到多個列，而索引僅包含其中的一部分列，那么MySQL也需要回表來獲取缺失列的數(shù)據(jù)。
- ORDER BY 或 LIMIT 子句：即使在一個非聚集索引上進(jìn)行查詢，如果查詢中包含了ORDER BY子句或LIMIT子句，并且排序或限制的依據(jù)不是索引中的列，也可能導(dǎo)致回表。
MySQL執(zhí)行update語句后，主鍵索引、輔助索引、聯(lián)合索引，數(shù)據(jù)都是怎么變的
主鍵索引的變化
主鍵索引通常是聚集索引，在InnoDB中，數(shù)據(jù)行實際上是存儲在主鍵索引的B+樹結(jié)構(gòu)中的葉子節(jié)點(diǎn)上的。這意味著數(shù)據(jù)行的物理位置是由主鍵值確定的。當(dāng)你執(zhí)行一個更新操作時：
- 如果更新的是非主鍵列，那么InnoDB會更新主鍵索引中對應(yīng)行的非主鍵列數(shù)據(jù)，但主鍵值不變，所以行的物理位置也不會改變。
- 如果更新的是主鍵列，那么InnoDB需要移動數(shù)據(jù)行到新的物理位置，因為主鍵索引決定了數(shù)據(jù)行的位置。這會導(dǎo)致整個數(shù)據(jù)行被移動，并且所有的輔助索引中指向該行的指針也需要更新，以指向新的主鍵值。
輔助索引的變化
輔助索引（也稱非聚集索引或二級索引）在InnoDB中包含兩部分信息：索引列的值和主鍵值（或主鍵的一部分，取決于索引設(shè)計）。更新操作對輔助索引的影響如下：
- 更新索引列：如果更新的是輔助索引所包含的列，那么InnoDB會更新該索引中的值。如果更新后的值已經(jīng)存在于索引中，那么可能會觸發(fā)索引的重復(fù)檢查，這在唯一索引中尤為關(guān)鍵。
- 更新主鍵列：如果更新操作改變了主鍵的值，那么所有相關(guān)的輔助索引中的主鍵值都需要更新，以指向新的主鍵值。
聯(lián)合索引的變化
聯(lián)合索引是包含多個列的索引。更新操作對聯(lián)合索引的影響取決于更新的是哪些列：
- 更新索引內(nèi)的列：如果更新的是聯(lián)合索引中的任何一列，那么InnoDB會更新該索引條目中的相應(yīng)值。
- 更新主鍵列：如果更新的是主鍵，那么聯(lián)合索引中指向該行的主鍵值也需要更新。
MVCC的實現(xiàn)
MVCC允許多個事務(wù)同時讀取同一行數(shù)據(jù)，而不會彼此阻塞，每個事務(wù)看到的數(shù)據(jù)版本是該事務(wù)開始時的數(shù)據(jù)版本。這意味著，如果其他事務(wù)在此期間修改了數(shù)據(jù)，正在運(yùn)行的事務(wù)仍然看到的是它開始時的數(shù)據(jù)狀態(tài)，從而實現(xiàn)了非阻塞讀操作。
對于「讀提交」和「可重復(fù)讀」隔離級別的事務(wù)來說，它們是通過 Read View 來實現(xiàn)的，它們的區(qū)別在于創(chuàng)建 Read View 的時機(jī)不同，大家可以把 Read View 理解成一個數(shù)據(jù)快照，就像相機(jī)拍照那樣，定格某一時刻的風(fēng)景。
- 「讀提交」隔離級別是在「每個select語句執(zhí)行前」都會重新生成一個 Read View；
- 「可重復(fù)讀」隔離級別是執(zhí)行第一條select時，生成一個 Read View，然后整個事務(wù)期間都在用這個 Read View。
Read View 有四個重要的字段：
圖片
- m_ids ：指的是在創(chuàng)建 Read View 時，當(dāng)前數(shù)據(jù)庫中「活躍事務(wù)」的事務(wù) id 列表，注意是一個列表，“活躍事務(wù)”指的就是，啟動了但還沒提交的事務(wù)。
- min_trx_id ：指的是在創(chuàng)建 Read View 時，當(dāng)前數(shù)據(jù)庫中「活躍事務(wù)」中事務(wù) id 最小的事務(wù)，也就是 m_ids 的最小值。
- max_trx_id ：這個并不是 m_ids 的最大值，而是創(chuàng)建 Read View 時當(dāng)前數(shù)據(jù)庫中應(yīng)該給下一個事務(wù)的 id 值，也就是全局事務(wù)中最大的事務(wù) id 值 + 1；
- creator_trx_id ：指的是創(chuàng)建該 Read View 的事務(wù)的事務(wù) id。
對于使用 InnoDB 存儲引擎的數(shù)據(jù)庫表，它的聚簇索引記錄中都包含下面兩個隱藏列：
圖片
- trx_id，當(dāng)一個事務(wù)對某條聚簇索引記錄進(jìn)行改動時，就會把該事務(wù)的事務(wù) id 記錄在 trx_id 隱藏列里；
- roll_pointer，每次對某條聚簇索引記錄進(jìn)行改動時，都會把舊版本的記錄寫入到 undo 日志中，然后這個隱藏列是個指針，指向每一個舊版本記錄，于是就可以通過它找到修改前的記錄。
在創(chuàng)建 Read View 后，我們可以將記錄中的 trx_id 劃分這三種情況：
圖片
一個事務(wù)去訪問記錄的時候，除了自己的更新記錄總是可見之外，還有這幾種情況：
- 如果記錄的 trx_id 值小于 Read View 中的 min_trx_id 值，表示這個版本的記錄是在創(chuàng)建 Read View 前已經(jīng)提交的事務(wù)生成的，所以該版本的記錄對當(dāng)前事務(wù)可見。
- 如果記錄的 trx_id 值大于等于 Read View 中的 max_trx_id 值，表示這個版本的記錄是在創(chuàng)建 Read View 后才啟動的事務(wù)生成的，所以該版本的記錄對當(dāng)前事務(wù)不可見。
- 如果記錄的 trx_id 值在 Read View 的 min_trx_id 和 max_trx_id 之間，需要判斷 trx_id 是否在 m_ids 列表中：
如果記錄的 trx_id 在 m_ids 列表中，表示生成該版本記錄的活躍事務(wù)依然活躍著（還沒提交事務(wù)），所以該版本的記錄對當(dāng)前事務(wù)不可見。
如果記錄的 trx_id 不在 m_ids列表中，表示生成該版本記錄的活躍事務(wù)已經(jīng)被提交，所以該版本的記錄對當(dāng)前事務(wù)可見。
這種通過「版本鏈」來控制并發(fā)事務(wù)訪問同一個記錄時的行為就叫 MVCC（多版本并發(fā)控制）。
項目
- 分庫分表是怎么做的，熱點(diǎn)問題怎么解決
算法
旋轉(zhuǎn)鏈表
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (k == 0 || head == null || head.next == null) {
return head;
}
int n = 1;
ListNode iter = head;
while (iter.next != null) {
iter = iter.next;
n++;
}
int add = n - k % n;
if (add == n) {
return head;
}
iter.next = head;
while (add-- > 0) {
iter = iter.next;
}
ListNode ret = iter.next;
iter.next = null;
return ret;
}
}
