面试题：Rust HashMap自定义哈希函数与高效访问

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

// 定义结构体
#[derive(Eq)]
struct MyStruct {
    id: u32,
    name: String,
}

// 实现 Hash trait
impl Hash for MyStruct {
    fn hash<H: Hasher>(&self, state: &mut H) {
        // 首先对 id 进行哈希，u32 类型有稳定且高效的哈希实现
        self.id.hash(state);
        // 然后对 name 进行哈希，String 类型也有自己的哈希实现
        self.name.hash(state);
    }
}

fn main() {
    let mut map = HashMap::new();
    let key1 = MyStruct { id: 1, name: "Alice".to_string() };
    let key2 = MyStruct { id: 2, name: "Bob".to_string() };

    map.insert(key1, "Value for Alice");
    map.insert(key2, "Value for Bob");

    if let Some(value) = map.get(&MyStruct { id: 1, name: "Alice".to_string() }) {
        println!("Value for key1: {}", value);
    }
}

哈希函数设计思路

组合多个字段的哈希值：结构体MyStruct有两个字段id和name，分别对它们调用hash方法。这样可以充分利用每个字段的特征，生成一个综合的哈希值。如果只对其中一个字段进行哈希，例如只对id哈希，那么当id相同但name不同时，两个不同的MyStruct实例会有相同的哈希值，这会导致哈希冲突增加。
使用标准库类型的默认哈希实现：u32和String类型在标准库中都有经过优化的哈希实现。直接复用这些实现可以保证哈希的稳定性和效率。

对访问效率的影响

减少哈希冲突：一个好的哈希函数可以尽量减少哈希冲突，即不同的键映射到相同的哈希值的情况。在上述实现中，通过组合多个字段的哈希值，使得不同的MyStruct实例有更大的概率产生不同的哈希值。哈希冲突减少后，HashMap在查找、插入和删除操作时，平均情况下的时间复杂度更接近理想的O(1)。
均匀分布：好的哈希函数还能使键在哈希表中均匀分布。如果哈希函数设计不当，可能导致键集中在哈希表的某些区域，造成局部的高负载，进而影响访问效率。通过组合多个字段的哈希值，有助于实现键在哈希表中的均匀分布，提高整体的访问性能。

星途面试题库

面试题：Rust HashMap自定义哈希函数与高效访问

知识考点

面试题答案

哈希函数设计思路

对访问效率的影响