CODEWITHSUNDEEP
go
Arch D. Robison
Arch D. Robison

Reputation: 4059

Go map with user-defined key with user-defined equality?

Suppose I have a struct type in Go that I want to use as a key in a map, but I don't want to use Go's builtin equality operation. What's the best way to build such a map?

For a concrete example, here is my key type and equality operation:

type Key struct {
    a *int
}

func Equal(x Key, y Key) bool {
    return *x.a == *y.a
}

How can I build a map that uses Equal for key comparison?

Upvotes: 38

Views: 23931

Answers (3)

Himanshu Jagtap
Himanshu Jagtap

Reputation: 26

I dont think so Go allows to overload Equality methods for specific struct types. Your structs can still act as key, if fields of your struct/nested struct are defined types, eg(int, bool, string) eg

type SmallKey struct {
    b int
}
type Key struct {
    a *SmallKey
}

func main() {
    z := make(map[Key]bool)
    mem := Key{
        a: &SmallKey{b: 1},
    }
    z[mem] = true
    fmt.Println(z)
}

If you have recursive fields in struct, then you can use pointer to your struct as key. eg


type Vertex struct {
    Neighbours []*Vertex 
}

func main() {
   z := make(map[*Vertex]bool)
}

Upvotes: 0

maerics
maerics

Reputation: 156662

Go has strict comparable semantics for values used as map keys. As such, you cannot define your own hash code and equality functions for map keys as you can in many other languages.

However, consider the following workaround. Instead of using the struct instances directly as a keys, use a derived attribute of the struct which is intrinsically usable as a key and has the equality semantics you desire. Often it is simple to derive an integer or string value as a hash code which serves as the identity for an instance.

Importantly, the keys should only collide if they truly represent semantic identity of the value being stored. That is, corresponding values should be truly interchangeable.

For example:

type Key struct {
  a *int
}

func (k *Key) HashKey() int {
  return *(*k).a
}

k1, k2 := Key{intPtr(1)}, Key{intPtr(2)}
m := map[int]string{}
m[k1.HashKey()] = "one"
m[k2.HashKey()] = "two"
// m = map[int]string{1:"one", 2:"two"}
m[k1.HashKey()] // => "one"

Of course, immutability is a critical concern with this approach. In the example above, if you modify the field a then the instance can no longer be used as a hash key because its identity has changed.

Upvotes: 32

evanmcdonnal
evanmcdonnal

Reputation: 48154

This is not possible in Go. There is no operator overloading or 'Equality' method you can override (due to not inheriting from a common base class like in .NET which your example reminds me of). This answer has more information on equality comparisons if you're interested; Is it possible to define equality for named types/structs?

As mentioned in the comments if you want to make something like this work I would recommend using a property on the object as a key. You can define equality based on how you set the value of that property (like it could be a checksum of the objects bytes or something if you're looking for memberwise equality).

Upvotes: 11

Related Questions