驚呆面試官的回答：HashMap和TreeMap的區(qū)別
? 前幾天，有一位粉絲在直播間問(wèn)了我這樣一個(gè)問(wèn)題，說(shuō)HashMap和TreeMap有什么區(qū)別。今天，我給大家分享一下我的理解。
1、兩者區(qū)別
我們知道不管是HashMap還是TreeMap，都是通過(guò)對(duì)象來(lái)對(duì)對(duì)象進(jìn)行索引的Map集合。我們把用來(lái)索引的對(duì)象叫做Key，而索引對(duì)應(yīng)的對(duì)象叫做Value。這就是我們平時(shí)說(shuō)的鍵值對(duì)。它們的類關(guān)系如圖所示：
關(guān)于HashMap和TreeMap的區(qū)別，我從以下4個(gè)方面來(lái)分析：
1）數(shù)據(jù)結(jié)構(gòu)方面
HashMap是基于哈希表+數(shù)組來(lái)實(shí)現(xiàn)的，而TreeMap是基于紅黑樹實(shí)現(xiàn)的。
使用HashMap需要鍵對(duì)象明確定義了hashCode()和equals()這兩個(gè)方法，而且為了優(yōu)化HashMap空間的使用，可以調(diào)整初始容量大小和擴(kuò)容。
TreeMap沒(méi)有大小設(shè)置選項(xiàng)，因?yàn)?，紅黑樹結(jié)構(gòu)總是處于平衡狀態(tài)。
2）效率方面
HashMap比TreeMap的性能更高。
HashMap的時(shí)間復(fù)雜度是O（1），它是通過(guò)哈希函數(shù)計(jì)算的哈希地址。
而TreeMap主要是保證數(shù)據(jù)平衡，時(shí)間復(fù)雜度是O（log2 n）。
3）線程安全方面
HashMap和TreeMap都是非線程安全的。
如果在多線程并發(fā)情況下建議使用ConcurrentHashMap；
如果既要保證線程安全又要保證順序，可以使用 Collections.synchronizedMap()方法轉(zhuǎn)化為線程安全的集合。
4）應(yīng)用場(chǎng)景方面
HashMap是無(wú)序的，而TreeMap是有序的。
TreeMap適用于按自然順序或自定義順序遍歷鍵的場(chǎng)景。
HashMap適用于在Map中插入、刪除和定位元素。
日常開發(fā)建議多使用HashMap，只有在需要排序的時(shí)候才使用TreeMap。
2、總結(jié)
最后，我把HashMap和TreeMap的更多詳細(xì)區(qū)別，都整理在這張表中了，需要的小伙伴可以在我的個(gè)人主頁(yè)中獲取。
基礎(chǔ) | 哈希圖 | 樹狀圖 |
Definition | HashMap是基于哈希表的Map接口實(shí)現(xiàn)。 | TreeMap是Map接口的基于Tree結(jié)構(gòu)的實(shí)現(xiàn)。 |
Interface Implements | HashMap實(shí)現(xiàn)Map, Cloneable和Serializable接口。 | TreeMap實(shí)現(xiàn)NavigableMap, Cloneable和Serializable接口。 |
空鍵/值 | HashMap允許單個(gè)null鍵和多個(gè)null值。 | TreeMap不允許使用空鍵, 但可以具有多個(gè)空值。 |
同質(zhì)/異質(zhì) | HashMap允許異構(gòu)元素, 因?yàn)樗粚?duì)鍵執(zhí)行排序。 | 由于排序, TreeMap允許將齊次值作為鍵。 |
Performance | HashMap比TreeMap更快, 因?yàn)樗鼮橹T如get()和put()之類的基本操作提供了O（1）的恒定時(shí)間性能。 | 與HashMap相比, TreeMap速度較慢, 因?yàn)樗鼮榇蠖鄶?shù)操作（如add(), remove()和contains()）提供O（log（n））的性能。 |
數(shù)據(jù)結(jié)構(gòu) | HashMap類使用哈希表。 | TreeMap在內(nèi)部使用Red-Black樹, 這是一種自平衡二進(jìn)制搜索樹。 |
Comparison Method | 它使用Object類的equals()方法比較鍵。Map類的equals()方法將其覆蓋。 | 它使用compareTo()方法比較鍵。 |
Functionality | HashMap類僅包含諸如get(), put(), KeySet()等基本功能。 | TreeMap類具有豐富的功能, 因?yàn)樗缦鹿δ埽簍ailMap(), firstKey(), lastKey(), pollFirstEntry(), pollLastEntry()。 |
元素順序 | HashMap不維護(hù)任何順序。 | 元素以自然順序（升序）排序。 |
Uses | 當(dāng)我們不需要按排序順序的鍵值對(duì)時(shí), 應(yīng)使用HashMap。 | 當(dāng)我們需要按排序（升序）順序的鍵值對(duì)時(shí), 應(yīng)使用TreeMap |
好了，以上就是我對(duì)HashMap和TreeMap的理解。
