phf_mut

这是一个用于完美哈希 可变 容器的 Rust 包，与已经存在的完美哈希 不可变 数据结构（例如其他包）形成对比。

假设您需要一个从键到值的映射，您的键域较小，并且您已经有一个完美的哈希函数。

phf 包支持不可变、编译时生成的映射。但可变映射和集合怎么办？这正是此包的作用所在。

在映射的情况下，假设某种类型的默认元素。请注意，我们将假设该映射将相当满。在稀疏映射的情况下，HashMap 可能无论如何都无法胜过。

我个人的用例是一个 完全 填充的映射和一个可默认构造的类型。因此，容器始终被视为满的。

在集合的情况下，假设域（可能键的集合）足够小，可以表示为某种位集。同样，对于非常小的域或稀疏集合，HashSet 加上自定义包装器（为了覆盖 PartialEq）将胜过此实现。

目录

• 背景
• 安装
• 使用方法
• 待办事项
• 贡献

背景

示例：您有一个贯穿一个小立方体的整数网格，并且您想存储大多数网格节点的某些 V。您可以在每个调用点写 myvec[x + w*y + w*h*z]。或者您只需写一次，将此函数作为完美哈希函数传递，然后由此包处理其余部分。

安装

将其添加到您的 Cargo.toml

[dependencies]
phf_mut = { git = "https://github.com/BenWiederhake/phf_mut.git", version = "0.4.1" }

这就足够了。

使用方法

只需使用它！复杂之处在于提出一个不错的 API，而不是编写代码。

extern crate phf_mut;
use phf_mut::{PerfectHash, Map};

struct Pairs {
    n: usize,
}

impl Pairs {
    pub fn new(n: usize) -> Self {
        Pairs { n: n }
    }

    fn sort((u, v): (usize, usize)) -> (usize, usize) {
        if u > v {
            (v, u)
        } else {
            (u, v)
        }
    }

    fn size_when(n: usize) -> usize {
        (n + 1) * n / 2
    }
}

impl PerfectHash for Pairs {
    type K = (usize, usize);

    fn hash(&self, k: Self::K) -> usize {
        let (a, b) = Self::sort(k);
        a + Self::size_when(b)
    }

    fn size(&self) -> usize {
        Self::size_when(self.n)
    }
}

fn main() {
    let mut mymap = Map::new(Pairs::new(10));
    mymap.insert((3, 7), String::from("Hello"));
    mymap[(7, 3)].push(' ');
    mymap.insert((4, 3), String::from("lovely"));
    mymap.insert((2, 9), String::from("World!"));
    print!("{}", mymap.get((3, 7))); // "Hello "
    print!("{}", mymap.get((2, 2))); // ""
    print!("{}", mymap.get((2, 9))); // "World!"
    print!("{}", mymap.get((7, 4))); // ""
    println!();
}

待办事项

• 让它功能齐全吗？
  • Default，PartialEq，Eq
  • Set 的 Index
  • 为HashInverse实例提供更友好的Debug实现
  • ::collect目标？(FromIterator<(K,V)>)
  • 同样，Extend<K,V>
• 请人们对使其成为“Rust风格”提出反馈

贡献

欢迎加入！可以创建问题或提交PR。