Requiem for a Hash Function, or: How I learned to love package maphash

Summary

Requiem for a Hash Function, or: How I learned to love package maphashSeptember 22, 2025Zürich, SchweizI am coming off from surgery right now and have some time on my hands, so I wanted to share a story about a learning experience.This post is a bit of a dual purpose one on a teachable moment as a software engineer — a chance to offer a retrospective from bad decisions and earn penance therefor.There is one episode that sticks out in my memory with a fair bit of shame: implementing the original metric hashing for the metric family data type in Prometheus’s client metrics. This hashing was used in the internals of the client metrics, so users wouldn’t be exposed to it directly — except in terms of CPU cost!You see, I implemented it initially in a very naive way, using FNV to digest each of the metric key-value metadata pairs. The underlying data type looked something like this: 1 2 3 4 5 6 7 8 9 10 11 12 13 type MetricFamily struct { Metrics map[uint64]*Metric } type Label struct { Name string Value string } type Metric struct { Labels []Label Value float64 } Note: The eagle-eyed reader will immediately notice that hash code-based indexing needs to consider the eventuality of a legitimate hash collision and that the proposed structure above does not solve this. That problem is OK to ignore, as that is merely tangential to the story. I have reduced the problem down to its essence: bad, specious hashing on my part.If why I am calling this point out is drawing a blank stare from you, as a reader, consider how the backing storage of something like a map or HashMap works: there is a backing store of entries (e.g., linked list, bucket, or similar) that provides the ability to disambiguate between keys whose hash codes collide. This is one of the reasons that Java requires classes that override Object#hashCode to also provide Object#equals (i.e., to use Object#equal to disambiguate between entries whose keys produce the same Object#hashCode).Metrics were identified by their...