如何使指针可哈希？

Question

如何使指针可哈希？

14

在 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));
}

然而，编译器要求我在Piece上定义Hash：

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 等于另一个。然而，我希望能够区分我的 positions 哈希映射中的不同 Rook 实例。

我该怎么做？我不想在 Piece 上定义 Hash，但是指针上已经定义了哈希函数，是吗？

- Wilfred Hughes

风格注意：您不需要 : HashMap<&Piece, (u8, u8)> 类型说明 - 所有内容都可以被推断出来。 - Shepmaster

2个回答

0

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

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

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);

- GZZ

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Shepmaster · Accepted Answer

在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));

然而，在这里使用引用或原始指针都有些危险。如果使用引用，一旦您移动了已插入的值，编译器将阻止您继续使用哈希映射，因为引用将不再有效。如果使用原始指针，编译器不会阻止您，但是您将拥有悬空指针，这可能导致内存不安全。在您的情况下，我认为应该重构代码，使某个部分在内存地址之外是唯一的。也许只是一些增加的数字：

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));