HashMap keyed by Rc<RefCell<..>>

#1

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>`
  |
#2

Rc<T> impl Hash only if T: Hash + ?Sized
https://doc.rust-lang.org/std/rc/struct.Rc.html#impl-Hash

3 Likes
#3

I see. Why is that? Why cannot Rc have a hash value if its contents does not?
Come to that why can RefCell not be hashed?

#4

Presumably because it would have to panic! when it can't borrow.

2 Likes
#5

it being RefCell which will panic using PartialOrd if it cannot borrow. Why is hash different?
it being Rc that should not be a issue.

#6

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.

1 Like
#7

Note that PartialEq for RefCell has to borrow too, and documents:

Panics if the value in either RefCell is currently borrowed.

2 Likes
#8

Are you trying to:

(1) hash by the address fo the Rc<RefCell<...>>
or
(2) hash by the contents of the Rc<RefCell<...>> ?

#9

Fair point, I haven't noticed it.

#10

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.

3 Likes
#11

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.

3 Likes
#12

Why do you have a refcell in the key?

Sidenote, with indexmap you have opt in mutable access to keys, so you could avoid this?

#13

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.

#14

If you are willing to hash by ADDRESS of Rc, rather than the value inside the RefCell, you can use the same technique as:

Instead of using Rc<RefCell> do

pub struct MyWrapper(Rc<RefCell<T>>);

then, using Hash based on address (not value) of Rc you can have "hashing on MyWrapper == hashing on address the Rc points to"

1 Like
#15

What is indexmap? I cannot find it in stdlib

#16

https://crates.io/crates/indexmap

1 Like