你好,我是田哥
本文主人翁是我星球里一位同學(xué),周一線上順豐面試遇到的問題,反饋面經(jīng)時,只記得部分的。
本來約的三點(diǎn)的面試,但是面試官提前上線看到我在線就說提前開始吧。
先看問題
- 說一個你認(rèn)為有挑戰(zhàn)的項(xiàng)目
- B+樹的特點(diǎn),有幾層,最大可以存放多少條數(shù)據(jù)
Redis
為什么使用跳表而不使用B+樹或二叉樹呢?- 如果單表數(shù)據(jù)量過千萬,怎么優(yōu)化?
- 一個500w條數(shù)據(jù)的表 a,一個300w數(shù)據(jù)的表 b,通過外鍵 tid 關(guān)聯(lián),如何最快的查詢出滿足條件的第50000到第50200中的這200條數(shù)據(jù)記錄?
試題解析
自我介紹
菜鳥的回答:
面試官你好,我叫張三,湖南人,畢業(yè)于XX大學(xué),從XX年畢業(yè)后就一直從事java開發(fā),差不多
3年了吧。來貴公司面試,尋求一份java開發(fā)工作。
自我介紹要說幾個點(diǎn):你是誰,你的優(yōu)點(diǎn)是什么?這么多年你干了啥?在學(xué)校獲得過什么獎?對哪些技術(shù)有深入研究?是否有高并發(fā)系統(tǒng)的設(shè)計?是否參與過什么大型項(xiàng)目?有沒有待過團(tuán)隊(duì)?
總之,把你最好的一面亮出來,讓人家知道你哪方面相對比較強(qiáng)。
說一個你認(rèn)為有挑戰(zhàn)的項(xiàng)目
這個問題其實(shí)是因人而異的,對于剛?cè)腴T的朋友,叫他搭建個項(xiàng)目就覺得很有挑戰(zhàn)性。所以,大部分對于這個他該如何回答也是一籌莫展。
其實(shí),對于大佬來說,“挑戰(zhàn)性”已經(jīng)不再是技術(shù),更多的是如何包裝項(xiàng)目哄好面試官(老板)、如何壓榨自己的下屬才是項(xiàng)目有挑戰(zhàn)性的點(diǎn)。
而在面試環(huán)節(jié),有“挑戰(zhàn)性”是對于面試官而言的一個標(biāo)準(zhǔn)。如果這個項(xiàng)目業(yè)務(wù)這個技術(shù)點(diǎn)面試官沒接觸過,聽起來很難,那這個就是一個“有挑戰(zhàn)”的項(xiàng)目。
如果面試官對你所說的挑戰(zhàn)項(xiàng)目很熟悉,此時可能對你來說是個機(jī)會也是個挑戰(zhàn),回答出面試官沒遇到的問題,并已經(jīng)解決的,那面試官妥妥的佩服你。反之,面試官都知道的問題,你卻答不上來,那就會讓面試大打折扣了。
技術(shù)棧也很重要,比如說:五六年前,你的技術(shù)棧中有dubbo、Spring Boot 那是很吃香的,但是現(xiàn)在已經(jīng)是標(biāo)配了。
但是有大數(shù)據(jù)、高并發(fā)、架構(gòu)改造經(jīng)驗(yàn)的開發(fā)者還是少,因?yàn)榻^大部分公司都沒法發(fā)展成為大公司。但。這個也是隨著軟件工程怎么發(fā)展都無法改變的事。
所以對于有挑戰(zhàn)的項(xiàng)目具有以下幾個特點(diǎn):
1、大數(shù)據(jù)量
2、高并發(fā)
3、架構(gòu)改造
只要你的項(xiàng)目能和這幾個東西沾一點(diǎn)邊,那你的項(xiàng)目level就高至少一級。
這里,我給你一個回答的模板:
1、我負(fù)責(zé)的是這個xxx業(yè)務(wù)項(xiàng)目,這個業(yè)務(wù)的是用來xxx的。
2、前期為了快速試錯,快速響應(yīng)市場,前期使用了簡單的xxxx方案。
3、隨著業(yè)務(wù)的發(fā)展,這個方案在xxx方面出現(xiàn)xxx的技術(shù)問題。
4、為了解決這些技術(shù)難點(diǎn),最終用了xxx方案,然后介紹其他方案,同時這些方案是怎么解決這些技術(shù)問題的。
平時都是怎么學(xué)習(xí)Java的
就如實(shí)的說自己的學(xué)習(xí)歷程,但要注意,學(xué)習(xí)要體現(xiàn)出自己是主動的,另外,標(biāo)注自己有個好習(xí)慣:記筆記,好幾下不如爛筆頭。
推薦看官網(wǎng),看書,看視頻。
學(xué)習(xí)過程中,不斷實(shí)踐,不斷反思,不斷總結(jié)。
說一下抽象類和接口
相同點(diǎn)
(1)都不能被實(shí)例化 (2)接口的實(shí)現(xiàn)類或抽象類的子類都只有實(shí)現(xiàn)了接口或抽象類中的方法后才能實(shí)例化。
不同點(diǎn)
(1)接口只有定義,不能有方法的實(shí)現(xiàn),JDK 8中可以定義default方法體,而抽象類可以有定義與實(shí)現(xiàn),方法可在抽象類中實(shí)現(xiàn)。
(2)實(shí)現(xiàn)接口的關(guān)鍵字為implements,繼承抽象類的關(guān)鍵字為extends。一個類可以實(shí)現(xiàn)多個接口,但一個類只能繼承一個抽象類。所以,使用接口可以間接地實(shí)現(xiàn)多重繼承。
(3)接口強(qiáng)調(diào)特定功能的實(shí)現(xiàn),而抽象類強(qiáng)調(diào)所屬關(guān)系。
(4)接口成員變量默認(rèn)為public static final,必須賦初值,不能被修改;其所有的成員方法都是public、abstract的。抽象類中成員變量默認(rèn)default,可在子類中被重新定義,也可被重新賦值;抽象方法被abstract修飾,不能被private、static、synchronized和native等修飾,必須以分號結(jié)尾,不帶花括號。
說一下HashMap和Hashtable
我們可以從五個方面來回答:
線程是否安全:HashMap 是非線程安全的, HashTable 是線程安全的。因?yàn)?HashTable 內(nèi)部的方法基本都經(jīng)過 synchronized 修飾。(如果你要保證線程安全的話就使用 ConcurrentHashMap);
效率:因?yàn)榫€程安全的問題, HashMap 要比 HashTable 效率高一點(diǎn)。另外, HashTable基本被淘汰,不要在代碼中使用它;
對 Null key 和 Null value 的支持:HashMap 可以存儲 null 的 key 和 value,但 null 作為鍵只能有一個,null 作為值可以有多個;HashTable 不允許有 null 鍵和 null 值,否則會拋出NullPointerException 。
初始容量帶下和每次擴(kuò)充容量大小的不同 :
① 創(chuàng)建時如果不指定容量初始值, Hashtable默認(rèn)的初始大小為 11,之后每次擴(kuò)充,容量變?yōu)樵瓉淼?2n+1。HashMap 默認(rèn)的初始化大小為 16。之后每次擴(kuò)充,容量變?yōu)樵瓉淼?2 倍。
② 創(chuàng)建時如果給定了容量初始值,那么Hashtable 會直接使用你給定的大小,而 HashMap 會將其擴(kuò)充為 2 的冪次方大?。?HashMap 中的tableSizeFor()
方法保證)。
底層數(shù)據(jù)結(jié)構(gòu):JDK1.8 以后的 HashMap 在解決哈希沖突時有了較大的變化,當(dāng)鏈表長度大于閾值(默認(rèn)為 8)(將鏈表轉(zhuǎn)換成紅黑樹前會判斷,如果當(dāng)前數(shù)組的長度度大于 64,那么會選擇先進(jìn)行數(shù)組擴(kuò)容,而不是轉(zhuǎn)換為紅黑樹)時,將鏈表轉(zhuǎn)化為紅黑樹,以減少搜索時間。Hashtable 沒有這樣的機(jī)制。
盡管是普通不能再普通的面試題了,可面試中,照樣很大部分人同學(xué)回答的不好?;卮鹬刑岬搅?的n次冪,面試官很有可能會繼續(xù)追問相關(guān)的問題,如果還不清楚的,建議對HashMap進(jìn)行系統(tǒng)的學(xué)習(xí)。
我的博客上之前發(fā)過兩篇文章:
HashMap的31連環(huán)炮,我倒在第5個上
三年必備, HashMap 源碼
HashMap
添加一個元素的流程
HashMap
在put添加元素過程可以分為下面9個步驟:
- 1.使用put()方法時,直接調(diào)
putVal()
方法 - 2.在put的時候先判斷數(shù)組是否為空,如果為空則進(jìn)行resize操作
- 3.以hash索引數(shù)組的長度-1與key的hash值進(jìn)行與運(yùn)算,得出在數(shù)組中的索引,如果索引指定的位置為空,則代表可以插入,直接插入一個新的node
- 4.判斷當(dāng)前的key是否存在,如果存在則進(jìn)行替換,如果替換成功則返回老的值
- 5.如果key不存在,則判斷當(dāng)前節(jié)點(diǎn)是否為樹類型,如果是樹類型的話,則按照樹的操作去追加新節(jié)點(diǎn)內(nèi)容
- 6.如果出現(xiàn)hash沖突的節(jié)點(diǎn)不是樹類型,則說明當(dāng)前發(fā)生的碰撞在鏈表里面,則這個時候就進(jìn)入循環(huán)處理邏輯
- 7.進(jìn)入循環(huán)邏輯之后先判斷被碰撞節(jié)點(diǎn)的下一個節(jié)點(diǎn)是否為空,如果為空就將新節(jié)點(diǎn)放入
- 8.放入后判斷當(dāng)前鏈表是否超過最大允許鏈表長度8,如果超過則轉(zhuǎn)為紅黑樹進(jìn)行插入
- 9.如果map的索引表為空或者當(dāng)前索引表長度還小于64(最大轉(zhuǎn)紅黑樹的索引數(shù)組表長度),那么進(jìn)行resize操作就行了;否則,如果被碰撞節(jié)點(diǎn)不為空,那么就順著被碰撞節(jié)點(diǎn)這條樹往后新增該節(jié)點(diǎn)插入
可以看看我博客(www.woaijava.cc)上的博文:三年必備, HashMap 源碼
什么是紅黑樹,特點(diǎn)是什么?
紅黑樹(Red Black Tree)是一種特化的AVL樹(平衡二叉樹),都是在進(jìn)行插入和刪除操作時通過特定操作保持二叉查找樹的平衡,從而獲得較高的查找性能。
紅黑樹的特點(diǎn)有5個:
所有葉子都是黑色(葉子是NIL結(jié)點(diǎn))
每個紅色節(jié)點(diǎn)的兩個子節(jié)點(diǎn)都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點(diǎn))
從任一節(jié)節(jié)點(diǎn)到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。
其實(shí)這個問題不難,難的是可能有的面試官會問紅黑樹的操作,左旋轉(zhuǎn)右旋轉(zhuǎn)...,我面試過幾百人,能說出來寥寥無幾。
B+樹的特點(diǎn),有幾層,最大可以存放多少條數(shù)據(jù)
B+樹的特點(diǎn)有兩個:
- 1.非葉子節(jié)點(diǎn)]僅具有索引作用,也就是說,非葉子節(jié)點(diǎn)只能存儲Key,不能存儲value
- 2.樹的所有葉節(jié)點(diǎn)構(gòu)成一個有序鏈表,可以按照key排序的次序依次遍歷全部數(shù)據(jù)。
B+樹一般是1~3層。
InnoDB頁的大小默認(rèn)是16KB:
- 假設(shè)一條記錄大小為1KB,則一個數(shù)據(jù)頁中可以存16條數(shù)據(jù)(忽略頁中的其他數(shù)據(jù)結(jié)構(gòu))
- 假設(shè)主鍵為int,指針大小為6B,則一個索引頁中可以存儲
16KB/(4B+6B)≈1638
個索引
所以,兩層的B+樹可以存儲:16*1638=26208
條數(shù)據(jù);三層的B+樹可以存儲:16*1638*1638=42928704
條數(shù)據(jù)。
MySQL
的索引為什么使用B+樹而不使用跳表?
B+樹是多叉樹結(jié)構(gòu),每個結(jié)點(diǎn)都是一個16k的數(shù)據(jù)頁,能存放較多索引信息,所以扇出很高。三層左右就可以存儲2kw
左右的數(shù)據(jù)。也就是說查詢一次數(shù)據(jù),如果這些數(shù)據(jù)頁都在磁盤里,那么最多需要查詢三次磁盤IO。
跳表是鏈表結(jié)構(gòu),一條數(shù)據(jù)一個結(jié)點(diǎn),如果最底層要存放2kw
數(shù)據(jù),且每次查詢都要能達(dá)到二分查找的效果,2kw
大概在2的24次方
左右,所以,跳表大概高度在24層左右。最壞情況下,這24層數(shù)據(jù)會分散在不同的數(shù)據(jù)頁里,也即是查一次數(shù)據(jù)會經(jīng)歷24次磁盤IO。
因此存放同樣量級的數(shù)據(jù),B+樹的高度比跳表的要少,如果放在MySQL數(shù)據(jù)庫上來說,就是磁盤IO次數(shù)更少,因此B+樹查詢更快。
而針對寫操作,B+樹需要拆分合并索引數(shù)據(jù)頁,跳表則獨(dú)立插入,并根據(jù)隨機(jī)函數(shù)確定層數(shù),沒有旋轉(zhuǎn)和維持平衡的開銷,因此跳表的寫入性能會比B+樹要好。
其實(shí),MySQL的存儲引擎是可以換的,以前mysql 5.5是myisam
,后來才有的innodb
,它們底層索引用的都是B+樹。也就是說,你完全可以造一個索引為跳表的存儲引擎裝到MySQL里。事實(shí)上,facebook
造了個rocksDB
的存儲引擎,里面就用了跳表。直接說結(jié)論,它的寫入性能確實(shí)是比innodb要好,但讀性能確實(shí)比innodb要差不少。感興趣的話,可以在文章最后面的參考資料里看到他們的性能對比數(shù)據(jù)。
Redis
為什么使用跳表而不使用B+樹或二叉樹呢?
因?yàn)锽+樹的原理是 葉子節(jié)點(diǎn)存儲數(shù)據(jù),非葉子節(jié)點(diǎn)存儲索引,B+樹的每個節(jié)點(diǎn)可以存儲多個關(guān)鍵字,它將節(jié)點(diǎn)大小設(shè)置為磁盤頁的大小,充分利用了磁盤預(yù)讀的功能。每次讀取磁盤頁時就會讀取一整個節(jié)點(diǎn),每個葉子節(jié)點(diǎn)還有指向前后節(jié)點(diǎn)的指針,為的是最大限度的降低磁盤的IO。因?yàn)閿?shù)據(jù)在內(nèi)存中讀取耗費(fèi)的時間是從磁盤的IO讀取的百萬分之一,而Redis是 內(nèi)存中操作數(shù)據(jù),不涉及IO,因此使用了跳表;
創(chuàng)建索引需要注意些什么?
這道題,也可以用在問你會哪些SQL優(yōu)化的時候。
- 最適合索引的列是出現(xiàn)在
WHERE
子句中的列,或連接子句中的列,而不是出現(xiàn)在 SELECT
關(guān)鍵字后的列。 - 根據(jù)情況創(chuàng)建復(fù)合索引,復(fù)合索引可以提高查詢效率。
- 避免創(chuàng)建過多的索引,索引會額外占用磁盤空間,降低寫操作效率。
- 主鍵盡可能選擇較短的數(shù)據(jù)類型,可以有效減少索引的磁盤占用提高查詢效率。
- 對字符串進(jìn)行索引,應(yīng)該定制一個前綴長度,可以節(jié)省大量的索引空間。
如果單表數(shù)據(jù)量過千萬,怎么優(yōu)化?
1、數(shù)據(jù)庫設(shè)計和表創(chuàng)建時,考慮性能問題,比如:單表不要有太多字段,建議在20以內(nèi)、索引并不是越多越好,要根據(jù)查詢有針對性的創(chuàng)建,考慮在WHERE和ORDER BY命令上涉及的列建立索引,可根據(jù)EXPLAIN來查看是否用了索引還是全表掃描、選擇合適的數(shù)據(jù)類型、選擇合適索引類型等。
2、SQL編寫時需要注意,比如:列表數(shù)據(jù)不要拿全表,要使用LIMIT來分頁,每頁數(shù)量也不要太大、可通過開啟慢查詢?nèi)罩緛碚页鲚^慢的SQL、避免select *,將需要查找的字段列出來等。
3,存儲引擎選擇,MyISAM適合SELECT密集型的表,而InnoDB適合INSERT和UPDATE密集型的表 。
4、分庫分表,比如:分庫把一個數(shù)據(jù)庫分成多個,建議做個讀寫分離就行了,真正的做分庫也會帶來大量的開發(fā)成本,得不償失!不推薦使用、分表就是把一張大表,按照如上過程都優(yōu)化了,還是查詢卡死,那就把這個表分成多張表,把一次查詢分成多次查詢,然后把結(jié)果組合返回給用戶。分表分為垂直拆分和水平拆分,通常以某個字段做拆分項(xiàng)。比如以id字段拆分為100張表:表名為 tableName_id%100。但:分表需要修改源程序代碼,會給開發(fā)帶來大量工作,極大的增加了開發(fā)成本,故:只適合在開發(fā)初期就考慮到了大量數(shù)據(jù)存在,做好了分表處理,不適合應(yīng)用上線了再做修改,成本太高等。
5、硬件升級,這辦法是最簡單的,相對的成本也高,老板就不愿意了。
6、數(shù)據(jù)庫升級,比如:把MySQL數(shù)據(jù)庫換成大數(shù)據(jù)引擎處理數(shù)據(jù)、換成阿里云POLARDB,POLARDB 是阿里云自研的下一代關(guān)系型分布式云原生數(shù)據(jù)庫,100%兼容MySQL,存儲容量最高可達(dá) 100T,性能最高提升至 MySQL 的 6 倍。
一個500w條數(shù)據(jù)的表 a,一個300w數(shù)據(jù)的表 b,通過外鍵 tid 關(guān)聯(lián),如何最快的查詢出滿足條件的第50000到第50200中的這200條數(shù)據(jù)記錄?
方法一:如果 a 表 tid 是自增長,并且是連續(xù)的,b表的id為索引。SQL語句如下。
select * from a,b where a.tid = b.id and a.tid>500000 limit 200;
方法二:如果 a 表的 tid 不是連續(xù)的,那么就需要使用覆蓋索引,tid 要么是主鍵,要么是輔助索引,b 表 id 也需要有索引。SQL語句如下。
select * from b, (select tid from a limit 50000,200) a where b.id = a.tid;
說說JVM的內(nèi)存模型
JVM內(nèi)存結(jié)構(gòu)有:程序計數(shù)器 、堆內(nèi)存 、 方法區(qū) 和 棧 (java虛擬機(jī)棧和本地方法棧)。
程序計數(shù)器(Program Counter Register)是一塊較小的內(nèi)存空間,它的作用可以看做是當(dāng)前線程所執(zhí)行的字節(jié)碼的行號指示器。在虛擬機(jī)的概念模型里(僅是概念模型,各種虛擬機(jī)可能會通過一些更高效的方式去實(shí)現(xiàn)),字節(jié)碼解釋器工作時就是通過改變這個計數(shù)器的值來選取下一條需要執(zhí)行的字節(jié)碼指令,分支、循環(huán)、跳轉(zhuǎn)、異常處理、線程恢復(fù)等基礎(chǔ)功能都需要依賴這個計數(shù)器來完成。
堆內(nèi)存是JVM中最大的一塊由年輕代和老年代組成,而年輕代內(nèi)存又被分成三部分, Eden空間 、 From Survivor空間 、 To Survivor空間 ,默認(rèn)情況下年輕代按照 8:1:1
的比例來分配;
方法區(qū)存儲類信息、常量、靜態(tài)變量等數(shù)據(jù),是線程共享的區(qū)域,為與Java堆區(qū)分,方法區(qū)還有一個別名Non-Heap(非堆);棧又分為java虛擬機(jī)棧和本地方法棧主要用于方法的執(zhí)行。方法區(qū)可理解為一種規(guī)范,其實(shí)現(xiàn)比如永久代、元空間。
Java虛擬機(jī)棧(Java Virtual Machine Stacks)也是線程私有的,它的生命周期與線程相同。虛擬機(jī)棧描述的是Java方法執(zhí)行的內(nèi)存模型:每個方法被執(zhí)行的時候都會同時創(chuàng)建一個棧幀(Stack Frame)用于存儲局部變量表、操作棧、動態(tài)鏈接、方法出口等信息。每一個方法被調(diào)用直至執(zhí)行完成的過程,就對應(yīng)著一個棧幀在虛擬機(jī)棧中從入棧到出棧的過程。
本地方法棧(Native Method Stacks)與虛擬機(jī)棧所發(fā)揮的作用是非常相似的,其區(qū)別不過是虛擬機(jī)棧為虛擬機(jī)執(zhí)行Java方法(也就是字節(jié)碼)服務(wù),而本地方法棧則是為虛擬機(jī)使用到的Native方法服務(wù)。虛擬機(jī)規(guī)范中對本地方法棧中的方法使用的語言、使用方式與數(shù)據(jù)結(jié)構(gòu)并沒有強(qiáng)制規(guī)定,因此具體的虛擬機(jī)可以自由實(shí)現(xiàn)它。
為什么需要Survivor區(qū)?
如果沒有Survivor,Eden區(qū)每進(jìn)行一次Minor GC ,并且沒有年齡限制的話, 存活的對象就會被送到老年代。這樣一來,老年代很快被填滿,觸發(fā)Major GC(因?yàn)镸ajor GC一般伴隨著Minor GC,也可以看做觸發(fā)了Full GC)。老年代的內(nèi)存空間遠(yuǎn)大于新生代,進(jìn)行一次Full GC消耗的時間比Minor GC長得多。
面試官可能會問:執(zhí)行時間長有什么壞處?
頻發(fā)的Full GC消耗的時間很長,會影響大型程序的執(zhí)行和響應(yīng)速度。
假如增加老年代空間,更多存活對象才能填滿老年代。雖然降低Full GC頻率,但是隨著老年代空間加大,一旦發(fā)生Full GC,執(zhí)行所需要的時間更長。
假如減少老年代空間,雖然Full GC所需時間減少,但是老年代很快被存活對象填滿,Full GC頻率增加。
所以Survivor的存在意義,就是減少被送到老年代的對象,進(jìn)而減少Full GC的發(fā)生,Survivor的預(yù)篩選保證,只有經(jīng)歷16 次Minor GC還能在新生代中存活的對象,才會被送到老年代。
你有什么想問我的嗎?
有的面試官是禮貌性的問,根本不在意你回答內(nèi)容,因?yàn)榇藭r估計面試就是涼涼啦。
但是,有反問的機(jī)會,大部分還是覺得你不錯,被錄取的概率非常大,所以還是得慎重回答
不管ta是怎么樣的心態(tài),咱們表現(xiàn)好自己就行。
這個問題看上去可有可無,其實(shí)很關(guān)鍵,一般面試官不喜歡說“沒問題”的人,因?yàn)槠浜茏⒅貑T工的個性和創(chuàng)新能力。企業(yè)不喜歡求職者問個人福利之類的問題。
貴公司對新入公司的員工有沒有什么項(xiàng)目、業(yè)務(wù)之類的培訓(xùn),我可以參加嗎?或者說貴公司的晉升機(jī)制是什么樣的?企業(yè)將很歡迎,因?yàn)轶w現(xiàn)出你對學(xué)習(xí)的熱情和對公司的忠誠度以及你的上進(jìn)心。
從上面面試問題來看,其實(shí)很大部分還是蠻簡單的,都是八股文的,但也有一些非八股文的,你覺得這次面試難嗎?
歡迎加入我的學(xué)習(xí)圈子,主要是分析面試技巧、模擬面試、修改簡歷、項(xiàng)目實(shí)戰(zhàn)等。