rust - 如何在 Rust 中的外部数据类型上实现 std::hash::Hash 特征？

标签 rust hashset refcell

我有一个基本的 LinkedList 实现，我想在其中迭代我的节点，并将这些节点添加到 HashSet 中。但是，我无法执行此操作，因为我的节点被包裹在 Rc<RefCell<Node<T>>> 中。 ，并且我在实现 std::hash::Hash 时遇到问题我的特质std::cell::Ref<'_, Node<T>>类型。

如何实现 Hash这个例子的特征？或者我错过了什么？

下面是一个失败测试用例的示例，该用例尝试将一些节点添加到 HashSet :

这是 Rust Playground 上的源代码: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=d79329dcb70ba54ff803dbcd93bd47d0

来源如下:

use std::cell::{RefCell, Ref};
use std::fmt;
use std::fmt::Display;
use std::ptr;
use std::rc::Rc;
use std::hash::{Hash, Hasher};
use std::collections::HashSet;

pub type NodeRef<T> = Rc<RefCell<Node<T>>>;

#[derive(Debug)]
pub struct LinkedList<T> {
    pub head: Option<NodeRef<T>>,
}

// #[derive(Hash)]
pub struct Node<T> {
    pub data: T,
    pub next: Option<NodeRef<T>>,
}

impl<T: fmt::Debug> fmt::Debug for Node<T> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "Node {{ data: {:?}, next: {:?} }}", self.data, self.next)
    }
}

impl<T> LinkedList<T>
where
    T: std::cmp::Eq
        + std::hash::Hash
        + std::clone::Clone
        + std::cmp::PartialOrd
        + std::cmp::PartialOrd
        + std::fmt::Debug,
{
    pub fn new() -> Self {
        Self { head: None }
    }

    pub fn append(&mut self, new_value: T) {
        if let Some(tail) = self.tail() {
            tail.borrow_mut().next = Some(Rc::new(RefCell::new(Node {
                data: new_value,
                next: None,
            })));
        } else {
            self.head = Some(Rc::new(RefCell::new(Node {
                data: new_value,
                next: None,
            })));
        }
    }

    pub fn tail(&self) -> Option<NodeRef<T>> {
        for node in self.iter() {
            if let None = node.clone().borrow().next {
                return Some(node);
            }
        }
        None
    }

    pub fn iter(&self) -> Iter<T> {
        Iter {
            next: self.head.clone(),
        }
    }
}

#[derive(Debug)]
pub struct Iter<T> {
    next: Option<NodeRef<T>>,
}

impl<'a, T> Iterator for Iter<T> {
    type Item = NodeRef<T>;

    fn next(&mut self) -> Option<Self::Item> {
        if let Some(next) = self.next.clone() {
            // Set the new self.next:
            if let Some(new_next) = next.borrow().next.clone() {
                self.next = Some(new_next);
            } else {
                self.next = None;
            }

            return Some(next);
        } else {
            None
        }
    }
}

impl<T: Display> Display for LinkedList<T> {
    fn fmt(&self, w: &mut std::fmt::Formatter) -> std::result::Result<(), std::fmt::Error> {
        write!(w, "[")?;
        let mut node = self.head.clone();
        while let Some(n) = node {
            write!(w, "{}", n.borrow().data)?;
            node = n.borrow().next.clone();
            if node.is_some() {
                write!(w, ", ")?;
            }
        }
        write!(w, "]")
    }
}

impl<T: PartialEq> PartialEq for Node<T> {
    fn eq(&self, other: &Self) -> bool {
        if ptr::eq(self, other) {
            // For loop detection - if the nodes share the same
            // reference, they are equal.
            return true;
        }
        self.data == other.data && self.next == other.next
    }

    fn ne(&self, other: &Self) -> bool {
        if !ptr::eq(self, other) {
            return true;
        }
        self.data != other.data && self.next == other.next
    }
}

// By implementing Eq, we are making the promise that our
// implementation of PartialEq is reflexive.
impl<T: Eq> Eq for Node<T> {
}


impl<T: Hash> std::hash::Hash for Node<T> {
    fn hash<H>(&self, state: &mut H)
        where H: std::marker::Sized + Hasher
    {
        self.data.hash(state);
        if let Some(next) = self.next.clone() {
            next.borrow().hash(state);
        }
    }
}

// // TODO: HELP!!!
// // Trying to implement Hash trait for Ref<'_, Node<T>>:
// impl<Node: Hash> std::hash::Hash for Ref<'_, Node> {
//     fn hash<H: Hasher>(&self, state: &mut H) {
//         self.data.hash(state);
//         if let Some(next) = self.next.clone() {
//             next.borrow().hash(state);
//         }
//     }
// }

impl<T: PartialEq> PartialEq for LinkedList<T> {
    fn eq(&self, other: &Self) -> bool {
        self.head == other.head
    }

    fn ne(&self, other: &Self) -> bool {
        self.head != other.head
    }
}

impl<T: Eq + std::fmt::Debug> Eq for LinkedList<T> {}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn eq() {
        let mut list = LinkedList::new();
        list.append(1);
        list.append(2);
        list.append(3);
        let mut list2 = LinkedList::new();
        list2.append(1);
        list2.append(2);
        list2.append(3);

        assert_eq!(list, list2);
        list2 = LinkedList::new();
        list2.append(3);
        assert_ne!(list, list2);
        list = LinkedList::new();
        list.append(3);
        assert_eq!(list, list2);
    }

    #[test]
    fn append() {
        let mut list = LinkedList::new();
        list.append(1);
        list.append(2);
        list.append(3);
        let mut list2 = LinkedList::new();
        list2.append(1);
        list2.append(2);
        list2.append(3);

        assert_eq!(list, list2);
        list2.append(1);
        assert_ne!(list, list2);
        list.append(1);
        assert_eq!(list, list2);
    }

    // TODO: fix this test case!
    #[test]
    fn hashset_iter_nodes() {
        let mut list = LinkedList::new();
        list.append(1);
        list.append(2);
        list.append(3);

        // the trait bound `std::cell::Ref<'_, Node<{integer}>>:
        // std::hash::Hash` is not satisfied (the trait `std::hash::Hash` is
        // not implemented for `std::cell::Ref<'_, Node<{integer}>>`)
        // [E0277]
        // the trait bound `std::cell::Ref<'_, Node<{integer}>>:
        // std::cmp::Eq` is not satisfied (the trait `std::cmp::Eq` is
        // not implemented for `std::cell::Ref<'_, Node<{integer}>>`)
        // [E0277]
        let mut set = HashSet::new();
        // iterate over nodes, adding each node to our hashset:
        for node in list.iter() {
            println!("iterating over node: {:?}", node);
            set.insert(&node.borrow());
        }
        assert_eq!(set.len(), 3);
    }
}

最佳答案

要将现有类型添加到 HashSet，我遵循 @rodrigo's advice在上面的注释中，并定义了一个新的包装类型:

pub struct HashedNode<T>(Rc<RefCell<Node<T>>>);

这样做使我能够实现 std::hash::Hash我的特质Rc<RefCell<Node<T>>>类型，如下所示:

impl<T: Hash> std::hash::Hash for HashedNode<T> {
  fn hash<H: Hasher>(&self, state: &mut H) {
     // ... etc
  }
}

这允许我定义一个 HashSet 并根据需要使用它:

let mut set: HashSet<HashedNode<i32>> = HashSet::new();

请注意，还需要一些其他解决方法，例如实现 Eq我的新特质 HashedNode类型，以及实现 From特质和from_node实用方法。

这是上面示例中的完成代码:

use std::cell::{RefCell, Ref};
use std::fmt;
use std::fmt::Display;
use std::ptr;
use std::rc::Rc;
use std::hash::{Hash, Hasher};
use std::collections::HashSet;

pub type NodeRef<T> = Rc<RefCell<Node<T>>>;

// Used specifically for hashing needs, like HashSet:
pub struct HashedNode<T>(NodeRef<T>);

#[derive(Debug)]
pub struct LinkedList<T> {
    pub head: Option<NodeRef<T>>,
}

// #[derive(Hash)]
pub struct Node<T> {
    pub data: T,
    pub next: Option<NodeRef<T>>,
}

impl<T: fmt::Debug> fmt::Debug for Node<T> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "Node {{ data: {:?}, next: {:?} }}", self.data, self.next)
    }
}

impl<T> LinkedList<T>
where
    T: std::cmp::Eq
        + std::hash::Hash
        + std::clone::Clone
        + std::cmp::PartialOrd
        + std::cmp::PartialOrd
        + std::fmt::Debug,
{
    pub fn new() -> Self {
        Self { head: None }
    }

    pub fn append(&mut self, new_value: T) {
        if let Some(tail) = self.tail() {
            tail.borrow_mut().next = Some(Rc::new(RefCell::new(Node {
                data: new_value,
                next: None,
            })));
        } else {
            self.head = Some(Rc::new(RefCell::new(Node {
                data: new_value,
                next: None,
            })));
        }
    }

    pub fn tail(&self) -> Option<NodeRef<T>> {
        for node in self.iter() {
            if let None = node.clone().borrow().next {
                return Some(node);
            }
        }
        None
    }

    pub fn iter(&self) -> Iter<T> {
        Iter {
            next: self.head.clone(),
        }
    }
}

#[derive(Debug)]
pub struct Iter<T> {
    next: Option<NodeRef<T>>,
}

impl<'a, T> Iterator for Iter<T> {
    type Item = NodeRef<T>;

    fn next(&mut self) -> Option<Self::Item> {
        if let Some(next) = self.next.clone() {
            // Set the new self.next:
            if let Some(new_next) = next.borrow().next.clone() {
                self.next = Some(new_next);
            } else {
                self.next = None;
            }

            return Some(next);
        } else {
            None
        }
    }
}

impl<T: Display> Display for LinkedList<T> {
    fn fmt(&self, w: &mut std::fmt::Formatter) -> std::result::Result<(), std::fmt::Error> {
        write!(w, "[")?;
        let mut node = self.head.clone();
        while let Some(n) = node {
            write!(w, "{}", n.borrow().data)?;
            node = n.borrow().next.clone();
            if node.is_some() {
                write!(w, ", ")?;
            }
        }
        write!(w, "]")
    }
}

impl<T: PartialEq> PartialEq for Node<T> {
    fn eq(&self, other: &Self) -> bool {
        if ptr::eq(self, other) {
            // For loop detection - if the nodes share the same
            // reference, they are equal.
            return true;
        }
        self.data == other.data && self.next == other.next
    }

    fn ne(&self, other: &Self) -> bool {
        if !ptr::eq(self, other) {
            return true;
        }
        self.data != other.data && self.next == other.next
    }
}

// By implementing Eq, we are making the promise that our
// implementation of PartialEq is reflexive.
impl<T: Eq> Eq for Node<T> {
}


impl<T: Hash> std::hash::Hash for HashedNode<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        // TODO: make hash work for nodes that have the same data
        self.0.borrow().data.hash(state);
    }
}

impl<T> From<T> for HashedNode<T> {
    fn from(item: T) -> Self {
        HashedNode(Rc::new(RefCell::new(Node {
            data: item,
            next: None,
        })))
    }
}

impl<T> HashedNode<T> {
    pub fn from_node(node: NodeRef<T>) -> Self {
        HashedNode(node)
    }
}


impl<T: PartialEq> PartialEq for HashedNode<T> {
    fn eq(&self, other: &Self) -> bool {
        if ptr::eq(self, other) {
            // For loop detection - if the nodes share the same
            // reference, they are equal.
            return true;
        }
        let other_node = other.0.borrow();
        let self_node = self.0.borrow();
        self_node.data == other_node.data && self_node.next == other_node.next
    }
}

impl<T: Eq> Eq for HashedNode<T> {}

impl<T: PartialEq> PartialEq for LinkedList<T> {
    fn eq(&self, other: &Self) -> bool {
        self.head == other.head
    }

    fn ne(&self, other: &Self) -> bool {
        self.head != other.head
    }
}

impl<T: Eq + std::fmt::Debug> Eq for LinkedList<T> {}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn eq() {
        let mut list = LinkedList::new();
        list.append(1);
        list.append(2);
        list.append(3);
        let mut list2 = LinkedList::new();
        list2.append(1);
        list2.append(2);
        list2.append(3);

        assert_eq!(list, list2);
        list2 = LinkedList::new();
        list2.append(3);
        assert_ne!(list, list2);
        list = LinkedList::new();
        list.append(3);
        assert_eq!(list, list2);
    }

    #[test]
    fn append() {
        let mut list = LinkedList::new();
        list.append(1);
        list.append(2);
        list.append(3);
        let mut list2 = LinkedList::new();
        list2.append(1);
        list2.append(2);
        list2.append(3);

        assert_eq!(list, list2);
        list2.append(1);
        assert_ne!(list, list2);
        list.append(1);
        assert_eq!(list, list2);
    }

    #[test]
    // Tests that our nodes can be hashed and saved into a set.
    fn hashset_iter_nodes() {
        let node = Rc::new(RefCell::new(Node{ data: 9, next: None}));
        let mut list = LinkedList::new();
        list.append(1);
        list.append(2);
        list.append(3);
        list.append_node(node.clone());

        let mut set: HashSet<HashedNode<i32>> = HashSet::new();
        // iterate over nodes, adding each node to our hashset:
        for node in list.iter() {
            set.insert(HashedNode::from_node(node));
        }
        assert_eq!(set.contains(&HashedNode::from_node(node)), true);
        assert_eq!(set.contains(&HashedNode::from(4)), false);
        assert_eq!(set.len(), 4);
    }
}

关于rust - 如何在 Rust 中的外部数据类型上实现 std::hash::Hash 特征？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55932914/

上一篇：casting - 克隆一个 Rc<RefCell<MyType> 特征对象并转换它

下一篇：rust - 返回实现多个特征的对象——装饰器模式

相关文章：

java - 创建一个HashMap，固定Key对应一个HashSet。出发点

rust - 为什么有时可以从不可变数组中借用 &mut 引用？

java - 了解哈希集

java - Hashset 和 Arraylist 性能

rust - 有效地获取Vec <Ref <'a, T>> from Ref<' a，BTreeSet <T >>

rust - 如何建立一个可变的Vecs池，以便在Drop上重复使用？

concurrency - 为什么 'if let' 会阻止使用 Mutex 的执行？

syntax - 为什么引入 dyn 语法？

rust - 在 Rust 中，向量如何在编译时既是动态的又是已知的？

Rust:如何返回对 Rc<RefCell<HashMap<K, V>> 值的引用？

©2024 IT工具网  联系我们