为何对Map键排序后计算FNV哈希可减少碰撞？性能解析

prometheus/common提供了两种计算map[string]string类型Labels的FNV1a 64位哈希实现：一种先对Label键排序再哈希，另一种直接遍历Map哈希（快速实现）。后者被指出更容易发生碰撞，核心原因可以从以下几点解释：

1. Go Map的遍历顺序是随机的，导致哈希输入不稳定 #

Go语言中Map的遍历顺序是随机化的，每次遍历的键顺序都可能不同。这意味着完全相同的一组Label键值对，直接遍历生成的哈希输入序列（键+值的组合顺序）可能完全不一样。

比如一组Labels：{"job": "api", "instance": "10.0.0.1"}，第一次遍历可能是job→instance，第二次可能是instance→job。将这两个不同顺序的序列输入FNV哈希算法，得到的哈希值大概率不同——但这组Labels本身是完全等价的，我们期望它们的哈希值一致。

同时，这种随机性还会导致不同的Label集合因为遍历顺序巧合，生成和另一组等价集合相同的输入序列，进而产生不必要的碰撞。

2. 排序让哈希输入具有确定性，消除了“伪碰撞” #

排序后，无论Map的遍历顺序如何，最终输入哈希算法的键值对序列都是固定的、按键排序后的顺序。这带来两个关键变化：

• 完全相同的Label集合，一定会生成相同的哈希输入序列，得到相同的哈希值（符合业务逻辑的正确结果）。
• 不同的Label集合，只有当它们的排序后序列完全一致时才会碰撞——这种碰撞是FNV1a 64位算法本身固有的碰撞（概率约为1/(2^64)），而非遍历顺序随机导致的额外“伪碰撞”。

3. 快速实现的“易碰撞”本质是伪碰撞过多 #

开发者所说的快速实现更容易碰撞，本质是指它会产生大量伪碰撞：

• 同一组Labels的不同遍历顺序得到不同哈希值（这是不符合业务期望的错误，而非传统哈希碰撞）。
• 不同Labels集合因为遍历顺序巧合生成相同输入序列，导致无意义的碰撞。

这些额外的碰撞都是输入序列不确定性带来的，而非哈希算法本身的问题。排序后则只保留了哈希算法固有的极低概率碰撞，因此碰撞可能性大幅降低。

内容的提问来源于stack exchange，提问作者vtm11