Maps with non-comparable keys

[aind...@gmail.com]

Now that generics is coming along, is there an easy way to extend the builtin map type to use a non-comparable key type? For example, given this constraint

type Key[T any] interface {
        Size() uint64
        Hash(seed uint64) uint64
        Equal(T) bool
}

and a type Foo like

type Foo []int
func (a Foo) Size() uint64 { ... }
func (a Foo) Hash(seed uint64) uint64 { ... }
func (a Foo) Equal(b Foo) bool { ... }

I'd like a map[Foo]struct{}. Is this possible now? Or does the runtime map have to be updated to support this?

[Axel Wagner]

It is not possible and I think it is unlikely to ever happen (though it might be reasonably implemented as a library at some point).

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/a9296c66-7715-45ac-9fce-b1d3bc5b4343n%40googlegroups.com.

[Ian Lance Taylor]

The addition of generics is independent of whether the builtin map
type can support non-comparable key types.

With generics it now becomes possible to write a new map type with
explicitly specified hash and equality functions. This could work
much like the builtin map type, but it would have methods (e.g.,
Lookup, Insert) rather than special syntax. However, nobody has
written such a type yet as far as I know.

Note that if anybody wants to write such a type, I recommend passing
in comparison and equality functions rather than requiring the key
type to have methods, as I mentioned in the talk at
https://www.youtube.com/watch?v=Pa_e9EeCdy8 .

Ian

[Kevin Chowski]

I tried my hand at it for fun :) it is a linear probed hashmap based on uint64 map keys: https://gotipplay.golang.org/p/gzrbS-B6ixg

I claim no rights nor responsibility for the above example; it only took me like 20 minutes and has extremely minimal testing; it may contain bugs. Use at your own risk. Et cetera et cetera I am not a lawyer ;)

[aind...@gmail.com]

> I think it is unlikely to ever happen

Yeah, it'd require a language change wouldn't it? Still, it'd be nice to take advantage

of the runtime's map implementation without starting from scratch.

> I tried my hand at it for fun

Nice work! I like the use of map[uint64][]keyVal.