## 说明 [`BTreeMap`](https://doc.rust-lang.org/std/collections/struct.BTreeMap.html) 是基于 **B 树（Balanced Tree）** 数据结构实现的有序键值对集合 **特点**： - 有序存储：所有键（`K`）按升序排列，满足 `Ord` trait - 自平衡树：每个节点包含多个键值对，保持树高度平衡（查询效率稳定） - 范围查询：支持高效的范围遍历（`range`）和前缀匹配 - 内存友好：数据按顺序存储，缓存命中率高于 `HashMap` **适用场景**： 1. 需要有序遍历 - 排行榜系统：按分数排序玩家数据 - 时间序列数据：按时间戳顺序存储日志/事件 - 字典序处理：按字母顺序处理字符串键 2. 高频范围查询 - 区间统计：统计某段时间内的订单数量 - 前缀搜索：查找以特定字符串开头的键 3. 内存敏感场景 - 嵌入式开发：避免哈希表的内存碎片问题 - 大数据量存储：更紧凑的内存布局 4. 键无法高效哈希 - 复杂结构键：当键的哈希计算成本较高时（如多层嵌套结构） ## 常用 `API` ### 创建相关 #### `new` 创建 ##### 说明通过 `new` 方法创建一个空的 `BTreeMap`, 不会自行分配任何内容 ```rust pub const fn new() -> BTreeMap ``` ##### EG ```rust use std::collections::BTreeMap; fn main() { // 创建空 BTreeMap（类型推断） let mut map = BTreeMap::new(); } ``` #### `new` 创建 ##### 说明通过 `new` 方法创建一个空的 `BTreeMap`, 不会自行分配任何内容 ```rust pub const fn new() -> BTreeMap ``` ##### EG ```rust use std::collections::BTreeMap; fn main() { // 创建空 BTreeMap（类型推断） let mut map = BTreeMap::new(); } ``` ### 修改删除相关 #### `insert` 插入 ##### 说明通过 `insert` 方法向 `BTreeMap` 插入 `key,value` 若 `BTreeMap` 中不存在 `key`，则返回 `None` 若 `BTreeMap` 中存在 `key`，则会更新 `Value`，并且返回旧值 ```rust pub fn insert(&mut self, key: K, value: V) -> Option where K: Ord, ``` ##### EG ```rust use std::collections::BTreeMap; let mut map = BTreeMap::new(); assert_eq!(map.insert(37, "a"), None); assert_eq!(map.is_empty(), false); map.insert(37, "b"); assert_eq!(map.insert(37, "c"), Some("b")); assert_eq!(map[&37], "c"); ``` #### `entry` ##### 说明获取给定 `key` 对应的项，以进行”检查-插入“模式的原子操作，避免多次哈希查找常搭配以下方法使用 - `or_insert`：方法在键对应的值存在时就返回这个值的可变引用，如果不存在则将参数作为新值插入并返回新值的可变引用 - `and_modify`：用于对已存在的键值对进行原地修改 - `key`：通过`entry`获取对应项后再掉用此方法即可获取对应键的引用 ```rust pub fn entry(&mut self, key: K) -> Entry<'_, K, V, A> where K: Ord, ``` ##### EG ```rust use std::collections::BTreeMap; let mut map = BTreeMap::new(); assert_eq!(map.insert(37, "a"), None); assert_eq!(map.is_empty(), false); map.insert(37, "b"); assert_eq!(map.insert(37, "c"), Some("b")); assert_eq!(map[&37], "c"); ``` #### `split_off` 分割 ##### 说明在指定的 `key` 处分割 `BTreeMap`，并返回包含 `key` 在内的后续 `map`。若 `key` 不存在则返回 `{}` ##### EG ```rust fn main() { let mut a = BTreeMap::new(); a.insert(1, "a"); a.insert(2, "b"); a.insert(3, "c"); a.insert(17, "d"); a.insert(41, "e"); let b = a.split_off(&3); println!("{:?}", b); } // {3: "c", 17: "d", 41: "e"} ``` #### `append` 合并 ##### 说明合并其他数据，此操作转移所有权， ```rust pub fn append(&mut self, other: &mut BTreeMap) where K: Ord, A: Clone, ``` ##### EG ```rust use std::collections::BTreeMap; fn main() { let mut a = BTreeMap::new(); a.insert(1, "a"); a.insert(2, "b"); a.insert(3, "c"); let mut b = BTreeMap::new(); b.insert(3, "d"); b.insert(4, "e"); b.insert(5, "f"); println!("s map a: {:?}", a); // s map a: {1: "a", 2: "b", 3: "c"} println!("s map b: {:?}", b); // s map b: {3: "d", 4: "e", 5: "f"} a.append(&mut b); println!("e map a: {:?}", a); // e map a: {1: "a", 2: "b", 3: "d", 4: "e", 5: "f"} println!("e map b: {:?}", b); // e map b: {} } ``` #### `remove` 删除 ##### 说明删除 `BTreeMap` 中的 `key`，如果 `key` 存在则返回旧值否则返回 `None` ```rust pub fn remove(&mut self, key: &Q) -> Option where K: Borrow + Ord, Q: Ord + ?Sized, ``` ##### EG ```rust use std::collections::BTreeMap; let mut map = BTreeMap::new(); map.insert(1, "a"); assert_eq!(map.remove(&1), Some("a")); assert_eq!(map.remove(&1), None); ``` #### `retain` ##### 说明根据闭包逻辑保留元素（只保留闭包返回 `true` 的元素） ```rust pub fn retain(&mut self, f: F) where K: Ord, F: FnMut(&K, &mut V) -> bool, ``` ##### EG ```rust use std::collections::BTreeMap; fn main() { let mut map: BTreeMap = (0..8).map(|x| (x, x*10)).collect(); println!("s map a: {:?}", map);//s map a: {0: 0, 1: 10, 2: 20, 3: 30, 4: 40, 5: 50, 6: 60, 7: 70} map.retain(|&k, _| k % 2 == 0); println!("e map b: {:?}", map);//e map b: {0: 0, 2: 20, 4: 40, 6: 60} } ``` #### `clear` 清空 ##### 说明清空所有元素，但保留已分配的内存容量 ```rust pub fn clear(&mut self) ``` ##### EG ```rust use std::collections::BTreeMap; fn main() { let mut map: BTreeMap = (0..8).map(|x| (x, x*10)).collect(); println!("s map a: {:?}", map.len());//s map a: 8 map.clear(); println!("e map b: {:?}", map.len());//e map b: 0 } ``` ### 查询取值相关 #### `get` 取值 ##### 说明返回当前 `key` 对应值的不可变引用, 不存在则返回 `None` ```rust pub fn get(&self, key: &Q) -> Option<&V> where K: Borrow + Ord, Q: Ord + ?Sized, ``` ##### EG ```rust use std::collections::BTreeMap; let mut map = BTreeMap::new(); map.insert(1, "a"); assert_eq!(map.get(&1), Some(&"a")); assert_eq!(map.get(&2), None); ``` #### `get_mut` ##### 说明返回当前 `key` 对应值的可变引用, 不存在则返回 `None` ```rust pub fn get_mut(&mut self, key: &Q) -> Option<&mut V> where K: Borrow + Ord, Q: Ord + ?Sized, ``` ##### EG ```rust use std::collections::BTreeMap; fn main() { let mut map = BTreeMap::new(); map.insert(1, "a"); if let Some(x) = map.get_mut(&1) { *x = "b"; } println!("{:?}",map.get(&1)); // Some("b") } ``` #### `extend` ##### 说明从一个迭代器中批量插入数据, 此操作会转移数据所有权 > 使用场景：合并两个 `Map`，或者将数组 `Vec` 转入 `Map` ```rust impl<'a, K, V, A> Extend<(&'a K, &'a V)> for BTreeMap where K: Ord + Copy, V: Copy, A: Allocator + Clone, ``` ##### EG ```rust use std::collections::BTreeMap; fn main() { let mut map = BTreeMap::new(); map.insert(1, "a"); let another_map = vec![(2, "b"), (3, "c")]; map.extend(another_map); // 批量拷入 println!("map: {:?}",map); // map: {1: "a", 2: "b", 3: "c"} } ``` #### `range` 范围查询 ##### 说明 `range(min..max)` 将生成从 `min`（包含）到 `max`（不包含）的元素。范围也可以以 (`Bound, Bound`) 的形式输入，例如，`range((Excluded(4), Included(10))) ` 将生成从 `4 ` 到 `10` 的左不包含、右包含的范围。 `panic` 情况： - 范围起始值大于结束值时引发 `panic` - 范围起始值等于结束值且两个边界均被排除时引发 `panic` ##### EG ```rust use std::collections::BTreeMap; use std::ops::Bound::Included; fn main() { let mut map = BTreeMap::new(); map.insert(3, "a"); map.insert(5, "b"); map.insert(8, "c"); for (&key, &value) in map.range((Included(&4), Included(&8))) { println!("{key}: {value}"); } assert_eq!(Some((&5, &"b")), map.range(4..).next()); } /** 5: b 8: c **/ ``` #### `contains_key` 检查存在值 ##### 说明检查 `BtreeMap` 中是否包含指定 `key`，存在则返回 `true`，反之返回 `false` ```rust pub fn contains_key(&self, key: &Q) -> bool where K: Borrow + Ord, Q: Ord + ?Sized, ``` ##### EG ```rust use std::collections::BTreeMap; fn main() { let mut map = BTreeMap::new(); map.insert(1, "a"); assert_eq!(map.contains_key(&1), true); assert_eq!(map.contains_key(&2), false); } ``` ### 遍历循环 #### keys和values ##### 说明 `keys`: 获取 `BtreeMap` 的 `key` 构成的迭代器，按 `key` 排序 `values`：获取 `BtreeMap` 的 `value` 构成的迭代器，按 `key` 排序 ##### EG ```rust use std::collections::BTreeMap; fn main() { let mut a = BTreeMap::new(); a.insert(2, "b"); a.insert(1, "a"); let keys: Vec<_> = a.keys().cloned().collect(); assert_eq!(keys, [1, 2]); let values: Vec<&str> = a.values().cloned().collect(); assert_eq!(values, ["a", "b"]); } ``` #### `Iter` ##### 说明获取 `map` 的只读迭代 `(&K, &V)`，按照 `key` 排序 ```rust pub fn iter(&self) -> Iter<'_, K, V> impl<'a, K, V> Iterator for Iter<'a, K, V> where K: 'a, V: 'a, type Item = (&'a K, &'a V); ``` ##### EG ```rust use std::collections::BTreeMap; fn main() { let mut map = BTreeMap::new(); map.insert(3, "c"); map.insert(2, "b"); map.insert(1, "a"); for (key, value) in map.iter() { println!("{key}: {value}"); } } /* 1: a 2: b 3: c */ ``` #### `Iter` ##### 说明获取 `map` 的只读迭代 `(&K, &V)`，按照 `key` 排序 ```rust pub fn iter_mut(&mut self) -> IterMut<'_, K, V> impl<'a, K, V> Iterator for IterMut<'a, K, V> type Item = (&'a K, &'a mut V); ``` ##### EG ```rust use std::collections::BTreeMap; fn main() { let mut map = BTreeMap::new(); map.insert("a", 1); map.insert("b", 2); map.insert("c", 3); println!("s map: {:?}", map); // s map: {"a": 1, "b": 2, "c": 3} for (key, value) in map.iter_mut() { if key != &"a" { *value += 10; } } println!("e map: {:?}", map); // e map: {"a": 1, "b": 12, "c": 13} } ``` ## 性能优化技巧批量插入预排序数据 ```rust let data = vec![("A", 1), ("B", 2), ("C", 3)]; let map: BTreeMap<_, _> = data.into_iter().collect(); // 比逐个 insert 更快 ``` 复用迭代器 ```rust // 避免多次创建迭代器 let mut iter = map.iter(); while let Some((k, v)) = iter.next() { // 处理逻辑 } ``` 使用 `entry` 避免重复查找 ```rust // 存在时更新，不存在时插入 map.entry("Alice") .and_modify(|score| *score += 5) .or_insert(100); ``` ## 和 `HashMap` 的区别 ### 数据结构与内部实现 |**特性**|**`BTreeMap`**|**`HashMap`**| |---|---|---| |**底层结构**|基于 **B-Tree**（平衡多路搜索树）|基于 **哈希表**（开放寻址法）| |**元素顺序**|按键的 **自然顺序** 排序（从小到大）|**无序**（依赖哈希函数和插入顺序）| |**键的要求**|键需实现 `Ord` trait|键需实现 `Eq` + `Hash` trait| ### 性能对比 | **操作** | **`BTreeMap`** | **`HashMap`** | | -------- | -------------- | ------------------- | | **查找** | `O(log n)` | 平均 `O(1)`，最坏 `O(n)` | | **插入** | `O(log n)` | 平均 `O(1)`，最坏 `O(n)` | | **删除** | `O(log n)` | 平均 `O(1)`，最坏 `O(n)` | | **范围查询** | `O(log n + k)` | 不支持（需遍历全部元素） | | **顺序迭代** | 高效（内存连续） | 低效（哈希表分散存储） | - **`BTreeMap`**：内存布局更紧凑（树节点按顺序存储），适合内存敏感场景 - **`HashMap`**：因哈希冲突和负载因子（默认 0.75）会有额外内存开销 ## 键的约束与排序 **`BTreeMap`**： - 键必须实现 `Ord` trait（可排序），例如 `i32`、`String` 等 - 自动维护键的顺序，支持范围查询（如 `.range(a..b)`） ```rust use std::collections::BTreeMap; let mut map = BTreeMap::new(); map.insert(3, "three"); map.insert(1, "one"); map.insert(2, "two"); // 自动按键排序: 1 → 2 → 3 for (k, v) in &map { println!("{}: {}", k, v); // 1: one, 2: two, 3: three } ``` **`HashMap`**： - 键必须实现 `Hash` + `Eq` trait（可哈希和相等比较） - 元素顺序不可预测，依赖哈希函数 ```rust use std::collections::HashMap; let mut map = HashMap::new(); map.insert(3, "three"); map.insert(1, "one"); map.insert(2, "two"); // 输出顺序可能为任意排列（如 2 → 3 → 1） for (k, v) in &map { Println! ("{}: {}", k, v); } ``` ### 使用场景 | **场景** | **推荐选择** | **理由** | | -------------- | ---------- | -------------------------- | | 需要 **按键顺序遍历** | `BTreeMap` | 天然支持有序操作（如范围查询 `. Range ()`） | | 需要 **快速单次查找** | `HashMap` | 哈希表平均 `O (1)` 的查找速度更快 | | 内存敏感，数据量中等 | `BTreeMap` | 内存布局更紧凑，减少碎片 | | 高频插入删除，不关心顺序 | `HashMap` | 平均 `O (1)` 的插入性能更优 | | 键无法高效哈希（如复杂结构） | `BTreeMap` | 避免哈希计算的性能开销 |