Rust常用数据结构教程 Map

一、Map类型

·键值对数据又称字典数据类型

·主要有两种

• · HashMap
  ·- BTreeMap

1.HashMap

·HashMap<K,V>类型储存了一个键类型K对应一个值类型V的映射。它通过一个 哈希函数（hashing function）来实现映射，决定如何将键和值放入内存中。

·HashMap的数据和Vec一样在heap上

hashMap的简单插入

#![allow(unused)]
fn main() {use std::collections::HashMap;let mut scores = HashMap::new();scores.insert(String::from("Blue"), 10);scores.insert(String::from("Yellow"), 50);for (key, value) in &scores {println!("{}: {}", key, value);}
}

 cargo runCompiling abc v0.1.0 (/home/wangji/installer/rust/bobo/abc)Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.91sRunning `target/debug/abc`
Yellow: 50
Blue: 10

entry().or_insert()更新hashMap

直接覆盖

#![allow(unused)]
fn main() {
use std::collections::HashMap;let mut scores = HashMap::new();scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Blue"), 25);println!("{:?}", scores);
}

or_insert在没有key的情况下才插入

#![allow(unused)]
fn main() {use std::collections::HashMap;let mut scores = HashMap::new();scores.insert(String::from("Blue"), 10);scores.entry(String::from("Yellow")).or_insert(50);scores.entry(String::from("Blue")).or_insert(50);println!("{:?}", scores);
}

 cargo runBlocking waiting for file lock on package cacheBlocking waiting for file lock on package cacheCompiling abc v0.1.0 (/home/wangji/installer/rust/bobo/abc)Finished `dev` profile [unoptimized + debuginfo] target(s) in 13.96sRunning `target/debug/abc`
{"Blue": 10, "Yellow": 50}

or_inser根据旧值更新一个值，会返回插入的pair的value的引用

#![allow(unused)]
fn main() {use std::collections::HashMap;let text = "hello world wonderful world";let mut map = HashMap::new();for word in text.split_whitespace() {let count = map.entry(word).or_insert(0);*count += 1;}println!("{:?}", map);
}

 cargo runFinished `dev` profile [unoptimized + debuginfo] target(s) in 0.00sRunning `target/debug/abc`
{"hello": 1, "wonderful": 1, "world": 2}

2.什么时候用HashMap

·仅次于Vec的常用数据类型
·存储数据为键值对类型
需要查找的速度

• in-memory cache

3.HashMap中的键

·因为要满足哈希函数，所以HashMap对键有特殊要求
·实现Hash、Eq、PartialEq
·一般结构体： #[derive(Debug, PartialEq, Hash, Eq)]

use std::collections::HashMap;// Hash Eq PartialEq
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
struct Car {id: i32,price: i32,
}fn main() {let _int_map: HashMap<i32, i32> = HashMap::new();let _int_map: HashMap<i32, i32> = HashMap::with_capacity(10);// 通过数组来创建maplet mut car_map = HashMap::from([("Car1",Car {id: 1,price: 10000,},),("Car2", Car { id: 2, price: 4000 }),("Car3",Car {id: 3,price: 890000,},),]);// 打印实际是无序的for (k, v) in &car_map {println!("{k}:{:?}", v);}// getprintln!("Some {:?}", car_map.get("Car1"));println!("None {:?}", car_map.get("Car6"));// 覆盖性插入insertcar_map.insert("Car4",Car {id: 4,price: 80000,},);println!("{:?}", car_map);car_map.insert("Car4",Car {id: 5,price: 300000,},);println!("{:?}", car_map);// 只在键没有时插入// Entrycar_map.entry("Car4").or_insert(Car { id: 9, price: 9000 });println!("{:?}", car_map);// removecar_map.remove("Car4");println!("{:?}", car_map);car_map.entry("Car4").or_insert(Car { id: 9, price: 9000 });println!("{:?}", car_map);// 加上注释PartialEq, Eq, Hashlet mut car_map = HashMap::from([(Car {id: 1,price: 10000,},"Car1",),(Car { id: 2, price: 4000 }, "Car2"),(Car {id: 3,price: 890000,},"Car3",),]);println!("Car2: {:?}\n",car_map.get(&Car {id: 1,price: 10000}));for (car, name) in &car_map {println!("{:?}: {name}", car)}// Filter：会原地修改mapcar_map.retain(|c, _| c.price < 5000);println!("< 4000  {:?}", car_map);
}

编译及运行

 cargo runBlocking waiting for file lock on build directoryCompiling data_struct v0.1.0 (/home/wangji/installer/rust/data_struct/data_struct)Finished `dev` profile [unoptimized + debuginfo] target(s) in 13.52sRunning `target/debug/data_struct`
Car1:Car { id: 1, price: 10000 }
Car3:Car { id: 3, price: 890000 }
Car2:Car { id: 2, price: 4000 }
Some Some(Car { id: 1, price: 10000 })
None None
{"Car4": Car { id: 4, price: 80000 }, "Car2": Car { id: 2, price: 4000 }, "Car1": Car { id: 1, price: 10000 }, "Car3": Car { id: 3, price: 890000 }}
{"Car4": Car { id: 5, price: 300000 }, "Car2": Car { id: 2, price: 4000 }, "Car1": Car { id: 1, price: 10000 }, "Car3": Car { id: 3, price: 890000 }}
{"Car4": Car { id: 5, price: 300000 }, "Car2": Car { id: 2, price: 4000 }, "Car1": Car { id: 1, price: 10000 }, "Car3": Car { id: 3, price: 890000 }}
{"Car2": Car { id: 2, price: 4000 }, "Car1": Car { id: 1, price: 10000 }, "Car3": Car { id: 3, price: 890000 }}
{"Car4": Car { id: 9, price: 9000 }, "Car2": Car { id: 2, price: 4000 }, "Car1": Car { id: 1, price: 10000 }, "Car3": Car { id: 3, price: 890000 }}
Car2: Some("Car1")Car { id: 3, price: 890000 }: Car3
Car { id: 1, price: 10000 }: Car1
Car { id: 2, price: 4000 }: Car2
< 4000  {Car { id: 2, price: 4000 }: "Car2"}

二、BTreeMap

map的有序形式

内部基于BTree创建

1.什么时候用BTreeMap

·当你需要有序map时
·当你查找时，有序可以提供你的性能 (比如二分查找法)
·注意：有序是有代价的
·BTreeMap缓存效率和搜索中进行了折衷

2.BTreeMap中的键

·因为需要对键值排序所以需要Key实现

• Ord
• PartialOrd

use std::collections::BTreeMap;// Hash Eq PartialEq
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
struct Car {id: i32,price: i32,
}impl Ord for Car {fn cmp(&self, other: &Self) -> std::cmp::Ordering {self.price.cmp(&other.price)}
}impl PartialOrd for Car {fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {Some(self.price.cmp(&other.price))}
}fn main() {let _int_map: BTreeMap<i32, i32> = BTreeMap::new();// let _int_map:BTreeMap<i32, i32> = BTreeMap::with_capacity(10);// 通过数组来创建maplet mut car_map = BTreeMap::from([("Car1",Car {id: 1,price: 10000,},),("Car2", Car { id: 2, price: 4000 }),("Car3",Car {id: 3,price: 890000,},),]);println!("{:#?}", car_map);println!("------------------------");let mut car_map = BTreeMap::from([(Car {id: 1,price: 10000,},1,),(Car { id: 2, price: 4000 }, 2),(Car {id: 3,price: 890000,},3,),]);for (k, v) in &car_map {println!("{:?}: {v}", k);}println!("----------------------");car_map.insert(Car {id: 4,price: 90000,},4,);for (k, v) in &car_map {println!("{:?}: {v}", k);}println!("----------------------");println!("{:?}",car_map.get(&Car {id: 1,price: 10000}));println!("{:?}", car_map.first_key_value());println!("{:?}", car_map.last_key_value());println!("----------------------");// removelet car = car_map.pop_first().unwrap();println!("{:?}", car);let car = car_map.pop_last().unwrap();println!("{:?}", car);println!("----------------------");for (k, v) in &car_map {println!("{:?}: {v}", k);}println!("----------------------");// remove(index)不建议你用car_map.remove(&Car {id: 1,price: 10000,});for (k, v) in &car_map {println!("{:?}: {v}", k);}println!("----------------------");car_map.clear();println!("{}", car_map.is_empty());
}

编译及运行

 cargo runCompiling data_struct v0.1.0 (/home/wangji/installer/rust/data_struct/data_struct)
warning: variable does not need to be mutable--> src/main.rs:27:9|
27 |     let mut car_map = BTreeMap::from([|         ----^^^^^^^|         ||         help: remove this `mut`|= note: `#[warn(unused_mut)]` on by defaultwarning: `data_struct` (bin "data_struct") generated 1 warning (run `cargo fix --bin "data_struct"` to apply 1 suggestion)Finished `dev` profile [unoptimized + debuginfo] target(s) in 6.51sRunning `target/debug/data_struct`
{"Car1": Car {id: 1,price: 10000,},"Car2": Car {id: 2,price: 4000,},"Car3": Car {id: 3,price: 890000,},
}
------------------------
Car { id: 2, price: 4000 }: 2
Car { id: 1, price: 10000 }: 1
Car { id: 3, price: 890000 }: 3
----------------------
Car { id: 2, price: 4000 }: 2
Car { id: 1, price: 10000 }: 1
Car { id: 4, price: 90000 }: 4
Car { id: 3, price: 890000 }: 3
----------------------
Some(1)
Some((Car { id: 2, price: 4000 }, 2))
Some((Car { id: 3, price: 890000 }, 3))
----------------------
(Car { id: 2, price: 4000 }, 2)
(Car { id: 3, price: 890000 }, 3)
----------------------
Car { id: 1, price: 10000 }: 1
Car { id: 4, price: 90000 }: 4
----------------------
Car { id: 4, price: 90000 }: 4
----------------------
true

参考

• Rust常用数据结构教程