如何使指针可哈希？

Question

在 Rust 中，我希望将枚举视为平等的，但仍然能够通过指针区分不同的实例。这是一个玩具示例：

use self::Piece::*;
use std::collections::HashMap;

#[derive(Eq, PartialEq)]
enum Piece {
    Rook,
    Knight,
}

fn main() {
    let mut positions: HashMap<&Piece, (u8, u8)> = HashMap::new();
    let left_rook = Rook;
    let right_rook = Rook;

    positions.insert(&left_rook, (0, 0));
    positions.insert(&right_rook, (0, 7));
}

但是，编译器要我在

Hash

上定义

Piece

：

error[E0277]: the trait bound `Piece: std::hash::Hash` is not satisfied
  --> src/main.rs:11:52
   |
11 |     let mut positions: HashMap<&Piece, (u8, u8)> = HashMap::new();
   |                                                    ^^^^^^^^^^^^ the trait `std::hash::Hash` is not implemented for `Piece`
   |
   = note: required because of the requirements on the impl of `std::hash::Hash` for `&Piece`
   = note: required by `<std::collections::HashMap<K, V>>::new`

error[E0599]: no method named `insert` found for type `std::collections::HashMap<&Piece, (u8, u8)>` in the current scope
  --> src/main.rs:15:15
   |
15 |     positions.insert(&left_rook, (0, 0));
   |               ^^^^^^
   |
   = note: the method `insert` exists but the following trait bounds were not satisfied:
           `&Piece : std::hash::Hash`

error[E0599]: no method named `insert` found for type `std::collections::HashMap<&Piece, (u8, u8)>` in the current scope
  --> src/main.rs:16:15
   |
16 |     positions.insert(&right_rook, (0, 7));
   |               ^^^^^^
   |
   = note: the method `insert` exists but the following trait bounds were not satisfied:
           `&Piece : std::hash::Hash`

我想在我的枚举上定义相等性，以便一个

Rook

等于另一个。但是，我希望能够在我的

Rook

哈希图中区分不同的

positions

实例。

我该怎么做？我不想在

Hash

上定义

Piece

，但肯定已经在指针上定义了散列？

Answer 1

Rust 中的原始指针（

*const T

，

*mut T

）和引用（

&T

，

&mut T

）是有区别的。你有一个参考。

Hash

为引用定义 委托给所引用项目的哈希值：

impl<T: ?Sized + Hash> Hash for &T {
    fn hash<H: Hasher>(&self, state: &mut H) {
        (**self).hash(state);
    }
}

但是，它是为原始指针定义的，如您所愿：

impl<T: ?Sized> Hash for *const T {
    fn hash<H: Hasher>(&self, state: &mut H) {
        if mem::size_of::<Self>() == mem::size_of::<usize>() {
            // Thin pointer
            state.write_usize(*self as *const () as usize);
        } else {
            // Fat pointer
            let (a, b) = unsafe {
                *(self as *const Self as *const (usize, usize))
            };
            state.write_usize(a);
            state.write_usize(b);
        }
    }
}

那行得通：

let mut positions = HashMap::new();
positions.insert(&left_rook as *const Piece, (0, 0));
positions.insert(&right_rook as *const Piece, (0, 7));

但是，在这里使用引用或原始指针充其量是不确定的。

如果您使用引用，一旦您移动了您插入的值，编译器将阻止您使用 hashmap，因为引用将不再有效。

如果你使用原始指针，编译器不会阻止你，但是你会有悬空指针，这会导致内存不安全。

在你的情况下，我想我会尝试重组代码，以便一段在内存地址之外是唯一的。也许只是一些递增的数字：

positions.insert((left_rook, 0), (0, 0));
positions.insert((right_rook, 1), (0, 7));

如果这看起来不可能，你总是可以

Box

给它一个稳定的内存地址。后一种解决方案更类似于 Java 等语言，默认情况下所有内容都是堆分配的。

---

正如Francis Gagné所说：

我宁愿将

&'a T

包装在另一个与

*const T

具有相同身份语义的结构中，也不愿删除生命周期

您可以创建一个结构来处理引用相等性：

#[derive(Debug)]
struct RefEquality<'a, T>(&'a T);

impl<'a, T> std::hash::Hash for RefEquality<'a, T> {
    fn hash<H>(&self, state: &mut H)
    where
        H: std::hash::Hasher,
    {
        (self.0 as *const T).hash(state)
    }
}

impl<'a, 'b, T> PartialEq<RefEquality<'b, T>> for RefEquality<'a, T> {
    fn eq(&self, other: &RefEquality<'b, T>) -> bool {
        self.0 as *const T == other.0 as *const T
    }
}

impl<'a, T> Eq for RefEquality<'a, T> {}

然后使用：

positions.insert(RefEquality(&left_rook), (0, 0));
positions.insert(RefEquality(&right_rook), (0, 7));

Answer 2

除了当前的答案之外，您还可以通过在原始指针上引入一个包装器来帮助 Rust 编译器跟踪引用，从而在使用内存地址作为键的同时增强内存安全性。

你不需要自己实现。 by_address 是一个有用的箱子，可以让你这样做。我会复制他们的演示如下：

use by_address::ByAddress;
use std::rc::Rc;

let rc = Rc::new(5);
let x = ByAddress(rc.clone());
let y = ByAddress(rc.clone());

// x and y are two pointers to the same address:
assert_eq!(x, y);

let z = ByAddress(Rc::new(5));

// *x and *z have the same value, but not the same address:
assert_ne!(x, z);