Use a hash/maphash uint64 as map key

[Pierre Durand]

Is it safe to use the result of a hash/maphash (uint64) as a map key.

Is there a risk of collision ? (different inputs generate the same hash)

Thank you

[Axel Wagner]

There are ∞ many possible hashable Go values (in particular, all strings) and 2^64 uint64, so yes, there is a possibility of collision.

How big that risk is depends on how many values you have and what the damage is, if a collision happens.

Wikipedia has a nifty table: https://en.wikipedia.org/wiki/Birthday_attack#Mathematics

There, you can see that if you have a 64 bit hash and have, say 190K elements, the probability of a random collision is roughly 10^-9 (so pretty small, but not completely impossible).

If a collision is truly problematic, a simple fix would be to use a map[K][]struct{K;V}. That way, if there *is* a collision on the hash, you store all the colliding values and can walk the slice to find the right one. As collisions should be rare, that should be an uncommon cost to pay.

--
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 visit https://groups.google.com/d/msgid/golang-nuts/c8076635-5311-4e17-81c7-4907857df145n%40googlegroups.com.

[robert engels]

That is not correct and will not work - what the op is talking about is if K collides - so this is only a single K - so map[K][]struct{K;V} will only ever have one element in the array…

To view this discussion visit https://groups.google.com/d/msgid/golang-nuts/CAEkBMfH6WzHLzoz%3DMe30MamY6th8miTqLFd4_LT_kJ%2BLB2%2B9gg%40mail.gmail.com.

[Axel Wagner]

Yes, I meant map[uint64][]struct{K;V}, thanks for correcting me.

[robert engels]

but if you have the K to compare to, why not just use map[K]V and let the standard map manage the hash and duplicates - since the OP referred to hash/maphash I assume they are using keys that are comparable

unless the OP is trying to write a complete custom map implementation - but I doubt that is the case if they didn’t understand that hashes can have duplicates

To view this discussion visit https://groups.google.com/d/msgid/golang-nuts/CAEkBMfHRHS_5V21MMC6oz5X75k-pXM8hCLN_tCTjfxnG5UEN7g%40mail.gmail.com.

[Axel Wagner]

My assumption is that OP wants to de-facto store keys in a map that are not `comparable` (e.g. use a `[]byte` as a key), without having to fully implement their own hash map. Of course, at some point we'll hopefully get #69559 to do this easily. In the meantime, using hash/maphash to calculate a hash and then using that as a key for the built-in map seems like a fair compromise.

[Robert Engels]

Agreed. I’ve been away from Go for a bit - I just assumed with hash/maphash the stdlib had a generic map… ugh. 

Rant… this highlights a key problem with Go. Perfect is the enemy of good. Java has had a map interface for 20 years. Millions of successful solutions have been developed. Just use it and move on to more important issues… but instead the Go team will argue over minutia while the code base continues to fragment. Very shortsighted. Go progresses like a code reviewer taking the time to ‘nit’ a PR - you know what - just approve it and take the time to submit your own PR to make those “improvements”. 

On Jun 26, 2025, at 12:17 AM, Axel Wagner <axel.wa...@googlemail.com> wrote:



[Jan Mercl]

On Thu, Jun 26, 2025 at 8:30 AM Robert Engels <ren...@ix.netcom.com> wrote:

> Agreed. I’ve been away from Go for a bit - I just assumed with hash/maphash the stdlib had a generic map… ugh.

Why should the _stdlib_ have a generic map when the _language_ had a
generic map since it went public in 2009?

[Robert Engels]

Because the stdlib generic map is not 1) an interface (e.g. cannot have concurrent semantics with same syntax ) and 2) cannot work with arbitrary types - they must implement comparable.

I thought this was obvious from the discussion.

> On Jun 26, 2025, at 1:55 AM, Jan Mercl <0xj...@gmail.com> wrote:

[Jason E. Aten]

Hi Pierre,

If it helps, I usually just cryptographically hash the key (e.g. with Blake3, a very

fast hash both with and without hardware support), and

turn a prefix of that hash (I typically use 33 bytes or 264 bits; has negligible chance of collision) 

into the string key of a built in map. For example,

https://github.com/glycerine/rpc25519/blob/master/hash/blake3.go#L104

- Jason

 

[Def Ceb]

The case of having a []byte key is doable by just converting the keys to/from string, since Go strings are essentially just immutable byte slices.

There'll be some overhead from all the copying if you end up having to convert a lot though.

To view this discussion visit https://groups.google.com/d/msgid/golang-nuts/CAEkBMfFoQrrbp6TH2UVTzSP6t1sRdHkB1KO%3DietSb9CoYgLxOQ%40mail.gmail.com.

[Robert Engels]

“ negligible chance of collision” is not scientific. It depends on the use case whether or not it is negligible. 

On Jun 26, 2025, at 2:14 AM, Jason E. Aten <j.e....@gmail.com> wrote:

negligible chance of collision

[Jan Mercl]

On Thu, Jun 26, 2025 at 9:12 AM Robert Engels <ren...@ix.netcom.com> wrote:

> Because the stdlib generic map is not 1) an interface (e.g. cannot have concurrent semantics with same syntax ) and 2) cannot work with arbitrary types - they must implement comparable.

I quoted a sentence with a complain about the lack of a generic map
in the stdlib. I was not responding to anything else, so please let's
not change the topic.

However, if we are now talking about interfaces. Everyone is free to
design an interface suitable to be implemented by a hash map. That
defintion could also be somewhere in the stdlib, yes. If only we can
all have the same needs or if there's an obvious design of said
interface that covers all needs. Everyone is free to propose it on the
issue tracker.

I am afraid, however, no such generally acceptable map interface design exists.

Looking at the Java map interface defintion makes my eyes bleed, but
maybe that's just me.

[Jason E. Aten]

On Thursday, June 26, 2025 at 9:22:14 AM UTC+2 Robert Engels wrote:

“ negligible chance of collision” is not scientific. It depends on the use case whether or not it is negligible. 

On Jun 26, 2025, at 2:14 AM, Jason E. Aten wrote:

negligible chance of collision

Thanks Robert. You're just setting me up for the punch line... :)

I left out the math to avoid the distraction from the basics of the approach. 

Pierre, if you want to put a little more rigor around that:

Let's assume birthday paradox (always wise) gives you only half the

bit-width, and that aggressively we are computing a new hash every femtosecond (to allow

CPUs to get a million times faster than today), then you would expect the first collision in 132 bits after 

1.721728e+17 years, or 24_596_114 times the time it will take for the earth to be destroyed by 

the sun becoming a red giant in ~ 7 billion years. 

That is what is generally meant by "negligible". In English, this means you can neglect hash collisions

from consideration.

Best wishes,

Jason

[Robert Engels]

I wasn’t trying to change the subject. You said why do we need a generic map when the stdlib has one… you responded to my statement about a “map” is an interface in Java and I If it makes you feel better, ignore 1 and just go with 2.

> On Jun 26, 2025, at 2:34 AM, Jan Mercl <0xj...@gmail.com> wrote: