3个不稳定版本
| 0.2.0 | 2020年10月22日 |
|---|---|
| 0.1.1 | 2020年10月19日 |
| 0.1.0 | 2020年10月19日 |
#1610 在 算法
每月25次下载
26KB
575 行
refset - 非拥有 HashSet
不拥有其数据的哈希集合类似物。
它可以用来“标记”项目，而无需将所有权转移到映射中
示例用法
/// Process arguments while ignoring duplicates
fn process_args(args: impl IntoIterator<Item=String>) {
let mut same= HashRefSet::new();
for argument in args.into_iter()
{
if !same.insert(argument.as_str()) {
// Already processed this input, ignore
continue;
}
//do work...
}
}
与serde crate的序列化支持
HashRefSet和HashType都实现了Serialize和Deserialize，如果启用了serde功能。默认情况下，它是不启用的。
哈希
目前我们使用SHA512哈希算法进行实现。我可能将实现选择不同类型的能力，但到目前为止我认为这已经足够。
缺点
由于项目本身没有插入，我们不能使用Eq来再次检查是否有哈希冲突。虽然使用的哈希算法（Sha512）产生冲突的可能性极低，尤其是对于小数据类型，但请注意，它并不是不可错的。
速度
HashRefSet比HashSet慢得多，因此大多数情况下应首选HashSet。即使需要Clone以将项目插入到HashSet中，对于简单数据结构，它也可以快10倍以上。HashRefSet应在使用时，如果Clone不是选项，或者Clone是插入类型上的一个显著重操作。
| 基准测试 | 测试 | 结果 |
|---|---|---|
| owning_strings | 通过克隆将String插入到HashSet中 |
~4,538 ns/iter |
| non_owning_strings | 通过引用将str插入到HashRefSet中 |
~48,271 ns/iter |
| owning_ints | 通过复制将u32插入到HashSet中 |
~937 ns/iter |
| non_owning_ints | 通过引用将&u32插入到HashRefSet中 |
~31,089 ns/iter |
何时使用而不是HashSet
- 要插入的类型需要同时存在于集合中并移动到其他地方。（见示例）
- 仅使用
Clone将项目副本插入到HashSet中是不可能的（非Clone类型）或者是一个操作成本很高的操作。（见基准测试） - SHA512 算法潜在（尽管极不可能）碰撞的不可靠性不是问题。
- 您需要将未指定大小的类型插入到
HashSet中。
Smallmap 实现
启用 smallmap 功能后，small 模块还通过 SmallRefMap 提供与 HashRefSet 相同的 API。它由 smallmap::Map 支持，而不是 HashSet，这可能会对性能或内存使用产生影响，也可能不会。
目前，哈希算法和使用方式与其他方面相同，但可能会改变。
SmallRefMap 的基准测试
与克隆或复制到 smallmap::Map 进行比较。
主要性能惩罚与上述表格相同，但有非常小的差异。
| 基准测试 | 测试 | 结果 |
|---|---|---|
| owning_strings | 通过克隆将 String 插入到 SmallMap |
~3,096 ns/iter |
| non_owning_strings | 通过引用将 str 插入到 SmallRefMap |
~47,302 ns/iter |
| owning_ints | 通过复制将 u32 插入到 SmallMap |
~316 ns/iter |
| non_owning_ints | 通过引用将 &u32 插入到 SmallRefMap |
~30,046 ns/iter |
但是，每个 SmallRefMap 页将至少消耗 16kb 的内存。这可能不是非常理想，但仍然是一个可用的功能。
许可证
MIT
依赖项
~380–650KB
~15K SLoC