如何在Rust中创建不存储键的HashSet与HashMap？

核心前提说明 #

Rust标准库的HashMap/HashSet必须存储完整键，本质是为了处理哈希冲突——当两个不同键的哈希值相同时，需要通过比较键本身来确认是否为同一元素。如果你的场景可以接受极低的碰撞风险，或者能通过额外校验降低碰撞概率，就能实现不存完整键的集合/映射。

1. 极简实现：仅存哈希值（适合低碰撞风险场景） #

如果业务中可以忽略哈希碰撞的可能性（比如用加密级哈希算法，或者键的哈希冲突概率可接受），直接基于哈希值构建集合或映射即可，插入时只需要传入键的引用，无需获取所有权：

use std::collections::{HashMap, HashSet};
use std::hash::{Hash, Hasher};

// 仅存哈希值的集合
struct HashOnlySet {
    inner: HashSet<u64>,
}

impl HashOnlySet {
    fn new() -> Self {
        Self { inner: HashSet::new() }
    }

    // 插入时接受键的引用，计算哈希后存储
    fn insert<K: Hash>(&mut self, key: &K) -> bool {
        let mut hasher = std::collections::hash_map::DefaultHasher::new();
        key.hash(&mut hasher);
        self.inner.insert(hasher.finish())
    }

    // 判断是否存在时，同样计算哈希值匹配
    fn contains<K: Hash>(&self, key: &K) -> bool {
        let mut hasher = std::collections::hash_map::DefaultHasher::new();
        key.hash(&mut hasher);
        self.inner.contains(&hasher.finish())
    }
}

// 仅存哈希值的映射
struct HashOnlyMap<V> {
    inner: HashMap<u64, V>,
}

impl<V> HashOnlyMap<V> {
    fn new() -> Self {
        Self { inner: HashMap::new() }
    }

    fn insert<K: Hash>(&mut self, key: &K, value: V) -> Option<V> {
        let mut hasher = std::collections::hash_map::DefaultHasher::new();
        key.hash(&mut hasher);
        self.inner.insert(hasher.finish(), value)
    }

    fn get<K: Hash>(&self, key: &K) -> Option<&V> {
        let mut hasher = std::collections::hash_map::DefaultHasher::new();
        key.hash(&mut hasher);
        self.inner.get(&hasher.finish())
    }
}

注意：如果用DefaultHasher这种非加密哈希，碰撞概率会高一些。如果要降低风险，可以换成SHA-256这类加密哈希，把哈希值类型改成[u8; 32]。

2. 进阶实现：双哈希校验（几乎避免碰撞） #

如果不能接受任何碰撞风险，可以存储两个不同哈希算法生成的哈希值，既大幅减少内存占用，又能把碰撞概率降到几乎为零：

use std::collections::HashMap;
use std::hash::{Hash, Hasher};
use sha2::{Sha256, Digest};

// 双哈希校验的映射
struct DoubleHashMap<V> {
    inner: HashMap<(u64, [u8; 32]), V>,
}

impl<V> DoubleHashMap<V> {
    fn new() -> Self {
        Self { inner: HashMap::new() }
    }

    fn insert<K: AsRef<[u8]> + Hash>(&mut self, key: &K, value: V) -> Option<V> {
        // 第一个哈希用标准库默认实现
        let mut hasher = std::collections::hash_map::DefaultHasher::new();
        key.hash(&mut hasher);
        let hash1 = hasher.finish();
        
        // 第二个哈希用SHA-256加密哈希
        let hash2 = Sha256::digest(key.as_ref()).into();
        
        self.inner.insert((hash1, hash2), value)
    }

    fn get<K: AsRef<[u8]> + Hash>(&self, key: &K) -> Option<&V> {
        let mut hasher = std::collections::hash_map::DefaultHasher::new();
        key.hash(&mut hasher);
        let hash1 = hasher.finish();
        let hash2 = Sha256::digest(key.as_ref()).into();
        
        self.inner.get(&(hash1, hash2))
    }
}

这种方式下，两个不同键同时生成相同双哈希值的概率可以忽略不计，同时内存占用远小于存储完整的大键。

3. 封装对齐标准库接口 #

可以给自定义的集合/映射实现Default、Extend等标准trait，让它的用法和标准库的HashSet/HashMap尽量一致，方便后续替换和维护。

内容的提问来源于stack exchange，提问作者Anders