還得是美團(tuán)啊！依舊是校招大戶，給力！

因此，實(shí)際應(yīng)用中需要在使用完ThreadLocal變量后調(diào)用remove()方法釋放資源。

強(qiáng)引用，軟引用，弱引用，虛引用，舉例子說明分別怎么使用

強(qiáng)引用 (Strong Reference)

這是最常見的引用類型，只要一個(gè)對象被強(qiáng)引用關(guān)聯(lián)，垃圾收集器永遠(yuǎn)不會回收這個(gè)對象，即使是在內(nèi)存不足的情況下。示例代碼：

String str = new String("Hello");
// str 是一個(gè)強(qiáng)引用，只要 str 存在，"Hello" 對象就不會被垃圾回收。

軟引用 (Soft Reference)

軟引用用于描述一些“有用但不是必須”的對象。如果內(nèi)存空間足夠，軟引用的對象不會被回收，但如果內(nèi)存不足，垃圾收集器會回收軟引用的對象。示例代碼：

import java.lang.ref.SoftReference;

SoftReference<String> softRef = new SoftReference<>(new String("Hello"));
String data = softRef.get(); // 如果軟引用的對象還沒有被回收，get() 將返回它
if (data == null) {
    System.out.println("Object has been garbage collected.");
} else {
    System.out.println("Object is still alive: " + data);
}

弱引用 (Weak Reference)

弱引用的對象擁有更短的生命周期。只要垃圾收集器進(jìn)行清理，無論內(nèi)存是否充足，弱引用的對象都會被回收。示例代碼：

import java.lang.ref.WeakReference;

WeakReference<String> weakRef = new WeakReference<>(new String("Hello"));
String data = weakRef.get(); // 如果弱引用的對象還沒有被回收，get() 將返回它
if (data == null) {
    System.out.println("Object has been garbage collected.");
} else {
    System.out.println("Object is still alive: " + data);
}

虛引用 (Phantom Reference)

虛引用是最弱的引用類型。一個(gè)對象如果有虛引用存在，幾乎跟沒有引用一樣，無法通過虛引用來獲取對象實(shí)例。虛引用的主要用途是跟蹤對象的垃圾回收過程。示例代碼：

import java.lang.ref.PhantomReference;
import java.lang.ref.ReferenceQueue;

ReferenceQueue<String> queue = new ReferenceQueue<>();
PhantomReference<String> phantomRef = new PhantomReference<>(new String("Hello"), queue);

// 無法通過 PhantomReference 獲取對象實(shí)例
String data = phantomRef.get(); // 返回 null
if (queue.poll() != null) {
    System.out.println("Object has been garbage collected and reference enqueued.");
}

在使用虛引用時(shí)，通常需要和ReferenceQueue配合使用。當(dāng)垃圾收集器準(zhǔn)備回收一個(gè)對象時(shí)，如果發(fā)現(xiàn)它有虛引用，就會把這個(gè)虛引用加入到與之關(guān)聯(lián)的引用隊(duì)列中。通過檢查這個(gè)隊(duì)列，可以了解對象何時(shí)被回收。

spring循環(huán)依賴是什么？怎么解決？

循環(huán)依賴指的是兩個(gè)類中的屬性相互依賴對方：例如 A 類中有 B 屬性，B 類中有 A屬性，從而形成了一個(gè)依賴閉環(huán)，如下圖。循環(huán)依賴問題在Spring中主要有三種情況：

• 第一種：通過構(gòu)造方法進(jìn)行依賴注入時(shí)產(chǎn)生的循環(huán)依賴問題。
• 第二種：通過setter方法進(jìn)行依賴注入且是在多例（原型）模式下產(chǎn)生的循環(huán)依賴問題。
• 第三種：通過setter方法進(jìn)行依賴注入且是在單例模式下產(chǎn)生的循環(huán)依賴問題。

只有【第三種方式】的循環(huán)依賴問題被 Spring 解決了，其他兩種方式在遇到循環(huán)依賴問題時(shí)，Spring都會產(chǎn)生異常。Spring 解決單例模式下的setter循環(huán)依賴問題的主要方式是通過三級緩存解決循環(huán)依賴。三級緩存指的是 Spring 在創(chuàng)建 Bean 的過程中，通過三級緩存來緩存正在創(chuàng)建的 Bean，以及已經(jīng)創(chuàng)建完成的 Bean 實(shí)例。具體步驟如下：

• 實(shí)例化 Bean：Spring 在實(shí)例化 Bean 時(shí)，會先創(chuàng)建一個(gè)空的 Bean 對象，并將其放入一級緩存中。
• 屬性賦值：Spring 開始對 Bean 進(jìn)行屬性賦值，如果發(fā)現(xiàn)循環(huán)依賴，會將當(dāng)前 Bean 對象提前暴露給后續(xù)需要依賴的 Bean（通過提前暴露的方式解決循環(huán)依賴）。
• 初始化 Bean：完成屬性賦值后，Spring 將 Bean 進(jìn)行初始化，并將其放入二級緩存中。
• 注入依賴：Spring 繼續(xù)對 Bean 進(jìn)行依賴注入，如果發(fā)現(xiàn)循環(huán)依賴，會從二級緩存中獲取已經(jīng)完成初始化的 Bean 實(shí)例。

通過三級緩存的機(jī)制，Spring 能夠在處理循環(huán)依賴時(shí)，確保及時(shí)暴露正在創(chuàng)建的 Bean 對象，并能夠正確地注入已經(jīng)初始化的 Bean 實(shí)例，從而解決循環(huán)依賴問題，保證應(yīng)用程序的正常運(yùn)行。

spring有哪些常用注解？

Spring框架提供了許多注解來簡化Java開發(fā)中的依賴注入（DI）和面向切面編程（AOP）。下面列舉了一些Spring中常用的注解及其用途：

• 依賴注入相關(guān)注解:
• @Autowired: 自動裝配Bean，Spring會自動尋找類型匹配的Bean并注入。
• @Qualifier: 與@Autowired配合使用，當(dāng)有多個(gè)相同類型的Bean時(shí)，可以指定具體要注入哪一個(gè)。
• @Primary: 當(dāng)存在多個(gè)相同類型的Bean時(shí)，指定首選的Bean。
• @Resource: 用于注入資源，可以指定名稱，優(yōu)先級低于@Autowired。
• 組件掃描和Bean定義注解:
• @Component: 泛指組件，用于定義Spring Bean。
• @Repository: 用于數(shù)據(jù)訪問層（DAO層）的Bean定義。
• @Service: 用于業(yè)務(wù)邏輯層的Bean定義。
• @Controller: 用于Web層的Bean定義。
• @RestController: 結(jié)合了@Controller和@ResponseBody，用于RESTful風(fēng)格的Web層Bean定義。
• @Configuration: 標(biāo)記類為配置類，可以替代XML配置文件。
• @Bean: 在配置類中定義Bean，可以替代XML配置中的<bean>標(biāo)簽。
• 作用域相關(guān)注解:
• @Scope: 定義Bean的作用域，如單例（singleton）、原型（prototype）等。
• 切面編程相關(guān)注解:
• @Aspect: 標(biāo)記類為切面。
• @Pointcut: 定義切入點(diǎn)表達(dá)式。
• @Before: 在切入點(diǎn)方法之前執(zhí)行。
• @After: 在切入點(diǎn)方法之后執(zhí)行，無論方法是否成功。
• @AfterReturning: 在切入點(diǎn)方法成功返回后執(zhí)行。
• @AfterThrowing: 在切入點(diǎn)方法拋出異常后執(zhí)行。
• Spring MVC和Web相關(guān)注解:
• @RequestMapping: 用于映射HTTP請求到處理方法。
• @GetMapping, @PostMapping, @PutMapping, @DeleteMapping: 分別用于映射GET、POST、PUT、DELETE請求。
• @PathVariable: 用于獲取URL中的變量值。
• @RequestParam: 用于獲取URL查詢字符串中的參數(shù)值。
• @RequestBody: 用于將HTTP請求體中的數(shù)據(jù)綁定到方法參數(shù)上。
• @ResponseBody: 表明方法的返回值應(yīng)該直接寫入HTTP響應(yīng)體中。
• Spring Boot相關(guān)注解:
• @SpringBootApplication: 包含了@Configuration、@EnableAutoConfiguration和@ComponentScan的功能，用于標(biāo)記Spring Boot的主配置類。
• @EnableAutoConfiguration: 開啟自動配置功能，讓Spring Boot能夠自動配置應(yīng)用。

JVM中堆分為哪些區(qū)域？

根據(jù) JVM8 規(guī)范，JVM 運(yùn)行時(shí)內(nèi)存共分為虛擬機(jī)棧、堆、元空間、程序計(jì)數(shù)器、本地方法棧五個(gè)部分。還有一部分內(nèi)存叫直接內(nèi)存，屬于操作系統(tǒng)的本地內(nèi)存，也是可以直接操作的。

JVM的內(nèi)存結(jié)構(gòu)主要分為以下幾個(gè)部分：

• 元空間：元空間的本質(zhì)和永久代類似，都是對JVM規(guī)范中方法區(qū)的實(shí)現(xiàn)。不過元空間與永久代之間最大的區(qū)別在于：元空間并不在虛擬機(jī)中，而是使用本地內(nèi)存。
• Java 虛擬機(jī)棧：每個(gè)線程有一個(gè)私有的棧，隨著線程的創(chuàng)建而創(chuàng)建。棧里面存著的是一種叫“棧幀”的東西，每個(gè)方法會創(chuàng)建一個(gè)棧幀，棧幀中存放了局部變量表（基本數(shù)據(jù)類型和對象引用）、操作數(shù)棧、方法出口等信息。棧的大小可以固定也可以動態(tài)擴(kuò)展。
• 本地方法棧：與虛擬機(jī)棧類似，區(qū)別是虛擬機(jī)棧執(zhí)行java方法，本地方法站執(zhí)行native方法。在虛擬機(jī)規(guī)范中對本地方法棧中方法使用的語言、使用方法與數(shù)據(jù)結(jié)構(gòu)沒有強(qiáng)制規(guī)定，因此虛擬機(jī)可以自由實(shí)現(xiàn)它。
• 程序計(jì)數(shù)器：程序計(jì)數(shù)器可以看成是當(dāng)前線程所執(zhí)行的字節(jié)碼的行號指示器。在任何一個(gè)確定的時(shí)刻，一個(gè)處理器（對于多內(nèi)核來說是一個(gè)內(nèi)核）都只會執(zhí)行一條線程中的指令。因此，為了線程切換后能恢復(fù)到正確的執(zhí)行位置，每條線程都需要一個(gè)獨(dú)立的程序計(jì)數(shù)器，我們稱這類內(nèi)存區(qū)域?yàn)椤熬€程私有”內(nèi)存。
• 堆內(nèi)存：堆內(nèi)存是 JVM 所有線程共享的部分，在虛擬機(jī)啟動的時(shí)候就已經(jīng)創(chuàng)建。所有的對象和數(shù)組都在堆上進(jìn)行分配。這部分空間可通過 GC 進(jìn)行回收。當(dāng)申請不到空間時(shí)會拋出 OutOfMemoryError。堆是JVM內(nèi)存占用最大，管理最復(fù)雜的一個(gè)區(qū)域。其唯一的用途就是存放對象實(shí)例：所有的對象實(shí)例及數(shù)組都在對上進(jìn)行分配。jdk1.8后，字符串常量池從永久代中剝離出來，存放在隊(duì)中。
• 直接內(nèi)存：直接內(nèi)存并不是虛擬機(jī)運(yùn)行時(shí)數(shù)據(jù)區(qū)的一部分，也不是Java 虛擬機(jī)規(guī)范中農(nóng)定義的內(nèi)存區(qū)域。在JDK1.4 中新加入了NIO(New Input/Output)類，引入了一種基于通道(Channel)與緩沖區(qū)（Buffer）的I/O 方式，它可以使用native 函數(shù)庫直接分配堆外內(nèi)存，然后通脫一個(gè)存儲在Java堆中的DirectByteBuffer 對象作為這塊內(nèi)存的引用進(jìn)行操作。這樣能在一些場景中顯著提高性能，因?yàn)楸苊饬嗽贘ava堆和Native堆中來回復(fù)制數(shù)據(jù)。

Java中堆和棧的區(qū)別？

• 用途：棧主要用于存儲局部變量、方法調(diào)用的參數(shù)、方法返回地址以及一些臨時(shí)數(shù)據(jù)。每當(dāng)一個(gè)方法被調(diào)用，一個(gè)棧幀（stack frame）就會在棧中創(chuàng)建，用于存儲該方法的信息，當(dāng)方法執(zhí)行完畢，棧幀也會被移除。堆用于存儲對象的實(shí)例（包括類的實(shí)例和數(shù)組）。當(dāng)你使用new關(guān)鍵字創(chuàng)建一個(gè)對象時(shí)，對象的實(shí)例就會在堆上分配空間。
• 生命周期：棧中的數(shù)據(jù)具有確定的生命周期，當(dāng)一個(gè)方法調(diào)用結(jié)束時(shí)，其對應(yīng)的棧幀就會被銷毀，棧中存儲的局部變量也會隨之消失。堆中的對象生命周期不確定，對象會在垃圾回收機(jī)制（Garbage Collection, GC）檢測到對象不再被引用時(shí)才被回收。
• 存取速度：棧的存取速度通常比堆快，因?yàn)闂Ｗ裱冗M(jìn)后出（LIFO, Last In First Out）的原則，操作簡單快速。堆的存取速度相對較慢，因?yàn)閷ο笤诙焉系姆峙浜突厥招枰嗟臅r(shí)間，而且垃圾回收機(jī)制的運(yùn)行也會影響性能。
• 存儲空間：棧的空間相對較小，且固定，由操作系統(tǒng)管理。當(dāng)棧溢出時(shí)，通常是因?yàn)檫f歸過深或局部變量過大。堆的空間較大，動態(tài)擴(kuò)展，由JVM管理。堆溢出通常是由于創(chuàng)建了太多的大對象或未能及時(shí)回收不再使用的對象。
• 可見性：棧中的數(shù)據(jù)對線程是私有的，每個(gè)線程有自己的棧空間。堆中的數(shù)據(jù)對線程是共享的，所有線程都可以訪問堆上的對象。

Redis

Redis常用的數(shù)據(jù)結(jié)構(gòu)及底層

Redis 提供了豐富的數(shù)據(jù)類型，常見的有五種數(shù)據(jù)類型：String（字符串），Hash（哈希），List（列表），Set（集合）、Zset（有序集合）。

• String 類型的應(yīng)用場景：緩存對象、常規(guī)計(jì)數(shù)、分布式鎖、共享 session 信息等。
• List 類型的應(yīng)用場景：消息隊(duì)列（但是有兩個(gè)問題：1. 生產(chǎn)者需要自行實(shí)現(xiàn)全局唯一 ID；2. 不能以消費(fèi)組形式消費(fèi)數(shù)據(jù)）等。
• Hash 類型：緩存對象、購物車等。
• Set 類型：聚合計(jì)算（并集、交集、差集）場景，比如點(diǎn)贊、共同關(guān)注、抽獎活動等。
• Zset 類型：排序場景，比如排行榜、電話和姓名排序等。

String 類型內(nèi)部實(shí)現(xiàn)

String 類型的底層的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)主要是 SDS（簡單動態(tài)字符串）。SDS 和我們認(rèn)識的 C 字符串不太一樣，之所以沒有使用 C 語言的字符串表示，因?yàn)?SDS 相比于 C 的原生字符串：

• SDS 不僅可以保存文本數(shù)據(jù)，還可以保存二進(jìn)制數(shù)據(jù)。因?yàn)?SDS 使用 len 屬性的值而不是空字符來判斷字符串是否結(jié)束，并且 SDS 的所有 API 都會以處理二進(jìn)制的方式來處理 SDS 存放在 buf[] 數(shù)組里的數(shù)據(jù)。所以 SDS 不光能存放文本數(shù)據(jù)，而且能保存圖片、音頻、視頻、壓縮文件這樣的二進(jìn)制數(shù)據(jù)。
• **SDS 獲取字符串長度的時(shí)間復(fù)雜度是 O(1)**。因?yàn)?C 語言的字符串并不記錄自身長度，所以獲取長度的復(fù)雜度為 O(n)；而 SDS 結(jié)構(gòu)里用 len 屬性記錄了字符串長度，所以復(fù)雜度為 O(1)。
• Redis 的 SDS API 是安全的，拼接字符串不會造成緩沖區(qū)溢出。因?yàn)?SDS 在拼接字符串之前會檢查 SDS 空間是否滿足要求，如果空間不夠會自動擴(kuò)容，所以不會導(dǎo)致緩沖區(qū)溢出的問題。

List 類型內(nèi)部實(shí)現(xiàn)

List 類型的底層數(shù)據(jù)結(jié)構(gòu)是由雙向鏈表或壓縮列表實(shí)現(xiàn)的：

• 如果列表的元素個(gè)數(shù)小于 512 個(gè)（默認(rèn)值，可由 list-max-ziplist-entries 配置），列表每個(gè)元素的值都小于 64 字節(jié)（默認(rèn)值，可由 list-max-ziplist-value 配置），Redis 會使用壓縮列表作為 List 類型的底層數(shù)據(jù)結(jié)構(gòu)；
• 如果列表的元素不滿足上面的條件，Redis 會使用雙向鏈表作為 List 類型的底層數(shù)據(jù)結(jié)構(gòu)；

但是在 Redis 3.2 版本之后，List 數(shù)據(jù)類型底層數(shù)據(jù)結(jié)構(gòu)就只由 quicklist 實(shí)現(xiàn)了，替代了雙向鏈表和壓縮列表。

Hash 類型內(nèi)部實(shí)現(xiàn)

Hash 類型的底層數(shù)據(jù)結(jié)構(gòu)是由壓縮列表或哈希表實(shí)現(xiàn)的：

• 如果哈希類型元素個(gè)數(shù)小于 512 個(gè)（默認(rèn)值，可由 hash-max-ziplist-entries 配置），所有值小于 64 字節(jié)（默認(rèn)值，可由 hash-max-ziplist-value 配置）的話，Redis 會使用壓縮列表作為 Hash 類型的底層數(shù)據(jù)結(jié)構(gòu)；
• 如果哈希類型元素不滿足上面條件，Redis 會使用哈希表作為 Hash 類型的底層數(shù)據(jù)結(jié)構(gòu)。

在 Redis 7.0 中，壓縮列表數(shù)據(jù)結(jié)構(gòu)已經(jīng)廢棄了，交由 listpack 數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)了。

Set 類型內(nèi)部實(shí)現(xiàn)

Set 類型的底層數(shù)據(jù)結(jié)構(gòu)是由哈希表或整數(shù)集合實(shí)現(xiàn)的：

• 如果集合中的元素都是整數(shù)且元素個(gè)數(shù)小于 512 （默認(rèn)值，set-maxintset-entries配置）個(gè)，Redis 會使用整數(shù)集合作為 Set 類型的底層數(shù)據(jù)結(jié)構(gòu)；
• 如果集合中的元素不滿足上面條件，則 Redis 使用哈希表作為 Set 類型的底層數(shù)據(jù)結(jié)構(gòu)。

ZSet 類型內(nèi)部實(shí)現(xiàn)

Zset 類型的底層數(shù)據(jù)結(jié)構(gòu)是由壓縮列表或跳表實(shí)現(xiàn)的：

• 如果有序集合的元素個(gè)數(shù)小于 128 個(gè)，并且每個(gè)元素的值小于 64 字節(jié)時(shí)，Redis 會使用壓縮列表作為 Zset 類型的底層數(shù)據(jù)結(jié)構(gòu)；
• 如果有序集合的元素不滿足上面的條件，Redis 會使用跳表作為 Zset 類型的底層數(shù)據(jù)結(jié)構(gòu)；

在 Redis 7.0 中，壓縮列表數(shù)據(jù)結(jié)構(gòu)已經(jīng)廢棄了，交由 listpack 數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)了。

Redis跳表的原理及應(yīng)用場景

Redis 只有 Zset 對象的底層實(shí)現(xiàn)用到了跳表，跳表的優(yōu)勢是能支持平均 O(logN) 復(fù)雜度的節(jié)點(diǎn)查找。

跳表結(jié)構(gòu)設(shè)計(jì)

鏈表在查找元素的時(shí)候，因?yàn)樾枰鹨徊檎遥圆樵冃史浅５停瑫r(shí)間復(fù)雜度是O(N)，于是就出現(xiàn)了跳表。跳表是在鏈表基礎(chǔ)上改進(jìn)過來的，實(shí)現(xiàn)了一種「多層」的有序鏈表，這樣的好處是能快讀定位數(shù)據(jù)。那跳表長什么樣呢？我這里舉個(gè)例子，下圖展示了一個(gè)層級為 3 的跳表。圖中頭節(jié)點(diǎn)有 L0~L2 三個(gè)頭指針，分別指向了不同層級的節(jié)點(diǎn)，然后每個(gè)層級的節(jié)點(diǎn)都通過指針連接起來：

• L0 層級共有 5 個(gè)節(jié)點(diǎn)，分別是節(jié)點(diǎn)1、2、3、4、5；
• L1 層級共有 3 個(gè)節(jié)點(diǎn)，分別是節(jié)點(diǎn) 2、3、5；
• L2 層級只有 1 個(gè)節(jié)點(diǎn)，也就是節(jié)點(diǎn) 3 。

如果我們要在鏈表中查找節(jié)點(diǎn) 4 這個(gè)元素，只能從頭開始遍歷鏈表，需要查找 4 次，而使用了跳表后，只需要查找 2 次就能定位到節(jié)點(diǎn) 4，因?yàn)榭梢栽陬^節(jié)點(diǎn)直接從 L2 層級跳到節(jié)點(diǎn) 3，然后再往前遍歷找到節(jié)點(diǎn) 4。

可以看到，這個(gè)查找過程就是在多個(gè)層級上跳來跳去，最后定位到元素。當(dāng)數(shù)據(jù)量很大時(shí)，跳表的查找復(fù)雜度就是 O(logN)。

那跳表節(jié)點(diǎn)是怎么實(shí)現(xiàn)多層級的呢？這就需要看「跳表節(jié)點(diǎn)」的數(shù)據(jù)結(jié)構(gòu)了，如下：

typedef struct zskiplistNode {
    //Zset 對象的元素值
    sds ele;
    //元素權(quán)重值
    double score;
    //后向指針
    struct zskiplistNode *backward;
  
    //節(jié)點(diǎn)的level數(shù)組，保存每層上的前向指針和跨度
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

Zset 對象要同時(shí)保存「元素」和「元素的權(quán)重」，對應(yīng)到跳表節(jié)點(diǎn)結(jié)構(gòu)里就是 sds 類型的 ele 變量和 double 類型的 score 變量。每個(gè)跳表節(jié)點(diǎn)都有一個(gè)后向指針（struct zskiplistNode *backward），指向前一個(gè)節(jié)點(diǎn)，目的是為了方便從跳表的尾節(jié)點(diǎn)開始訪問節(jié)點(diǎn)，這樣倒序查找時(shí)很方便。

跳表是一個(gè)帶有層級關(guān)系的鏈表，而且每一層級可以包含多個(gè)節(jié)點(diǎn)，每一個(gè)節(jié)點(diǎn)通過指針連接起來，實(shí)現(xiàn)這一特性就是靠跳表節(jié)點(diǎn)結(jié)構(gòu)體中的zskiplistLevel 結(jié)構(gòu)體類型的 level 數(shù)組。

level 數(shù)組中的每一個(gè)元素代表跳表的一層，也就是由 zskiplistLevel 結(jié)構(gòu)體表示，比如 leve[0] 就表示第一層，leve[1] 就表示第二層。zskiplistLevel 結(jié)構(gòu)體里定義了「指向下一個(gè)跳表節(jié)點(diǎn)的指針」和「跨度」，跨度時(shí)用來記錄兩個(gè)節(jié)點(diǎn)之間的距離。

比如，下面這張圖，展示了各個(gè)節(jié)點(diǎn)的跨度。第一眼看到跨度的時(shí)候，以為是遍歷操作有關(guān)，實(shí)際上并沒有任何關(guān)系，遍歷操作只需要用前向指針（struct zskiplistNode *forward）就可以完成了。

跨度實(shí)際上是為了計(jì)算這個(gè)節(jié)點(diǎn)在跳表中的排位。具體怎么做的呢？因?yàn)樘碇械墓?jié)點(diǎn)都是按序排列的，那么計(jì)算某個(gè)節(jié)點(diǎn)排位的時(shí)候，從頭節(jié)點(diǎn)點(diǎn)到該結(jié)點(diǎn)的查詢路徑上，將沿途訪問過的所有層的跨度累加起來，得到的結(jié)果就是目標(biāo)節(jié)點(diǎn)在跳表中的排位。

跳表節(jié)點(diǎn)查詢過程

查找一個(gè)跳表節(jié)點(diǎn)的過程時(shí)，跳表會從頭節(jié)點(diǎn)的最高層開始，逐一遍歷每一層。在遍歷某一層的跳表節(jié)點(diǎn)時(shí)，會用跳表節(jié)點(diǎn)中的 SDS 類型的元素和元素的權(quán)重來進(jìn)行判斷，共有兩個(gè)判斷條件：

• 如果當(dāng)前節(jié)點(diǎn)的權(quán)重「小于」要查找的權(quán)重時(shí)，跳表就會訪問該層上的下一個(gè)節(jié)點(diǎn)。
• 如果當(dāng)前節(jié)點(diǎn)的權(quán)重「等于」要查找的權(quán)重時(shí)，并且當(dāng)前節(jié)點(diǎn)的 SDS 類型數(shù)據(jù)「小于」要查找的數(shù)據(jù)時(shí)，跳表就會訪問該層上的下一個(gè)節(jié)點(diǎn)。

如果上面兩個(gè)條件都不滿足，或者下一個(gè)節(jié)點(diǎn)為空時(shí)，跳表就會使用目前遍歷到的節(jié)點(diǎn)的 level 數(shù)組里的下一層指針，然后沿著下一層指針繼續(xù)查找，這就相當(dāng)于跳到了下一層接著查找。

跳表節(jié)點(diǎn)層數(shù)設(shè)置

跳表的相鄰兩層的節(jié)點(diǎn)數(shù)量的比例會影響跳表的查詢性能。

舉個(gè)例子，下圖的跳表，第二層的節(jié)點(diǎn)數(shù)量只有 1 個(gè)，而第一層的節(jié)點(diǎn)數(shù)量有 6 個(gè)。

這時(shí)，如果想要查詢節(jié)點(diǎn) 6，那基本就跟鏈表的查詢復(fù)雜度一樣，就需要在第一層的節(jié)點(diǎn)中依次順序查找，復(fù)雜度就是 O(N) 了。所以，為了降低查詢復(fù)雜度，我們就需要維持相鄰層結(jié)點(diǎn)數(shù)間的關(guān)系。

**跳表的相鄰兩層的節(jié)點(diǎn)數(shù)量最理想的比例是 2:1，查找復(fù)雜度可以降低到 O(logN)**。

下圖的跳表就是，相鄰兩層的節(jié)點(diǎn)數(shù)量的比例是 2 : 1。那怎樣才能維持相鄰兩層的節(jié)點(diǎn)數(shù)量的比例為 2 : 1 呢？

如果采用新增節(jié)點(diǎn)或者刪除節(jié)點(diǎn)時(shí)，來調(diào)整跳表節(jié)點(diǎn)以維持比例的方法的話，會帶來額外的開銷。

Redis 則采用一種巧妙的方法是，跳表在創(chuàng)建節(jié)點(diǎn)的時(shí)候，隨機(jī)生成每個(gè)節(jié)點(diǎn)的層數(shù)，并沒有嚴(yán)格維持相鄰兩層的節(jié)點(diǎn)數(shù)量比例為 2 : 1 的情況。

具體的做法是，跳表在創(chuàng)建節(jié)點(diǎn)時(shí)候，會生成范圍為[0-1]的一個(gè)隨機(jī)數(shù)，如果這個(gè)隨機(jī)數(shù)小于 0.25（相當(dāng)于概率 25%），那么層數(shù)就增加 1 層，然后繼續(xù)生成下一個(gè)隨機(jī)數(shù)，直到隨機(jī)數(shù)的結(jié)果大于 0.25 結(jié)束，最終確定該節(jié)點(diǎn)的層數(shù)。

這樣的做法，相當(dāng)于每增加一層的概率不超過 25%，層數(shù)越高，概率越低，層高最大限制是 64。雖然我前面講解跳表的時(shí)候，圖中的跳表的「頭節(jié)點(diǎn)」都是 3 層高，但是其實(shí)如果層高最大限制是 64，那么在創(chuàng)建跳表「頭節(jié)點(diǎn)」的時(shí)候，就會直接創(chuàng)建 64 層高的頭節(jié)點(diǎn)。

MySQL

B+樹的優(yōu)缺點(diǎn)是什么？

• B+樹有一個(gè)最大的好處，方便掃庫，B樹必須用中序遍歷的方法按序掃庫，而B+樹直接從葉子結(jié)點(diǎn)挨個(gè)掃一遍就完了。B+樹支持range-query(區(qū)間查詢)非常方便，而B樹不支持。這是數(shù)據(jù)庫選用B+樹的最主要原因。
• B+樹最大的性能問題是會產(chǎn)生大量的隨機(jī)IO，隨著新數(shù)據(jù)的插入，葉子節(jié)點(diǎn)會慢慢分裂，邏輯上連續(xù)的葉子節(jié)點(diǎn)在物理上往往不連續(xù)，甚至分離的很遠(yuǎn)，但做范圍查詢時(shí)，會產(chǎn)生大量讀隨機(jī)IO。對于大量的隨機(jī)寫也一樣，舉一個(gè)插入key跨度很大的例子，如7->1000->3->2000 ... 新插入的數(shù)據(jù)存儲在磁盤上相隔很遠(yuǎn)，會產(chǎn)生大量的隨機(jī)寫IO。

索引的實(shí)踐優(yōu)化知道哪些？

常見優(yōu)化索引的方法：

• All（全表掃描）：在這些情況里，all 是最壞的情況，因?yàn)椴捎昧巳頀呙璧姆绞?
• index（全索引掃描）：index 和 all 差不多，只不過 index 對索引表進(jìn)行全掃描，這樣做的好處是不再需要對數(shù)據(jù)進(jìn)行排序，但是開銷依然很大。所以，要盡量避免全表掃描和全索引掃描。
• range（索引范圍掃描）：range 表示采用了索引范圍掃描，一般在 where 子句中使用 < 、>、in、between 等關(guān)鍵詞，只檢索給定范圍的行，屬于范圍查找。從這一級別開始，索引的作用會越來越明顯，因此我們需要盡量讓 SQL 查詢可以使用到 range 這一級別及以上的 type 訪問方式。
• ref（非唯一索引掃描）：ref 類型表示采用了非唯一索引，或者是唯一索引的非唯一性前綴，返回?cái)?shù)據(jù)返回可能是多條。因?yàn)殡m然使用了索引，但該索引列的值并不唯一，有重復(fù)。這樣即使使用索引快速查找到了第一條數(shù)據(jù)，仍然不能停止，要進(jìn)行目標(biāo)值附近的小范圍掃描。但它的好處是它并不需要掃全表，因?yàn)樗饕怯行虻模幢阌兄貜?fù)值，也是在一個(gè)非常小的范圍內(nèi)掃描。
• eq_ref（唯一索引掃描）：eq_ref 類型是使用主鍵或唯一索引時(shí)產(chǎn)生的訪問方式，通常使用在多表聯(lián)查中。比如，對兩張表進(jìn)行聯(lián)查，關(guān)聯(lián)條件是兩張表的 user_id 相等，且 user_id 是唯一索引，那么使用 EXPLAIN 進(jìn)行執(zhí)行計(jì)劃查看的時(shí)候，type 就會顯示 eq_ref。
• const（結(jié)果只有一條的主鍵或唯一索引掃描）：const 類型表示使用了主鍵或者唯一索引與常量值進(jìn)行比較，比如 select name from product where id=1。

除了關(guān)注 type，我們也要關(guān)注 extra 顯示的結(jié)果。這里說幾個(gè)重要的參考指標(biāo)：

• Using filesort ：當(dāng)查詢語句中包含 group by 操作，而且無法利用索引完成排序操作的時(shí)候， 這時(shí)不得不選擇相應(yīng)的排序算法進(jìn)行，甚至可能會通過文件排序，效率是很低的，所以要避免這種問題的出現(xiàn)。
• Using temporary：使了用臨時(shí)表保存中間結(jié)果，MySQL 在對查詢結(jié)果排序時(shí)使用臨時(shí)表，常見于排序 order by 和分組查詢 group by。效率低，要避免這種問題的出現(xiàn)。
• Using index：所需數(shù)據(jù)只需在索引即可全部獲得，不須要再到表中取數(shù)據(jù)，也就是使用了覆蓋索引，避免了回表操作，效率不錯(cuò)。

框架

請求到SpringBoot具體處理函數(shù)的流程

1. 請求接收:當(dāng)一個(gè)HTTP請求到達(dá)服務(wù)器時(shí)，它會被服務(wù)器容器（如Tomcat、Jetty或Undertow）接收。服務(wù)器容器將請求轉(zhuǎn)發(fā)給Spring Boot的前端控制器DispatcherServlet。
2. 前端控制器處理:DispatcherServlet作為Spring MVC的核心組件，負(fù)責(zé)接收請求并進(jìn)行初步處理。它會委托HttpRequestHandlerMapping或HandlerMapping接口的實(shí)現(xiàn)類去尋找合適的處理器（即控制器方法）。
3. 映射處理器:HandlerMapping接口的實(shí)現(xiàn)類（如RequestMappingHandlerMapping）會根據(jù)URL、HTTP方法等信息，查找與請求匹配的處理器方法。查找成功后，HandlerMapping會返回一個(gè)HandlerExecutionChain對象，包含處理器對象和攔截器列表。
4. 處理器適配器:DispatcherServlet會調(diào)用HandlerAdapter接口的實(shí)現(xiàn)類來確定如何調(diào)用處理器方法。找到合適的HandlerAdapter后，它會調(diào)用HandlerAdapter的handle方法來執(zhí)行處理器方法。
5. 參數(shù)綁定和類型轉(zhuǎn)換:在調(diào)用處理器方法前，參數(shù)綁定和類型轉(zhuǎn)換會自動進(jìn)行。這包括從請求中提取數(shù)據(jù)并將其轉(zhuǎn)換為處理器方法所需的參數(shù)類型。WebDataBinder和HandlerMethodArgumentResolver參與此過程。
6. 攔截器執(zhí)行:如果HandlerExecutionChain中包含攔截器，則在調(diào)用處理器方法前后會執(zhí)行攔截器的preHandle和postHandle方法。
7. 調(diào)用處理器方法:經(jīng)過上述步驟后，具體的處理器方法（控制器方法）將被執(zhí)行。控制器方法可能會返回一個(gè)模型和視圖，或者直接返回一個(gè)響應(yīng)體。
8. 處理返回值:根據(jù)控制器方法的返回值類型，HandlerAdapter會選擇相應(yīng)的ViewResolver或ResponseBody處理器來處理返回值。如果是視圖，ViewResolver會解析視圖名稱并生成視圖對象。如果是響應(yīng)體，HttpMessageConverter會將返回的對象轉(zhuǎn)換為HTTP響應(yīng)體。
9. 視圖渲染:如果有視圖對象，它會被渲染，將模型數(shù)據(jù)填充到視圖模板中，生成HTML或其他格式的響應(yīng)。
10. 響應(yīng)發(fā)送:最終的響應(yīng)（HTML頁面、JSON數(shù)據(jù)等）將被封裝在HTTP響應(yīng)中發(fā)送回客戶端。
11. 攔截器后處理:如果有攔截器，postHandle和afterCompletion方法將在響應(yīng)發(fā)送后被調(diào)用，以便進(jìn)行額外的后處理或資源清理。

算法

• 層序遍歷

      

       

        


        
點(diǎn)擊關(guān)注公眾號，閱讀更多精彩內(nèi)容