6

I'm trying to implement a toy search algorithm and need to maintain a set of explored states. A state is a struct:

type VWState struct { botLocation VWCoords dirtLocations []VWCoords }

My first thought was that a simple Set could be implemented using a map[VWState]bool, but I can't seem to figure out a way to make it work. If I try to use a VWState as a key to a map, I get the following panic:

Panic: runtime error: hash of unhashable type vw.VWState (PC=0x40EB0D)

Is there a way to make this work? Can I implement a custom hashing function for the struct, or should I be looking at some other ways to implement this?

Any help would be greatly appreciated.

Improve this question

2 Answers 2

Reset to default
4

You can use a pointer to your struct as a map key:

map[*VWState]bool

If you want to be able to compare equivalent structs, you can create a method to output a key for the map. String() would be convenient, since you could also use it to print your struct, or tie in a hash function and output something shorter, even an int.

Something as simple as this may suffice, though you could make the output shorter if you like (being careful not to recursively call String() in your format line):

func (s VWState) String() string { return fmt.Sprintf("%#v", s) } func main() { m := make(map[string]bool) s := VWState{} m[s.String()] = true }
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

This change makes it compile, but am I correct in thinking this would use the hash of the pointer itself, and thus would not detect two different struct instances with equivalent contents? If so, is there any way to achieve that behavior?
Yes, that's correct. If you want equivalent structs to have the same key, you'll need to provide some way to generate that key.
Do you know if the language offers any tools for implementing that behavior such that it would work with the built-in maps? Something along the lines of Java's hashCode() or Python's __hash__(), or should I use a map[int]bool and extract the hash manually before inserting?
I added an example with String(). There's no magic like that in Go, you'd have to create a hash method of your own to output a unique int. If you use a full string representation though, you can rely on the map implementation's hashing to ensure you don't have collisions.
Using the string representation as a key does the trick. Thanks!
2

If there is a sensible maximum length for dirtLocations then you could use an array instead of a slice. Arrays are hashable (provided the element is hashable).

type VWState struct { botLocation VWCoords dirtLocations [4]VWCoords }

You'll then need to either add a count of the number of valid dirtLocations or detect the zero value of VWCoords to work out how many slots in dirtLocations are valid.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.