比较哈希策略

概述

Chronicle 有许多哈希实现，包括 City 和 Murmur。它也有自己的 Vanilla Hash，但这是如何测试的？

什么是香草哈希？

Vanilla Hash 被设计为尽可能简单，并针对正交位测试进行了优化（见下文）这与 City 1.1 和 Murmur 3 哈希策略进行了比较。

这是用新数据填充 64 字节/256 字节缓冲区并生成 64 位哈希的第 99 个百分位延迟。 JMH 用于执行测量。请参见 Main64bytes 和 Main256bytes

哈希策略	64 字节 99% 平铺	256 字节 99% 平铺
香草	67纳秒	112纳秒
城市1.1	90纳秒	182纳秒
杂音 3	104纳秒	211纳秒

完整的测试结果在这里。

您可以执行哪些测试来检查哈希策略是否良好？

您可以进行许多简单的测试。测试无法识别一个好的散列，但它们可以表明一个散列是一个糟糕的散列。通过一项测试可能意味着它将无法通过另一项测试。

在每种情况下，都会以不同的随机起点运行多个测试。对第 99% 的百分位数进行评分，即最差的 1%。这是因为您不需要在某些时候或平均情况下有效的散列。你需要一个大部分时间都能工作的。（在所有情况下，您都可以发明一种病态情况，其中任何特定的哈希都会崩溃）

为了一致性，分数越低越好。测试的构建方式应为 0 分表示测试失败。

在每个测试中，使用 8,192 位或 1024 KB 的输入，一次切换一位。从这些输入中，生成了 8,192 x 64 位哈希值。

然而，对于随机测试，采用了一系列随机 64 位值。这些对于了解测试的散列策略的好数字是有用的。

哈希值掩码

在此测试中，每个散列均以 16,384（散列数的两倍）为模，并报告冲突数。大多数哈希策略在这个测试中表现良好。

雪崩分数

在此测试中，将每个散列与前一个散列（前一个位翻转）进行比较，以查看任何给定位被翻转的可能性。理想的是 50%，与报告的最差 1% 的差异总和为 50%。

延迟速度

在此测试中，记录了执行散列所需的时间，并报告了最差的 1% 延迟。

正交位

此测试的目的是确保所有散列的位与生成的每个其他散列尽可能不同。想想 8 Queens Problem，除了 64 位数字。理想情况是每个数字都具有与其他数字不同的相同位数，并且尽可能高。

在此测试中，每个散列都与其他每个散列进行比较。对不同的位数进行计数。如果不同位的数量小于 18，则给予 2^(17-n) 的惩罚分数。不同的位数越少，指数级的惩罚就越大。如果任何 8K 哈希值与其他 8K 哈希值的差异小于 5 位，即使所有其他对都很好，这也是失败的。

我将其称为正交位测试，因为您可以将 64 位数字建模为 64 维位向量。理想情况下，您希望生成的所有哈希值之间的角度尽可能高。

在所有测试中，这个测试显示了 String.hashCode() 和 HashMap.hash(int) 与其他哈希策略之间的最大差异。

测试 String.hashCode()

String.hashCode() 是一个非常糟糕的散列，尤其是对于 较低的 位。它是标准的，不能更改或破坏向后兼容性。然而，这不一定是个问题，因为 HashMap 使用一个 agitate 函数来降低一些高位以随机化低位。


 int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

结果

CheckMain 类对每个散列策略运行一套测试。

VANILLA 正交位：99% 分块分数：6066 速度：延迟的 99% 分块为 0.223 us 雪崩：从 50% 漂移的 99% 分块为 0.55% 哈希掩码：99% 分块冲突：1815

CITY_1_1 正交位：99% 分块分数：7395 速度：延迟的 99% 分块为 0.267 us 雪崩：从 50% 漂移的 99% 分块为 0.55% 哈希掩码：99% 分块冲突：1817

MURMUR_3 正交位：99% 分块分数：7524 速度：延迟的 99% 分块为 0.378 us 雪崩：从 50% 漂移的 99% 分块为 0.54% 哈希掩码：99% 分块冲突：1815

STRING32 正交位：99% 分块分数： 295906433 速度：延迟的 99% 分块为 1.580 us 雪崩：从 50% 漂移的 99% 分块为 1.02% 哈希掩码：99% 分块冲突：1814

STRING64 正交位：99% 分块分数： 1939167 速度：延迟的 99% 分块为 1.520 us 雪崩：从 50% 漂移的 99% 分块为 0.61% 哈希掩码：99% 分块冲突：1816

STRING32_WITHOUT_AGITATE 正交位：99% 分块分数： 879390386 速度：延迟的 99% 分块为 1.573 us 雪崩：从 50% 漂移的 99% 分块为 3.53% 哈希掩码：99% 分块冲突： 6593

随机正交位：99% 分块分数：7444 速度：延迟的 99% 分块为 0.058 us 雪崩：从 50% 漂移的 99% 分块为 0.53% 哈希掩码：99% 分块冲突：1817

SECURE_RANDOM 正交位：99% 分块分数：7449 速度：延迟的 99% 分块为 0.861 us 雪崩：从 50% 漂移的 99% 分块为 0.54% 哈希掩码：99% 分块冲突：1816

SEEDED_VANILLA

正交位：99%平铺分数：6000

速度：99% 的延迟时间为 0.219 us

雪崩：从 50% 开始的 99% 的漂移是 0.55%

哈希掩码：99% 瓦片碰撞：1814

SEEDED_CITY_1_1

正交位：99%平铺分数：7313

速度：99% 的延迟时间为 0.270 us

雪崩：从 50% 到 99% 的漂移是 0.54%

哈希掩码：99% 瓦片碰撞：1813

SEEDED_MURMUR_3

正交位：99%平铺分数：7404

速度：99% 的延迟时间为 0.359 us

雪崩：从 50% 到 99% 的漂移是 0.53%

哈希掩码：99% 瓦片碰撞：1810

注意：Seeded Vanilla Hash 是 Chronicle Enterprise 的一部分

结论

Vanilla、City 和 Murmur 哈希器是最快的。

虽然 String.hashCode() 很简单，但基于每个字符的乘法运算却很昂贵。相比之下，所有其他人使用 longs 一次处理 8 个字节。请参阅 STRINGS32_WITHOUT_AGITATE 与 STRING32 的比较。 HashMap 使用的是后者。

32 位字符串 hashCode() 即使在 Avalanche 测试中表现不佳。在 SMHasher 中，这个测试的分数超过 1% 被认为是失败的。

Mask of Hash 测试虽然简单，但似乎在所有情况下都表现良好。例外情况是 String.hashCode() ，如前所述，它没有非常随机的低位。

我发现有趣的是正交测试分数有多么不同。前三个哈希策略再次一直很低。即使是 64 位版本的 String.hashCode() 也有很大的变化，产生的哈希值只有不到 18 位的不同，实际上很多位是相同的。

免责声明

Vanilla Hash 针对 Orthogonal Bits 测试进行了优化。因此，它获得稍微好一点的结果也就不足为奇了。这并不意味着 Vanilla Hash 优于 City 或 Murmur。这可能只是意味着它最适合 Orthogonal Bits 测试。

概述