Have *almost* made my struct hashable! :)

help
#1

Hello,

I want to be able to put this struct inside a hashset, in order to only store unique instances. However, I have my own definition of unique...

#[derive(Eq, Debug)]
struct PossibilityReport {
    place: (InventoryIdx, BoardIdx),
    piece: (PieceIdx, RotationIdx),
    next: BoardIdx,
}

impl PartialEq for PossibilityReport {
    fn eq(&self, other: &Self) -> bool {
        self.piece.0 == other.piece.0
            && Side::from(other.piece.1).to_opposite().to_usize() == self.piece.1
            && self.next == other.next
    }
}

I'm a bit confused as to how I should impl Hash on this struct? I Because I thought it's the hash that determines whether something is unique, so should my equality check be included in the hashing somehow?

Looking for some guidance on how Hash and Eq work together.

Thanks!

#2

The hash is only ever used as a pre-check, and then the actual determination is made with ==: It’s ok for two objects that aren’t equal to have the same hash value, but if A == B, then both A and B must have the same hash value.

In this case, you could include self.piece.0 in the hash calculation, but I’m not sure about anything else— it depends on what side::from(other.piece.1).to_opposite().to_usize() is actually calculating.

#3

Ah okay, sounds like just the piece.0 should be hashed, yeah :slight_smile:

So I'm implementing an algorithm that checks for all possible placements and orientations of a piece. Some pieces are symmetrical though, so if a piece is rotated twice (that is to say it is upside down) and it has no effect on the outcome of next then there is no point including it again in the list (hashset).

#4

It seems your struct is not reflexive. It means you shouldn't impl Eq on it.

1 Like
#5

Oh good catch!

So Equality needs to be the prior description, OR one where all things are the same?

impl PartialEq for PossibilityReport {
    fn eq(&self, other: &Self) -> bool {
        self.piece.0 == other.piece.0
            && ((Side::from(other.piece.1).to_opposite().to_usize() == self.piece.1) || (self.piece.1 == other.piece.1))
            && self.next == other.next
    }
}
1 Like
#6

gentle bump.

#7

I think the simplest solution is to have a "canonical" version of PossibilityReport where piece is transformed to the "minimum Side". Then you can eq/hash as normal.

#8

You need to make sure that a.eq(b) returns the same result as b.eq(a), so if you have this clause:

((Side::from(other.piece.1).to_opposite().to_usize() == self.piece.1) || (self.piece.1 == other.piece.1))

This also needs to be true (I can’t tell whether it is already or not):

((Side::from(self.piece.1).to_opposite().to_usize() == other.piece.1) || (self.piece.1 == other.piece.1))
#9

Adding to my previous comment...

Just derive Eq, Hash. Create a key function which creates a PossibilityReport that is equal when it should be. Then populate a HashMap using map.insert(item.key(), item()). At this point, you may decide to create a different struct for the key for flexibility.

Untested example:

impl PossibilityReport {
    fn key(&self) -> PossibilityReport {
        let min_rot = std::cmp::min(self.piece.1, Side::from(self.piece.1).to_opposite().to_usize());
        PossibilityReport {
            place: self.place,
            piece: (self.piece.0, min_rot),
            next: self.next,
        }
    }
}

fn add_to_set(map: &mut HashMap<PossibilityReport, PossibilityReport>,
        item: PossibilityReport) {
    map.insert(item.key(), item);
}