大家好，我是小米，一個(gè)喜歡分享技術(shù)的 29 歲程序員。這次，我想跟大家聊聊我前不久在一次 Java 社招面試中遇到的一道題：“如何決定使用 HashMap 還是 TreeMap？”面試官一個(gè)問題丟過來，我還沒開口，腦子里就開始狂飆內(nèi)存了！

那天面試是在一家金融科技公司。面試官坐在對(duì)面，一臉溫和地說：“小米，我們經(jīng)常在實(shí)際開發(fā)中需要選擇合適的數(shù)據(jù)結(jié)構(gòu)。你能說說在什么情況下會(huì)選擇 HashMap，什么時(shí)候會(huì)用 TreeMap 嗎？”

第一步：了解背景，找到切入點(diǎn)

既然是面試題，咱們先從基礎(chǔ)聊起，確保邏輯清晰、全面鋪墊。

1. 什么是 HashMap？

HashMap 是 Java 中基于哈希表實(shí)現(xiàn)的鍵值對(duì)存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)。它的特性是：

• 查找/插入性能快：時(shí)間復(fù)雜度是 O(1)（哈希沖突少時(shí)）。
• 無序存儲(chǔ)：它不保證元素的順序。
• 允許一個(gè) null 鍵和多個(gè) null 值。

2. 什么是 TreeMap？

TreeMap 是基于紅黑樹實(shí)現(xiàn)的鍵值對(duì)存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)，特性如下：

• 鍵是有序的：默認(rèn)按自然順序排序，或者按 Comparator 提供的順序排序。
• 查找/插入性能較慢：時(shí)間復(fù)雜度為 O(log n)。
• 不允許 null 鍵，但允許多個(gè) null 值。

小米思考

我一邊在腦海中快速?gòu)?fù)習(xí)知識(shí)點(diǎn)，一邊腦補(bǔ)了兩個(gè)典型的使用場(chǎng)景。為了讓面試官“驚喜”，我決定邊講邊結(jié)合實(shí)際案例。

第二步：從性能說開，找到“速度與順序”的平衡點(diǎn)

“小米，具體舉個(gè)例子吧?！泵嬖嚬偬崾疚?。

“好嘞！”我先拋出兩個(gè)問題，“你是想要快速查找元素呢，還是需要保證數(shù)據(jù)的有序性？”

如果性能是第一要義，比如需要頻繁查詢數(shù)據(jù)，而對(duì)順序沒要求，HashMap 是首選。它利用哈希表直接定位到存儲(chǔ)位置，插入和查找效率都非常高。

案例 1：電商購(gòu)物車的實(shí)現(xiàn)

購(gòu)物車是電商系統(tǒng)中最常見的功能。

用戶把商品加入購(gòu)物車，通常以商品 ID 作為鍵，商品信息作為值存儲(chǔ)。此時(shí)：

• 查詢效率至關(guān)重要，因?yàn)橛脩綦S時(shí)可能查看購(gòu)物車中的商品。
• 不關(guān)心商品的順序，只需要快速響應(yīng)即可。

用代碼簡(jiǎn)單表示一下：

圖片

“小米，那 TreeMap 就沒用了嗎？”面試官追問。

“當(dāng)然不是！”我馬上補(bǔ)充，“TreeMap 的最大優(yōu)勢(shì)在于數(shù)據(jù)有序性?！?/p>

案例 2：排行榜功能的實(shí)現(xiàn)

假設(shè)你要實(shí)現(xiàn)一個(gè)簡(jiǎn)單的在線游戲排行榜，按玩家分?jǐn)?shù)從低到高排列。此時(shí)，TreeMap 是再合適不過的選擇：

• TreeMap 默認(rèn)按照鍵的順序存儲(chǔ)數(shù)據(jù)，天然支持有序性。
• 紅黑樹的結(jié)構(gòu)使得插入和查找的效率在 O(log n) 的范圍內(nèi)。

以下是代碼示例：

圖片

結(jié)果輸出：

圖片

第三步：深挖需求，結(jié)合業(yè)務(wù)細(xì)節(jié)

講完性能和順序，我又主動(dòng)提到了內(nèi)存和線程安全問題。

“在實(shí)際開發(fā)中，我們還需要根據(jù)項(xiàng)目需求選擇，比如：”

1. HashMap 是不是線程安全？HashMap 在多線程環(huán)境下可能導(dǎo)致數(shù)據(jù)不一致。為了線程安全，可以使用 Collections.synchronizedMap() 或 ConcurrentHashMap。

2. TreeMap 是否占用更多內(nèi)存？由于 TreeMap 的底層是紅黑樹，它會(huì)存儲(chǔ)額外的樹節(jié)點(diǎn)結(jié)構(gòu)，相較于 HashMap 占用稍多的內(nèi)存。如果你的數(shù)據(jù)量特別大、對(duì)有序性要求較低，HashMap 會(huì)更高效。

第四步：加點(diǎn)料，讓回答更“靈活”

“面試官，其實(shí) HashMap 和 TreeMap 也能一起用！”我給出了第三種答案。

案例 3：分區(qū)處理大數(shù)據(jù)

如果需要快速定位分區(qū)，同時(shí)保證分區(qū)內(nèi)的數(shù)據(jù)有序，可以結(jié)合 HashMap 和 TreeMap：

• 用 HashMap 存儲(chǔ)分區(qū)的映射關(guān)系。
• 每個(gè)分區(qū)使用 TreeMap 維護(hù)有序的數(shù)據(jù)。

代碼示例：

圖片

總結(jié)：如何選擇？

我看著面試官，最后總結(jié)了一句：“其實(shí)選擇 HashMap 還是 TreeMap，關(guān)鍵在于性能與順序的取舍。如果需要快速查詢，選 HashMap；如果需要保證順序，選 TreeMap?！?/p>

面試官點(diǎn)了點(diǎn)頭，笑著說：“很不錯(cuò)！”