确定性哈希随机决胜

发表于 本文字数： 2.6k 阅读时长 ≈ 9 分钟

确定性哈希随机决胜：低成本、可复现的平局策略

在游戏开发中，我们经常需要从一组候选项中选出“最优解”。当多个候选项的主评分完全相同时，一个容易被忽略的问题就出现了：平局时该选谁？，如果只依赖于判别时的不等号，那么结果必然是“偏置”的。

我是在一次网格密度搜索中遇到这个问题的。最终采用的方案是确定性哈希随机决胜（Deterministic Hash-based Random Tie-breaking）：用一次随机取种，为每个候选项生成可复现的伪随机优先级，在不收集全部平局候选的情况下完成决胜。

从网格密度搜索说起

假设地图由一个二维网格表示，每个格子记录该位置是否存在目标。搜索时，用一个固定尺寸的矩形窗口遍历所有合法位置，计算窗口覆盖范围内的目标数量，也就是该窗口的密度，实现中采用的就是经典的二维前缀和算法。

这类查询通常有两个方向：

  • 最密集搜索：选择密度最高的窗口；
  • 最稀疏搜索：选择密度最低的窗口。

问题在于，多个窗口经常拥有相同密度。空网格中的最稀疏搜索尤其极端：所有窗口的密度都是 0。

一种常见实现是只在发现更优密度时更新结果：

1
2
3
4
5
if (density > bestDensity)
{
    best = candidate;
    bestDensity = density;
}

如果窗口始终按照从左到右、从下到上的顺序扫描，那么相同密度下永远是最先遇到的窗口获胜。最终表现就是结果长期偏向固定方向。

这里需要增加同密度情况下的二级比较规则：

  1. 密度始终拥有最高优先级；
  2. 密度相同时，在候选窗口之间随机决胜；
  3. 相同战斗状态下结果可以复现；
  4. 不收集候选、不排序，不产生额外 GC；
  5. 尽量少消耗全局随机数序列。

核心思路

一次完整查询只从随机数生成器中获取一个种子：

1
uint querySeed = unchecked((uint)random.Next());

每个候选窗口都可以根据左下角坐标得到唯一的一维索引：

1
uint candidateId = unchecked((uint)(startY * gridWidth + startX));

随后计算该窗口的决胜优先级：

1
uint tieBreakKey = Mix(querySeed ^ candidateId);

最终比较规则可以写成二元排序键：

1
2
最密集搜索：先最大化 density，再最小化 tieBreakKey
最稀疏搜索：先最小化 density，再最小化 tieBreakKey

因此，哈希优先级只负责解决平局，永远不会推翻主评分。

统一比较规则

最密集和最稀疏搜索可以共用一套更新逻辑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
uint querySeed = unchecked((uint)random.Next());

bool hasBest = false;
int bestX = default;
int bestY = default;
int bestDensity = default;
uint bestTieBreakKey = default;

for (int startY = minY; startY <= maxY; startY++)
{
    for (int startX = minX; startX <= maxX; startX++)
    {
        int density = CalculateDensity(startX, startY);

        bool betterDensity = !hasBest || (sparse
            ? density < bestDensity
            : density > bestDensity);

        bool equalDensity = hasBest && density == bestDensity;

        // 密度更差，不可能胜出，直接跳过
        if (!betterDensity && !equalDensity)
            continue;

        // 只有可能胜出的候选才计算
        uint candidateId = unchecked((uint)(startY * gridWidth + startX));
        uint tieBreakKey = Mix(querySeed ^ candidateId);

        if (equalDensity && tieBreakKey >= bestTieBreakKey)
            continue;

        hasBest = true;
        bestX = startX;
        bestY = startY;
        bestDensity = density;
        bestTieBreakKey = tieBreakKey;
    }
}

是否允许密度为 0 的窗口成为结果，属于具体查询的语义，不应混入平局决胜规则。例如，最稀疏搜索通常允许返回空窗口；最密集搜索则可以在整张网格为空时直接返回“无结果”。

32 位混洗函数可以采用以下结构：

1
2
3
4
5
6
7
8
9
10
11
12
private static uint Mix(uint value)
{
    unchecked
    {
        value ^= value >> 16;
        value *= 0x7FEB352Du;
        value ^= value >> 15;
        value *= 0x846CA68Bu;
        value ^= value >> 16;
        return value;
    }
}

这是常见的 32 位整数混洗结构，目标是获得良好的雪崩效应：输入只改变少量 bit，输出中的大量 bit 都会变化。

这里的整数溢出是算法的一部分，因此需要明确使用 uint 和 unchecked。

实际实现注意把哈希计算延后到候选项有机会胜出时，跳过所有主评分更差的候选，减少不必要的混洗运算。

工作机制

1. 结果是确定的

哈希混洗没有内部状态。只要查询种子、候选 ID、候选集合和密度不变，最终结果就不会改变。这使它适合回放、帧同步、问题复现和自动化测试等需要确定性的场景。

2. 候选身份与遍历顺序分离

决胜优先级来自候选项自身的稳定 ID，而不是“第几个被访问”。即使改变遍历顺序，只要候选集合和 ID 不变，获胜者也不会改变。

网格窗口的 ID 来自左下角坐标的一维映射：

1
candidateId = y × width + x

只要坐标合法且索引没有溢出，每个窗口都有不同的 ID。对于其他问题，ID 也可以来自数组下标或实体编号；关键在于它必须稳定且唯一，不要直接依赖没有稳定性承诺的运行时 GetHashCode()。

3. Mix 提供伪随机排列

querySeed ^ candidateId 先使用异或将两个信息组合起来：

  • querySeed：本次查询的随机状态。
  • candidateId：候选区域的唯一身份。

固定种子下，不同索引经过异或后仍然不同；更换种子后，所有候选的输入都会变化，相当于重新洗牌。

单纯计算 querySeed ^ candidateId 仍会保留明显的位模式，因此需要再经过 Mix 扩散。

Mix 由异或移位和奇数乘法组成。这些运算在 32 位空间中均可逆，所以整个函数是一个排列：不同的 32 位输入会得到不同的输出。只要候选 ID 唯一，固定种子下的决胜 key 也不会碰撞。

改变查询种子后，候选项的优先级会被重新排列，从外部观察就像进行了一次轻量洗牌。

与其他方案的比较

方案 全局随机数消耗 额外空间 是否依赖遍历顺序 说明
始终取第一个 0 O(1) 是 快，但会形成固定偏置
收集平局项后随机 1 O(M) 否 易于理解，但需要保存候选
蓄水池抽样 随平局数增长 O(1) 具体结果依赖 能实现严格均匀抽样
哈希随机决胜 每次查询 1 次 O(1) 否 可复现、低耦合、易于内联

哈希方案最大的工程价值，是把随机消耗从“每个候选一次”降为“每次查询一次”。候选数量、地图大小或筛选条件发生变化时，不会线性消耗全局随机序列。

多结果查询

网格搜索有时需要返回多个分散的区域。常见做法是先找出当前最优窗口，再通过 NMS（非极大值抑制）排除其附近窗口，然后重复搜索。

为了避免每一轮继续消耗全局随机序列，可以从同一个查询种子派生轮次种子：

1
2
3
uint roundSeed = Mix(unchecked(querySeed + (uint)roundIndex * 0x9E3779B9u));

uint tieBreakKey = Mix(roundSeed ^ candidateId);

不同轮次会得到不同的候选优先级，而整次多结果查询仍然只需消费一次全局随机数。如果需要选择 K 个结果，并且每轮重新扫描 N 个窗口，整体时间复杂度仍为 O(K × N)，决胜本身只占用 O(1) 额外空间。

空网格的特殊情况

空网格是最稀疏搜索最典型的平局场景：所有合法窗口的密度都为 0。此时虽然可以跳过前缀和构建和密度计算，但不能直接返回第一个窗口，否则固定方向偏置会再次出现。

一种简单的快速路径是：

1
2
3
4
5
6
7
8
bool isEmpty = grid.IsEmpty;

if (!isEmpty)
    BuildPrefixSum();

int density = isEmpty
    ? 0
    : CalculateDensity(startX, startY);

底层仍需遍历合法窗口并执行哈希决胜，同时保留搜索范围检查和多结果 NMS。对于最密集搜索，如果空网格在语义上没有有效结果，则可以在进入扫描前直接返回。

使用边界

这套方法并不是任何场景下的“完美随机”，使用时需要注意以下几点：

  • 它提供的是高质量伪随机排名，不是密码学安全随机；
  • 它能消除固定遍历偏置，但不等价于对任意候选集合都经过数学证明的严格均匀抽样；
  • 候选 ID 一旦重复，key 的唯一性和遍历顺序无关性就会被破坏；
  • 超过 32 位 ID 空间时，应改用 64 位索引和相应的 64 位混洗函数；
  • 跨平台确定性不仅取决于 Mix，还取决于种子来源、候选集合和评分计算是否一致；
  • 如果希望目标在一段时间内保持稳定，可以复用查询种子，而不是每次更新都重新取种；
  • 若需要抵抗参与者预测或操纵结果，应改用密码学方案，而不是普通整数混洗。
  • 随机的是候选窗口而不是连续区域；一片空旷区域包含的合法窗口越多，被整体选中的概率通常也越高。

此外，所谓“零 GC”来自整个查询实现：使用值类型、普通循环和局部变量，不创建临时列表或迭代器。Mix 本身虽然不分配内存，但无法抵消调用链中其他代码产生的分配。

总结

确定性哈希随机决胜可以概括为一句话：

先用主评分决定谁有资格获胜，再用“查询种子 + 候选唯一 ID”生成确定性的伪随机排名，让平局候选完成无固定方向偏置的决胜。

在网格密度搜索中，它让等密度窗口不再固定偏向扫描起点，同时保留了线性扫描、零额外集合和确定性回放等工程特征。抽象到其他问题，本质仍然相同：先比较真正重要的业务评分，只在平局时使用种子化哈希优先级。

它不是为了替代所有随机抽样算法，而是在确定性、性能、低内存开销和游戏表现之间取得一个实用平衡。