Lib.rs

› 数据结构
#hash-map #entry #borrowed #key #key-string #forms #collection

hashmap-entry-ownable

HashMap::entry() 的一个变体，接受借用形式的键

作者：vthriller

2 个不稳定版本

0.2.0 2019年3月21日
0.1.0 2019年3月20日

#2241 in 数据结构

MIT/Apache

20KB
324 行

hashmap-entry-ownable

HashMap::entry() 的一个变体，接受借用形式的键。

兼容性

对于 std::collections::HashMap，需要 Rust 的 nightly 版本以及 crate 功能 nightly。详情请见 hash_raw_entry).

可以通过名为 hashbrown 的 crate 功能启用对 hashbrown 的支持。

entry_ownable() 可以用作 entry() 的直接替换，除非

  • 使用了 Entry::key()，
  • entry 被匹配为枚举（Entry::Occupied/Entry::Vacant）。

描述

如果您经常从借用形式的键（例如，从 &str 而不是 String）创建/更新条目，请使用此 crate。

use std::collections::HashMap;
use hashmap_entry_ownable::std_hash::EntryAPI;

let rhyme = vec![
	"Mary", "had", "a", "little", "lamb",
	"little", "lamb", "little", "lamb",
];

let mut words: HashMap<String, _> = HashMap::new();

for w in rhyme {
	// words.entry() accepts String but not &str
	// this version saves us 4 short-living allocations
	// for consecutive appearances of "little" and "lamb"
	let counter = words.entry_ownable(w).or_insert(0);
	*counter += 1;
}

此代码可以使用 match map.get_mut(k)/map.insert(k.to_owned(), …) 来模拟。如果大量使用键，这将比常规 Entry API 更快，但 entry_ownable() 变体

  • 与常规的 entry() 一样简洁，
  • 只对键进行一次散列，而 get_mut()/insert() 如果键不在映射中，则进行两次散列。

基准测试

std::collections::HashMap:

test silly_bench::entry_1         ... bench:   2,162,452 ns/iter (+/- 17,586)
test silly_bench::get_or_insert_1 ... bench:   2,310,910 ns/iter (+/- 7,183)
test silly_bench::entry_ownable_1 ... bench:   1,586,380 ns/iter (+/- 7,156)

test silly_bench::entry_2         ... bench:   3,427,428 ns/iter (+/- 104,755)
test silly_bench::get_or_insert_2 ... bench:   2,926,719 ns/iter (+/- 11,077)
test silly_bench::entry_ownable_2 ... bench:   2,167,021 ns/iter (+/- 8,140)

test silly_bench::entry_4         ... bench:   6,068,954 ns/iter (+/- 56,549)
test silly_bench::get_or_insert_4 ... bench:   4,150,970 ns/iter (+/- 18,292)
test silly_bench::entry_ownable_4 ... bench:   3,321,019 ns/iter (+/- 18,487)

test silly_bench::entry_8         ... bench:  11,278,344 ns/iter (+/- 82,014)
test silly_bench::get_or_insert_8 ... bench:   6,602,424 ns/iter (+/- 33,360)
test silly_bench::entry_ownable_8 ... bench:   5,631,416 ns/iter (+/- 54,613)

hashbrown::HashMap:

test silly_bench::entry_1         ... bench:   1,469,848 ns/iter (+/- 9,229)
test silly_bench::get_or_insert_1 ... bench:   1,489,309 ns/iter (+/- 10,865)
test silly_bench::entry_ownable_1 ... bench:   1,370,580 ns/iter (+/- 5,152)

test silly_bench::entry_2         ... bench:   2,351,940 ns/iter (+/- 10,374)
test silly_bench::get_or_insert_2 ... bench:   1,801,549 ns/iter (+/- 12,360)
test silly_bench::entry_ownable_2 ... bench:   1,634,317 ns/iter (+/- 7,421)

test silly_bench::entry_4         ... bench:   4,418,648 ns/iter (+/- 18,059)
test silly_bench::get_or_insert_4 ... bench:   2,451,798 ns/iter (+/- 10,702)
test silly_bench::entry_ownable_4 ... bench:   2,292,556 ns/iter (+/- 16,042)

test silly_bench::entry_8         ... bench:   8,350,365 ns/iter (+/- 39,678)
test silly_bench::get_or_insert_8 ... bench:   3,837,979 ns/iter (+/- 20,885)
test silly_bench::entry_ownable_8 ... bench:   3,749,296 ns/iter (+/- 5,678)

许可证

这个crate大量借鉴了Rust的libstd库，因此遵循Apache 2.0和MIT许可证。

依赖项

~215KB