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