京公网安备11010502063487号选 BTreeMap 还是 HashMap,取决于要不要「有序」。这篇不讲抽象的 O(log n) 与 O(1),而是把有序遍历、范围查询、键的 trait 要求、插入与查找耗时、范围查询耗时和分配形态都真实跑了出来。
编译:成功
运行(退出码 0):
遍历: [10, 20, 30, 40, 50, 60, 70, 80, 90]
range(30..=60): [30, 40, 50, 60]
range(..30): [10, 20] range(75..): [80, 90]
first_key_value Some((10, 20)) last_key_value Some((90, 180))
pop_first Some((10, 20)) pop_last Some((90, 180)) 剩 7 个
小于等于 45 的最大键: Some(40) 源码:
1 | use std::collections::HashMap;
2 | fn main() { let m: HashMap<i32, i32> = HashMap::new(); let _ = m.range(1..5); }
编译:失败
error[E0599]: no method named `range` found for struct `HashMap<K, V, S, A>` in the current scope
--> <实验目录>/src/u60b.rs:2:66
|
2 | fn main() { let m: HashMap<i32, i32> = HashMap::new(); let _ = m.range(1..5); }
| ^^^^^ method not found in `HashMap<i32, i32>`
error: aborting due to 1 previous error
For more information about this error, try `rustc --explain E0599`.HashMap 的哈希与扩容见HashMap 的哈希与扩容。
源码:
1 | use std::collections::{BTreeMap, HashMap};
2 | #[derive(PartialEq, Eq, Hash, Debug)] struct P(i32);
3 | fn main() {
4 | let mut h = HashMap::new(); h.insert(P(1), "hash ok");
5 | let mut b = BTreeMap::new(); b.insert(P(1), "btree");
6 | println!("{:?} {:?}", h, b);
7 | }
编译:失败
error[E0277]: the trait bound `P: Ord` is not satisfied
--> <实验目录>/src/u60c.rs:5:36
|
5 | let mut b = BTreeMap::new(); b.insert(P(1), "btree");
| ^^^^^^ the trait `Ord` is not implemented for `P`
|
note: required by a bound in `BTreeMap::<K, V, A>::insert`
--> <rust 标准库源码>/library/alloc/src/collections/btree/map.rs:1047:12
|
1045 | pub fn insert(&mut self, key: K, value: V) -> Option<V>
| ------ required by a bound in this associated function
1046 | where
1047 | K: Ord,
| ^^^ required by this bound in `BTreeMap::<K, V, A>::insert`
help: consider annotating `P` with `#[derive(Ord)]`
|
2 | #[derive(PartialEq, Eq, Hash, Debug)] #[derive(Ord)]
| ++++++++++++++
error: aborting due to 1 previous error
For more information about this error, try `rustc --explain E0277`.
编译:成功
运行(退出码 0):
自定义 Ord(反序)的遍历: [Rev(3), Rev(2), Rev(1)] 编译:成功
运行(退出码 0):
n= 1000: 插入 HashMap 0.06 ms / BTreeMap 0.10 ms 查找 HashMap 0.01 ms / BTreeMap 0.07 ms
n= 100000: 插入 HashMap 2.58 ms / BTreeMap 9.76 ms 查找 HashMap 1.03 ms / BTreeMap 7.78 ms
n= 1000000: 插入 HashMap 30.71 ms / BTreeMap 119.13 ms 查找 HashMap 26.05 ms / BTreeMap 128.90 ms耗时是本机 release 模式的实测(取 3 次最小),键为 xorshift 生成的随机 u64;键类型、值大小或机器不同,倍数会变。
编译:成功
运行(退出码 0):
BTreeMap::range 找到 143 个,用时 1.209µs
HashMap 全表过滤 找到 143 个,用时 2.609166ms 编译:成功
运行(退出码 0):
BTreeMap<u64,u64> 1000 个:alloc 167 次,最大单次 544 字节
HashMap<u64,u64> 1000 个:alloc 10 次,最大单次 34824 字节