如何实现与顺序无关的整数列表Hash trait？

你的原实现存在多个严重问题，无法保证相同元素集合（不同顺序）哈希一致，还会导致大量错误的哈希碰撞：

• 不同元素集合可能有相同乘积：比如{2, 3}和{6}的乘积都是6，但它们是完全不同的集合
• 包含0的集合乘积全为0：所有带0的集合都会被判定为哈希相同
• 整数溢出：当元素较大时，乘积会超出usize的范围，溢出后的结果会导致更多无意义的哈希碰撞

正确实现思路 #

因为元素顺序不影响相等性，核心思路是将集合转换为一个顺序固定的表示形式，再对这个固定形式哈希。最直接的方式是先对内部的Vec<usize>进行排序，排序后相同元素的集合不管原顺序如何，都会得到完全一致的有序序列，此时再哈希就能保证相等的集合哈希值相同。

同时必须注意：Hash trait的实现必须和PartialEq、Eq的实现保持一致——相等的实例必须有相同的哈希值，所以需要先正确实现这两个trait。

完整代码实现 #

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

#[derive(Clone, Debug)]
struct PolytopeVertex(Vec<usize>);

// 实现PartialEq：比较排序后的元素序列
impl PartialEq for PolytopeVertex {
    fn eq(&self, other: &Self) -> bool {
        if self.0.len() != other.0.len() {
            return false;
        }
        let mut self_sorted = self.0.clone();
        let mut other_sorted = other.0.clone();
        self_sorted.sort();
        other_sorted.sort();
        self_sorted == other_sorted
    }
}

// 直接继承Eq，因为PartialEq已经满足Eq的要求
impl Eq for PolytopeVertex {}

// 实现Hash：对排序后的序列哈希
impl Hash for PolytopeVertex {
    fn hash<H: Hasher>(&self, state: &mut H) {
        let mut sorted = self.0.clone();
        sorted.sort();
        sorted.hash(state);
    }
}

可选优化 #

如果PolytopeVertex的内部列表会被频繁哈希，可以考虑在结构体中缓存排序后的版本，避免每次哈希都重复排序和克隆：

#[derive(Clone, Debug)]
struct PolytopeVertex {
    original: Vec<usize>,
    sorted: Vec<usize>,
}

impl PolytopeVertex {
    fn new(mut original: Vec<usize>) -> Self {
        let mut sorted = original.clone();
        sorted.sort();
        Self { original, sorted }
    }
}

// PartialEq直接比较缓存的sorted字段
impl PartialEq for PolytopeVertex {
    fn eq(&self, other: &Self) -> bool {
        self.sorted == other.sorted
    }
}

impl Eq for PolytopeVertex {}

// Hash直接使用缓存的sorted字段哈希
impl Hash for PolytopeVertex {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.sorted.hash(state);
    }
}

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