如果您正在阅读本文,您很可能熟悉 Map 接口以及可以适当应用的位置。如果没有,那就来这里。今天我们将讨论 Java TreeMap 实现的特点,更具体地说,它与 HashMap 有何不同以及如何正确使用它。
通过实现NavigableMap和SortedMap接口,TreeMap 获得了 HashMap 所没有的额外功能,但它在性能方面付出了代价。还有LinkedHashMapclass ,它还允许您以特定顺序存储数据(将数据添加到地图的顺序)。要了解这三个类之间的差异,请查看此表:
如您所见,这些类有很多共同点,但也有一些不同之处。虽然 TreeMap 类是最通用的,但它不能总是将null存储为键。此外,访问 TreeMap 的元素花费的时间最长。因此,如果您不需要按某种排序顺序存储数据,最好使用HashMap或LinkedHashMap。
搜索元素从树的根开始,在我们的例子中是 61。然后我们将节点值与我们要查找的值进行比较。如果我们的价值较小,那么我们就往左走;如果它更大,那么我们就往右走。重复此过程,直到我们找到所需的值或遇到值为null的元素(树的叶子)。红色和黑色用于简化树的导航和平衡。构建红黑树时必须始终遵守以下规则:
目前为止就这样了!我希望您现在已经清楚 TreeMap 类,并希望您在解决实际编码任务时正确应用它。
比较 TreeMap、HashMap 和 LinkedHashMap
Map 接口最常用的实现是 HashMap。它易于使用并保证快速访问数据,因此它是解决大多数问题的最佳选择。大多数,但不是全部。有时您需要以结构化方式存储数据并能够在其中导航。在这种情况下,Map 接口的另一个实现 (TreeMap) 可以派上用场。TreeMap 实现了NavigableMap接口,它继承了SortedMap,而 SortedMap 又继承了 Map 接口。
哈希表 | 链表 | 树图 | |
---|---|---|---|
数据排序 | 随机的。不能保证订单会随着时间的推移而维持。 | 按照添加数据的顺序 | 按升序或基于指定的比较器 |
时间复杂度 | O(1) | O(1) | O(日志(n)) |
实现接口 | 地图 | 地图 | NavigableMap SortedMap 地图 |
数据结构 | 水桶 | 水桶 | 红黑树 |
支持空键吗? | 是的 | 是的 | 是的,如果您使用比较器,则允许 null |
线程安全? | 不 | 不 | 不 |
红黑树
您可能注意到,在幕后,TreeMap 使用一种称为红黑树的数据结构。以这种结构存储数据正是提供数据排序的原因。那么这是什么树呢?让我们弄清楚!想象一下,您需要存储数字-字符串对。数字 16、20、52、55、61、65、71、76、81、85、90、93 和 101 将成为密钥。如果将数据存储在传统列表中,并且需要查找键为 101 的元素,则需要逐步遍历所有 13 个元素才能找到它。对于 13 个元素,这没什么大不了的,但是当处理一百万个元素时,我们就会遇到大问题。为了解决这些问题,程序员使用稍微复杂一点的数据结构。这就是红黑树出场的地方!
- 根必须是黑色的。
- 树的叶子必须是黑色的。
- 一个红色节点必须有两个黑色子节点。
- 黑色节点可以有任何颜色的子节点。
- 从节点到其叶子的路径必须包含相同数量的黑色节点。
- 新节点被添加到叶子中。
来自 SortedMap 和 NavigableMap 接口的方法
和HashMap一样,TreeMap实现了Map接口,也就是说TreeMap拥有HashMap存在的所有方法。但是 TreeMap 还实现了SortedMap和NavigableMap接口,因此从中获得了额外的功能。SortedMap是一个扩展Map并添加与排序数据集相关的方法的接口:- firstKey():返回地图中第一个元素的键
- lastKey():返回最后一个元素的键
- headMap(K end) : 返回一个包含当前地图所有元素的地图,从开始到键为end的元素
- tailMap(K start):返回一个包含当前地图所有元素的地图,从开始元素到结束
- subMap(K start, K end):返回一个包含当前地图所有元素的地图,从开始元素到以end为键的元素。
- firstEntry():返回第一个键值对
- lastEntry():返回最后一个键值对
- pollFirstEntry():返回并删除第一对
- pollLastEntry():返回并删除最后一对
- ceilingKey(K obj):返回大于或等于键obj的最小键k。如果没有这样的键,则返回 null
- floorKey(K obj):返回小于或等于键obj的最大键k。如果没有这样的键,则返回 null
- lowerKey(K obj):返回小于键obj的最大键k。如果没有这样的键,则返回 null
- higherKey(K obj):返回比键obj大的最小键k。如果没有这样的键,则返回 null
- ceilingEntry(K obj):类似于ceilingKey(K obj)方法,只返回一个键值对(或null)
- floorEntry(K obj):类似于floorKey(K obj)方法,只返回一个键值对(或null)
- lowerEntry(K obj):类似于lowerKey(K obj)方法,只返回一个键值对(或null)
- higherEntry(K obj):类似于higherKey(K obj)方法,只返回一个键值对(或null)
- descendingKeySet():返回一个 NavigableSet,其中包含以相反顺序排序的所有键
- descendingMap():返回一个 NavigableMap 包含所有以相反顺序排序的对
- navigableKeySet():返回一个 NavigableSet 对象,其中包含按存储顺序排列的所有键
- headMap(K upperBound, boolean incl):返回包含从开始到 upperBound 元素的对的映射。incl参数表示返回的map中是否包含upperBound元素
- tailMap(K lowerBound, boolean incl) : 功能类似于之前的方法,只返回从 lowerBound 到末尾的对
- subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl):与前面的方法一样,返回从 lowerBound 到 upperBound 的对;参数 lowIncl 和 highIncl 指示是否在新地图中包含边界元素。
树图的例子
大量的额外方法似乎是不必要的,但事实证明它们比您乍看之下要有用得多。让我们一起探讨以下示例。想象一下,我们在一家大公司的营销部门工作,我们有一个数据库,其中包含我们要向其展示广告的人员。有两个细节需要记住:- 我们需要跟踪每个人的印象数
- 向未成年人展示广告的算法不同。
public class Person {
public String firstName;
public String lastName;
public int age;
public Person(String firstName, String lastName, int age) {
this.firstName = firstName;
this.lastName = lastName;
this.age = age;
}
}
我们在主类 中实现逻辑:
import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
TreeMap<Person, Integer> map = new TreeMap<>(Comparator.comparingInt(o -> o.age));
map.put(new Person("John", "Smith", 17), 0);
map.put(new Person("Ivan", "Petrenko", 65), 0);
map.put(new Person("Pedro", "Escobar", 32), 0);
map.put(new Person("Shirley", "Hatfield", 14), 0);
map.put(new Person("Abby", "Parsons", 19), 0);
Person firstAdultPerson = map.navigableKeySet().stream().filter(person -> person.age>18).findFirst().get();
Map<Person, Integer> youngPeopleMap = map.headMap(firstAdultPerson, false);
Map<Person, Integer> adultPeopleMap = map.tailMap(firstAdultPerson, true);
showAdvertisementToYoung(youngPeopleMap);
showAdvertisementToAdult(adultPeopleMap);
}
public static void showAdvertisementToYoung(Map map) {}
public static void showAdvertisementToAdult(Map map) {}
}
在Main类中,创建一个TreeMap,其中每个key代表一个具体的人,每个value是这个月的广告展示次数。我们向构造函数传递一个按年龄对人进行排序的比较器。我们用任意值填充地图。现在我们想在我们的小数据存储库中获取对第一个成年人的引用。我们使用 Stream API 来做到这一点。然后我们得到两个单独的地图,我们将其传递给显示广告的方法。我们可以通过多种方式完成这项任务。TreeMap 类的方法库使我们能够为各种需要创建自定义解决方案。您不需要全部记住它们,因为您始终可以使用 IDE 中的文档或提示。 为了巩固您所学的知识,我们建议您观看我们的 Java 课程中的视频课程
GO TO FULL VERSION