面试题：Rust中HashMap哈希函数的基础选择与特性

默认哈希函数：
- 在Rust的HashMap中，默认使用的哈希函数是FxHasher。FxHasher是一种快速且非密码学安全的哈希函数。它旨在提供良好的性能，特别是在大量数据插入和查找的场景下。
在不同数据类型上的应用特点：
- 基本数据类型：
  - 对于像u8、u16、u32、u64、i8、i16、i32、i64等整数类型，FxHasher通常会直接基于这些整数的位模式进行计算，生成一个哈希值。由于整数类型的表示相对简单直接，哈希计算速度较快，能够在较短时间内将不同的整数值映射到不同的哈希桶中，减少哈希冲突。
  - 对于f32和f64浮点数类型，FxHasher会将浮点数的二进制表示作为整数来处理，并基于此进行哈希计算。虽然浮点数的二进制表示相对复杂，但FxHasher仍然能以较快的速度生成哈希值，不过由于浮点数的精度问题，在某些边界情况下可能会产生与预期略有不同的哈希分布。
- 复合数据类型：
  - 对于String类型，FxHasher会遍历字符串中的每个字符，并结合字符的编码值（如UTF - 8编码值）进行哈希计算。通过这种方式，不同内容的字符串能够得到不同的哈希值，在实际应用中，对于常见的字符串操作，FxHasher能提供较好的哈希分布，减少冲突。
  - 对于Vec类型，FxHasher会对Vec中的每个元素依次进行哈希计算，并将这些哈希值以某种方式组合（例如通过异或操作等）得到整个Vec的哈希值。这使得不同元素内容的Vec能有不同的哈希值，对于元素较少的Vec，哈希计算速度较快，但对于元素较多的Vec，哈希计算时间会相应增加。
对自定义类型使用HashMap时选择合适哈希函数：
- 实现Hash trait：如果自定义类型没有内部可变状态且其字段类型都实现了Hash trait，可以通过derive宏来自动实现Hash trait。例如：

use std::collections::HashMap;
use std::hash::Hash;

#[derive(Hash, Eq, PartialEq)]
struct Point {
    x: i32,
    y: i32,
}

fn main() {
    let mut map = HashMap::new();
    let point = Point { x: 10, y: 20 };
    map.insert(point, "Some value");
}

手动实现Hash trait：如果自定义类型的字段不能简单地使用derive宏来实现Hash，或者需要自定义哈希逻辑，可以手动实现Hash trait。在实现中，要确保不同值的实例能产生不同的哈希值。例如，对于一个包含Vec和String的自定义类型：

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

struct CustomType {
    data: Vec<i32>,
    name: String,
}

impl Hash for CustomType {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.data.hash(state);
        self.name.hash(state);
    }
}

impl PartialEq for CustomType {
    fn eq(&self, other: &Self) -> bool {
        self.data == other.data && self.name == other.name
    }
}

impl Eq for CustomType {}

fn main() {
    let mut map = HashMap::new();
    let custom = CustomType {
        data: vec![1, 2, 3],
        name: "example".to_string(),
    };
    map.insert(custom, "Some value");
}

在手动实现Hash trait时，要注意与PartialEq和Eq trait的一致性，因为HashMap在比较键时会同时使用Hash和PartialEq。

星途面试题库

面试题：Rust中HashMap哈希函数的基础选择与特性

知识考点

面试题答案