KV存储 HashMap

HashMap也是rust标准库中提供的集合类型,但是又和动态数组不同,HashMap中存储的是-映射的KV键值对,并提供了平均复杂度为O(1)的查询方法,当我们希望通过一个Key取查询值时,该类型相当有用。 rust中哈希类型为HashMap<K,V>

创建HashMap

和Vec的创建类似,也可以用new方法来创建HashMap,然后通过insert方法插入键值对

使用new方法创建

use std::collections::HashMap;

let mut my_gems = HashMap::new();

my_gems.insert("红宝石",1);
my_gems.insert("蓝宝石",2);
my_gems.insert("河边捡的误以为是宝石的破石头",18);

该HashMap的类型:HashMap<&str,i32> 但是还有一点,就是使用HashMap需要手动通过use...从标准库中引入到我们当前的作用域中,之前使用另外2个集合类型String和Vec时,我们并没有引入 因为HashMap没有包括在rust的prelude中 所有的集合类型都是动态的,无固定的内存大小,底层的数据都存储在内存堆上,然后通过一个存储在栈中的引用类型来访问,同时,和其他类型一样,HashMap也是内聚性的,所有的K类型相同,V也是

和Vec一样,如果预先知道要存储的KV对个数,可以使用HashMap::with_capacity(capacity)创建指定大小的HashMap,避免频繁的内存分配和调用,提升性能

使用迭代器和collect创建

实际我们更多遇见的,从另外一个数据结构中,获取到对应的数据,最终生成HashMap 考虑一个场景,1张表格中记录了各个足球联赛中各个队伍名称和积分的信息,如果被到导入rust中,一个合理的数据结构是Vec<String,u32>类型,该数组的元素是一个个元组,该数据结构和表格数据很契合:表格中的数据都是逐行存储,每一行都有一个(队伍,名称,积分)的信息 但是很多时候,又需要通过队伍名称来查询对应的积分,此时动态数组就不适用了,因此可以用HashMap来保存相关的队伍名称->积分映射关系

fn main(){
	use std::collections::HashMap;
	
	let teams_list=vec![
		("China".to_string(),100),
		("Amercia".to_string(),10),
		("Japan".to_string(),50),
	];
	
	let mut teams_map = Hash::new();
	for team in &teams_list{
		teams_map.insert(&team.0,team.1);
	}
	
	println!("{:?}",teams_map)
}

遍历数组,将每一个元组作为KV插入HashMap中,很简单,但是,不够rusty 好在,rust提供了:先将Vec转为迭代器,然后通过collect方法,将迭代器的元素收集后,转为HashMap

fn main(){
	use std::fmt::collections::HashMap;
	
	let teams_list = vec![
		("China".to_string()，100)，
		("Amercia".to)string(),10),
		("Japan".to_string()，50),
	];
	
	let teams_map:HashMap<_,_> = teams_list.into_iter().collect();
	
	println!("{:?}",teams_up)
}

into_iter方法将列表转为迭代器,接着通过collect进行收集,不过需要注意的是,collect方法在内部实际上支持多种类型的目标集合,因此我们需要通过类型标注HashMap<_,_>告诉编译器:帮忙收集HashMap集合类型,具体的KV类型,请编译器进行推导 但是有时候rust编译器大聪明:看不懂,让你手动标注

所有权转移

HashMap的所有权和其他类型无区别:

• 若类型实现Copy特征,该类型会被复制进HashMap,因此无所谓所有权
• 若没实现Copy特征,所有权被转移给HashMap中

fn main(){
	use std::collections::HashMap;
	
	let name = String::from("Sunface");
	let age = 18;
	
	let mut handsome_boys = HashMap::new();
	handsome_boys,insert(name,age);
	
	println!("因为过于无耻,{}已经被从帅气男孩名单中除名",name);
	println!("还有，它的真实年龄远远不止{}岁",age);
}

Error:

name是String类型,因此收到所有权限制,在insert时,所有权转移给了handsome_boys,所以在最后使用时,会遇到这个无情但是意料之中的报错。 如果使用引用类型放入HashMap中,确保该引用的生命周期至少和HashMap获得一样久

fn main(){
	use std::collections::HashMaps;
	
	let name = String:;from("Sunface");
	let age = 18;
	
	let mut handsome_boys = HashMap::new();
	handsome_boys.insert(&name,age);
	
	std::mem::drop(name);
	println!("因为过于无耻,{:?}ui经被除名了",handsome_boys);
	println!("还有,他的真实年龄远远不止{}岁",age);
	
}

上面借用name获取了引用,然后插入了handsome_boys,但是紧接着,就通过drop函数手动将name字符串从内存中移除,Error:

查询HashMap

通过get方法获取元素:

use std::collections::HashMap;

let mut scores = HashMap::new();

scores.insert(String::from("Blue"),10);
scores.insert(String::from("Yellow"),50);

let team_name = String::from("Blue");
let scores:Option<&i32> = scores.get(&team_name);

注意:

• get方法返回1个Option<&i32>类型:查询不到时,会返回一个None,查询到返回Some<&i32>
• &i32是对HashMap中值的借用,如果不适用借用,可能发生所有权的转移
• get方法的key参数必须是一个引用,如这里的scores.get(&team_name),这是因为HashMap<K,V>的get方法的签名如下:

impl<K,V> HashMap<K,V>

where
	K:Eq+Hash,
{
	pub fn get<Q>(&self,k:&Q)->Option<&V>
	where
		K:Borrow<Q>,
		Q:Hash+Eq+?Sized,
	{...}
}

可以看见签名中的k:&Q,下面的特征约束K:Borrow<Q>指的是类型K需要能从另一种形式Q被借用,这种情况下,String实现了Borrow<str>,所以&String和&str类型都可以用于get方法 还可以继续拓展: 上面的代码中,如果我们想要直接获得值类型的score怎么办:

let score:i32 = scores.get(&team_name).copied().unwrap_or(0);

官方文档中查询Option的copied方法和unwrap_or方法的含义以及该怎么用 还可以通过循环依次遍历KV对:

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);
}

更新HashMap中的值

更新值的时候,涉及多种情况,一一说明:

fn main(){
	use std::collections::HashMap:;new();
	
	let mut scores = HashMap::new();
	
	scores.insert("Blue",10);
	
	//覆盖已有的值
	let old = scores.insert("Blue",20);
	assert_eq!(old，Some(10));
	
	//查询新键入的值
	let new = scores.get("Blue");
	assert_eq!(new,some(&20));
	
	//查询Yellow对应的值,若不存在则插入新值
	let v = scores.entry("Yellow").or_insert(5);
	assert_eq!(*v,5);
	
	//查询Yellow对应的值,若不存在则插入新值
	let v = scores.entry("Yellow").or_insert(50);
	assert_eq!(*v,5); //已经存在,因此50没有插入
}

再已有值的基础上更新

查询某个key对应的值,若不存在则插入新值,若存在则对已有的值进行更新,例如在文本中统计词语出现的次数:

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);

上述代码中,新建一个map用于保存词语出现的次数,出入一个词语会进行判断:之前没有插入过,则使用该词语作为Key,插入次数0作为Value,若之前插入过则取出之前统计的该词语出现的次数,对其加1 Notice:

• or_insert返回了&mut v引用,因此可以通过该引可变引用直接修改map中对应的值
• 使用count引用时,需要先进行解引用*count,否则会出现类型不匹配

哈希函数

到底什么是Hash? 如果要实现Key和Value的一一对应,是不是意味着我们要能够比较2个Key的相等性?一个类型能否作为Key的关键就是是否能够进行相等比较,或者说该类型是否实现了std::cmp::Eq特征 eg:f32和f64浮点数,没有实现std::cmp::Eq特征,因此不可以用作HashMap的Key 那么,一个较为复杂的值作为Key,怎么在底层对它进行存储,怎么使用它进行查询和比较,有哈希函数:通过把Key计算后映射为哈希值,使用该哈希值来进行存储,查询,比较 如何保证不同Key通过哈希后2个值不同?如果相同,意味着我们使用不同的Key,却查到了同一个结果,错误… 若要追求安全,尽量减少冲突,同时防止拒绝服务(Denial of Service,DOS)服务,需要使用密码学安全的哈希函数,HashMap就是使用了这样的哈希函数;反之若要追求性能,就需要使用没有那么安全的算法

高性能第三方库

若标准库默认的哈希函数不能满足你的性能需求,就需要去crates.io上寻找其他哈希函数实现,使用方法很简单:

use std::hash::BuildHasherDefault;
use std::collectiosn::HashMap;
//引入第三方哈希函数
use twox_hash::XxHash64;

//指定HashMap使用第三方的哈希函数XxHash64
let mut hash:HashMap<_,_,BuildHasherDefault<XxHash64>>=Default::defalut();

hash.insert(42,'the answer');
assert_eq!(hash.get(&42),Some(&"The answer"))；

目前,HashMap使用的哈希函数是SpiHash,性能不是很高,但是安全性很高,SipHash在中等大小的Key上,性能相当不错,但是对于小型的Key(例如整数)或者大型Key(例如字符串)来说,性能还是不够好,若是需要极致性能,或者实现算法,可以考虑:ahash