最近整理面試題庫的時(shí)候把用友2018秋招Java筆試題一完整做了一遍。所謂秋招八股文網(wǎng)上總結(jié)很多但真到筆試場景里很多java基礎(chǔ)題還是會(huì)因?yàn)椤捌綍r(shí)太熟”而翻車。這套題整體不偏不怪幾乎沒有框架、中間件這類追新內(nèi)容絕大多數(shù)考點(diǎn)都落在java基礎(chǔ)、java容器、面向?qū)ο缶幊蘪ava外加一道手寫算法、幾道多線程和JVM相關(guān)題。對一個(gè)想做Java后端方向的人來說這套卷子算是很典型的校招筆試樣本。這篇文章就按我實(shí)際做題的順序把每類題背后的原理、易錯(cuò)點(diǎn)以及刷完之后想明白的東西完整記錄一遍希望能給正在準(zhǔn)備Java筆試的同學(xué)提供一個(gè)可參考的復(fù)盤思路。1. 先看整體這套卷子在考什么、難度如何1.1 考點(diǎn)分布與分值傾向整套題做完我對它的第一印象是考察面廣但每一塊的深度都不至于逼你“背源碼”。它的知識(shí)點(diǎn)分布大體可以分成下面幾個(gè)模塊考察模塊典型題目方向難度分值傾向Java基礎(chǔ)語法基本數(shù)據(jù)類型、運(yùn)算符、表達(dá)式、標(biāo)識(shí)符命名規(guī)則低單選/填空面向?qū)ο缶幊蘆ava封裝繼承多態(tài)、抽象類和接口、重載與重寫中單選/簡答Java常用類String、包裝類、枚舉、Object方法中單選/代碼輸出Java容器ArrayList、HashMap、HashSet、迭代器中高單選/代碼輸出異常處理異常的體系、try-catch-finally、受檢異常與非受檢異常中單選/代碼輸出JVM基礎(chǔ)內(nèi)存區(qū)域、類加載、OOM場景中高單選/簡答多線程線程創(chuàng)建方式、synchronized、volatile、并發(fā)問題中高簡答/編程簡單算法排序、數(shù)組處理、字符串處理中手寫代碼這個(gè)結(jié)構(gòu)其實(shí)很能反映傳統(tǒng)軟件企業(yè)的校招出題習(xí)慣他們不太指望應(yīng)屆生一上來就精通分布式、微服務(wù)而是想確認(rèn)你有沒有扎實(shí)的Java語言功底。因?yàn)榭蚣芸梢匀肼毢髮W(xué)但語言基礎(chǔ)不牢固后面帶起來會(huì)非常痛苦。1.2 為什么校招筆試總愛考基礎(chǔ)題很多同學(xué)刷題時(shí)會(huì)有一種錯(cuò)覺基礎(chǔ)題太簡單不值得花時(shí)間。但用友這套題給我最大的提醒恰恰相反——它用大量“看起來簡單”的題目篩掉了概念模糊的人。比如String的比較、Integer的緩存范圍、HashMap的擴(kuò)容時(shí)機(jī)這些題目代碼寫出來都不到十行但每個(gè)點(diǎn)背后都連著JVM內(nèi)存、集合源碼、語法規(guī)則一整條知識(shí)鏈。筆試題的難點(diǎn)不在于“會(huì)不會(huì)寫”而在于“能不能準(zhǔn)確說出為什么”。如果你只是背過結(jié)論而不是真正理解底層機(jī)制換個(gè)問法立刻就會(huì)露餡。1.3 做題時(shí)間分配的建議這套題的題量屬于中等偏上我實(shí)際做完一遍大約是70到80分鐘。如果是在真實(shí)筆試環(huán)境里我的策略是單選題不超過1分鐘一題不確定的先跳過代碼輸出題控制在3到5分鐘內(nèi)手算不出來就畫棧幀圖兩道算法題至少留出20分鐘。畢竟筆試看的是總分時(shí)間要優(yōu)先花在能穩(wěn)定拿分的題目上不要為一道偏題死磕。2. 基礎(chǔ)語法與面向?qū)ο箢}目看著簡單扣分點(diǎn)全在細(xì)節(jié)2.1 基本數(shù)據(jù)類型與引用類型傳參考的是JVM棧幀意識(shí)這套題里有一道很典型的考察方法參數(shù)傳遞的題目大致是給出一個(gè)交換兩個(gè)int變量值的方法問main方法里輸出什么public class SwapTest { public static void main(String[] args) { int a 10; int b 20; swap(a, b); System.out.println(a , b); } public static void swap(int x, int y) { int tmp x; x y; y tmp; } }答案當(dāng)然是10,20。但很多人在考場上會(huì)猶豫原因在于對“值傳遞”和“引用傳遞”的概念沒有真正落到JVM層面。Java的參數(shù)傳遞只有一種值傳遞。對于基本數(shù)據(jù)類型傳來的就是棧幀里的一個(gè)副本你在swap方法里怎么改都不會(huì)影響main方法的局部變量。對于引用類型傳來的是對象引用地址的一個(gè)副本所以在方法里通過這個(gè)引用修改對象內(nèi)部狀態(tài)外面的對象會(huì)感知到但如果對引用變量本身重新賦值外面是感知不到的。畫一張簡易的棧幀圖這個(gè)問題就非常清晰了。更進(jìn)階的版本是Integer包裝類的傳參絕大多數(shù)人會(huì)在這一步踩坑Integer i1 127; Integer i2 127; System.out.println(i1 i2); // true Integer i3 128; Integer i4 128; System.out.println(i3 i4); // false原因涉及Integer的內(nèi)部緩存IntegerCache默認(rèn)緩存了-128到127范圍內(nèi)的對象。Integer i1 127走的是自動(dòng)裝箱實(shí)際調(diào)用Integer.valueOf(127)命中了緩存對象所以i1 i2是true。而128超出緩存范圍每次valueOf都會(huì)new一個(gè)新對象所以i3 i4是false。這道題如果平時(shí)沒注意過源碼筆試現(xiàn)場很容易憑感覺猜。2.2 、equals與String常量池一道題串起一串考點(diǎn)關(guān)于String這套題里幾乎可以確認(rèn)必有一道這樣的代碼輸出題String s1 hello; String s2 new String(hello); String s3 hello; System.out.println(s1 s2); // false System.out.println(s1.equals(s2)); // true System.out.println(s1 s3); // true比較的是引用地址equals在String類中被重寫為比較字符序列。字符串字面量在編譯期就會(huì)放入常量池s1和s3指向同一個(gè)池中的對象所以s1 s3為true。new String(hello)則在堆中額外創(chuàng)建了一個(gè)新對象引用地址和常量池對象不同所以s1 s2為false。如果再深挖一層new String(hello)到底創(chuàng)建了幾個(gè)對象答案是如果常量池中已經(jīng)有“hello”那只創(chuàng)建堆中一個(gè)對象如果常量池里還沒有那么在創(chuàng)建堆對象之前JVM會(huì)先把“hello”放入字符串常量池這樣就一共創(chuàng)建了兩個(gè)對象。這種問法在筆試?yán)镆步?jīng)常出現(xiàn)要會(huì)分情況討論。還有一道常見變形題涉及字符串拼接String a hello; String b world; String c a b;這里要分編譯期和運(yùn)行期。如果拼接的雙方都是編譯期常量比如hello world編譯器會(huì)直接優(yōu)化成helloworld放常量池如果里面含有變量底層會(huì)通過StringBuilder或StringBuffer做拼接生成的新字符串在堆上不在常量池。這也是為什么循環(huán)里做字符串累加性能差的原因因?yàn)槊看窝h(huán)都可能new出新的StringBuilder和String對象。2.3 重載、重寫與多態(tài)編譯期和運(yùn)行期要分開看面向?qū)ο缶幊蘆ava這個(gè)板塊最容易丟分的是“重載和重寫結(jié)合多態(tài)”的題目。比如下面這種class Animal { public void eat() { System.out.println(Animal eat); } } class Dog extends Animal { public void eat() { System.out.println(Dog eat); } public void bark() { System.out.println(Dog bark); } } public class Test { public static void main(String[] args) { Animal a new Dog(); a.eat(); // 輸出什么 } }答案輸出Dog eat。因?yàn)閑at()方法是重寫方法的分派在運(yùn)行期發(fā)生JVM根據(jù)對象的實(shí)際類型Dog來決定調(diào)用Dog的eat方法這叫動(dòng)態(tài)綁定。但如果你寫成a.bark()編譯直接報(bào)錯(cuò)因?yàn)榫幾g器根據(jù)引用類型Animal只能確定Animal類中聲明的方法static類型決定了編譯期的可見范圍。重載則是另一個(gè)維度重載是同一個(gè)類中方法名相同、參數(shù)列表不同它在編譯期就能確定調(diào)用哪個(gè)方法。所以如果有個(gè)方法叫eat(Animal a)和eat(Dog d)調(diào)用時(shí)傳Dog對象編譯期就會(huì)選擇參數(shù)類型更具體的eat(Dog d)方法。這種“編譯期重載 運(yùn)行期重寫”的組合題在筆試題里非常常見一定要把兩個(gè)階段分開考慮。2.4 抽象類和接口考試喜歡問“你怎么選”用友這套題里有一道簡答題問抽象類和接口的區(qū)別。這類題屬于Java八股文里的經(jīng)典款但答得好不好區(qū)別在于能不能說出“設(shè)計(jì)意圖”而不是羅列語法差異。從語法層面看抽象類可以有構(gòu)造方法、普通成員變量、具體方法可以含有抽象方法接口在Java 8之后可以有default方法和static方法Java 9之后可以有私有方法但本質(zhì)上接口強(qiáng)調(diào)的是“能力契約”抽象類強(qiáng)調(diào)的是“血緣關(guān)系”。從設(shè)計(jì)角度看當(dāng)你需要定義“一類事物是什么”并且有公共狀態(tài)要維護(hù)時(shí)用抽象類當(dāng)你只需要定義“一類事物能做什么”而且這個(gè)能力可能被完全無關(guān)的類實(shí)現(xiàn)時(shí)用接口。比如Bird繼承抽象類Animal體現(xiàn)分類體系而Flyable接口讓飛機(jī)和鳥都能擁有飛行能力。這個(gè)設(shè)計(jì)意圖講清楚面試官才會(huì)覺得你是真的理解面向?qū)ο蠖恢皇窃诒潮砀瘛?. 集合框架HashMap 基本是必考大題3.1 ArrayList與LinkedList不要死記“讀快寫慢”集合這里用友的筆試題常見開頭是“ArrayList和LinkedList的區(qū)別”。很多教程喜歡用一句話概括ArrayList適合隨機(jī)訪問LinkedList適合頻繁插入刪除。這句話對但有誤導(dǎo)性。ArrayList底層是動(dòng)態(tài)數(shù)組通過索引訪問的時(shí)間復(fù)雜度是O(1)在尾部添加元素也通常是O(1)但在中間插入或刪除元素時(shí)需要移動(dòng)后面的元素平均是O(n)。LinkedList底層是雙向鏈表頭尾插入刪除是O(1)但中間插入刪除前提是你已經(jīng)持有對應(yīng)節(jié)點(diǎn)的引用否則按索引操作時(shí)仍然需要從頭遍歷到目標(biāo)位置復(fù)雜度還是O(n)。所以如果筆試?yán)飭枴霸谝延墟湵砉?jié)點(diǎn)引用的情況下頻繁刪除要不要用LinkedList”答案是比ArrayList更合適但如果只是按索引隨機(jī)訪問LinkedList反而更慢。審題要看清楚“前提條件”這是集合題最大的坑。3.2 HashSet如何保證元素不重復(fù)HashSet去重的底層其實(shí)是HashMap。它內(nèi)部維護(hù)了一個(gè)HashMap字段把添加的元素作為keyvalue統(tǒng)一是一個(gè)固定對象。因?yàn)镠ashMap的key不可能重復(fù)所以HashSet天然去重。但去重判斷有兩個(gè)步驟先調(diào)用元素的hashCode()計(jì)算哈希找到對應(yīng)的哈希桶再調(diào)用equals()逐一比較桶內(nèi)元素。只有hashCode相同且equals為true時(shí)才判定為重復(fù)對象。很多人只知道要重寫equals忘了同時(shí)重寫hashCode結(jié)果導(dǎo)致兩個(gè)邏輯相等的對象被放進(jìn)了不同桶HashSet完全失去去重能力。筆試題如果有“自定義類放進(jìn)HashSet需要注意什么”回答核心就是這一句equals和hashCode必須一起重寫且滿足equals相等的兩個(gè)對象hashCode必須相等。3.3 HashMap的哈希、沖突、擴(kuò)容與為什么容量是2的冪HashMap幾乎是每一套Java筆試的必考題用友這套也不例外。要答好HashMap不能只背結(jié)論建議按“存數(shù)據(jù)的過程”梳理一遍。當(dāng)調(diào)用put(key, value)時(shí)HashMap先通過key的hashCode()計(jì)算出一個(gè)int值然后對這個(gè)哈希值做一次擾動(dòng)處理讓高位也參與后續(xù)的數(shù)組下標(biāo)計(jì)算目的就是減少哈希碰撞。之后根據(jù)hash (table.length - 1)計(jì)算數(shù)組下標(biāo)這里的位運(yùn)算等價(jià)于hash % table.length但前提是數(shù)組長度必須是2的冪。這正是HashMap容量默認(rèn)為16、指定初始容量也會(huì)自動(dòng)調(diào)整成2的冪的原因用位運(yùn)算替代取模性能更高同時(shí)2的冪在擴(kuò)容時(shí)的元素遷移也更好處理可以按新增一個(gè)高位比特位決定元素落在原位置還是原位置舊容量。當(dāng)key發(fā)生哈希碰撞時(shí)JDK 8開始會(huì)先把沖突元素以鏈表方式掛在同一個(gè)桶上鏈表長度超過8且數(shù)組長度大于等于64時(shí)鏈表會(huì)轉(zhuǎn)成紅黑樹避免極端情況下查詢退化成O(n)。如果數(shù)組長度沒到64即使鏈表超長也只會(huì)先擴(kuò)容而不是轉(zhuǎn)樹。這一點(diǎn)筆試很容易出判斷題。擴(kuò)容機(jī)制也是高頻問題。默認(rèn)加載因子是0.75也就是說當(dāng)元素個(gè)數(shù)超過容量 × 0.75時(shí)HashMap會(huì)觸發(fā)擴(kuò)容把數(shù)組長度擴(kuò)大為原來的兩倍。為什么0.75這是一個(gè)時(shí)間與空間的折中加載因子太大比如1.0空間利用率高但哈希沖突嚴(yán)重查詢變慢加載因子太小比如0.5沖突少但浪費(fèi)大量空間。0.75在大多數(shù)場景下是均衡值所以官方默認(rèn)用它。3.4 fail-fast機(jī)制迭代器中詭異的ConcurrentModificationException集合題目里代碼輸出題很喜歡考這一個(gè)場景ListString list new ArrayList(); list.add(a); list.add(b); for (String s : list) { list.remove(s); }這段代碼運(yùn)行時(shí)會(huì)拋出ConcurrentModificationException原因就是ArrayList內(nèi)部的迭代器是fail-fast設(shè)計(jì)。迭代器內(nèi)部維護(hù)了一個(gè)expectedModCount初始值等于集合的modCount。modCount是結(jié)構(gòu)性修改計(jì)數(shù)器每次添加、刪除元素都會(huì)加1。在迭代過程中如果集合被外部修改不是通過迭代器自身的remove方法modCount和expectedModCount就會(huì)不一致迭代器在下一輪next()時(shí)發(fā)現(xiàn)差值就立刻拋出異常。這本質(zhì)上是一種“快速失敗”的安全機(jī)制避免在有并發(fā)修改的情況下繼續(xù)讀到臟數(shù)據(jù)。如果確實(shí)需要在遍歷中刪除應(yīng)該使用Iterator.remove()或者把要?jiǎng)h除的元素收集起來循環(huán)結(jié)束后統(tǒng)一刪除。4. JVM內(nèi)存與異常筆試中無聲的拉分題4.1 運(yùn)行時(shí)數(shù)據(jù)區(qū)劃分與內(nèi)存溢出場景JVM基礎(chǔ)題最?？嫉木褪沁\(yùn)行時(shí)數(shù)據(jù)區(qū)。每塊區(qū)域存什么、為什么會(huì)溢出要能背得準(zhǔn)確。我按題目的常見問法整理過一個(gè)對照區(qū)域存儲(chǔ)內(nèi)容典型異常程序計(jì)數(shù)器當(dāng)前線程執(zhí)行字節(jié)碼的行號(hào)指示器無異常虛擬機(jī)棧棧幀局部變量表、操作數(shù)棧、方法返回地址等StackOverflowError棧深度不足OutOfMemoryError申請?？臻g不足本地方法棧為native方法服務(wù)同虛擬機(jī)棧堆幾乎所有對象實(shí)例和數(shù)組OutOfMemoryError: Java heap space方法區(qū)/元空間類信息、常量、靜態(tài)變量、JIT緩存等OutOfMemoryError: Metaspace熱詞里有一個(gè)高頻報(bào)錯(cuò)java: outofmemoryerror: insufficient memory。實(shí)際中如果遇到這種提示先別急著眼花繚亂加堆內(nèi)存要看清楚是哪個(gè)區(qū)域的問題。如果是Java heap space優(yōu)先排查是否有大對象沒有釋放、一次性加載了過多數(shù)據(jù)、或者存在內(nèi)存泄漏如果是Metaspace優(yōu)先排查類加載器是否過多、動(dòng)態(tài)生成類是否過多。面試時(shí)能說出“先定位區(qū)域再調(diào)整參數(shù)”這個(gè)思路比只背-Xmx要加分很多。4.2 類加載過程與雙親委派機(jī)制類加載考得多的流程是加載、驗(yàn)證、準(zhǔn)備、解析、初始化。這五步里面“準(zhǔn)備”階段是最容易出概念的坑。準(zhǔn)備階段為類的靜態(tài)變量分配內(nèi)存并設(shè)置默認(rèn)值比如static int a 100在準(zhǔn)備階段a的值是0到初始化階段才會(huì)被賦值為100。但如果這個(gè)靜態(tài)變量是編譯期常量比如static final int b 100準(zhǔn)備階段就會(huì)直接賦值為100因?yàn)樗诰幾g期就寫入了ConstantValue屬性。雙親委派機(jī)制也屬于高頻簡答題。簡單說類加載器收到類加載請求后不會(huì)自己先去加載而是先委托給父類加載器一直向上委托到啟動(dòng)類加載器。只有父加載器無法加載時(shí)子加載器才會(huì)嘗試自己加載。這樣做的好處是保證核心類庫的加載一致性比如你寫一個(gè)java.lang.String類不管類加載器怎么加載最終都會(huì)由啟動(dòng)類加載器加載到rt.jar里的String避免核心類被篡改。筆試如果要你簡述把這三句話講清楚就夠拿分了。4.3 try-catch-finally的執(zhí)行順序與返回值陷阱異常板塊的代碼輸出題十有八九考finally?？聪旅孢@段代碼public static int test() { int i 0; try { return i; } finally { System.out.println(finally); } }方法返回什么答案是0。很多人答錯(cuò)是因?yàn)橐詾閕之后返回值會(huì)變成1。這里的關(guān)鍵是return i是先取i的當(dāng)前值0作為返回值然后才讓局部變量i自增為1。finally里的代碼會(huì)在方法返回前執(zhí)行但如果沒有在finally里return那么之前確定的返回值不會(huì)被改變。也就是說返回值的確定發(fā)生在finally執(zhí)行之前finally里你修改普通局部變量不是返回的那個(gè)值不會(huì)影響最終結(jié)果。但如果finally里也寫了return情況就不同了public static int test() { int i 0; try { return i; } finally { return 3; } }這時(shí)的返回值是3。因?yàn)閒inally中的return會(huì)覆蓋try中的return而且不推薦這樣寫因?yàn)闀?huì)造成返回結(jié)果難以預(yù)測代碼可讀性很差。面試題里出現(xiàn)這種代碼多半是考察你是否知道finally的優(yōu)先級和return的執(zhí)行時(shí)機(jī)。另外還要注意一點(diǎn)finally里的代碼也不是絕對會(huì)執(zhí)行比如在try里調(diào)用System.exit(0)會(huì)直接終止JVM或者發(fā)生死循環(huán)finally都不會(huì)被執(zhí)行到。4.4 受檢異常與非受檢異常throws和throw別混用異常體系的基礎(chǔ)題核心是區(qū)分受檢異常和非受檢異常。受檢異常是除了RuntimeException及其子類以外的Exception子類比如IOException、SQLException編譯器強(qiáng)制要求處理要么try-catch要么在方法簽名上聲明throws。非受檢異常是RuntimeException及其子類比如NullPointerException、ArrayIndexOutOfBoundsException編譯器不強(qiáng)制處理但程序運(yùn)行時(shí)如果發(fā)生了卻沒有捕獲線程會(huì)直接終止。筆試題里容易挖坑的是throws和throw的區(qū)別。throw是拋出異常對象用在方法體內(nèi)后面跟的是一個(gè)異常實(shí)例throw new RuntimeException(...)。throws是方法簽名的一部分聲明這個(gè)方法可能拋出哪些異常后面跟的是異常類型。比如public void readFile() throws IOException。注意如果一個(gè)方法聲明拋出受檢異常調(diào)用方要么處理要么繼續(xù)向上聲明編譯器會(huì)檢查這一點(diǎn)。非受檢異常則不需要一定聲明。理解了這兩點(diǎn)異常選擇題基本不會(huì)掉坑。5. 手寫算法冒泡排序和快速排序的考場正確姿勢5.1 冒泡排序理解交換邏輯比背模板重要用友這套筆試題的編程題手寫排序的概率很高冒泡是基礎(chǔ)中的基礎(chǔ)。冒泡排序的思路是每次比較相鄰兩個(gè)元素如果順序錯(cuò)誤就交換這樣每一輪下來最大值會(huì)像氣泡一樣“冒”到數(shù)組末尾。核心實(shí)現(xiàn)如下public static void bubbleSort(int[] arr) { if (arr null || arr.length 2) { return; } // 外層循環(huán)表示需要冒泡的輪數(shù) for (int i 0; i arr.length - 1; i) { boolean swapped false; // 內(nèi)層循環(huán)比較相鄰元素已排好的末尾元素可以不再參與 for (int j 0; j arr.length - 1 - i; j) { if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; swapped true; } } if (!swapped) { break; } } }這里的優(yōu)化點(diǎn)在于swapped標(biāo)志位如果某一輪內(nèi)層循環(huán)沒有任何交換說明數(shù)組已經(jīng)有序直接break提前結(jié)束。筆試時(shí)能寫出這個(gè)優(yōu)化說明你理解冒泡的本質(zhì)是“相鄰元素比較交換”而不是死記模板。冒泡排序時(shí)間復(fù)雜度是O(n2)最好情況下原數(shù)組有序優(yōu)化后能達(dá)到O(n)空間復(fù)雜度O(1)穩(wěn)定排序。5.2 快速排序邊界條件是手寫題最大的坑快速排序用Java實(shí)現(xiàn)也是高頻手寫題。它的核心思想是分治選一個(gè)基準(zhǔn)元素把數(shù)組分成小于等于基準(zhǔn)和大于等于基準(zhǔn)兩部分然后遞歸排序左右兩邊。常見寫法public static void quickSort(int[] arr, int left, int right) { if (left right) { return; } int pivot partition(arr, left, right); quickSort(arr, left, pivot - 1); quickSort(arr, pivot 1, right); } private static int partition(int[] arr, int left, int right) { // 默認(rèn)取最左邊的元素作為基準(zhǔn) int pivotValue arr[left]; int i left; int j right; while (i j) { // 從右往左找第一個(gè)小于基準(zhǔn)的元素 while (i j arr[j] pivotValue) { j--; } // 從左往右找第一個(gè)大于基準(zhǔn)的元素 while (i j arr[i] pivotValue) { i; } if (i j) { int tmp arr[i]; arr[i] arr[j]; arr[j] tmp; } } // 基準(zhǔn)歸位 arr[left] arr[i]; arr[i] pivotValue; return i; }寫這個(gè)代碼最容易錯(cuò)的地方是邊界條件。比如遞歸的終止條件是left right不是left right內(nèi)層兩個(gè)while循環(huán)里都必須再加i j條件否則可能會(huì)越界最后基準(zhǔn)歸位時(shí)要把基準(zhǔn)元素和arr[i]交換返回的i就是基準(zhǔn)元素在數(shù)組中的最終位置。這里建議在紙上跑一遍長度為5或6的數(shù)組把每一輪i、j變化寫出來比死記代碼有用得多。5.3 手寫題的追加追問復(fù)雜度和穩(wěn)定性面試官經(jīng)常會(huì)追問冒泡和快排的時(shí)間復(fù)雜度分別是多少穩(wěn)定嗎為什么冒泡時(shí)間復(fù)雜度平均和最壞都是O(n2)穩(wěn)定?？炫牌骄鵒(n log n)最壞O(n2)不穩(wěn)定?？炫诺淖顗那闆r其實(shí)是每次選擇的基準(zhǔn)都接近當(dāng)前序列的最大或最小值比如對已經(jīng)有序的數(shù)組固定取第一個(gè)元素作為基準(zhǔn)會(huì)退化成O(n2)。所以實(shí)際工程中會(huì)用三數(shù)取中法、隨機(jī)基準(zhǔn)等方式優(yōu)化。筆試和面試的手寫題并不是“代碼跑通就結(jié)束”你需要對復(fù)雜度推導(dǎo)有概念?？炫诺腛(n log n)可以這么簡單理解每一輪partition都要遍歷數(shù)組復(fù)雜度O(n)如果能穩(wěn)定地把數(shù)組對半分遞歸深度是log n層所以總體是O(n log n)。如果能說出“基準(zhǔn)選擇越均分性能越好”這一層就會(huì)讓面試官覺得你是真懂而不只是背了結(jié)論。5.4 白板編程的常見失誤清單結(jié)合我自己刷題和真實(shí)筆試踩過的坑手寫代碼最常犯的錯(cuò)誤有這幾個(gè)沒有判空。arr為null或長度為0/1時(shí)方法一進(jìn)來就空指針或越界。邊界條件差一。比如冒泡的arr.length - 1 - i少個(gè)-1就可能數(shù)組越界快排的left right寫成left right會(huì)漏掉單元素?cái)?shù)組的終止條件。交換變量時(shí)忘記用臨時(shí)變量或者用了位運(yùn)算結(jié)果寫錯(cuò)。內(nèi)層循環(huán)條件不收斂比如快排兩個(gè)內(nèi)層while沒有限制i j導(dǎo)致指針越界。寫完之后不檢查一遍特殊情況。如果筆試時(shí)間允許第一時(shí)間拿一個(gè)有序數(shù)組和一個(gè)逆序數(shù)組在腦子里跑一遍。很多低級錯(cuò)誤能被這個(gè)方法攔住。這個(gè)清單我每次刷題都會(huì)看一遍尤其快排這種分治遞歸的題邊界一旦出錯(cuò)整個(gè)代碼就是0分。6. 多線程與并發(fā)從創(chuàng)建線程到內(nèi)存可見性6.1 創(chuàng)建線程的幾種方式面試官真正想聽的是什么多線程板塊用友這套題里有一道簡答題創(chuàng)建線程有幾種方式常見答案通常是三種繼承Thread類、實(shí)現(xiàn)Runnable接口、實(shí)現(xiàn)Callable接口配合FutureTask。實(shí)際上更完整的答法是四種第四種是通過線程池提交任務(wù)。直接繼承Thread類的問題在于Java是單繼承你繼承了Thread就不能再繼承其他類職責(zé)上也不符合“把任務(wù)和線程分開”的思想。實(shí)現(xiàn)Runnable接口更靈活但Runnable的run方法沒有返回值也拋不出受檢異常。Callable接口的call方法有返回值配合FutureTask可以拿到異步執(zhí)行結(jié)果適合需要返回結(jié)果的場景。而線程池ThreadPoolExecutor是生產(chǎn)環(huán)境最推薦的創(chuàng)建方式因?yàn)樗軓?fù)用線程、控制并發(fā)數(shù)、管理生命周期。面試官問這個(gè)題不希望你只背三種方式更希望你最后落點(diǎn)到“生產(chǎn)環(huán)境用線程池”這個(gè)結(jié)論。簡單示例// 通過Callable FutureTask CallableInteger task () - { Thread.sleep(1000); return 42; }; FutureTaskInteger futureTask new FutureTask(task); new Thread(futureTask).start(); Integer result futureTask.get(); // 阻塞等待結(jié)果6.2 線程安全問題的本質(zhì)原子性、可見性、有序性線程安全的考題核心逃不出三個(gè)詞原子性、可見性、有序性。原子性說的是一個(gè)操作或多個(gè)操作要么全部執(zhí)行且不被打斷要么全部不執(zhí)行。比如i在字節(jié)碼層面不是一個(gè)原子操作它包含讀取i、加1、寫回三步多線程同時(shí)執(zhí)行就可能產(chǎn)生丟失更新。解決辦法是加鎖、使用原子類比如AtomicInteger或者用synchronized保證代碼塊的原子性?？梢娦哉f的是一個(gè)線程修改變量后其他線程能不能立刻看到。在多核CPU下線程可能把變量緩存到本地內(nèi)存沒有及時(shí)刷回主內(nèi)存導(dǎo)致其他線程讀到舊值。volatile關(guān)鍵字就是解決可見性的它能保證一個(gè)線程寫volatile變量后該變量會(huì)立即刷回主內(nèi)存并且其他線程讀到該變量時(shí)會(huì)失效本地緩存重新從主內(nèi)存加載。但volatile不能保證原子性典型例子是volatile int count多個(gè)線程執(zhí)行count依然會(huì)丟數(shù)據(jù)。有序性說的是編譯器和CPU為了優(yōu)化可能對指令重排多線程下重排可能導(dǎo)致不可預(yù)期的結(jié)果。內(nèi)存屏障是限制重排的手段synchronized和volatile在底層都會(huì)引入內(nèi)存屏障來約束重排序。筆試如果只要求選概念知道這三個(gè)詞的含義和各自對應(yīng)場景基本就夠用了但如果要深問就要能舉出雙重檢查鎖單例為什么用volatile修飾instance因?yàn)榉乐沟氖恰皩ο笠呀?jīng)分配內(nèi)存但還沒初始化完成”這類指令重排問題。6.3 synchronized與volatile什么時(shí)候用誰synchronized和volatile的對比在Java面試題里屬于必問。我用一個(gè)表來對比維度synchronizedvolatile作用保證原子性、可見性、有序性只保證可見性、有序性不保證原子性使用位置修飾方法或代碼塊修飾變量性能影響涉及鎖的競爭與釋放開銷較大比鎖輕量但也不能濫用適用場景多線程對共享變量進(jìn)行復(fù)合操作如累加、讀寫后修改讀多寫少、寫入新值不依賴舊值的場景如狀態(tài)標(biāo)志位一個(gè)經(jīng)典場景是控制線程停止private volatile boolean running true; public void stop() { running false; } public void run() { while (running) { // do something } }這里用volatile就足夠因?yàn)閞unning的寫入不依賴它當(dāng)前的值且不需要保證原子性如果用synchronized會(huì)顯得笨重性能也差。6.4 一道經(jīng)典多線程筆試題兩個(gè)線程交替打印1到100這套題的多線程編程題大概率會(huì)考“線程交替執(zhí)行”類。最典型的就是兩個(gè)線程交替打印1到100?？梢越柚鷖ynchronized wait/notify實(shí)現(xiàn)public class PrintNumber { private static int number 1; private static final Object lock new Object(); public static void main(String[] args) { Runnable task () - { while (true) { synchronized (lock) { if (number 100) { break; } System.out.println(Thread.currentThread().getName() : number); number; lock.notifyAll(); try { if (number 100) { lock.wait(); } } catch (InterruptedException e) { Thread.currentThread().interrupt(); } } } }; new Thread(task, 線程A).start(); new Thread(task, 線程B).start(); } }這里有幾個(gè)細(xì)節(jié)值得說明。第一wait()和notifyAll()必須在synchronized代碼塊內(nèi)使用否則會(huì)拋IllegalMonitorStateException。第二wait()會(huì)讓出鎖并進(jìn)入等待所以兩個(gè)線程能交替持有鎖。第三判斷number 100要放在while循環(huán)內(nèi)部并且在每輪喚醒后也要重新判斷否則可能打印出101。第四捕獲InterruptedException后務(wù)必恢復(fù)中斷狀態(tài)Thread.currentThread().interrupt()這是很多面試官會(huì)追問的細(xì)節(jié)。如果筆試要求更高還可以用LockSupport.park/unpark或者Semaphore實(shí)現(xiàn)但原理一致控制好線程的等待和喚醒時(shí)機(jī)。多線程編程題關(guān)鍵不在于把代碼寫得多炫而在于你能不能講清楚“為什么這樣寫是線程安全的”。復(fù)盤完這套題我自己最直觀的感覺是基礎(chǔ)不牢地動(dòng)山搖。很多題平時(shí)看答案解析覺得都會(huì)但真到閉卷手寫的時(shí)候每一個(gè)細(xì)節(jié)都會(huì)暴露出來。我自己踩過的坑是HashMap的擴(kuò)容條件記反了、finally里有return時(shí)覆蓋返回值這一點(diǎn)總是記不住、快排邊界第一遍寫錯(cuò)了。建議準(zhǔn)備秋招的同學(xué)可以按這套卷子的模塊做一張自測清單把每道題寫成帶“為什么”的筆記而不是只記答案。只要能做到拿到任何一道基礎(chǔ)題都能講出底層的鏈路筆試基本就穩(wěn)了。