- HashMap的put方法
- HashMap的擴容過程
- 自定義協議怎麼解決粘包問題
- LeetCode129題(求根節點到葉節點數字之和)
- mysql的索引結構
- 為什麼用B+樹
- having的作用
- 聚簇索引
- 聚簇索引相比非聚簇索引的優點
- 線程池的七大參數 corePoolSize maximumPoolSize BlockingQueue keepAliveTime TimeUnit ThreadFactory RejectedExecutionHandler
- 線程池的運行過程
- mysql的四個隔離級別
- dubbo的負載均衡策略 Random LoadBalance RoundRobin LoadBalance LeastActive LoadBalance ConsistentHash LoadBalance
- java的動態代理
- Spring哪裡用到了動態代理?
- 說一下CGlib動態代理
- MQ如何保證消息不會丟失? 生產者確認機制 Return消息機制 消費者手動消息確認 持久化
今天分享一下字節跳動抖音電商的面經,希望對小夥伴們有所幫助~
文章目錄:
HashMap的put方法
put方法過程:
- 如果table沒有初始化就先進行初始化過程
- 使用hash算法計算key的索引
- 判斷索引處有沒有存在元素,沒有就直接插入
- 如果索引處存在元素,則遍歷插入,有兩種情況,一種是鍊表形式就直接遍歷到尾端插入,一種是紅黑樹就按照紅黑樹結構插入
- 鍊表的數量大於閾值8,就要轉換成紅黑樹的結構
- 添加成功後會檢查是否需要擴容
HashMap的擴容過程
1.8擴容機制:當元素個數大於threshold時,會進行擴容,使用2倍容量的數組代替原有數組。採用尾插入的方式將原數組元素拷貝到新數組。1.8擴容之後鍊表元素相對位置沒有變化,而1.7擴容之後鍊表元素會倒置。
由於數組的容量是以2的冪次方擴容的,那麼一個Entity在擴容時,新的位置要麼在原位置,要麼在原長度+原位置的位置。原因是數組長度變為原來的2倍,表現在二進位上就是多了一個高位參與數組下標計算。也就是說,在元素拷貝過程不需要重新計算元素在數組中的位置,只需要看看原來的hash值新增的那個bit是1還是0,是0的話索引沒變,是1的話索引變成「原索引+oldCap」(根據e.hash & (oldCap - 1) == 0判斷) 。
這樣可以省去重新計算hash值的時間,而且由於新增的1bit是0還是1可以認為是隨機的,因此resize的過程會均勻的把之前的衝突的節點分散到新的bucket。
自定義協議怎麼解決粘包問題
- 固定長度的數據包。為字節流加上自定義固定長度報頭,報頭中包含字節流長度,然後一次send到對端,對端在接收時,先從緩存中取出定長的報頭,然後再取真實數據。
- 以指定字符串為包的結束標誌。當字節流中遇到特殊的符號值時就認為到一個包的結尾。
- header + body格式。這種格式的包一般分為兩部分,即包頭和包體,包頭是固定大小的,且包頭中含有一個欄位來表明包體有多大。
LeetCode129題(求根節點到葉節點數字之和)
深度優先搜索。從根節點開始,遍歷每個節點,如果遇到葉子節點,則將葉子節點對應的數字加到數字之和。如果當前節點不是葉子節點,則計算其子節點對應的數字,然後對子節點遞歸遍歷。
沒有困難的題目,只有勇敢的刷題人!
// 輸入: [1,2,3]
// 1
// / \
// 2 3
// 輸出: 25
class Solution {
public int sumNumbers(TreeNode root) {
if (root == null) {
Return 0;
}
return sumNumbersHelper(root, 0);
}
private int sumNumbersHelper(TreeNode node, int sum) {
if (node == null) {
return 0;
}
if (sum > Integer.MAX_VALUE / 10 || (sum == Integer.MAX_VALUE / 10 && node.val > Integer.MAX_VALUE % 10)) {
throw new IllegalArgumentException("exceed max int value");
}
sum = sum * 10 + node.val;
if (node.left == null && node.right == null) {
return sum;
}
return sumNumbersHelper(node.right, sum) + sumNumbersHelper(node.left, sum);
}
}
MySQL的索引結構
MySQL 資料庫使用最多的索引類型是BTREE索引,底層基於B+樹數據結構來實現。
B+ 樹是基於B 樹和葉子節點順序訪問指針進行實現,它具有B樹的平衡性,並且通過順序訪問指針來提高區間查詢的性能。
在 B+ 樹中,節點中的 key 從左到右遞增排列,如果某個指針的左右相鄰 key 分別是 keyi 和 keyi+1,則該指針指向節點的所有 key 大於等於 keyi 且小於等於 keyi+1。
進行查找操作時,首先在根節點進行二分查找,找到key所在的指針,然後遞歸地在指針所指向的節點進行查找。直到查找到葉子節點,然後在葉子節點上進行二分查找,找出 key 所對應的數據項。
為什麼用B+樹
B+樹的特點就是夠矮夠胖,能有效地減少訪問節點次數從而提高性能。
二叉樹:二分查找樹,雖然也有很好的查找性能log2N,但是當N比較大的時候,樹的深度比較高。數據查詢的時間主要依賴於磁碟IO的次數,二叉樹深度越大,查找的次數越多,性能越差。最壞的情況會退化成鍊表。所以,B+樹更適合作為MySQL索引結構。
B樹:因為B+的分支結點存儲著數據,我們要找到具體的數據,需要進行一次中序遍歷按序來掃,而由於B+樹的數據都存儲在葉子結點中,葉子結點均為索引,方便掃庫,只需要掃一遍葉子結點即可。所以B+樹更加適合在區間查詢的情況,而在資料庫中基於範圍的查詢是非常頻繁的,所以B+樹更適合用於資料庫索引。
having的作用
having 用來分組查詢後指定一些條件來輸出查詢結果,having作用和where類似,但是having只能用在group by場合,並且必須位於group by之後order by之前。
SELECT cust_id, COUNT(*) AS orders
FROM orders
GROUP BY cust_id
HAVING COUNT(*) >= 2;
聚簇索引
聚集索引的葉子節點就是整張表的行記錄。innodb 主鍵使用的是聚簇索引。聚集索引要比非聚集索引查詢效率高很多。聚集索引葉子節點的存儲是邏輯上連續的,使用雙向鍊表連接,葉子節點按照主鍵的順序排序,因此對於主鍵的排序查找和範圍查找速度比較快。
對於InnoDB來說,聚集索引一般是表中的主鍵索引,如果表中沒有顯示指定主鍵,則會選擇表中的第一個不允許為NULL的唯一索引。如果沒有主鍵也沒有合適的唯一索引,那麼innodb內部會生成一個隱藏的主鍵作為聚集索引,這個隱藏的主鍵長度為6個字節,它的值會隨著數據的插入自增。
聚簇索引相比非聚簇索引的優點
- 數據訪問更快,因為聚簇索引將索引和數據保存在同一個B+樹中,因此從聚簇索引中獲取數據比非聚簇索引更快;
- 聚集索引葉子節點的存儲是邏輯上連續的,所以對於主鍵的排序查找和範圍查找速度會更快。
線程池的七大參數
ThreadPoolExecutor 的通用構造函數:
public ThreadPoolExecutor(int corePoolSize, int maximumPoolSize, long keepAliveTime, TimeUnit unit, BlockingQueue<Runnable> workQueue, ThreadFactory threadFactory, RejectedExecutionHandler handler);
corePoolSize
當有新任務時,如果線程池中線程數沒有達到線程池的基本大小,則會創建新的線程執行任務,否則將任務放入阻塞隊列。當線程池中存活的線程數總是大於 corePoolSize 時,應該考慮調大 corePoolSize。
maximumPoolSize
當阻塞隊列填滿時,如果線程池中線程數沒有超過最大線程數,則會創建新的線程運行任務。否則根據拒絕策略處理新任務。非核心線程類似於臨時借來的資源,這些線程在空閒時間超過 keepAliveTime 之後,就應該退出,避免資源浪費。
BlockingQueue
存儲等待運行的任務。
keepAliveTime
非核心線程空閒後,保持存活的時間,此參數只對非核心線程有效。設置為0,表示多餘的空閒線程會被立即終止。
TimeUnit
時間單位,具體如下:
TimeUnit.DAYS
TimeUnit.HOURS
TimeUnit.MINUTES
TimeUnit.SECONDS
TimeUnit.MILLISECONDS
TimeUnit.MICROSECONDS
TimeUnit.NANOSECONDS
ThreadFactory
每當線程池創建一個新的線程時,都是通過線程工廠方法來完成的。在 ThreadFactory 中只定義了一個方法 newThread,每當線程池需要創建新線程就會調用它。
public class MyThreadFactory implements ThreadFactory {
private final String poolName;
public MyThreadFactory(String poolName) {
this.poolName = poolName;
}
public Thread newThread(Runnable runnable) {
return new MyAppThread(runnable, poolName);//將線程池名字傳遞給構造函數,用於區分不同線程池的線程
}
}
RejectedExecutionHandler
當隊列和線程池都滿了時,根據拒絕策略處理新任務。
AbortPolicy:默認的策略,直接拋出RejectedExecutionException
DiscardPolicy:不處理,直接丟棄
DiscardOldestPolicy:將等待隊列隊首的任務丟棄,並執行當前任務
CallerRunsPolicy:由調用線程處理該任務
線程池的運行過程
mysql的四個隔離級別
先了解下幾個概念:髒讀、不可重複讀、幻讀。
- 髒讀是指在一個事務處理過程里讀取了另一個未提交的事務中的數據。
- 不可重複讀是指在對於資料庫中的某行記錄,一個事務範圍內多次查詢卻返回了不同的數據值,這是由於在查詢間隔,另一個事務修改了數據並提交了。
- 幻讀是當某個事務在讀取某個範圍內的記錄時,另外一個事務又在該範圍內插入了新的記錄,當之前的事務再次讀取該範圍的記錄時,會產生幻行,就像產生幻覺一樣,這就是發生了幻讀。
不可重複讀和髒讀的區別是,髒讀是某一事務讀取了另一個事務未提交的髒數據,而不可重複讀則是讀取了前一事務提交的數據。
幻讀和不可重複讀都是讀取了另一條已經提交的事務,不同的是不可重複讀的重點是修改,幻讀的重點在於新增或者刪除。
事務隔離就是為了解決上面提到的髒讀、不可重複讀、幻讀這幾個問題。
MySQL資料庫為我們提供的四種隔離級別:
- Serializable (串行化):通過強制事務排序,使之不可能相互衝突,從而解決幻讀問題。
- Repeatable read (可重複讀):MySQL的默認事務隔離級別,它確保同一事務的多個實例在並發讀取數據時,會看到同樣的數據行,解決了不可重複讀的問題。
- Read committed (讀已提交):一個事務只能看見已經提交事務所做的改變。可避免髒讀的發生。
- Read uncommitted (讀未提交):所有事務都可以看到其他未提交事務的執行結果。
查看隔離級別:
select @@transaction_isolation;
設置隔離級別:
set session transaction isolation level read uncommitted;
dubbo的負載均衡策略
Dubbo提供了多種均衡策略,默認為Random隨機調用。
Random LoadBalance
基於權重的隨機負載均衡機制。
- 隨機,按權重設置隨機概率
- 在一個截面上碰撞的概率高,但調用量越大分布越均勻,而且按概率使用權重後也比較均勻,有利於動態調整提供者權重
RoundRobin LoadBalance
基於權重的輪詢負載均衡機制,不推薦。
- 輪循,按公約後的權重設置輪循比率
- 存在慢的提供者累積請求的問題,比如:第二台機器很慢,但沒掛,當請求調到第二台時就卡在那,久而久之,所有請求都卡在調到第二台上
LeastActive LoadBalance
- 最少活躍調用數,相同活躍數的隨機,活躍數指調用前後計數差
- 使慢的提供者收到更少請求,因為越慢的提供者的調用前後計數差會越大
ConsistentHash LoadBalance
- 一致性 Hash,相同參數的請求總是發到同一提供者。(如果你需要的不是隨機負載均衡,是要一類請求都到一個節點,那就走這個一致性hash策略。)
- 當某一台提供者掛時,原本發往該提供者的請求,基於虛擬節點,平攤到其它提供者,不會引起劇烈變動。
java的動態代理
動態代理:代理類在程序運行時創建,在內存中臨時生成一個代理對象,在運行期間對業務方法進行增強。
JDK實現代理只需要使用newProxyInstance方法:
static Object newProxyInstance(ClassLoader loader, Class<?>[] interfaces, InvocationHandler h )
參數說明:
- ClassLoader loader:指定當前目標對象使用的類加載器
- Class<?>[] interfaces:目標對象實現的接口的類型
- InvocationHandler h:當代理對象調用目標對象的方法時,會觸發事件處理器的invoke方法()
以下是JDK動態代理Demo:
public class DynamicProxyDemo {
public static void main(String[] args) {
//被代理的對象
MySubject realSubject = new RealSubject();
//調用處理器
MyInvacationHandler handler = new MyInvacationHandler(realSubject);
MySubject subject = (MySubject) Proxy.newProxyInstance(realSubject.getClass().getClassLoader(),
realSubject.getClass().getInterfaces(), handler);
System.out.println(subject.getClass().getName());
subject.rent();
}
}
interface MySubject {
public void rent();
}
class RealSubject implements MySubject {
@Override
public void rent() {
System.out.println("rent my house");
}
}
class MyInvacationHandler implements InvocationHandler {
private Object subject;
public MyInvacationHandler(Object subject) {
this.subject = subject;
}
@Override
public Object invoke(Object object, Method method, Object[] args) throws Throwable {
System.out.println("before renting house");
//invoke方法會攔截代理對象的方法調用
Object o = method.invoke(subject, args);
System.out.println("after rentint house");
return o;
}
}
Spring哪裡用到了動態代理?
Spring AOP 是通過動態代理技術實現的。
什麼是AOP?
AOP,面向切面編程,作為面向對象的一種補充,將公共邏輯(事務管理、日誌、緩存等)封裝成切面,跟業務代碼進行分離,可以減少系統的重複代碼和降低模塊之間的耦合度。切面就是那些與業務無關,但所有業務模塊都會調用的公共邏輯。
動態代理的實現方式?
動態代理技術的實現方式有兩種:
- 基於接口的 JDK 動態代理。
- 基於繼承的 CGLib 動態代理。在Spring中,如果目標類沒有實現接口,那麼Spring AOP會選擇使用CGLIB來動態代理目標類。
說一下CGlib動態代理
CGLIB(Code Generator Library)是一個強大的、高性能的代碼生成庫。其被廣泛應用於AOP框架(Spring、dynaop)中,用以提供方法攔截操作。CGLIB代理主要通過對字節碼的操作,為對象引入間接級別,以控制對象的訪問。
CGLib 動態代理相對於 JDK 動態代理局限性就小很多,目標對象不需要實現接口,底層是通過繼承目標對象產生代理子對象。
MQ如何保證消息不會丟失?
消息丟失場景:生產者生產消息到rabbitmq Server消息丟失、RabbitMQ Server存儲的消息丟失和RabbitMQ Server到消費者消息丟失。
消息丟失從三個方面來解決:生產者確認機制、消費者手動確認消息和持久化。以下實現以 RabbitMQ 為例。
生產者確認機制
生產者發送消息到隊列,無法確保發送的消息成功的到達server。
解決方法:
- 事務機制。在一條消息發送之後會使發送端阻塞,等待RabbitMQ的回應,之後才能繼續發送下一條消息。性能差。
- 開啟生產者確認機制,只要消息成功發送到交換機之後,RabbitMQ就會發送一個ack給生產者(即使消息沒有Queue接收,也會發送ack)。如果消息沒有成功發送到交換機,就會發送一條nack消息,提示發送失敗。
在 Springboot 是通過 publisher-confirms 參數來設置 confirm 模式:
spring:
rabbitmq:
#開啟 confirm 確認機制
publisher-confirms: true
在生產端提供一個回調方法,當服務端確認了一條或者多條消息後,生產者會回調這個方法,根據具體的結果對消息進行後續處理,比如重新發送、記錄日誌等。
// 消息是否成功發送到Exchange
final RabbitTemplate.ConfirmCallback confirmCallback = (CorrelationData correlationData, boolean ack, String cause) -> {
log.info("correlationData: " + correlationData);
log.info("ack: " + ack);
if(!ack) {
log.info("異常處理....");
}
};
rabbitTemplate.setConfirmCallback(confirmCallback);
Return消息機制
生產者確認機制只確保消息正確到達交換機,對於從交換機路由到Queue失敗的消息,會被丟棄掉,導致消息丟失。
對於不可路由的消息,可以通過 Return 消息機制來處理。
Return消息機制提供了回調函數 ReturnCallback,當消息從交換機路由到Queue失敗才會回調這個方法。需要將mandatory 設置為 true ,才能監聽到路由不可達的消息。
spring:
rabbitmq:
#觸發ReturnCallback必須設置mandatory=true, 否則Exchange沒有找到Queue就會丟棄掉消息, 而不會觸發ReturnCallback
template.mandatory: true
通過 ReturnCallback 監聽路由不可達消息。
final RabbitTemplate.ReturnCallback returnCallback = (Message message, int replyCode, String replyText, String exchange, String routingKey) ->
log.info("return exchange: " + exchange + ", routingKey: "
+ routingKey + ", replyCode: " + replyCode + ", replyText: " + replyText);
rabbitTemplate.setReturnCallback(returnCallback);
當消息從交換機路由到Queue失敗時,會返回 return exchange: , routingKey: MAIL, replyCode: 312, replyText: NO_ROUTE。
消費者手動消息確認
有可能消費者收到消息還沒來得及處理MQ服務就宕機了,導致消息丟失。因為消息者默認採用自動ack,一旦消費者收到消息後會通知MQ Server這條消息已經處理好了,MQ 就會移除這條消息。
解決方法:消費者設置為手動確認消息。消費者處理完邏輯之後再給broker回復ack,表示消息已經成功消費,可以從broker中刪除。當消息者消費失敗的時候,給broker回復nack,根據配置決定重新入隊還是從broker移除,或者進入死信隊列。只要沒收到消費者的 acknowledgment,broker 就會一直保存著這條消息,但不會 requeue,也不會分配給其他 消費者。
消費者設置手動ack:
#設置消費端手動 ack
spring.rabbitmq.listener.simple.acknowledge-mode=manual
消息處理完,手動確認:
@RabbitListener(queues = RabbitMqConfig.MAIL_QUEUE)
public void onMessage(Message message, Channel channel) throws IOException {
try {
Thread.sleep(5000);
} catch (InterruptedException e) {
e.printStackTrace();
}
long deliveryTag = message.getMessageProperties().getDeliveryTag();
//手工ack;第二個參數是multiple,設置為true,表示deliveryTag序列號之前(包括自身)的消息都已經收到,設為false則表示收到一條消息
channel.basicAck(deliveryTag, true);
System.out.println("mail listener receive: " + new String(message.getBody()));
}
當消息消費失敗時,消費端給broker回復nack,如果consumer設置了requeue為false,則nack後broker會刪除消息或者進入死信隊列,否則消息會重新入隊。
持久化
如果RabbitMQ服務異常導致重啟,將會導致消息丟失。RabbitMQ提供了持久化的機制,將內存中的消息持久化到硬碟上,即使重啟RabbitMQ,消息也不會丟失。
消息持久化需要滿足以下條件:
- 消息設置持久化。發布消息前,設置投遞模式delivery mode為2,表示消息需要持久化。
- Queue設置持久化。
- 交換機設置持久化。
當發布一條消息到交換機上時,Rabbit會先把消息寫入持久化日誌,然後才向生產者發送響應。一旦從隊列中消費了一條消息的話並且做了確認,RabbitMQ會在持久化日誌中移除這條消息。在消費消息前,如果RabbitMQ重啟的話,伺服器會自動重建交換機和隊列,加載持久化日誌中的消息到相應的隊列或者交換機上,保證消息不會丟失。
如果本文對你有幫助,別忘記給我個3連 ,點讚,轉發,評論,
咱們下期見!答案獲取方式:已贊 已評 已關~
學習更多知識與技巧,關注與私信博主(03)
原文出處:https://www.nowcoder.com/discuss/945270