pthash-rs

Rust对PTHash的绑定，一个实现完美哈希函数的C++库，使用

• Giulio Ermanno Pibiri和Roberto Trani. "PTHash: Revisiting FCH Minimal Perfect Hashing". 在第44届国际信息检索研究和发展会议（SIGIR）的论文中。2021。
• Giulio Ermanno Pibiri和Roberto Trani. "Parallel and External-Memory Construction of Minimal Perfect Hash Functions with PTHash". 知识和数据工程（TKDE） Transactions。2023。

构建

apt install build-essential libclang-dev
git clone https://gitlab.softwareheritage.org/swh/devel/pthash-rs.git
cd pthash-rs
git submodule update --init --recursive
cargo build

内部代码结构

由于C++模板比Rust泛型更接近宏，Rust结构体类型参数的每个可能实例都需要映射到一个具体的C++类。

在使用crate时这是不可见的，但意味着只有本crate明确允许的哈希算法和编码器才能使用。此外，可以通过功能调整允许列表，以减少模板实例化和与Rust类型链接的组合爆炸；有关详细信息，请参阅Cargo.toml。

示例

最小PHF

use pthash::{
    BuildConfiguration, DictionaryDictionary, Hashable, Minimal, MurmurHash2_64, Phf, SinglePhf
};

let temp_dir = tempfile::tempdir().unwrap();
let mut config = BuildConfiguration::new(temp_dir.path().to_owned());
// config.minimal_output = true; // unlike the C++ API, this is implicit from f's type

let keys: Vec<&[u8]> = vec!["abc".as_bytes(), "def".as_bytes(), "ghikl".as_bytes()];

let mut f = SinglePhf::<Minimal, MurmurHash2_64, DictionaryDictionary>::new();
f.build_in_internal_memory_from_bytes(&keys, &config).expect("Failed to build");

// Hashes are unique and in the [0; 3) segment
let mut hashes: Vec<u64> = keys.iter().map(|key| f.hash(key)).collect();
hashes.sort();
assert_eq!(hashes, vec![0, 1, 2]);

// Hashing an object that wasn't provided when building the function collides
assert!(f.hash(b"not_a_key".as_bytes()) < 3);

非最小PHF

use pthash::{
    BuildConfiguration, DictionaryDictionary, Hashable, Nonminimal, MurmurHash2_64, Phf, SinglePhf
};

let temp_dir = tempfile::tempdir().unwrap();
let mut config = BuildConfiguration::new(temp_dir.path().to_owned());

let keys: Vec<&[u8]> = vec!["abc".as_bytes(), "def".as_bytes(), "ghikl".as_bytes()];

let mut f = SinglePhf::<Nonminimal, MurmurHash2_64, DictionaryDictionary>::new();
f.build_in_internal_memory_from_bytes(&keys, &config).expect("Failed to build");

// Hashes are unique
let mut hashes: Vec<u64> = keys.iter().map(|key| f.hash(key)).collect();
hashes.sort();

// But not necessarily in the [0; 3) segment (not minimal)
// assert_eq!(hashes, vec![0, 1, 2]);

// Hashing an object that wasn't provided when building the function may collide
// assert!(!hashes.contains(f.hash(b"not_a_key".as_bytes())));