大家好，我是小林。

今天分享秋招的字節(jié)、快手 Java 后端面經(jīng)，我篩選了Java+MySQL+Redis+MQ+網(wǎng)絡(luò)+操作系統(tǒng)共性的面試題，排除了項(xiàng)目和實(shí)習(xí)經(jīng)歷的問題，同學(xué)反饋?zhàn)止?jié)面試體驗(yàn)很好，遇到不會的，面試官會一步一步引導(dǎo)，還會詳細(xì)解釋下，返回環(huán)節(jié)還介紹了部門情況。

整體難度不算太難，還算比較基礎(chǔ)，很多都是高頻面試題，可以收藏起來，反復(fù)復(fù)習(xí)。

網(wǎng)絡(luò)

從輸入域名到瀏覽器看見頁面經(jīng)歷了什么過程？

簡單的網(wǎng)絡(luò)模型

• 解析URL：分析 URL 所需要使用的傳輸協(xié)議和請求的資源路徑。如果輸入的 URL 中的協(xié)議或者主機(jī)名不合法，將會把地址欄中輸入的內(nèi)容傳遞給搜索引擎。如果沒有問題，瀏覽器會檢查 URL 中是否出現(xiàn)了非法字符，則對非法字符進(jìn)行轉(zhuǎn)義后在進(jìn)行下一過程。
• 緩存判斷：瀏覽器會判斷所請求的資源是否在緩存里，如果請求的資源在緩存里且沒有失效，那么就直接使用，否則向服務(wù)器發(fā)起新的請求。
• DNS解析：如果資源不在本地緩存，首先需要進(jìn)行DNS解析。瀏覽器會向本地DNS服務(wù)器發(fā)送域名解析請求，本地DNS服務(wù)器會逐級查詢，最終找到對應(yīng)的IP地址。
• 獲取MAC地址：當(dāng)瀏覽器得到 IP 地址后，數(shù)據(jù)傳輸還需要知道目的主機(jī) MAC 地址，因?yàn)閼?yīng)用層下發(fā)數(shù)據(jù)給傳輸層，TCP 協(xié)議會指定源端口號和目的端口號，然后下發(fā)給網(wǎng)絡(luò)層。網(wǎng)絡(luò)層會將本機(jī)地址作為源地址，獲取的 IP 地址作為目的地址。然后將下發(fā)給數(shù)據(jù)鏈路層，數(shù)據(jù)鏈路層的發(fā)送需要加入通信雙方的 MAC 地址，本機(jī)的 MAC 地址作為源 MAC 地址，目的 MAC 地址需要分情況處理。通過將 IP 地址與本機(jī)的子網(wǎng)掩碼相結(jié)合，可以判斷是否與請求主機(jī)在同一個(gè)子網(wǎng)里，如果在同一個(gè)子網(wǎng)里，可以使用 APR 協(xié)議獲取到目的主機(jī)的 MAC 地址，如果不在一個(gè)子網(wǎng)里，那么請求應(yīng)該轉(zhuǎn)發(fā)給網(wǎng)關(guān)，由它代為轉(zhuǎn)發(fā)，此時(shí)同樣可以通過 ARP 協(xié)議來獲取網(wǎng)關(guān)的 MAC 地址，此時(shí)目的主機(jī)的 MAC 地址應(yīng)該為網(wǎng)關(guān)的地址。
• 建立TCP連接：主機(jī)將使用目標(biāo) IP地址和目標(biāo)MAC地址發(fā)送一個(gè)TCP SYN包，請求建立一個(gè)TCP連接，然后交給路由器轉(zhuǎn)發(fā)，等路由器轉(zhuǎn)到目標(biāo)服務(wù)器后，服務(wù)器回復(fù)一個(gè)SYN-ACK包，確認(rèn)連接請求。然后，主機(jī)發(fā)送一個(gè)ACK包，確認(rèn)已收到服務(wù)器的確認(rèn)，然后 TCP 連接建立完成。
• HTTPS 的 TLS 四次握手：如果使用的是 HTTPS 協(xié)議，在通信前還存在 TLS 的四次握手。
• 發(fā)送HTTP請求：連接建立后，瀏覽器會向服務(wù)器發(fā)送HTTP請求。請求中包含了用戶需要獲取的資源的信息，例如網(wǎng)頁的URL、請求方法（GET、POST等）等。
• 服務(wù)器處理請求并返回響應(yīng)：服務(wù)器收到請求后，會根據(jù)請求的內(nèi)容進(jìn)行相應(yīng)的處理。例如，如果是請求網(wǎng)頁，服務(wù)器會讀取相應(yīng)的網(wǎng)頁文件，并生成HTTP響應(yīng)。

TCP的三次握手過程？三次握手的原因是什么？

圖片

在這里插入圖片描述

• 第一次握手（SYN）：客戶端向服務(wù)器發(fā)送一個(gè)帶有SYN標(biāo)志的數(shù)據(jù)包，請求建立連接?？蛻舳藭x擇一個(gè)隨機(jī)的初始序列號（ISN）作為起始序號。
• 第二次握手（SYN+ACK）：服務(wù)器收到客戶端的請求后，會發(fā)送一個(gè)帶有SYN和ACK（確認(rèn)）標(biāo)志的數(shù)據(jù)包作為響應(yīng)。服務(wù)器也會選擇一個(gè)隨機(jī)的初始序列號，并將客戶端的初始序列號加1作為確認(rèn)號。同時(shí)，服務(wù)器也表示自己已經(jīng)收到了客戶端的請求。
• 第三次握手（ACK）：客戶端收到服務(wù)器的響應(yīng)后，會發(fā)送一個(gè)帶有ACK標(biāo)志的數(shù)據(jù)包作為確認(rèn)。客戶端會將服務(wù)器的初始序列號加1作為確認(rèn)號，并向服務(wù)器表示自己已經(jīng)收到了服務(wù)器的響應(yīng)。

完成了這三次握手后，TCP連接就建立起來了，雙方可以開始進(jìn)行數(shù)據(jù)的傳輸。

三次握手的目的是確保雙方都能夠收到對方的請求和確認(rèn)，并且雙方都同意建立連接。這樣可以防止因?yàn)榫W(wǎng)絡(luò)延遲或丟包等問題導(dǎo)致連接建立失敗或不穩(wěn)定。同時(shí)，三次握手也能夠防止已經(jīng)失效的連接請求報(bào)文段在網(wǎng)絡(luò)中重新出現(xiàn)，避免了資源的浪費(fèi)。

TCP為什么可靠?

• 序列號與確認(rèn)機(jī)制：TCP將每個(gè)數(shù)據(jù)包分配一個(gè)唯一的序列號，并且接收方會發(fā)送確認(rèn)消息來確認(rèn)已經(jīng)接收到的數(shù)據(jù)。發(fā)送方會根據(jù)接收到的確認(rèn)消息判斷是否需要重新發(fā)送丟失的數(shù)據(jù)包。
• 數(shù)據(jù)校驗(yàn)和：TCP使用校驗(yàn)和來驗(yàn)證數(shù)據(jù)在傳輸過程中是否發(fā)生了損壞。接收方會計(jì)算校驗(yàn)和并與發(fā)送方發(fā)送的校驗(yàn)和進(jìn)行比較，如果不一致，則說明數(shù)據(jù)包發(fā)生了損壞，需要重新發(fā)送。
• 滑動窗口機(jī)制：TCP使用滑動窗口來控制發(fā)送方發(fā)送數(shù)據(jù)的速度和接收方接收數(shù)據(jù)的速度，以避免因發(fā)送速度過快或接收速度過慢而導(dǎo)致的數(shù)據(jù)丟失或堵塞。
• 重傳機(jī)制：如果發(fā)送方?jīng)]有收到接收方的確認(rèn)消息，或者接收方收到的數(shù)據(jù)包校驗(yàn)和不一致，發(fā)送方會重新發(fā)送數(shù)據(jù)包，確保數(shù)據(jù)的可靠傳輸。
• 擁塞控制：TCP具有擁塞控制機(jī)制，可以根據(jù)網(wǎng)絡(luò)的擁塞情況來調(diào)整發(fā)送數(shù)據(jù)的速率，避免網(wǎng)絡(luò)擁塞導(dǎo)致的數(shù)據(jù)丟失和延遲。

HTTP狀態(tài)碼有哪些？

圖片

五大類 HTTP 狀態(tài)碼

1xx：信息性狀態(tài)碼，表示服務(wù)器已接收了客戶端請求，客戶端可繼續(xù)發(fā)送請求。

• 100 Continue
• 101 Switching Protocols
• 2xx：成功狀態(tài)碼，表示服務(wù)器已成功接收到請求并進(jìn)行處理。

200 OK 表示客戶端請求成功

• 204 No Content 成功，但不返回任何實(shí)體的主體部分
• 206 Partial Content 成功執(zhí)行了一個(gè)范圍（Range）請求

3xx：重定向狀態(tài)碼，表示服務(wù)器要求客戶端重定向。

• 301 Moved Permanently 永久性重定向，響應(yīng)報(bào)文的Location首部應(yīng)該有該資源的新URL
• 302 Found 臨時(shí)性重定向，響應(yīng)報(bào)文的Location首部給出的URL用來臨時(shí)定位資源
• 303 See Other 請求的資源存在著另一個(gè)URI，客戶端應(yīng)使用GET方法定向獲取請求的資源
• 304 Not Modified 服務(wù)器內(nèi)容沒有更新，可以直接讀取瀏覽器緩存
• 307 Temporary Redirect 臨時(shí)重定向。與302 Found含義一樣。302禁止POST變換為GET，但實(shí)際使用時(shí)并不一定，307則更多瀏覽器可能會遵循這一標(biāo)準(zhǔn)，但也依賴于瀏覽器具體實(shí)現(xiàn)

4xx：客戶端錯(cuò)誤狀態(tài)碼，表示客戶端的請求有非法內(nèi)容。

• 400 Bad Request 表示客戶端請求有語法錯(cuò)誤，不能被服務(wù)器所理解
• 401 Unauthonzed 表示請求未經(jīng)授權(quán)，該狀態(tài)代碼必須與 WWW-Authenticate 報(bào)頭域一起使用
• 403 Forbidden 表示服務(wù)器收到請求，但是拒絕提供服務(wù)，通常會在響應(yīng)正文中給出不提供服務(wù)的原因
• 404 Not Found 請求的資源不存在，例如，輸入了錯(cuò)誤的URL

5xx：服務(wù)器錯(cuò)誤狀態(tài)碼，表示服務(wù)器未能正常處理客戶端的請求而出現(xiàn)意外錯(cuò)誤。

• 500 Internel Server Error 表示服務(wù)器發(fā)生不可預(yù)期的錯(cuò)誤，導(dǎo)致無法完成客戶端的請求
• 503 Service Unavailable 表示服務(wù)器當(dāng)前不能夠處理客戶端的請求，在一段時(shí)間之后，服務(wù)器可能會恢復(fù)正常

操作系統(tǒng)

進(jìn)程間通信有哪些？

• 管道（Pipe）：管道是一種半雙工的通信方式，可以在具有親緣關(guān)系的進(jìn)程之間進(jìn)行通信。它可以分為匿名管道和命名管道。匿名管道只能在具有共同祖先的進(jìn)程之間使用，而命名管道可以在不具有親緣關(guān)系的進(jìn)程之間使用。

優(yōu)點(diǎn)：簡單易用，無需額外的系統(tǒng)調(diào)用和復(fù)雜的設(shè)置。

缺點(diǎn)：只能在具有親緣關(guān)系的進(jìn)程之間進(jìn)行通信，且只能實(shí)現(xiàn)單向通信。

• 信號（Signal）：信號是一種異步的通信方式，用于通知進(jìn)程發(fā)生了某種事件。一個(gè)進(jìn)程可以向另一個(gè)進(jìn)程發(fā)送信號，接收信號的進(jìn)程可以選擇采取相應(yīng)的行動。

優(yōu)點(diǎn)：簡單、快速，適用于簡單的通信需求。

缺點(diǎn)：信號的發(fā)送和接收是異步的，無法傳遞大量數(shù)據(jù)，且不支持雙向通信。

• 共享內(nèi)存（Shared Memory）：共享內(nèi)存是一種高效的通信方式，多個(gè)進(jìn)程可以將同一塊內(nèi)存空間映射到各自的地址空間中，從而實(shí)現(xiàn)共享數(shù)據(jù)。

優(yōu)點(diǎn)：傳輸效率高，適用于大量數(shù)據(jù)的共享。

缺點(diǎn)：需要額外的同步機(jī)制來保證數(shù)據(jù)的一致性和互斥訪問，容易造成數(shù)據(jù)競爭和死鎖。

• 信號量（Semaphore）：信號量是一種用于進(jìn)程間同步的機(jī)制，可以用來保護(hù)共享資源的互斥訪問。

優(yōu)點(diǎn)：可以用于進(jìn)程間的同步和互斥。

缺點(diǎn)：只提供了同步和互斥的功能，無法傳遞大量數(shù)據(jù)。

• 消息隊(duì)列：消息隊(duì)列是一種消息傳遞的機(jī)制，可以在不同進(jìn)程之間傳遞特定格式的消息。

優(yōu)點(diǎn)：支持多對多的進(jìn)程通信，每個(gè)消息都有特定的格式。

缺點(diǎn)：消息的發(fā)送和接收是同步的，且不支持實(shí)時(shí)性要求較高的通信。

• 套接字（Socket）：套接字是一種通用的進(jìn)程間通信機(jī)制，可以在不同主機(jī)上的進(jìn)程之間進(jìn)行通信。

優(yōu)點(diǎn)：支持網(wǎng)絡(luò)通信，可以在不同主機(jī)上的進(jìn)程之間進(jìn)行通信。

缺點(diǎn)：相對于其他IPC方式，套接字的使用和編程復(fù)雜度較高。

電腦 4GB內(nèi)存，我申請 5GB內(nèi)存可以嗎？

應(yīng)用程序通過 malloc 函數(shù)申請內(nèi)存的時(shí)候，實(shí)際上申請的是虛擬內(nèi)存，此時(shí)并不會分配物理內(nèi)存。

虛擬內(nèi)存的最大值首先操作系統(tǒng)的位數(shù)，32 位操作系統(tǒng)和 64 位操作系統(tǒng)的虛擬地址空間大小是不同的，在 Linux 操作系統(tǒng)中，虛擬地址空間的內(nèi)部又被分為內(nèi)核空間和用戶空間兩部分，如下所示：

圖片

• 32 位系統(tǒng)的內(nèi)核空間占用 1G，位于最高處，剩下的 3G 是用戶空間，所以在 32 位操作系統(tǒng)場景下，執(zhí)行malloc申請5G內(nèi)存，會失敗。
• 64 位系統(tǒng)的內(nèi)核空間和用戶空間都是 128T，所以在 64 位操作系統(tǒng)場景下，即使物理內(nèi)存只有 4G，但是還是可以申請5G虛擬內(nèi)存，能申請成功。

申請成功之后，在使用這5G內(nèi)存時(shí)候會有問題嗎？

會有問題，會發(fā)生 OOM 的錯(cuò)誤，內(nèi)存溢出。

當(dāng)應(yīng)用程序讀寫了這塊虛擬內(nèi)存，CPU 就會去訪問這個(gè)虛擬內(nèi)存， 這時(shí)會發(fā)現(xiàn)這個(gè)虛擬內(nèi)存沒有映射到物理內(nèi)存， CPU 就會產(chǎn)生缺頁中斷，進(jìn)程會從用戶態(tài)切換到內(nèi)核態(tài)，并將缺頁中斷交給內(nèi)核的 Page Fault Handler （缺頁中斷函數(shù)）處理。

缺頁中斷處理函數(shù)會看是否有空閑的物理內(nèi)存：

• 如果有，就直接分配物理內(nèi)存，并建立虛擬內(nèi)存與物理內(nèi)存之間的映射關(guān)系。
• 如果沒有空閑的物理內(nèi)存，那么內(nèi)核就會開始進(jìn)行的工作，如果回收內(nèi)存工作結(jié)束后，空閑的物理內(nèi)存仍然無法滿足此次物理內(nèi)存的申請，那么內(nèi)核就會放最后的大招了觸發(fā) OOM （Out of Memory）機(jī)制。

MySQL

索引的底層是怎么實(shí)現(xiàn)的？

MySQL 默認(rèn)存儲引擎是 InnoDB，InnoDB 默認(rèn)是使用 B+樹 作為索引的數(shù)據(jù)結(jié)構(gòu)。

主鍵索引 B+Tree

為什么用B+樹呢？

• B+Tree vs 二叉樹：對于有 N 個(gè)葉子節(jié)點(diǎn)的 B+Tree，其搜索復(fù)雜度為O(logdN)，其中 d 表示節(jié)點(diǎn)允許的最大子節(jié)點(diǎn)個(gè)數(shù)為 d 個(gè)。在實(shí)際的應(yīng)用當(dāng)中， d 值是大于100的，這樣就保證了，即使數(shù)據(jù)達(dá)到千萬級別時(shí)，B+Tree 的高度依然維持在 3~4 層左右，也就是說一次數(shù)據(jù)查詢操作只需要做 3~4 次的磁盤 I/O 操作就能查詢到目標(biāo)數(shù)據(jù)。而二叉樹的每個(gè)父節(jié)點(diǎn)的兒子節(jié)點(diǎn)個(gè)數(shù)只能是 2 個(gè)，意味著其搜索復(fù)雜度為 O(logN)，這已經(jīng)比 B+Tree 高出不少，因此二叉樹檢索到目標(biāo)數(shù)據(jù)所經(jīng)歷的磁盤 I/O 次數(shù)要更多。
• B+Tree vs Hash：Hash 在做等值查詢的時(shí)候效率賊快，搜索復(fù)雜度為 O(1)。但是 Hash 表不適合做范圍查詢，它更適合做等值的查詢，這也是 B+Tree 索引要比 Hash 表索引有著更廣泛的適用場景的原因。
• B+Tree vs B Tree：B+Tree 只在葉子節(jié)點(diǎn)存儲數(shù)據(jù)，而 B 樹 的非葉子節(jié)點(diǎn)也要存儲數(shù)據(jù)，所以 B+Tree 的單個(gè)節(jié)點(diǎn)的數(shù)據(jù)量更小，在相同的磁盤 I/O 次數(shù)下，就能查詢更多的節(jié)點(diǎn)。另外，B+Tree 葉子節(jié)點(diǎn)采用的是雙鏈表連接，適合 MySQL 中常見的基于范圍的順序查找，而 B 樹無法做到這一點(diǎn)。

你是如何選擇什么字段來做索引的？

• 字段有唯一性限制的，比如商品編碼；
• 經(jīng)常用于 WHERE 查詢條件的字段，這樣能夠提高整個(gè)表的查詢速度，如果查詢條件不是一個(gè)字段，可以建立聯(lián)合索引。
• 經(jīng)常用于 GROUP BY 和 ORDER BY 的字段，這樣在查詢的時(shí)候就不需要再去做一次排序了，因?yàn)槲覀兌家呀?jīng)知道了建立索引之后在 B+Tree 中的記錄都是排序好的。

假如現(xiàn)在有三個(gè)普通索引a，b，c，sql查詢where a = xx and b = xx and c == xx會怎么樣？

會進(jìn)行索引合并，對多個(gè)索引分別進(jìn)行條件掃描，然后將它們各自的結(jié)果進(jìn)行合并。

MySQL5.0之前，一個(gè)表一次只能使用一個(gè)索引，無法同時(shí)使用多個(gè)索引分別進(jìn)行條件掃描。但是從5.1開始，引入了索引合并優(yōu)化技術(shù)，對同一個(gè)表可以使用多個(gè)索引分別進(jìn)行條件掃描。

那如果不想索引合并呢？怎么解決？

如果出現(xiàn)了索引合并，那么一般同時(shí)也意味著我們的索引建立得不太合理，因?yàn)樗饕喜?是可以通過建立聯(lián)合索引進(jìn)行更一步優(yōu)化的，減少索引掃描的次數(shù)。

比如，建立聯(lián)合索引（a, b, c），這條查詢語句遵循最左匹配原則，所以三個(gè)字段都可以利用聯(lián)合索引。

圖片

Redis

Redis在項(xiàng)目中的應(yīng)用？

主要用做緩存，提升查詢的性能，避免請求查詢mysql。

Redis過期淘汰策略有哪些？

Redis 內(nèi)存淘汰策略共有八種，這八種策略大體分為「不進(jìn)行數(shù)據(jù)淘汰」和「進(jìn)行數(shù)據(jù)淘汰」兩類策略。

1、不進(jìn)行數(shù)據(jù)淘汰的策略

noeviction（Redis3.0之后，默認(rèn)的內(nèi)存淘汰策略） ：它表示當(dāng)運(yùn)行內(nèi)存超過最大設(shè)置內(nèi)存時(shí)，不淘汰任何數(shù)據(jù)，這時(shí)如果有新的數(shù)據(jù)寫入，會報(bào)錯(cuò)通知禁止寫入，不淘汰任何數(shù)據(jù)，但是如果沒用數(shù)據(jù)寫入的話，只是單純的查詢或者刪除操作的話，還是可以正常工作。

2、進(jìn)行數(shù)據(jù)淘汰的策略

針對「進(jìn)行數(shù)據(jù)淘汰」這一類策略，又可以細(xì)分為「在設(shè)置了過期時(shí)間的數(shù)據(jù)中進(jìn)行淘汰」和「在所有數(shù)據(jù)范圍內(nèi)進(jìn)行淘汰」這兩類策略。

在設(shè)置了過期時(shí)間的數(shù)據(jù)中進(jìn)行淘汰：

• volatile-random：隨機(jī)淘汰設(shè)置了過期時(shí)間的任意鍵值；
• volatile-ttl：優(yōu)先淘汰更早過期的鍵值。
• volatile-lru（Redis3.0 之前，默認(rèn)的內(nèi)存淘汰策略）：淘汰所有設(shè)置了過期時(shí)間的鍵值中，最久未使用的鍵值；
• volatile-lfu（Redis 4.0 后新增的內(nèi)存淘汰策略）：淘汰所有設(shè)置了過期時(shí)間的鍵值中，最少使用的鍵值；

在所有數(shù)據(jù)范圍內(nèi)進(jìn)行淘汰：

• allkeys-random：隨機(jī)淘汰任意鍵值;
• allkeys-lru：淘汰整個(gè)鍵值中最久未使用的鍵值；
• allkeys-lfu（Redis 4.0 后新增的內(nèi)存淘汰策略）：淘汰整個(gè)鍵值中最少使用的鍵值。

Java

HashMap底層原理

• 數(shù)據(jù)結(jié)構(gòu)：在 JDK 1.7 版本之前， HashMap 數(shù)據(jù)結(jié)構(gòu)是數(shù)組和鏈表，HashMap通過哈希算法將元素的鍵（Key）映射到數(shù)組中的槽位（Bucket）。如果多個(gè)鍵映射到同一個(gè)槽位，它們會以鏈表的形式存儲在同一個(gè)槽位上，因?yàn)殒湵淼牟樵儠r(shí)間是O(n)，所以沖突很嚴(yán)重，一個(gè)索引上的鏈表非常長，效率就很低了，所以在 JDK 1.8版本的時(shí)候做了優(yōu)化，當(dāng)一個(gè)鏈表的長度超過8的時(shí)候就轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)，不再使用鏈表存儲，而是使用紅黑樹，查找時(shí)使用紅黑樹，時(shí)間復(fù)雜度O（log n），可以提高查詢性能，但是在數(shù)量較少時(shí)，即數(shù)量小于6時(shí)，會將紅黑樹轉(zhuǎn)換回鏈表。

圖片

• 插入鍵值對的put方法的區(qū)別：JDK 1.8中會將節(jié)點(diǎn)插入到鏈表尾部，而1.7中是采用頭插；
• 哈希算法：JDK 1.7中的 hash() 擾動函數(shù)需要進(jìn)行4次異或運(yùn)算；而 JDK 1.8中則是將 (h = key.hashCode()) ^ (h >>> 16) 的結(jié)果作為計(jì)算下標(biāo)的hash值，只需要一次異或運(yùn)算就可以讓hashCode的高位和低位同時(shí)參與下標(biāo)值的計(jì)算，更具有隨機(jī)性，可以使元素分布更均勻；

// JDK 1.7 hash 方法源碼.
final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}


// JDK 1.8 hash 方法源碼.
static final int hash(Object key) {
      int h;
      // key.hashCode()：返回散列值也就是hashcode
      // ^：按位異或
      // >>>:無符號右移，忽略符號位，空位都以0補(bǔ)齊
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

HashMap的擴(kuò)容過程，說一下

hashMap默認(rèn)的負(fù)載因子是0.75，即如果hashmap中的元素個(gè)數(shù)超過了總?cè)萘?5%，則會觸發(fā)擴(kuò)容，擴(kuò)容分為兩個(gè)步驟：

• 新的數(shù)組擴(kuò)容 2 倍大小
• 計(jì)算每個(gè)元素新的位置，然后遷移元素

JDK 1.8 在擴(kuò)容 2 倍容量后，在遷移數(shù)據(jù)時(shí)，不需要重新計(jì)算元素的hash進(jìn)行元素遷移，而是用原先位置key的hash值與舊數(shù)組的長度（oldCap）進(jìn)行"與"操作。

圖片

舉一個(gè)例子，假設(shè)元素 e 存儲在舊數(shù)據(jù)的桶位 i 中：

• 如果(e.hash & oldCap) == 0 ，那么當(dāng)前元素的桶位置不變。
• 如果(e.hash & oldCap) == 1，那么桶的位置就是原位置+原數(shù)組長度（oldCap）

為什么用 e.hash & oldCap 計(jì)算新位置？

首先我們要明確三點(diǎn):

1. HashMap的數(shù)組大小一定是2的N次冪
2. HashMap擴(kuò)容時(shí)一般為增大一倍，即size = size * 2
3. HashMap的索引計(jì)算方式為 hash(key) & (size - 1)，由1可知，size-1的二進(jìn)制「低位都為1」

我們假設(shè) oldCap = 16, 即 2^4，16 - 1 = 15, 二進(jìn)制表示為 0000 0000 0000 0000 0000 0000 0000 1111，可見除了低4位, 其他位置都是0，則 (16-1) & hash 自然就是取hash值的低4位，我們假設(shè)它為 abcd（abcd 各自的值可能是 0 或者 1）。

當(dāng)我們將oldCap擴(kuò)大兩倍后， 新的index的位置就變成了 (32-1) & hash, 其實(shí)就是取 hash值的低5位.。那么對于同一個(gè)Node, 低5位的值無外乎下面兩種情況:

0abcd
1abcd

其中, 0abcd與原來的index值一致, 而1abcd = 0abcd + 10000 = 0abcd + oldCap（這里的oldCap是 16，二進(jìn)制數(shù)：10000 ）

故雖然數(shù)組大小擴(kuò)大了一倍，但是同一個(gè)key在新舊table中對應(yīng)的index卻存在一定聯(lián)系：要么一致，要么相差一個(gè) oldCap。

而新舊index是否一致就體現(xiàn)在hash值的第4位(我們把最低為稱作第0位), 怎么拿到這一位的值呢, 只要:

hash & 0000 0000 0000 0000 0000 0000 0001 0000

上式就等效于

hash & oldCap

故得出結(jié)論:

• 如果(e.hash & oldCap) == 0 ，那么當(dāng)前元素的桶位置不變。
• 如果(e.hash & oldCap) == 1，那么桶的位置就是原位置+原數(shù)組長度（oldCap）

ArrayList底層是怎么實(shí)現(xiàn)擴(kuò)容的？

• 當(dāng)創(chuàng)建ArrayList對象時(shí)，如果使用的是無參構(gòu)造器，則初始elementData容量為0，第1次添加，則擴(kuò)容elementData為10，如需要再次擴(kuò)容，則擴(kuò)容elementData:為1.5倍
• 如果使用的是指定大小的構(gòu)造器，則初始elementData容量為指定大小，如果需要擴(kuò)容，則直接擴(kuò)容elementData為1.5倍。

ArrayList和LinkedList的區(qū)別

• 是否保證線程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保證線程安全；
• 底層數(shù)據(jù)結(jié)構(gòu)： Arraylist 底層使用的是 Object 數(shù)組；LinkedList 底層使用的是 雙向鏈表 數(shù)據(jù)結(jié)構(gòu)（JDK1.6 之前為循環(huán)鏈表，JDK1.7 取消了循環(huán)。注意雙向鏈表和雙向循環(huán)鏈表的區(qū)別，下面有介紹到?。?/li>
• 插入和刪除是否受元素位置的影響： ① ArrayList 采用數(shù)組存儲，所以插入和刪除元素的時(shí)間復(fù)雜度受元素位置的影響。 比如：執(zhí)行add(E e)方法的時(shí)候， ArrayList 會默認(rèn)在將指定的元素追加到此列表的末尾，這種情況時(shí)間復(fù)雜度就是 O(1)。但是如果要在指定位置 i 插入和刪除元素的話（add(int index, E element)）時(shí)間復(fù)雜度就為 O(n-i)。因?yàn)樵谶M(jìn)行上述操作的時(shí)候集合中第 i 和第 i 個(gè)元素之后的(n-i)個(gè)元素都要執(zhí)行向后位/向前移一位的操作。② LinkedList 采用鏈表存儲，所以對于add(E e)方法的插入，刪除元素時(shí)間復(fù)雜度不受元素位置的影響，近似 O(1)，如果是要在指定位置i插入和刪除元素的話（(add(int index, E element)） 時(shí)間復(fù)雜度近似為o(n))因?yàn)樾枰纫苿拥街付ㄎ恢迷俨迦搿?/li>
• 是否支持快速隨機(jī)訪問： LinkedList 不支持高效的隨機(jī)元素訪問，而 ArrayList 支持。快速隨機(jī)訪問就是通過元素的序號快速獲取元素對象(對應(yīng)于get(int index)方法)。
• 內(nèi)存空間占用： ArrayList 的空 間浪費(fèi)主要體現(xiàn)在在 list 列表的結(jié)尾會預(yù)留一定的容量空間，而 LinkedList 的空間花費(fèi)則體現(xiàn)在它的每一個(gè)元素都需要消耗比 ArrayList 更多的空間（因?yàn)橐娣胖苯雍罄^和直接前驅(qū)以及數(shù)據(jù)）。

消息隊(duì)列

MQ如何防止消息不丟失？

使用一個(gè)消息隊(duì)列，其實(shí)就分為三大塊：生產(chǎn)者、中間件、消費(fèi)者，所以要保證消息就是保證三個(gè)環(huán)節(jié)都不能丟失數(shù)據(jù)。

圖片

• 消息生產(chǎn)階段：生產(chǎn)者會不會丟消息，取決于生產(chǎn)者對于異常情況的處理是否合理。從消息被生產(chǎn)出來，然后提交給 MQ 的過程中，只要能正常收到 （ MQ 中間件） 的 ack 確認(rèn)響應(yīng)，就表示發(fā)送成功，所以只要處理好返回值和異常，如果返回異常則進(jìn)行消息重發(fā)，那么這個(gè)階段是不會出現(xiàn)消息丟失的。
• 消息存儲階段：RabbitMQ 或 Kafka 這類專業(yè)的隊(duì)列中間件，在使用時(shí)是部署一個(gè)集群，生產(chǎn)者在發(fā)布消息時(shí)，隊(duì)列中間件通常會寫「多個(gè)節(jié)點(diǎn)」，也就是有多個(gè)副本，這樣一來，即便其中一個(gè)節(jié)點(diǎn)掛了，也能保證集群的數(shù)據(jù)不丟失。
• 消息消費(fèi)階段：消費(fèi)者接收消息+消息處理之后，才回復(fù) ack 的話，那么消息階段的消息不會丟失。不能收到消息就回 ack，否則可能消息處理中途掛掉了，消息就丟失了。

MQ消息大量堆積怎么辦？

• 從生產(chǎn)者端解決：一般我們的系統(tǒng)容量或者處理能力都是規(guī)劃好的，出現(xiàn)消息堆積的情況，大部分是由于流量暴增引起，這個(gè)時(shí)候可以考慮控制生產(chǎn)者的速率，對前端機(jī)器流量進(jìn)行限速限流。
• 從消費(fèi)者端解決。消費(fèi)者端解決的思路有兩種：

假如消費(fèi)者數(shù)還有增加的空間，那么我們加消費(fèi)者解決。

假如沒有拓展的可能，但吞吐量還沒達(dá)到MQ的上限，只是消費(fèi)者消費(fèi)能力不足，比如消費(fèi)者總體消費(fèi)能力已經(jīng)到達(dá)上線（數(shù)據(jù)庫寫入能力等），或者類似Kafka的消費(fèi)者數(shù)量與partition數(shù)有關(guān)，如果前期設(shè)計(jì)沒有做好水平拓展的設(shè)計(jì)，這個(gè)時(shí)候多少個(gè)partition就只能對應(yīng)多少個(gè)消費(fèi)者。這個(gè)時(shí)候我們可以先把一部分消息先打到另外一個(gè)MQ中或者先落到日志文件中，再拓展消費(fèi)者進(jìn)行消費(fèi)，優(yōu)先恢復(fù)上游業(yè)。

• 從整體系統(tǒng)上進(jìn)行解決：第2點(diǎn)有提到就是有些MQ的設(shè)計(jì)限制，導(dǎo)致的消費(fèi)者數(shù)是沒法動態(tài)拓展的，這個(gè)時(shí)候可以考慮將原先隊(duì)列進(jìn)行拆分，比如新建一個(gè)topic 分擔(dān)一部分消息，這個(gè)方式需要對系統(tǒng)的上下游都要進(jìn)行調(diào)整，在實(shí)際操作難度可能比較高，處理起來可能也比較耗時(shí)，如果在事前有做好這個(gè)設(shè)計(jì)那事發(fā)后就能很好進(jìn)行調(diào)整。

算法

算法題：最長公共子串

算法題：K個(gè)一組翻轉(zhuǎn)鏈表