面试：如何决定使用 HashMap 还是 TreeMap？

落日映苍穹つ 2022-12-19 01:29 83阅读 0赞

点击上方“java大数据修炼之道”,选择“设为星标”

优质文章和精品资源, 第一时间送达![format_png][]

关注公众号后台回复**资源**获取实战教学资料+视频

来源：我是程序汪

**问：如何决定使用 HashMap 还是 TreeMap？**

介绍

`TreeMap<K,V>`的Key值是要求实现`java.lang.Comparable`，所以迭代的时候TreeMap默认是按照Key值升序排序的；TreeMap的实现是基于红黑树结构。适用于按自然顺序或自定义顺序遍历键（key）。

`HashMap<K,V>`的Key值实现散列`hashCode()`，分布是散列的、均匀的，不支持排序；数据结构主要是桶(数组)，链表或红黑树。适用于在Map中插入、删除和定位元素。

结论

如果你需要得到一个有序的结果时就应该使用TreeMap（因为HashMap中元素的排列顺序是不固定的）。除此之外，由于HashMap有更好的性能，所以大多不需要排序的时候我们会使用HashMap。

拓展

**1、HashMap 和 TreeMap 的实现**

**HashMap：** 基于哈希表实现。使用HashMap要求添加的键类明确定义了`hashCode()`和`equals()`\[可以重写`hashCode()`和`equals()`\]，为了优化HashMap空间的使用，您可以调优初始容量和负载因子。

*  HashMap(): 构建一个空的哈希映像
 *  HashMap(Map m): 构建一个哈希映像，并且添加映像m的所有映射
 *  HashMap(int initialCapacity): 构建一个拥有特定容量的空的哈希映像
 *  HashMap(int initialCapacity, float loadFactor): 构建一个拥有特定容量和加载因子的空的哈希映像

**TreeMap：** 基于红黑树实现。TreeMap没有调优选项，因为该树总处于平衡状态。

*  TreeMap()：构建一个空的映像树
 *  TreeMap(Map m): 构建一个映像树，并且添加映像m中所有元素
 *  TreeMap(Comparator c): 构建一个映像树，并且使用特定的比较器对关键字进行排序
 *  TreeMap(SortedMap s): 构建一个映像树，添加映像树s中所有映射，并且使用与有序映像s相同的比较器排序

**2、HashMap 和 TreeMap 都是非线程安全**

HashMap继承AbstractMap抽象类，TreeMap继承自SortedMap接口。

**AbstractMap抽象类：** 覆盖了equals()和hashCode()方法以确保两个相等映射返回相同的哈希码。如果两个映射大小相等、包含同样的键且每个键在这两个映射中对应的值都相同，则这两个映射相等。映射的哈希码是映射元素哈希码的总和，其中每个元素是Map.Entry接口的一个实现。因此，不论映射内部顺序如何，两个相等映射会报告相同的哈希码。

**SortedMap接口：** 它用来保持键的有序顺序。SortedMap接口为映像的视图(子集)，包括两个端点提供了访问方法。除了排序是作用于映射的键以外，处理SortedMap和处理SortedSet一样。添加到SortedMap实现类的元素必须实现Comparable接口，否则您必须给它的构造函数提供一个Comparator接口的实现。TreeMap类是它的唯一一个实现。

**3、TreeMap中默认是按照升序进行排序的，如何让他降序**

通过自定义的比较器来实现

定义一个比较器类，实现Comparator接口，重写compare方法，有两个参数，这两个参数通过调用compareTo进行比较，而compareTo默认规则是：

>  *  如果参数字符串等于此字符串，则返回 0 值；
>  *  如果此字符串小于字符串参数，则返回一个小于 0 的值；
>  *  如果此字符串大于字符串参数，则返回一个大于 0 的值。

自定义比较器时，在返回时多添加了个负号，就将比较的结果以相反的形式返回，代码如下：

static class MyComparator implements Comparator{
        @Override
        public int compare(Object o1, Object o2) {
            // TODO Auto-generated method stub
            String param1 = (String)o1;
            String param2 = (String)o2;
            return -param1.compareTo(param2);
        }
    }

之后，通过MyComparator类初始化一个比较器实例，将其作为参数传进TreeMap的构造方法中：

MyComparator comparator = new MyComparator();
    
    
    Map<String,String> map = new TreeMap<String,String>(comparator);

这样，我们就可以使用自定义的比较器实现降序了

public class MapTest {
    
    
        public static void main(String[] args) {
            //初始化自定义比较器
            MyComparator comparator = new MyComparator();
            //初始化一个map集合
            Map<String,String> map = new TreeMap<String,String>(comparator);
            //存入数据
            map.put("a", "a");
            map.put("b", "b");
            map.put("f", "f");
            map.put("d", "d");
            map.put("c", "c");
            map.put("g", "g");
            //遍历输出
            Iterator iterator = map.keySet().iterator();
            while(iterator.hasNext()){
                String key = (String)iterator.next();
                System.out.println(map.get(key));
            }
        }
    
    
        static class MyComparator implements Comparator{
    
    
            @Override
            public int compare(Object o1, Object o2) {
                // TODO Auto-generated method stub
                String param1 = (String)o1;
                String param2 = (String)o2;
                return -param1.compareTo(param2);
            }
    
    
        }
    
    
    }

![1e9a61c1795464632dfac98891d82d81.png][]

欢迎关注“Java大数据修炼之道”，我们分享最有价值的Java的干货文章，助力您成为有思想的Java开发工程师！

**推荐阅读：**

1、[项目中常用的19条MySQL优化][19_MySQL]

2、[必须收藏！SpringBoot注解大全][SpringBoot]

3、[最新SQL数据库面试题以及答案！][SQL]

4、[面试官：来说说单点登录的三种实现方式][Link 1]

5、[老板要求用java将word转为PDF，这么搞？][java_word_PDF]

6、[吐血整理！14个Spring MVC顶级技巧！][14_Spring MVC]

7、[MySQL：互联网公司常用分库分表方案汇总][MySQL]

8、[卧槽，为什么volatile关键字保证不了线程安全啊][volatile]

9、[这21个刁钻HashMap面试题，我把阿里面试官吊打了！][21_HashMap]

10、[Spring Boot “内存泄漏”？看看美团大牛是如何排查的][Spring Boot]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1NjYxMTcx_size_16_color_FFFFFF_t_70][]

[format_png]: /images/20221120/a2a49461dd9c4af6b20062fe0a16e9dd.png
[1e9a61c1795464632dfac98891d82d81.png]: /images/20221120/e855d6c0966d43239005dfa7aa10f82d.png
[19_MySQL]: http://mp.weixin.qq.com/s?__biz=MzU1NjczNTM5NQ==&mid=2247492315&idx=1&sn=37c6888e30892c7fae56d0769c35a571&chksm=fbc22c17ccb5a501df41ddeaecf0f7e85e292b45d6c7522e4d6a4d9c4a93a389338ee175eae8&scene=21#wechat_redirect
[SpringBoot]: http://mp.weixin.qq.com/s?__biz=MzU1NjczNTM5NQ==&mid=2247493234&idx=1&sn=2c1164a6660993e4c9d42cc972235885&chksm=fbc228beccb5a1a8eee97316c21121d8b19125491464c3f2fab82c35fb47ba80299421a9e54e&scene=21#wechat_redirect
[SQL]: http://mp.weixin.qq.com/s?__biz=MzU1NjczNTM5NQ==&mid=2247493386&idx=1&sn=6014e7fb6c2a43ca8df3b011754fa4e1&chksm=fbc229c6ccb5a0d068fdce76d8e457510c9c43e866952a917ae63ee0f1da8c5c25bd5d3879a2&scene=21#wechat_redirect
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzU1NjczNTM5NQ==&mid=2247493492&idx=1&sn=cd0a9b65387d5107fe9d0e1ded268d22&chksm=fbc229b8ccb5a0ae5f433e40aeb031d462bc825b837ca9e09720b6b58439dada694eeb54bbaf&scene=21#wechat_redirect
[java_word_PDF]: http://mp.weixin.qq.com/s?__biz=MzU1NjczNTM5NQ==&mid=2247492363&idx=1&sn=6975a1a5de92dc49d04654f21ffa7c21&chksm=fbc22dc7ccb5a4d1b94f2a9bbce26082c9f845fbbf7d588a5540d072bcef39b2281d0b705f91&scene=21#wechat_redirect
[14_Spring MVC]: http://mp.weixin.qq.com/s?__biz=MzU1NjczNTM5NQ==&mid=2247493345&idx=1&sn=edde6ca39a12c08acdab32c03e66369e&chksm=fbc2282dccb5a13bb7010d0ba909b021a92c4530bdd515e1449893f1f589bb903915626f15ac&scene=21#wechat_redirect
[MySQL]: http://mp.weixin.qq.com/s?__biz=MzU1NjczNTM5NQ==&mid=2247493296&idx=1&sn=d3d9f8bb4d12555f870297ab3c7564e2&chksm=fbc2287cccb5a16a527c08f0d620b4a61a2af45634c895cee2f0d49907684000b43d43973ec6&scene=21#wechat_redirect
[volatile]: http://mp.weixin.qq.com/s?__biz=MzU1NjczNTM5NQ==&mid=2247492809&idx=1&sn=47c50b227f8063129ed09edc91449100&chksm=fbc22a05ccb5a31383ee13bb6c58f8c12dada691c16624e028f23f24c32d1e4201b4ebd1a354&scene=21#wechat_redirect
[21_HashMap]: http://mp.weixin.qq.com/s?__biz=MzU1NjczNTM5NQ==&mid=2247490277&idx=1&sn=63d44db7ae6930f25478119f423227d4&chksm=fbc1d429ccb65d3fc4be6ab008e4318d3beeccb1394801c72e33cbb9fd162868dce2b9b0c0f2&scene=21#wechat_redirect
[Spring Boot]: http://mp.weixin.qq.com/s?__biz=MzU1NjczNTM5NQ==&mid=2247493061&idx=1&sn=059d8dcf396bb5a4627d47ff4caa2b4f&chksm=fbc22b09ccb5a21f763789682341712c81e967d31949e2ee4d9161f348839c69fbf9d5aab7f2&scene=21#wechat_redirect
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1NjYxMTcx_size_16_color_FFFFFF_t_70]: /images/20221120/0695a537349d43a2b0cc06dbf0c67d67.png