How to make composite key for a hash map in go

Question

First, my definition of composite key - two ore more values combine to make the key. Not to confuse with composite keys in databases.

My goal is to save computed values of pow(x, y) in a hash table, where x and y are integers. This is where I need ideas on how to make a key, so that given x and y, I can look it up in the hash table, to find pow(x,y).

For example:

pow(2, 3) => {key(2,3):8}

What I want to figure out is how to get the map key for the pair (2,3), i.e. the best way to generate a key which is a combination of multiple values, and use it in hash table.

Answer 1

The easiest and most flexible way is to use a struct as the key type, including all the data you want to be part of the key, so in your case:

type Key struct {
    X, Y int
}

And that's all. Using it:

m := map[Key]int{}
m[Key{2, 2}] = 4
m[Key{2, 3}] = 8

fmt.Println("2^2 = ", m[Key{2, 2}])
fmt.Println("2^3 = ", m[Key{2, 3}])

Output (try it on the Go Playground):

2^2 =  4
2^3 =  8

Spec: Map types: You may use any types as the key where the comparison operators == and != are fully defined, and the above Key struct type fulfills this.

Spec: Comparison operators: Struct values are comparable if all their fields are comparable. Two struct values are equal if their corresponding non-blank fields are equal.

One important thing: you should not use a pointer as the key type (e.g. *Key), because comparing pointers only compares the memory address, and not the pointed values.

Also note that you could also use arrays (not slices) as key type, but arrays are not as flexible as structs. You can read more about this here: Why have arrays in Go?

This is how it would look like with arrays:

type Key [2]int

m := map[Key]int{}
m[Key{2, 2}] = 4
m[Key{2, 3}] = 8

fmt.Println("2^2 = ", m[Key{2, 2}])
fmt.Println("2^3 = ", m[Key{2, 3}])

Output is the same. Try it on the Go Playground.

Answer 2

Go can't make a hash of a slice of ints.

Therefore the way I would approach this is mapping a struct to a number.

Here is an example of how that could be done:

package main

import (
    "fmt"
)

type Nums struct {
    num1 int
    num2 int
}

func main() {
    powers := make(map[Nums]int)
    numbers := Nums{num1: 2, num2: 4}

    powers[numbers] = 6

    fmt.Printf("%v", powers[input])
}

I hope that helps

Answer 3

Your specific problem is nicely solved by the other answers. I want to add an additional trick that may be useful in some corner cases.

Given that map keys must be comparable, you can also use interfaces. Interfaces are comparable if their dynamic values are comparable.

This allows you to essentially partition the map, i.e. to use multiple types of keys within the same data structure. For example if you want to store in your map n-tuples (it wouldn't work with arrays, because the array length is part of the type).

The idea is to define an interface with a dummy method (but it can surely be not dummy at all), and use that as map key:

type CompKey interface {
    isCompositeKey() bool
}

var m map[CompKey]string

At this point you can have arbitrary types implementing the interface, either explicitly or by just embedding it.

In this example, the idea is to make the interface method unexported so that other structs may just embed the interface without having to provide an actual implementation — the method can't be called from outside its package. It will just signal that the struct is usable as a composite map key.

type AbsoluteCoords struct {
    CompKey
    x, y int
}

type RelativeCoords struct {
    CompKey
    x, y int
}

func foo() {
    p := AbsoluteCoords{x: 1, y: 2}
    r := RelativeCoords{x: 10, y: 20}

    m[p] = "foo"
    m[r] = "bar"

    fmt.Println(m[AbsoluteCoords{x: 10, y: 20}]) // "" (empty, types don't match)
    
    fmt.Println(m[RelativeCoords{x: 10, y: 20}]) // "bar" (matches, key present)
}

Of course nothing stops you from declaring actual methods on the interface, that may be useful when ranging over the map keys.

The disadvantage of this interface key is that it is now your responsibility to make sure the implementing types are actually comparable. E.g. this map key will panic:

type BadKey struct {
    CompKey
    nonComparableSliceField []int
}

b := BadKey{nil, []int{1,2}}
m[b] = "bad!" // panic: runtime error: hash of unhashable type main.BadKey

All in all, this might be an interesting approach when you need to keep two sets of K/V pairs in the same map, e.g. to keep some sanity in function signatures or to avoid defining structs with N very similar map fields.

Playground https://play.golang.org/p/0t7fcvSWdy7