Java TreeMap和HashMap区别对比

培训教学 潘老师 7个月前 (10-12) 150 ℃ (0) 扫码查看

在本教程中,我们将重点讨论TreeMap和HashMap之间的核心区别。

TreeMap和HashMap非常相似,它们都是实现了Map接口的集合。但它们也有一些区别,使其中一个在某些情况下更胜一筹。让我们来看看这些区别。

1.HashMap和TreeMap之间的区别

让我们讨论一些这两个映射之间的主要区别。

1.1. 类层次结构

HashMap类扩展了AbstractMap类并实现了Map接口,而TreeMap类扩展了AbstractMap类并实现了NavigableMap接口。

// HashMap类
public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable
// TreeMap类
public class TreeMap<K, V> extends AbstractMap<K, V> implements NavigableMap<K, V>, Cloneable, Serializable

1.2. 内部实现

  • HashMap在内部使用HashTable并基于散列的原理工作。它将桶存储为LinkedList的形式,当一个桶中的条目超过8个时,LinkedList将转换为平衡树(TreeNodes)。
  • TreeMap在内部使用红黑树,这是一种自平衡二叉搜索树。

1.3. 空键和空值

TreeMap不允许空键,但可以包含任意数量的空值。 HashMap允许一个空键(对于其他空键,现有值将被简单地用新值覆盖)以及任意数量的空值。

TreeMap<String, String> map = new TreeMap<>();
// 将null键放入TreeMap抛出NullPointerException
map.put(null, "value");  

TreeMap在内部使用compareTo()或Comparable和Comparator接口中的compare()方法来根据键来维护元素的顺序,对于空键,这些方法会引发’NullPointerException’异常。

1.4. 功能

与HashMap相比,TreeMap在功能上更丰富。除了Map接口的常规方法(get()、put()、remove())之外,它还包含了来自NavigableMap接口的方法,如pollFirstEntry()、pollLastEntry()、tailMap()、firstKey()、lastKey()等,而HashMap类没有这些方法。

//创建TreeMap
TreeMap<String, String> map = new TreeMap<>();
//存值
map.put("key1", "value1");
map.put("key2", "value2");
map.put("key3", "value3");
// 打印map
System.out.println(map);        // 输出 {key1=value1, key2=value2, key3=value3}
// 获取第一个key
System.out.println(map.firstKey());         // 输出 key1
//获取最后一个key
System.out.println(map.lastKey());           // 输出 key3
// 获取第一个键值对
System.out.println(map.firstEntry());       // 输出key1=value1
// 获取并移除最后一个键值对
System.out.println(map.pollLastEntry());     // 输出key3=value3
// 再次打印map
System.out.println(map);                          // 输出 {key1=value1, key2=value2}

1.5. 元素顺序

HashMap不维护元素的任何顺序,即它不会保证在Map迭代期间首先插入Map的元素将首先打印出来。 TreeMap按其键的排序顺序存储元素。排序可以是默认的自然排序顺序(数字的升序和字符串的字母顺序)或基于在Map创建期间指定的Comparator对象的自定义排序。

// 创建HashMap
HashMap<Integer, String> map = new HashMap<>();
// 存值
map.put(10, "value1");
map.put(2, "value2");
map.put(13, "value3");
map.put(5, "value4");
map.put(25, "value5");
// 打印 map
System.out.println(map);   //{2=value2, 5=value4, 25=value5, 10=value1, 13=value3}  - No ordering
// 使用常规的TreeMap()构造函数创建TreeMap,该构造函数对元素进行排序。
// 基于key的自然排序顺序
TreeMap<Integer, String> map = new TreeMap<>();
//存值
map.put(10, "value1");
map.put(2, "value2");
map.put(13, "value3");
map.put(5, "value4");
map.put(25, "value5");
//打印 map
System.out.println(map);  //{2=value2, 5=value4, 10=value1, 13=value3, 25=value5}
// 通过指定Comparator对象使用TreeMap(Comparator)构造函数创建TreeMap。
// 使用Lambda表达式作为自定义键排序的依据,创建TreeMap(Comparator)构造函数。
map = new TreeMap<Integer,String>((I1,I2) -> (I1<I2) ? 1 : (I1>I2) ? -1 : 0);
// 存值
map.put(10, "value1");
map.put(2, "value2");
map.put(13, "value3");
map.put(5, "value4");
map.put(25, "value5");
// 打印 map
System.out.println(map);  //{25=value5, 13=value3, 10=value1, 5=value4, 2=value2}

1.6. 性能比较

  • HashMap比TreeMap更快,对于最基本的操作(如get()、put()、contains()和remove())在最佳情况下提供了常数时间性能O(1),不会发生哈希冲突的情况。
  • 在发生哈希冲突的情况下(两个键具有相同的哈希码),HashMap通过使用LinkedList来存储冲突的元素来处理它,因此在这种情况下性能降低到O(n)。
  • 为了在哈希冲突时改善HashMap的性能,当一个桶中的条目数量超过8时,LinkedList会转化为平衡树,从而将最坏情况的性能从O(n)改善到O(log(n))。

另一方面,TreeMap对于大多数基本操作(如get()、put()、contains()和remove())提供O(log(n))的性能。

1.7. 内存使用

TreeMap在内存管理方面性能更好,因为它不在内部维护一个数组来存储键-值对。

在HashMap中,数组大小在初始化或调整大小时确定,通常大于实际需要的大小,这会浪费内存。而TreeMap没有这个问题。

1.8. 键搜索

HashMap在比较Map的键时使用hashCode()和equals()方法,而TreeMap在比较键时使用compareTo()或compare()方法。

// 创建HashMap
HashMap<Integer, String> hashMap = new HashMap<>();
// 存值
hashMap.put(10, "value1");
hashMap.put(10, "value2");
System.out.println("HashMap: " + hashMap);
// 创建 TreeMap
TreeMap<Integer, String> treeMap = new TreeMap<>();
// 存值
treeMap.put(10, "value1");
treeMap.put(10, "value2");
System.out.println("TreeMap: " + treeMap);

请注意程序输出:

OutputHashMap: {10=value2}
TreeMap: {10=value2}

尽管两种情况的输出相同,但在内部,HashMap在比较键时使用equals(),因此拒绝了第二个键,因为它是重复的。而TreeMap在比较键时使用compareTo(),从而拒绝了第二个键。

此外,这两个映射都更新了先前的条目,Map里只有一个条目。

2.何时使用HashMap和TreeMap

如果需要按排序顺序添加元素(键-值对),我们应该使用TreeMap。让我们以创建一个按字母顺序排列的词典为例。因此,我们可以轻松使用TreeMap来实现这一点。

TreeMap在内存使用方面更加高效,因此在不确定要存储的元素数量时,它是一个良好的映射实现。

HashMap是更通用的映射实现,可以在不需要对数据进行排序的情况下使用,条目可以以任何顺序或序列维护。在高性能应用程序中,我们可以优先使用HashMap而不是TreeMap,因为与TreeMap相比,它的性能更好。

3.结论

在本文中,我们看到了HashMap和TreeMap之间的一些关键区别,以及在使用它们时可以根据哪些因素来做出决定。


版权声明:本站文章,如无说明,均为本站原创,转载请注明文章来源。如有侵权,请联系博主删除。
本文链接:https://www.panziye.com/teach/9452.html
喜欢 (0)
请潘老师喝杯Coffee吧!】
分享 (0)
用户头像
发表我的评论
取消评论
表情 贴图 签到 代码

Hi,您需要填写昵称和邮箱!

  • 昵称【必填】
  • 邮箱【必填】
  • 网址【可选】