What do I need to do to Hash a HashSet<Rc<My>>

#1

I would like to do the following:

    #[derive(Hash, Eq, PartialEq, Debug)]
    struct My {
        a: HashSet<Rc<My>>,
    }

But im getting the error:

    error[E0277]: the trait bound `std::collections::HashSet<std::rc::Rc<My>>: std::hash::Hash` is not satisfied
      --> src/main.rs:13:5
       |
    13 |     a: HashSet<Rc<My>>,
       |     ^^^^^^^^^^^^^^^^^^ the trait `std::hash::Hash` is not implemented for `std::collections::HashSet<std::rc::Rc<My>>`
       |
       = note: required by `std::hash::Hash::hash`

Now my question is:

What do I need to do to get this to compile in an idiomatic way?

0 Likes

#2

Why do you need to use a HashSet? Could you use a BTreeSet?

Because HashSet doesn’t guarantee an order to its elements, even if they are inserted in the same order, you can’t give a sensible implementation of Hash without copying all of the elements over to another structure and sorting it, then hashing. Therefore HashSet cannot implement Hash. BTreeSet doesn’t have this issue, it needs it’s elements to be Ord and it also implements Ord, so you can have a BTreeSet<BTreeSet<_>>, whereas you can’t have a HashSet<HashSet<_>> (which is very similar to what you are trying to do)

1 Like

#3

Well im desperately trying to work my way through this book (source code link is on that page) in an attempt to use Rust for something more advanced then hello world, and in that book they use the Java HashSet. I wonder how that works there but not in Rust?

0 Likes

#4

Here is the Java implementation of hashCode, which what java.util.HashSet inherits from java.util.AbstractSet.

public int hashCode()
{
   Iterator<E> itr = iterator();
   int hash = 0;
   int pos = size();
   while (--pos >= 0)
     hash += hashCode(itr.next());
   return hash;
}

As you can see it doesn’t depend on the order of the elements, as it is just summing up the hashses of the elements. But in Rust, you can’t do something like this, as you have to go through the Hasher trait, which could plug into a hasher that does depend on order (like the default hasher for HashSet), so you hash a HashSet in Rust.

Note that BTreeSet has all of the set operations that HashSet has, and some more, so it should just be a drop in replacement.

2 Likes

#5

Found an issue that will show up in the BTreeSet later on.

In the docs it says the following:

It is a logic error for an item to be modified in such a way that the item’s ordering relative to any other item, as determined by the Ord trait, changes while it is in the set. This is normally only possible through Cell , RefCell , global state, I/O, or unsafe code.

My type will later have to be a HashSet<Rc<RefCell<My>>> where I will have to merge sets in different My instances.

0 Likes

#6

Is it common for getting into this type of problems when naively trying to translate Java to Rust? And if so what is a better way of doing the translation between codes?

0 Likes

#7

Yeah, it is hard to translate from Java to Rust naively, they are so different that they often use incompatible ways of doing things.

What are you trying to do with My in the end?

0 Likes

#8

See also:

0 Likes

#9

My is just a minimal example for the question. What im doing is a struct:

    pub struct Container {
        group: HashSet<Rc<Container>>,
        amount: f64,
    }

Container will have 3 methods:
get_amount
add_water
connect_to

Container is a container for water, where amount is how much water is in the container and group is all the direct and indirect connections to other Containers. If water is filled to any container that water must be evenly distributed to all connected containers. And if two containers are connected all connections must be merged AND all the water must be split between the new connections so the whole group is evenly distributed. Does that make sense?

Now the book show multiple implementations to the problem in Java and each chapeters optimizes on different attributes in quality code. However I got stuck at even the first reference implementation :slight_smile: when doing it in Rust.

0 Likes

#10

Wouldn’t this also break HashSet? If you change the hash without re-hashing the item, your merging sets aren’t going to work well… Unless I’m misunderstanding how the hash is computed.

1 Like

#11

You could manually implement Hash based on the amount alone, similarly with BTreeSet, you could manually implement Ord and PartialOrd based on the amount alone.

1 Like

#12

I’m pretty sure that what you really need is a graph , not a set of sets. Try crate petgraph, which is a de-facto graph library for Rust.

0 Likes

#13

He is trying to follow along a book for learning purposes, so using other crates would be counter-productive.

1 Like

#14

Consider giving each container a unique, immutable ID, and manually implementing hash based on the ID, ignoring the inner containers and the amount. That is essentially how python makes arbitrary instances of custom classes hashable.

1 Like

#15

So I have tried to go with the unique id approach like this:

use std::cell::RefCell;
use std::rc::{Rc, Weak};
use std::collections::HashSet;
use std::{
    sync::atomic::{AtomicUsize, Ordering}
};
use std::hash::{Hash, Hasher};

static OBJECT_COUNTER: AtomicUsize = AtomicUsize::new(0);

#[derive(Hash, Eq, PartialEq, Debug)]
struct Object(usize);

impl Object {
    fn new() -> Self {
        Object(OBJECT_COUNTER.fetch_add(1, Ordering::SeqCst))
    }
}

#[derive(Debug)]
struct My {
    id: Object,
    a: HashSet<Rc<RefCell<My>>>,
}

impl My {
    pub fn new() -> Self {
        My {
            id: Object::new(),
            a: HashSet::with_capacity(1000),
        }
    }
}

impl Hash for My {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.id.hash(state);
    }
}

impl Eq for My {}

impl PartialEq for My {
    fn eq(&self, other: &My) -> bool {
        self.id == other.id
    }
}

fn main() {
    let mut sys = My::new();
    let in_val = Rc::new(RefCell::new(My::new()));
    sys.a.insert(Rc::clone(&in_val));

    match sys.a.get(&in_val) {
        Some(value) => println!("{:?}", value),
        None => println!("There was not value"),
    }

    for sy in sys.a.iter() {
        sy.borrow_mut().a.insert(Rc::new(RefCell::new(My::new())));
    }
    println!("New value is {:?}", sys);
    println!("Capacity is {:?}", sys.a.capacity());
}

However im still getting errors about Hash not being implemented for My, what am I missing?

error[E0277]: the trait bound `std::cell::RefCell<My>: std::hash::Hash` is not satisfied
  --> src/main.rs:28:5
   |
28 |     a: HashSet<Rc<RefCell<My>>>,
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `std::hash::Hash` is not implemented for `std::cell::RefCell<My>`
   |
   = note: required because of the requirements on the impl of `std::hash::Hash` for `std::rc::Rc<std::cell::RefCell<My>>`
   = note: required because of the requirements on the impl of `std::fmt::Debug` for `std::collections::HashSet<std::rc::Rc<std::cell::RefCell<My>>>`
   = note: required because of the requirements on the impl of `std::fmt::Debug` for `&std::collections::HashSet<std::rc::Rc<std::cell::RefCell<My>>>`
   = note: required for the cast to the object type `dyn std::fmt::Debug`

error[E0277]: the trait bound `std::cell::RefCell<My>: std::hash::Hash` is not satisfied
  --> src/main.rs:35:16
   |
35 |             a: HashSet::with_capacity(1000),
   |                ^^^^^^^^^^^^^^^^^^^^^^ the trait `std::hash::Hash` is not implemented for `std::cell::RefCell<My>`
   |
   = note: required because of the requirements on the impl of `std::hash::Hash` for `std::rc::Rc<std::cell::RefCell<My>>`
   = note: required by `<std::collections::HashSet<T>>::with_capacity`

error[E0599]: no method named `insert` found for type `std::collections::HashSet<std::rc::Rc<std::cell::RefCell<My>>>` in the current scope
  --> src/main.rs:57:11
   |
57 |     sys.a.insert(Rc::clone(&in_val));
   |           ^^^^^^
   |
   = note: the method `insert` exists but the following trait bounds were not satisfied:
           `std::rc::Rc<std::cell::RefCell<My>> : std::hash::Hash`

error[E0599]: no method named `get` found for type `std::collections::HashSet<std::rc::Rc<std::cell::RefCell<My>>>` in the current scope
  --> src/main.rs:59:17
   |
59 |     match sys.a.get(&in_val) {
   |                 ^^^
   |
   = note: the method `get` exists but the following trait bounds were not satisfied:
           `std::rc::Rc<std::cell::RefCell<My>> : std::hash::Hash`

error[E0599]: no method named `iter` found for type `std::collections::HashSet<std::rc::Rc<std::cell::RefCell<My>>>` in the current scope
  --> src/main.rs:64:21
   |
64 |     for sy in sys.a.iter() {
   |                     ^^^^
   |
   = note: the method `iter` exists but the following trait bounds were not satisfied:
           `std::rc::Rc<std::cell::RefCell<My>> : std::hash::Hash`

error[E0599]: no method named `capacity` found for type `std::collections::HashSet<std::rc::Rc<std::cell::RefCell<My>>>` in the current scope
  --> src/main.rs:68:40
   |
68 |     println!("Capacity is {:?}", sys.a.capacity());
   |                                        ^^^^^^^^
   |
   = note: the method `capacity` exists but the following trait bounds were not satisfied:
           `std::rc::Rc<std::cell::RefCell<My>> : std::hash::Hash`

error: aborting due to 6 previous errors
0 Likes