很多剛開始刷牛客的同學(xué)都會卡在“集合類”和“Map”這兩節(jié)說實話這不怪大家。前面學(xué)的變量、循環(huán)、數(shù)組都是“單打獨斗”到了集合和Map這兒突然冒出來一堆接口、實現(xiàn)類、方法名光是ArrayList和LinkedList怎么選就夠糾結(jié)半天。這篇文章我就以帶刷第42、43題為例把集合類和Map的考點、底層邏輯、常用方法一次講透讓零基礎(chǔ)的同學(xué)也能直接上手寫題。如果你是那種“數(shù)組還沒玩明白就被扔到HashMap源碼里”的初學(xué)者或者你正在刷?？偷腏ava入門題看到“集合類”“Map”這兩個標(biāo)題就頭大那這篇文章就是給你準(zhǔn)備的。我會用最直白的話拆解底層原理再帶著你一行一行把題目代碼寫出來。文章里所有的代碼都是我按實際刷題場景寫的調(diào)試過、能跑你直接跟著敲就行。1. 為什么集合類和Map是刷題路上的分水嶺數(shù)組能存一組數(shù)但數(shù)組的長度一旦確定就不能變了。日常寫代碼的時候你根本不知道用戶會輸入多少條數(shù)據(jù)這時候就必須用集合。集合類的出現(xiàn)本質(zhì)上就是解決“數(shù)量不確定”和“操作復(fù)雜”這兩個痛點。而Map解決的是另一個問題——“按名字找東西”。數(shù)組按下標(biāo)找Map按key找這兩種查找模型幾乎是所有后續(xù)編程的基石。?？桶鸭项惡蚆ap放在第42、43題位置非常講究。前面的題讓你用數(shù)組、循環(huán)、字符串把語法基礎(chǔ)打牢到這里就開始考驗?zāi)恪坝檬裁慈萜餮b數(shù)據(jù)”的抽象能力。這兩題過了你才能無障礙地去看后面各種算法題因為算法題里幾乎無處不在地用集合和Map做輔助。所以這兩題刷明白意義不只是過了兩道題而是你從“寫代碼”跨越到“設(shè)計代碼”的起點。另外這兩題也特別適合用來熟悉IDE的自動補全和API查找。我自己帶學(xué)生的時候發(fā)現(xiàn)很多人寫集合類代碼方法名全靠背背不住就卡住。實際上集合類的方法名非常規(guī)律比如“添加”是add“刪除”是remove“判斷有沒有”是contains“拿長度”是size你只要記住這一套規(guī)律再用IDE補全一提示基本就能順下來。刷這兩題的價值就是把這一套規(guī)律刻進肌肉記憶。提示?？瓦@類平臺刷題時環(huán)境不帶IDE自動補全有的帶有的不帶所以方法名最好在本地IDE里練熟再去平臺提交。2. 動手寫題之前先把集合框架的地圖鋪開2.1 List家族ArrayList和LinkedList別選錯List是一個接口它的語義是“有序、可重復(fù)”的序列。所謂有序就是元素按插入順序排列你放進a、b、c取出來就是a、b、c?？芍貜?fù)就是說同一個元素可以出現(xiàn)兩次比如存兩個“hello”沒問題。List最常見的兩個實現(xiàn)是ArrayList和LinkedList。ArrayList底層是數(shù)組查詢快、改也快但是中間插入和刪除慢因為要搬移后面的元素。LinkedList底層是雙向鏈表兩頭操作特別快但中間查找慢。刷入門題的時候你只需要記住一個默認(rèn)選擇拿不準(zhǔn)就用ArrayList因為大部分場景下數(shù)組搬移的開銷可以忽略而鏈表每次get某個下標(biāo)都要從頭遍歷寫起來還容易迷糊。import java.util.ArrayList; import java.util.List; public class ListDemo { public static void main(String[] args) { ListString list new ArrayList(); list.add(Java); // 尾部添加 list.add(集合); list.add(Map); System.out.println(list.size()); // 3 System.out.println(list.get(0)); // Java數(shù)組按下標(biāo)拿快 list.remove(1); // 刪除下標(biāo)1的“集合” System.out.println(list.contains(Map)); // true遍歷找 } }這段代碼里的size()、get()、remove()、contains()是你刷題時最常用的方法。注意list.remove(1)和list.remove(Java)不一樣一個是按下標(biāo)刪一個是按元素刪。初學(xué)者最容易在這里踩坑后面我會專門說。2.2 Set家族去重這件事底層是哈希Set的語義只有一句話不允許重復(fù)元素。為什么不允許重復(fù)因為它底層就是Map你沒看錯HashSet本質(zhì)就是一個HashMap的殼元素被放進Set時是被當(dāng)作Map的key存進去的。Map的key天然不能重復(fù)所以Set也就不能重復(fù)了。判斷重復(fù)的標(biāo)準(zhǔn)是hashCode和equals先算hashCode定位到桶如果桶里有元素再用equals逐個比較。你如果自己定義了一個類放進HashSet卻不重寫hashCode和equals那兩個“內(nèi)容一樣”的對象也會被當(dāng)成不同元素。這是后面SE階段的重難點刷牛客題階段通常用不到自定義對象但原理你得知道不然看到“HashSet為何去重失敗”的討論會一頭霧水。Set有三個常用實現(xiàn)HashSet無序去重最快LinkedHashSet按插入順序去重TreeSet按自然順序或比較器排序去重刷題場景里如果你要“去重排序”一個TreeSet直接搞定如果你只想去重不在意順序HashSet就夠了。2.3 Map的核心邏輯key-value的查找表Map不是Collection體系的一員它有自己獨立的接口體系。Collection存單個元素Map存的是“鍵值對”。你可以把Map想成一本字典key是詞條value是釋義。查的時候你給一個key它直接告訴你value是多少。這個查找過程如果底層是HashMap那平均就是O(1)級別的非常快。HashMap的底層是數(shù)組鏈表紅黑樹。put一個鍵值對時先算key的hashCode再經(jīng)過擾動函數(shù)散列到數(shù)組下標(biāo)該位置為空就直接放不為空就掛在鏈表后面鏈表太長超過8且數(shù)組長度夠超過64就轉(zhuǎn)成紅黑樹。get的時候同樣算hash找到桶然后在鏈表或紅黑樹里用equals找key。刷基礎(chǔ)題階段你不需要把紅黑樹背下來但你必須理解一個核心點Map是拿key來找value。所以如果你的需求是“統(tǒng)計每個字符出現(xiàn)了幾次”字符是key、次數(shù)是value這個模型瞬間就清晰了。如果你要“記錄學(xué)號和姓名”學(xué)號是key、姓名是value也是一樣的道理。Map常用的實現(xiàn)有HashMap、LinkedHashMap、TreeMap、Hashtable。刷題最常用的是HashMap默認(rèn)無序、查得快需要按key排序時用TreeMap需要按插入順序遍歷時用LinkedHashMap。Hashtable是老古董線程安全但是慢而且不允許null鍵null值不用管它。3. 第42題手把手拆解集合類操作與去重排序3.1 題面考點分析我?guī)⒌臅r候拿到的題目版本大概是這樣的從鍵盤輸入若干個整數(shù)以某個結(jié)束符結(jié)束要求用集合類完成“去重 升序輸出”。這道題的核心考點有三個集合類的選擇、輸入處理、集合遍歷輸出。很多初學(xué)者一上來就數(shù)組硬剛先數(shù)有幾個數(shù)再建數(shù)組再去重再排序……可以是可以但代碼量非常大而且容易出錯。這道題就是逼你轉(zhuǎn)換思維容器不是只能選數(shù)組Set本身就能去重TreeSet順便還能排序你只需要把元素往里面一丟所有臟活累活它都替你干了。這就是刷題的意義——見識到工具本身的力量。3.2 我寫的參考代碼import java.util.Scanner; import java.util.TreeSet; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); TreeSetInteger set new TreeSet(); while (sc.hasNextInt()) { int num sc.nextInt(); set.add(num); } for (Integer val : set) { System.out.print(val ); } sc.close(); } }你沒看錯核心代碼就這么幾行。樹結(jié)構(gòu)幫你排序Set語義幫你去重遍歷輸出就完事了。讀數(shù)據(jù)用的是hasNextInt()也就是“只要還有整數(shù)就一直讀”這不依賴你事先知道有多少個數(shù)也不依賴結(jié)束符自動化判題程序會自動幫你模擬輸入結(jié)束。3.3 關(guān)鍵方法逐行詳解先說TreeSet的add()方法。前面說了TreeSet底層是TreeMap而TreeMap底層是一棵紅黑樹。每次add時元素會被插入到樹中合適的位置樹的中序遍歷本身就是有序的。所以add完所有元素后你直接用foreach遍歷拿到的就是升序序列。TreeSet內(nèi)部會自動調(diào)用元素的compareTo方法比較大小Integer已經(jīng)實現(xiàn)了這個接口所以不用你手動寫比較器。hasNextInt()是Scanner里一個非常實用的方法。它的工作方式是先阻塞等待輸入有數(shù)據(jù)時返回true沒數(shù)據(jù)時返回false。在牛客這種自動判題環(huán)境里輸入管道關(guān)閉后hasNextInt()會自動返回false循環(huán)自動退出不需要你寫什么“輸入0結(jié)束”之類的邏輯。這個細(xì)節(jié)很多新手不知道以為循環(huán)會卡住實際不會。foreach循環(huán)本質(zhì)上是編譯器幫你調(diào)用了迭代器。TreeSet的迭代器按照紅黑樹的中序遍歷順序返回元素所以輸出天然有序。這里要注意一個細(xì)節(jié)foreach里你不能remove元素否則會拋ConcurrentModificationException。如果你要在遍歷時刪除元素得用迭代器自己的remove方法。不過這種去重排序場景用不到刪除知道有這么回事就行。3.4 新手最容易寫錯的兩個地方第一個坑是類型寫錯。有人寫TreeSet 這是語法錯誤。Java泛型不支持基本類型必須用包裝類Integer。int和Integer之間會自動裝箱拆箱add(num)里num是int自動變成Integer對象取出來的時候foreach里的val是Integer還能直接參與運算。這個過程看起來“透明”但你要知道背后發(fā)生了裝箱拆箱不然遇到null時你根本不知道為什么會空指針。第二個坑是錯用HashSet。HashSet也能去重但它是無序的如果你直接用HashSet存完就輸出順序是亂的。加上排序還得再Collections.sort(new ArrayList(set))白折騰一圈。所以遇到“去重排序”這種題腦子里的第一反應(yīng)應(yīng)該是TreeSet而不是HashSet。這個直覺很重要刷題多了你會發(fā)現(xiàn)很多題目考的就是你對“哪個容器最適合當(dāng)前場景”的判斷力。注意TreeSet存儲自定義對象時如果沒實現(xiàn)Comparable接口add方法直接拋ClassCastException。所以以后你用TreeSet裝自己的類時記得要么實現(xiàn)Comparable要么在new TreeSet時傳一個比較器Comparator。4. 第43題手把手拆解Map的統(tǒng)計與遍歷4.1 為什么一看到“統(tǒng)計次數(shù)”就應(yīng)該是Map如果題目說“統(tǒng)計一串字符中每個字符出現(xiàn)的次數(shù)”80%的正確答案都要用到Map。原因很簡單統(tǒng)計次數(shù)的本質(zhì)是建立“字符-次數(shù)”的映射關(guān)系。你來一個字符我就得去查一下“這個字符之前出現(xiàn)過沒”出現(xiàn)過就把次數(shù)加一沒出現(xiàn)過就放進Map并初始化成1。這不正是Map的key查value的應(yīng)用場景嗎有人可能會想用兩個數(shù)組一個存字符一個存次數(shù)也能做啊。能是可以但數(shù)組的index是整數(shù)字符不能直接當(dāng)下標(biāo)你得先想辦法把每個字符映射成一個唯一的整數(shù)還得處理范圍問題。Map直接幫你把key定為字符類型value定為Integer比兩個數(shù)組的做法簡潔得多也更不容易寫出邊界bug。這就是為什么我總說Map不是高級技巧它是你腦子里該有的第一反應(yīng)。4.2 完整參考代碼字符計數(shù)import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); String line sc.nextLine(); MapCharacter, Integer map new HashMap(); for (int i 0; i line.length(); i) { char c line.charAt(i); if (c ) { continue; // 跳過空格題目一般只統(tǒng)計可見字符 } map.put(c, map.getOrDefault(c, 0) 1); } for (Map.EntryCharacter, Integer entry : map.entrySet()) { System.out.println(entry.getKey() entry.getValue()); } } }核心就是map.put(c, map.getOrDefault(c, 0) 1)這一行。它的邏輯如果c已經(jīng)在Map里getOrDefault返回當(dāng)前次數(shù)加一后覆蓋回去如果c不在Map里getOrDefault返回默認(rèn)值0加一變成1put進去。一句話完成“判斷存在與否 更新計數(shù)”這就是Map處理統(tǒng)計問題最舒服的姿勢。4.3 getOrDefault、put、entrySet這些方法都在干嘛put()是所有Map實現(xiàn)都必須有的核心方法。調(diào)用put(key, value)時HashMap先算key的hashCode定位到數(shù)組下標(biāo)然后執(zhí)行“插入或覆蓋”的操作如果下標(biāo)處沒有元素直接放入如果有元素且key相等equals判斷就用新value覆蓋舊value并返回舊value如果有元素但key不等說明哈希碰撞了就掛到鏈表后面或插入紅黑樹。getOrDefault(key, defaultVal)是一個看起來簡單但極其實用的方法。它的語義是如果Map里有這個key返回對應(yīng)的value沒有返回defaultVal。這個方法在刷題里簡直是無價之寶因為統(tǒng)計場景里“沒有出現(xiàn)過0次”這件事太常見了沒有它你就得先containsKey判斷再get再put要寫三行代碼。有它一行搞定。entrySet()返回的是Map.Entry對象的Set視圖。每個Map.Entry代表一個鍵值對有g(shù)etKey()和getValue()兩個方法。用foreach遍歷entrySet是遍歷Map最常用的方式因為它同時拿到key和value不需要再多查一次。如果你只需要key可以遍歷keySet()只遍歷value就用values()。這三個方法組合起來基本覆蓋了Map遍歷的所有場景。4.4 遍歷Map的幾種姿勢對比我直接給你一個表格對比你自己感受一下差異遍歷方式寫法適合場景注意事項entrySet()for (Map.EntryK,V e : map.entrySet())同時需要key和value最常用性能也好keySet() get()for (K k : map.keySet())只需要key或者要按key取valuevalue在循環(huán)里單獨查一次多一次hashvalues()for (V v : map.values())只需要value拿不到keyforEach(Java 8)map.forEach((k, v) - {...})函數(shù)式風(fēng)格需要lambda基礎(chǔ)我的建議是前三種你必須手寫熟練因為有些面試筆試環(huán)境不讓你用太新的語法而且手寫一遍能強化你對Map結(jié)構(gòu)的記憶。forEach留到你學(xué)完lambda再用初期不要強行秀操作。另外如果你遍歷TreeMap這三種方式返回的順序都會按key的自然順序排好版這點和HashMap不一樣判斷“要不要輸出順序”時選對實現(xiàn)類就行。5. 刷這兩題最容易踩的坑我?guī)湍闾崆芭诺?.1 泛型基礎(chǔ)類型寫錯的崩潰瞬間我見過太多次這個報錯Type argument cannot be of primitive type。就是你寫了ArrayList 或者HashMapchar, Integer。Java泛型必須是引用類型int要寫成Integerchar要寫成Character。初學(xué)者經(jīng)常抱怨“為什么這么設(shè)計”很簡單泛型要支持Object的方法基本類型不是Object沒法統(tǒng)一處理。后面你會接觸到基本類型專用集合比如IntList但現(xiàn)在你只需要記住集合和Map一律用包裝類。在你寫完代碼后最好主動檢查一遍所有尖括號里的類型是不是包裝類這個習(xí)慣能省很多編譯錯誤。5.2 remove方法的重載歧義List的remove有兩個重載remove(int index)和remove(Object o)。當(dāng)你寫list.remove(2)時編譯器會優(yōu)先匹配remove(int)所以它刪的是下標(biāo)為2的元素而不是值為2的元素。如果你有一個List 想刪掉值為2的元素你必須寫list.remove(Integer.valueOf(2))。這是Java API設(shè)計里一個著名的坑?？驮u論區(qū)幾乎每過幾期就有人問。刷題的時候如果發(fā)現(xiàn)“刪錯了”先往這個方向想。5.3 遍歷時刪除元素導(dǎo)致并發(fā)修改異常剛才提過foreach遍歷集合時刪除元素會拋ConcurrentModificationException。原理是集合內(nèi)部有個modCount修改次數(shù)計數(shù)器迭代器在創(chuàng)建時會記住這個值每次next()之前都會檢查當(dāng)前modCount和預(yù)期值是否一致不一致就拋異常。你可能會問那我真要在遍歷時刪除怎么辦答案是使用迭代器Iterator自己IteratorInteger it list.iterator(); while (it.hasNext()) { Integer val it.next(); if (val 3) { it.remove(); // 安全刪除它會把modCount同步一致 } }這個方法在后面的算法題里會頻繁碰到比如“刪除鏈表中所有等于某個值的節(jié)點”。提前把這套規(guī)則理解透會少掉很多頭發(fā)。5.4 HashMap和Hashtable別搞混面試八股文里有一道經(jīng)典題HashMap和Hashtable的區(qū)別。刷題階段你只需要記住HashMap允許key和value為nullHashtable不允許HashMap是線程不安全的但性能好單線程刷題沒問題Hashtable是線程安全的但方法都加了鎖性能差現(xiàn)在基本被淘汰了。選擇題如果看到“線程安全且效率高”這種選項那是在釣魚因為效率和線程安全往往是矛盾的?，F(xiàn)在的官方推薦是如果需要線程安全用ConcurrentHashMap而不是Hashtable。5.5 輸出格式要求牛客的判題系統(tǒng)對輸出格式有嚴(yán)格檢查尤其是“多余空格”。比如要求輸出“1 2 3”你輸出“1 2 3 ”末尾多一個空格有些判題系統(tǒng)能過有些判題系統(tǒng)就判錯。我建議你養(yǎng)成一個好習(xí)慣用StringBuilder或一個標(biāo)志位來控制空格不要無腦在循環(huán)里拼“元素空格”。這是我刷題踩過很多次后的經(jīng)驗看起來是小問題實際浪費的時間非常多。StringBuilder sb new StringBuilder(); for (Integer val : set) { if (sb.length() 0) { sb.append( ); } sb.append(val); } System.out.println(sb);這種寫法不會有多余空格也方便你在拼完字符串后進一步處理比直接在循環(huán)里打印要靈活得多。6. 刷完這兩題以后我建議你這樣繼續(xù)練6.1 動手把每個實現(xiàn)類都跑一遍你剛學(xué)的TreeSet、HashMap最好別只在牛客上用。我建議你回到本地IDE新建一個測試類把ArrayList、LinkedList、HashSet、TreeSet、HashMap、TreeMap這六個類全部new一遍。每個類都執(zhí)行一遍添加、刪除、查詢、遍歷用debug模式看一眼里面的結(jié)構(gòu)。尤其是HashMap你把斷點打在put方法上能看到它怎么計算hash、怎么找桶、怎么掛鏈表這個印象比讀十遍文章都深刻。6.2 做兩道綜合題鞏固一下?？蜕嫌胁簧倬C合題比如“統(tǒng)計一個英文句子中不同單詞的數(shù)量”或“尋找數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字”。前者用Set和Map結(jié)合后者只用Map就能解。這些題目會逼著你把集合類和Map串起來用比孤立刷題效果更好。做的時候先停下來想一想“這道題我應(yīng)該用List還是Set還是Map”想對容器再動手這是最重要的解題步驟。6.3 看一遍集合類的繼承結(jié)構(gòu)圖不需要背但你要能畫出這樣一條鏈路Iterable - Collection - List/Set/Queue然后List下面有ArrayList/LinkedList/VectorSet下面有HashSet/LinkedHashSet/TreeSetMap是獨立接口下面有HashMap/LinkedHashMap/TreeMap。這張圖能幫你建立“接口-實現(xiàn)類”的坐標(biāo)系以后看到任何一個類你都能立刻說出它屬于哪個陣營、有什么特點。說白了集合框架的重點不是背方法而是建立坐標(biāo)系方法的使用反而水到渠成。6.4 形成一個自己的“容器選擇清單”根據(jù)我自己的經(jīng)驗等你做過的題足夠多你會自然形成一套“選容器”的條件反射。我在這分享我的版本給你參考需要存一串元素且允許重復(fù)ArrayList需要頻繁在頭部或中間增刪LinkedList雖然筆試很少考這個不允許重復(fù)且不管順序HashSet不允許重復(fù)且要排序TreeSet不允許重復(fù)但要保持插入順序LinkedHashSet需要鍵值映射、不在意順序HashMap需要鍵值映射、按鍵排序TreeMap需要鍵值映射、按插入順序遍歷LinkedHashMap這套清單不是標(biāo)準(zhǔn)答案但它能幫你在看到題目需求的第一時間下意識地選到合適的容器。有了這個慣性你后面刷各種算法題都會輕松很多。最后再分享一個帶刷過程中我反復(fù)跟學(xué)生強調(diào)的體會集合類和Map這部分內(nèi)容初學(xué)的時候感覺像在背一堆API但其實它們背后全都是很樸素的數(shù)據(jù)結(jié)構(gòu)思想。數(shù)組、鏈表、哈希、樹這些聽起來“高大上”的詞落到日常寫代碼里就是“我該選哪個容器”。你只要親自把這些容器一個個new出來、調(diào)試、用debug看內(nèi)部變化很快就能建立屬于自己的手感。刷題這件事不怕慢就怕不親自動手拆。希望這篇帶刷能幫你跨過這個坎繼續(xù)往后刷的時候你會發(fā)現(xiàn)自己寫代碼的思路清晰了不止一個檔次。