如何使指针可散列? [英] How do I make a pointer hashable?

问题描述

在 Rust 中，我想将枚举视为相等，但仍然能够通过指针区分不同的实例.这是一个玩具示例:

使用 self::Piece::*;使用 std::collections::HashMap;#[派生(Eq, PartialEq)]枚举片{车，骑士，}fn 主(){让 mut 位置:HashMap<&Piece, (u8, u8)>= HashMap::new();让 left_rook = Rook;让 right_rook = Rook;position.insert(&left_rook, (0, 0));position.insert(&right_rook, (0, 7));}

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

error[E0277]: trait bound `Piece: std::hash::Hash` 不满足-->src/main.rs:11:52|11 |让 mut 位置:HashMap<&Piece, (u8, u8)>= HashMap::new();|^^^^^^^^^^^^ 特性 `std::hash::Hash` 没有为 `Piece` 实现|= 注意:由于对 `&Piece` 的 `std::hash::Hash` 的 impl 的要求，这是必需的= 注意:`<std::collections::HashMap<K, V>>::new` 需要错误[E0599]:在当前范围内找不到类型`std::collections::HashMap<&Piece, (u8, u8)>`的名为`insert`的方法-->src/main.rs:15:15|15 |position.insert(&left_rook, (0, 0));|^^^^^^|= 注意:方法 `insert` 存在，但不满足以下特征边界:`&Piece : std::hash::Hash`错误[E0599]:在当前范围内找不到类型为`std::collections::HashMap<&Piece, (u8, u8)>`的名为`insert`的方法-->src/main.rs:16:15|16 |position.insert(&right_rook, (0, 7));|^^^^^^|= 注意:方法 `insert` 存在，但不满足以下特征边界:`&Piece : std::hash::Hash`

我希望在我的枚举上定义相等性，以便一个 Rook 等于另一个.但是，我希望能够在我的 positions 哈希图中区分不同的 Rook 实例.

我该怎么做?我不想在 Piece 上定义 Hash，但肯定已经在指针上定义了散列?

解决方案

raw pointers (*const T, *mut Tcode>) 和 references (&T, &mut T) 在 Rust 中.你有一个参考.

Hash 被定义为，用于将引用委托给被引用项的散列:

impl&T { 的哈希fn hash(&self, state: &mut H) {(**self).hash(state);}}

然而，它是 为原始指针定义，如您所愿:

impl*const T { 的哈希fn hash(&self, state: &mut H) {if mem::size_of::() == mem::size_of::() {//细指针state.write_usize(*self as *const () as usize);} 别的 {//胖指针让 (a, b) = 不安全 {*(self as *const Self as *const (usize, usize))};state.write_usize(a);state.write_usize(b);}}}

这行得通:

让 mut 位置 = HashMap::new();position.insert(&left_rook as *const Piece, (0, 0));position.insert(&right_rook as *const Piece, (0, 7));

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

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

如果您使用原始指针，编译器不会阻止您，但是您将有可能导致内存不安全的悬空指针.

在您的情况下，我想我会尝试重构代码，以便在内存地址之外的部分是唯一的.也许只是一些递增的数字:

positions.insert((left_rook, 0), (0, 0));位置插入((right_rook，1)，(0，7))；

如果这看起来不可能，你总是可以Box 给它一个稳定的内存地址.后一种解决方案更类似于 Java 等语言，默认情况下，所有内容都是堆分配的.

<小时>

正如 Francis Gagné 所说::><块引用>

我宁愿将 &'a T 包装在另一个与 *const T 具有相同标识语义的结构中，而不是删除生命周期

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

#[derive(Debug, Eq)]struct RefEquality<'a, T>(&'a T);impl'a，T>std::hash::Hash for RefEquality<'a, T>;{fn hash(&self, state: &mut H)在哪里H: std::hash::Hasher,{(self.0 as *const T).hash(state)}}impl<'a,'b,T>PartialEq<RefEquality<'b，T>对于 RefEquality 'a，T>{fn eq(&self, other: &RefEquality<'b, T>) ->布尔{self.0 as *const T == other.0 as *const T}}

然后使用它:

positions.insert(RefEquality(&left_rook), (0, 0));位置.插入(RefEquality(&right_rook)，(0, 7))；

In Rust, I want to treat enums as equal, but still be able to distinguish different instances by pointer. Here's a toy example:

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

However, the compiler wants me to define Hash on 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`

I want equality defined on my enums so that one Rook is equal to another. However, I want to be able to distinguish different Rook instances in my positions hashmap.

How do I do this? I don't want to define Hash on Piece, but surely hashing is already defined on pointers?

解决方案

There's a difference between raw pointers (*const T, *mut T) and references (&T, &mut T) in Rust. You have a reference.

Hash is defined for references as delegating to the hash of the referred-to item:

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

However, it is defined for raw pointers as you desire:

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

And that works:

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

However, using either references or raw pointers here is iffy at best.

If you use a reference, the compiler will stop you from using the hashmap once you have moved the values you have inserted as the reference will no longer be valid.

If you use raw pointers, the compiler won't stop you, but then you will have dangling pointers which can lead to memory unsafety.

In your case, I think I'd try to restructure the code so that a piece is unique beyond the memory address. Perhaps just some incremented number:

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

If that seems impossible, you can always Box the piece to give it a stable memory address. This latter solution is more akin to languages like Java where everything is heap-allocated by default.

---

As Francis Gagné says:

I'd rather wrap a &'a T in another struct that has the same identity semantics as *const T than have the lifetime erased

You can create a struct that handles reference equality:

#[derive(Debug, Eq)]
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
    }
}

And then use that:

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

这篇关于如何使指针可散列?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！