Rust插件库ph的使用，高效功能扩展与模块化开发工具

ph 是由 Piotr Beling 开发的 Rust 库，提供了（最小）完美哈希函数的实现。

最小完美哈希函数(MPHF)是从键集 K 到集合 {0, 1, …, |K|−1} 的双射。

该库包含以下实现：

• PHast – 基于桶放置的函数，具有非常快速的评估和低于每键2位的存储大小
• 两种指纹最小完美哈希函数的变体：
  • 不带群优化的(FMPH, fmph::Function)
  • 带群优化的(FMPHGO, fmph::GOFunction)

所有这些函数都可以为任何预先给定的可哈希项集 K 构建。

示例

以下是使用 fmph::Function 的基本示例：

use ph::fmph;

let keys = ['a', 'b', 'z'];
let f = fmph::Function::from(keys.as_ref());
// f为每个键分配一个来自集合{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 和 bitmap 来表示给定可哈希元素集的子集的示例：

use ph::fmph;
use bitm::{BitAccess, BitVec};  // bitm用于操作位图
use std::hash::Hash;

pub struct Subset { // 表示给定集合的子集
    hash: fmph::Function, // 将集合元素双射到位图的位
    bitmap: Box<[u64]> // 哈希指向的位为1 <=> 元素在子集中
}

impl Subset {
    pub fn of<E: Hash + Sync>(set: &[E]) -> Self { // 构建给定集合的空子集
        Subset {
            hash: set.into(),
            bitmap: Box::with_zeroed_bits(set.len())
        }
    }

    pub fn contain<E: Hash>(&self, e: &E) -> bool { // 检查e是否在子集中
        self.bitmap.get_bit(self.hash.get_or_panic(e) as usize) as bool
    }

    pub fn insert<E: Hash(&mut self, e: &E) { // 将e插入子集
        self.bitmap.set_bit(self.hash.get_or_panic(e) as usize)
    }

    pub fn remove<E: Hash>(&mut self, e: &E) { // 从子集中移除e
        self.bitmap.clear_bit(self.hash.get_or_panic(e) as usize)
    }

    pub fn len(&self) -> usize { // 返回子集中的元素数量
        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"); // 可能会panic或将任何项插入子集

完整示例

下面是一个更完整的示例，展示了如何使用 ph 库进行高效的数据查询和存储：

use ph::fmph;
use std::collections::HashMap;

// 定义一个学生结构体
#[derive(Hash)]
struct Student {
    id: u32,
    name: String,
}

fn main() {
    // 创建学生数据集
    let students = vec![
        Student { id: 1001, name: "Alice".to_string() },
        Student { id: 1002, name: "Bob".to_string() },
        Student { id: 1003, name: "Charlie".to_string() },
    ];

    // 构建完美哈希函数
    let f = fmph::Function::from(students.as_ref());
    
    // 创建成绩存储映射
    let mut scores = HashMap::new();
    
    // 为每个学生分配成绩
    for (i, student) in students.iter().enumerate() {
        let hash_value = f.get(student).unwrap();
        scores.insert(hash_value, (80 + i) as f32); // 模拟成绩
    }
    
    // 查询特定学生的成绩
    let bob = Student { id: 1002, name: "Bob".to_string() };
    if let Some(score) = scores.get(&f.get(&bob).unwrap()) {
        println!("Bob's score is: {}", score);
    }
    
    // 打印所有学生信息
    for student in &students {
        let hash = f.get(student).unwrap();
        println!("ID: {}, Name: {}, Hash: {}, Score: {}",
            student.id, student.name, hash, scores[&hash]);
    }
    
    // 验证哈希的唯一性
    let mut hashes: Vec<_> = students.iter()
        .map(|s| f.get(s).unwrap())
        .collect();
    hashes.sort_unstable();
    assert_eq!(hashes, vec![0, 1, 2]);
}

特性

• PHast 提供极快的评估速度
• FMPH 和 FMPHGO 分别使用约2.8和2.1位/键
• 所有函数都是O(1)时间复杂度
• 构建过程需要很少的辅助空间
• 可以并行化构建
• 支持不将键保留在内存中的构建方式

安装

在项目目录中运行以下Cargo命令：

cargo add ph

或在Cargo.toml中添加：

ph = "0.9.6"

许可证

MIT OR Apache-2.0