I cannot put a Rc<RefCell<..>> as a key in a HashMap. The error (below) refers to RefCell not Rc. I do not understand. Since Rc has hash why is the compiler looking inside to the RefCell?
use std::cell::{RefCell};
use std::collections::HashMap;
use std::rc::Rc;
fn main(){
let h:HashMap<Rc<RefCell<usize>>, bool> = HashMap::new();
}
error[E0277]: the trait bound `std::cell::RefCell<usize>: std::hash::Hash` is not satisfied
--> src/main.rs:5:47
|
5 | let h:HashMap<Rc<RefCell<usize>>, bool> = HashMap::new();
| ^^^^^^^^^^^^ the trait `std::hash::Hash` is not implemented for `std::cell::RefCell<usize>`
|
For RefCell::borrow(), the document explicitly states that it may panic if the RefCell already uniquely borrowed. But Hash::hash() doesn't. And I think "hashing" should be infailable operation, so it should never panic except for extreme case like OOM.
For Rc, let's assume we have foo and baz.
let foo: Rc<str> = "baz".into();
let bar: Rc<str> = "baz".into();
foo == bar is true, so they should produce identical hash value. But their allocations are different so as address, so they should be hashed based on the content, not address.
Note that if you want to force this to work, you could always make a wrapper type and implement Hash for it manually:
use std::{
cell::RefCell,
hash::{Hash, Hasher},
ops::Deref,
rc::Rc,
};
#[derive(Debug, PartialEq, Eq)]
pub struct HashingRcRefCell<T>(pub Rc<RefCell<T>>);
impl<T> From<Rc<RefCell<T>>> for HashingRcRefCell<T> {
fn from(val: Rc<RefCell<T>>) -> Self {
HashingRcRefCell(val)
}
}
impl<T> Deref for HashingRcRefCell<T> {
type Target = RefCell<T>;
fn deref(&self) -> &RefCell<T> {
&self.0
}
}
impl<T> Hash for HashingRcRefCell<T>
where
T: Hash,
{
fn hash<H>(&self, state: &mut H)
where
H: Hasher,
{
self.0.borrow().hash(state)
}
}
Even if you get this to work, though, I would not recommend using it. HashMap will misbehave if any key values change, so if you ever use the fact that these keys are in a RefCell, you'll end up with "disappearing" values - if you have bad keys with internal mutability whose hashes and values change, this will happen. Keys you inserted will appear to no longer be in the hashmap, and I believe this can happen even for keys which didn't change (as long as some key in the hashmap changed).
If you have custom PartialEq, Eq and custom Hash implementations which exclude whatever data you're changing, then you can be OK. But otherwise, be warned - this is not a good idea.
And this is likely why RefCell (or any other type that uses interior mutability) doesn't implement Hash, because it would behave badly with HashMap and std doesn't want to encourage that behavior.
It makes no difference to me.
I have a connected graph that may have cycles and traversing that graph I would like to detect cycles.
The graph is implemented with Rc<RefCell<NODE>>, and of course each NODE has Rc<RefCell<NODE>> pointing to other NODEs.
There are other solutions, I am not desperate (I could give each node a ID field (yuck) or I could abandon the whole approach and use a arena algorithm where the nodes reside in a Vec<NODE> and the connections are described as tables of usize pairs, or some thing similar. It is not really important but I find reasoning about the graph easier using a more direct structure.