Dart SplayTreeMap
最后修改于 2025 年 4 月 4 日
在 Dart 中，SplayTreeMap 是一种自平衡二叉搜索树，它以排序顺序维护条目。它提供了高效的查找、插入和删除操作。
SplayTreeMap 实现了 Map 接口，并根据键的自然顺序或自定义比较器对键进行排序。它会自动重组自身以优化访问模式。
创建 SplayTreeMap
创建 SplayTreeMap 的最简单方法是使用构造函数。条目会根据键自动排序。
main.dart
import 'dart:collection';
void main() {
var scores = SplayTreeMap<String, int>();
scores['Bob'] = 85;
scores['Alice'] = 90;
scores['Charlie'] = 95;
print(scores);
}
我们创建一个 SplayTreeMap 来存储姓名-分数对。键将按升序自动排序。请注意，插入顺序不影响最终顺序。
$ dart main.dart
{Alice: 90, Bob: 85, Charlie: 95}
使用比较器进行自定义排序
我们可以提供一个自定义比较器来定义键的排序顺序。
main.dart
import 'dart:collection';
void main() {
var products = SplayTreeMap<String, double>(
(a, b) => b.compareTo(a) // Sort in descending order
);
products['Laptop'] = 999.99;
products['Mouse'] = 19.99;
products['Keyboard'] = 49.99;
print(products);
}
比较器函数会颠倒字符串的自然顺序。这将导致产品按字母顺序从 Z 排到 A。
$ dart main.dart
{Mouse: 19.99, Laptop: 999.99, Keyboard: 49.99}
访问第一个和最后一个元素
由于 SplayTreeMap 的排序特性，它可以高效地访问其第一个和最后一个元素。
main.dart
import 'dart:collection';
void main() {
var temperatures = SplayTreeMap<DateTime, double>();
temperatures[DateTime(2023, 1, 15)] = -5.2;
temperatures[DateTime(2023, 1, 10)] = -8.1;
temperatures[DateTime(2023, 1, 20)] = 2.4;
print('First date: ${temperatures.firstKey()}');
print('Last date: ${temperatures.lastKey()}');
print('Lowest temp: ${temperatures[temperatures.firstKey()]}');
print('Highest temp: ${temperatures[temperatures.lastKey()]}');
}
我们使用日期作为键来存储温度读数。firstKey 和 lastKey 方法可以高效地为我们提供最早和最晚的日期。
$ dart main.dart First date: 2023-01-10 00:00:00.000 Last date: 2023-01-20 00:00:00.000 Lowest temp: -8.1 Highest temp: 2.4
范围操作
SplayTreeMap 支持使用 from、to 和 between 操作进行高效的范围查询。
main.dart
import 'dart:collection';
void main() {
var studentGrades = SplayTreeMap<int, String>();
studentGrades[101] = 'A';
studentGrades[102] = 'B';
studentGrades[103] = 'C';
studentGrades[104] = 'A';
studentGrades[105] = 'B';
print('Grades from ID 102:');
print(studentGrades.from(102));
print('\nGrades between 102 and 104:');
print(studentGrades.range(102, 104));
}
我们可以根据键范围高效地检索地图的子集。from 方法获取从指定键开始的所有条目，而 range 方法获取两个键之间的条目。
$ dart main.dart
Grades from ID 102:
{102: B, 103: C, 104: A, 105: B}
Grades between 102 and 104:
{102: B, 103: C}
通过 splaying 进行性能优化
SplayTreeMap 会自动将频繁访问的元素移近根节点，以加快访问速度。
main.dart
import 'dart:collection';
void main() {
var cache = SplayTreeMap<String, String>();
// Initial population
for (var i = 0; i < 100; i++) {
cache['key$i'] = 'value$i';
}
// Access pattern - frequent access to key42
for (var i = 0; i < 1000; i++) {
var value = cache['key42']; // This access becomes faster over time
if (i % 100 == 0) {
print('Accessed key42 ${i + 1} times');
}
}
}
splaying 行为优化了对常用键的访问。经过多次访问后，“key42”将位于树的根附近，以便更快地查找。
$ dart main.dart Accessed key42 1 times Accessed key42 101 times Accessed key42 201 times Accessed key42 301 times Accessed key42 401 times Accessed key42 501 times Accessed key42 601 times Accessed key42 701 times Accessed key42 801 times Accessed key42 901 times
最佳实践
- 排序数据：当需要按键排序数据时使用。
- 访问模式：非常适合访问分布不均匀的情况。
- 比较器：提供一个用于自定义排序逻辑。
- 键类型：确保键是可比较的，或者提供比较器。
来源
本教程涵盖了 Dart 的 SplayTreeMap，并通过实际示例演示了其作为有序键值集合的关键特性和用法。
作者
列出 所有 Dart 教程。