章
目
录
在本教程中,我们将重点讨论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之间的一些关键区别,以及在使用它们时可以根据哪些因素来做出决定。