ph 是由 Piotr Beling 开发的基于完美哈希的数据结构Rust库。

该库包含两种基于指纹的最小完美哈希函数（MPHF）的实现：不带（FMPH）和带（FMPHGO）组优化。最小完美哈希函数（MPHF）是从键集 K 到集合 {0, 1, ..., |K|-1} 的双射。

FMPH 和 FMPHGO 可以为任何给定的可哈希项集 K（提前给出）构造，并且分别使用大约 2.8 和 2.1 比特/键进行表示。FMPH 和 FMPHGO 评估速度快（期望为 O(1)）。它们的构造需要很少的辅助空间，所需时间短（期望为 O(|K|)，对于 FMPH 尤其如此），并且可以并行化或在不将键保留在内存中的情况下执行。

参考文献

在研究目的中使用 ph 时，请引用以下论文，该论文提供了关于 FMPH 和 FMPHGO 的详细信息

• Piotr Beling, 基于指纹的最小完美哈希重访, ACM实验算法杂志，2023年，https://doi.org/10.1145/3596453

示例

以下示例说明了 fmph::Function 的使用，但可以将其替换为 fmph::GOFunction 而无需任何其他更改。

基本示例

use ph::fmph;

let keys = ['a', 'b', 'z'];
let f = fmph::Function::from(keys.as_ref());
// f assigns each key a unique number from the set {0, 1, 2}
for k in keys { println!("The key {} is assigned the value {}.", k, f.get(&k).unwrap()); }
let mut values = [f.get(&'a').unwrap(), f.get(&'b').unwrap(), f.get(&'z').unwrap()];
values.sort();
assert_eq!(values, [0, 1, 2]);

使用 fmph::Function 和位图表示一组给定的可哈希元素的子集的示例

use ph::fmph;
use bitm::{BitAccess, BitVec};  // bitm is used to manipulate bitmaps
use std::hash::Hash;

pub struct Subset { // represents a subset of the given set
    hash: fmph::Function, // bijectively maps elements of the set to bits of bitmap
    bitmap: Box<[u64]> // the bit pointed by the hash for e is 1 <=> e is in the subset
}

impl Subset {
    pub fn of<E: Hash + Sync>(set: &[E]) -> Self { // constructs empty subset of the given set
        Subset {
            hash: set.into(),
            bitmap: Box::with_zeroed_bits(set.len())
        }
    }

    pub fn contain<E: Hash>(&self, e: &E) -> bool { // checks if e is in the subset
        self.bitmap.get_bit(self.hash.get_or_panic(e) as usize) as bool
    }

    pub fn insert<E: Hash>(&mut self, e: &E) { // inserts e into the subset
        self.bitmap.set_bit(self.hash.get_or_panic(e) as usize)
    }

    pub fn remove<E: Hash>(&mut self, e: &E) { // removes e from the subset
        self.bitmap.clear_bit(self.hash.get_or_panic(e) as usize)
    }

    pub fn len(&self) -> usize { // returns the number of elements in the subset
        self.bitmap.count_bit_ones()
    }
}

let mut subset = Subset::of(["alpha", "beta", "gamma"].as_ref());
assert_eq!(subset.len(), 0);
assert!(!subset.contain(&"alpha"));
assert!(!subset.contain(&"beta"));
subset.insert(&"beta");
subset.insert(&"gamma");
assert_eq!(subset.len(), 2);
assert!(subset.contain(&"beta"));
subset.remove(&"beta");
assert_eq!(subset.len(), 1);
assert!(!subset.contain(&"beta"));
// subset.insert(&"zeta"); // may either panic or insert any item into subset

上述的 Subset 是一个具有 1 位有效负载的 可更新检索数据结构 的示例。可以通过用其他有效负载的向量替换位图来泛化。