差不多是最快的便携式64位哈希函数，质量不错。
这是Leonid Yuriev原始文章的翻译。
代替免责声明我将省略哈希函数的定义以及其加密应用程序的属性和要求的详细列表，并假定读者要么具有必要的最低知识，要么会继续阅读 。 还应注意，除非另有明确说明，否则在下文中，我将讨论非加密（不适用于加密）哈希函数。
平价散列用于许多算法中，几乎总是需要最有效（快速）的数据处理，以及一定程度的散列质量。 这里，术语“质量”首先是指相对于初始数据的某种“随机性”（随机性）。 不那么经常地施加附加要求，例如抵抗故意产生的碰撞或不可逆性。
多一点乏味为了清楚起见，有必要更详细地定义哈希函数的“质量”概念和其余要求：
基线质量和雪崩效应 ：更改任意一组源数据中的一个或多个任意位会导致结果的每个位以½的概率发生更改。
- 不可逆性或第一个原像抵抗性：无法从哈希结果中获取原始数据或单个位。
- 抵抗一阶碰撞和/或第二次成像前的抵抗：查找/拟合原始数据集以获得指定结果或部分结果的难度，包括在知道初始数据集的情况下。
- 抵抗二阶碰撞：难以找到/拟合两个不同的数据集，这些数据集将给出相同的结果或重要部分的匹配。
省略了对基础数学的长时间引用，可以将其总结为：
- 在确保高性能的同时满足上述所有要求是一个非常困难的问题，解决该问题将为我们提供良好的加密哈希函数。 但是我们还不会这样做。
- 提供基本质量需要足够数量的ALU操作。 简而言之，质量始终会影响速度。
- 要获得位宽大于ALU操作的位宽的高质量结果，需要的混合次数增加了几倍，因此基本的ALU操作也要增加几倍。
- 通常， 创建快速散列函数涉及在速度，质量和结果位数之间权衡折衷 。
因此，我可以说t1ha的出现是在质量和速度之间寻求折衷的结果，同时考虑了现代处理器的功能以及已经发现的混合和扩展依赖关系的方法（算术逻辑组合）（雪崩效应）。
t1ha的基本版本是用于构建哈希表和其他相关应用程序的最快的便携式哈希函数之一。 t1ha的基本版本专注于64位Little-endian体系结构，采用64位Salt值（种子）并产生64位结果，其中包括通过密钥长度和种子进行增强。 值得注意的是， t1ha的目的是为零输入数据（零大小和零种子的键）返回0。
回答最受欢迎的问题64位操作 ：也许应该指出，正是64位操作提供了速度和质量而又不损害可移植性。 实际上，算术运算的数字能力越宽，它们产生的雪崩效应就越多，并且它们对数据的混合就越好。 此外，在所有其他条件相同的情况下，数据处理当然要比4快8字节。另一方面，许多现代处理器都可以精确地使用64位操作，并且可以或多或少地将其完全转换为32位一点点。 所有其他选项，包括SIMD操作，都迫使我们大大牺牲了在非本地平台上的可移植性和/或速度。
64位结果 ：要构造哈希表，在许多情况下，较小的位宽度结果就足够了。 甚至32位可能也绰绰有余。 但是，使用64位操作时，自然会产生64位结果。 同时，足够高质量的64位哈希结果使您可以快速执行非相等比较，并以较高的准确性进行相等比较。
上述替换比较的“魔术”似乎是不清楚的和不必要的，或者仅通过数据局部性（即更少的CPU缓存污染）就可以将散列速度提高一个数量级 。 简而言之，可以构建哈希表结构，使计算出的哈希值并排放置（打包在缓存行中）。 然后，仅当哈希值匹配时，CPU才会获取实际数据。 在这种情况下， t1ha的64位允许获得最佳结果 。 话虽如此，但是128位将不再具有优势，而总是有可能从64位中获取更少的数据。
与HighwayHash的比较 ：对于Google员工的这个非正式项目，我有不同的看法 。
- 一方面，它具有良好的代码和出色的技术实现。 另一方面， HighwayHash的密码强度可能很高（至少等于SipHash ）。 在HighwayHash内，有许多操作可以让我们期望结果不会很差。 但是，没有任何证据可以使我们可靠地说出来。 所提供的“强度”证明取决于统计测试的结果，但无法复制它们（有时甚至允许我自己做些多余的评论 ）。
- 只有在具有AVX2或SSE41的x86_64上，HighwayHash确实非常快。 仅使用AES-NI或SHA加速难道不是那么容易吗？
如果一切顺利，将向t1ha套件中添加其他选项（主要是针对结果位数），并针对E2K进行优化。 在此，我想结束与HighwayHash进行比较的主题。
质素
在各个方面评估哈希函数的质量可能非常困难。 可以通过分析或通过执行各种统计测试来完成。 不幸的是，这种分析方法对于评估哈希函数的质量和速度之间的折衷效果不是很有效。 此外，对这些功能的比较分析评估往往是主观的。
相反，统计测试可以提供清晰的定量估计。 为此，有经过验证的测试包，例如SMHasher 。 对于t1ha ，结果很简单-所有t1ha选项都通过了所有测试，而没有任何注释。 另一方面，不应假定t1ha具有超出目标应用程序（构建哈希表）所需属性的任何属性。
在t1ha的所有级别（变体）上的碰撞次数对应于生日悖论 。 严格来说， t1ha中的碰撞概率对应于随机离散值与相应位的重合概率。
在所有高质量哈希函数中观察到相似的冲突概率。 但是，这只是概率，因此实际冲突次数可能会因每个特定数据集而异。
这篇文章首次发表后， 伊夫·奥顿 （ Yves Orton）发现 ，第一个t1ha1()并不总是满足严格的雪崩准则 。 对于t1ha1()目标应用而言，此缺点微不足道，并且从实际角度来看并不t1ha1() 。 但是，在下一个t1ha2()级/变体中消除了此缺点，该原本计划提供更高的质量。 在使用当前版本编译器的新处理器上， t1ha2()平均比t1ha1()快一个周期，而在其他情况下，速度可能慢一个周期。 值得注意的是， t1ha2()还提供了流哈希模式和128位结果。
读者当然希望对t1ha的质量和/或强度进行透彻而深入的分析。 但是，根据目标t1ha应用领域，这似乎是多余的。 简而言之，即使对于短键，速度对我们而言也更为重要。 因此，没有考虑多轮混合。 当前的t1ha版本节省了周期并提供了64位结果-用统计学以外的任何方式来衡量发现的折中实际上是没有意义的，其结果也很好。
其实我刚刚跟随Google的同事介绍了他们如何提供统计证明
基准测试
关于“ 最快 ”的说法。 需要特别注意的是，在所有平台/体系结构上，哈希函数显然不可能同时有用且最快。 不同的处理器具有不同的可用指令集，并以不同的效率执行相似的指令。 显然，很可能无法创建“ 普遍最快 ”的功能。 但是，使用“
最快»至少在最常见的平台（x86_64）上具有可移植性，同时又最快的功能，而在使用像样的优化编译器的现代处理器上几乎没有损失的机会。
该项目的源代码包括一个测试，该测试既检查结果的正确性，又测量每个实现的变体的速度。 同时，在x86上，根据处理器（和编译器）的功能，可以检查功能的其他变体，并在处理器周期中进行测量。
此外，该项目的网站还包含表格，其中包含Reini Urban的SMHasher修改版的性能测量结果。 可以仔细检查所有数字并/或使用特定的编译器在特定的处理器上获得结果。
在这里，您可以将t1ha与其最接近的竞争对手进行比较。
散列短键 （平均1..31字节）。
查看右列“周期/哈希”（越小越好） ：
| 功能介绍 | MiB /秒 | 循环/哈希 |
|---|
| 1公顷 | 12228.80 | 35.55 |
| 快速哈希64 | 5578.06 | 43.42 |
| 城市哈希64 | 11041.72 | 51.77 |
| xx哈希64 | 11123.15 | 56.17 |
| Metrohash | 11808.92 | 46.33 |
散列长键 （256 Kb）。
查看中间栏“ MiB / Second”（越大越好） ：
| 功能介绍 | MiB /秒 | 循环/哈希 |
|---|
| 1公顷 | 12228.80 | 35.55 |
| Farmhash64 | 12145.36 | 60.12 |
| 城市哈希64 | 11041.72 | 51.77 |
| xx哈希64 | 11123.15 | 56.17 |
| 鬼的 | 11820.20 | 60.39 |
t1ha的变体
t1ha的开发此类目标的第一个目标是获得质量足够高的快速可移植功能，以构建哈希表。
然后，我们希望拥有哈希函数的最快版本，该版本可以提供质量可比的结果，但要尽可能地适合目标平台。 例如，基本的t1ha版本以小尾数字节顺序工作，因此，对于大尾数体系结构来说，必须进行转换，而不可避免地会损失性能。 那么，为什么不摆脱特定目标平台上不必要的操作呢？ 这样，添加了更多选项：
- 小端和大端的32位平台的简化版本。
- 使用AES-NI指令的变体，但没有AVX。
- 使用AES-NI和AVX指令的两种变体。
后来很明显，将需要更多为各种应用设计的选项，包括不同的位宽结果，质量和耐用性要求。 这种多样性需要适当的系统化。 这是通过更改命名方案来实现的，其中数字后缀表示功能的“级别”：
t1ha0() -是当前处理器的最快选项。t1ha1() -是t1ha1()的基本便携式64位版本。t1ha2() -是可移植的64位版本，对质量略有关注。t1ha3() -是用于指纹识别的快速便携式128位版本。- 等
在此方案中，假定t1ha0()是根据当前处理器的平台和功能实现重定向的调度程序。 另外，可以引入使用后缀“ _le”和“ _be”在little-endian和big-endian变体之间进行明确选择。 因此，在“ t1ha”招牌下，现在有几个哈希函数，这个家族将在未来发展壮大，其中包括针对俄罗斯E2K“ Elbrus”进行了优化的版本。
通过查看内置的测试输出（ make check ），可以掌握当前函数集及其属性的一般概念。 值得注意的是，所有功能均通过所有SM Hasher测试，并且AES-NI变体的性能根据处理器型号的不同而有很大差异：
Intel(R) Core(TM) i7-6700K CPU @ 3.00GHz Build by GNU C/C++ compiler 8.2 [...] - use RDPMC_40000001 as clock source - measure granularity and overhead: 53 cycles, 0.0188679 iteration/cycle Bench for tiny keys (7 bytes): t1ha0 : 13.14 cycle/hash, 1.877 cycle/byte, 1.598 Gb/s @3GHz t1ha1_64le : 15.14 cycle/hash, 2.163 cycle/byte, 1.387 Gb/s @3GHz t1ha2_atonce : 15.50 cycle/hash, 2.163 cycle/byte, 1.387 Gb/s @3GHz t1ha1_64be : 16.78 cycle/hash, 2.397 cycle/byte, 1.251 Gb/s @3GHz xxhash32 : 17.17 cycle/hash, 2.453 cycle/byte, 1.223 Gb/s @3GHz StadtX : 17.59 cycle/hash, 2.513 cycle/byte, 1.194 Gb/s @3GHz t1ha0_32le : 18.28 cycle/hash, 2.612 cycle/byte, 1.149 Gb/s @3GHz t1ha0_32be : 20.24 cycle/hash, 2.892 cycle/byte, 1.037 Gb/s @3GHz xxhash64 : 22.17 cycle/hash, 3.167 cycle/byte, 0.947 Gb/s @3GHz t1ha2_atonce128* : 29.93 cycle/hash, 4.277 cycle/byte, 0.701 Gb/s @3GHz t1ha2_stream* : 79.81 cycle/hash, 11.402 cycle/byte, 0.263 Gb/s @3GHz HighwayHash64_avx2 : 83.75 cycle/hash, 11.964 cycle/byte, 0.251 Gb/s @3GHz HighwayHash64_sse41 : 85.25 cycle/hash, 12.179 cycle/byte, 0.246 Gb/s @3GHz t1ha2_stream128* : 99.06 cycle/hash, 14.152 cycle/byte, 0.212 Gb/s @3GHz HighwayHash64_portable: 480.75 cycle/hash, 68.679 cycle/byte, 0.044 Gb/s @3GHz HighwayHash64_pure_c : 652.58 cycle/hash, 93.226 cycle/byte, 0.032 Gb/s @3GHz Bench for large keys (16384 bytes): t1ha0 : 1185.00 cycle/hash, 0.072 cycle/byte, 41.478 Gb/s @3GHz t1ha2_atonce : 3436.00 cycle/hash, 0.210 cycle/byte, 14.305 Gb/s @3GHz t1ha2_atonce128* : 3440.00 cycle/hash, 0.210 cycle/byte, 14.288 Gb/s @3GHz t1ha1_64le : 3449.00 cycle/hash, 0.211 cycle/byte, 14.251 Gb/s @3GHz t1ha2_stream* : 3479.00 cycle/hash, 0.212 cycle/byte, 14.128 Gb/s @3GHz t1ha2_stream128* : 3508.00 cycle/hash, 0.214 cycle/byte, 14.011 Gb/s @3GHz StadtX : 3550.00 cycle/hash, 0.217 cycle/byte, 13.846 Gb/s @3GHz xxhash64 : 4121.00 cycle/hash, 0.252 cycle/byte, 11.927 Gb/s @3GHz t1ha1_64be : 4567.00 cycle/hash, 0.279 cycle/byte, 10.762 Gb/s @3GHz HighwayHash64_avx2 : 4580.00 cycle/hash, 0.280 cycle/byte, 10.732 Gb/s @3GHz HighwayHash64_sse41 : 6412.00 cycle/hash, 0.391 cycle/byte, 7.666 Gb/s @3GHz t1ha0_32le : 7191.00 cycle/hash, 0.439 cycle/byte, 6.835 Gb/s @3GHz t1ha0_32be : 7928.00 cycle/hash, 0.484 cycle/byte, 6.200 Gb/s @3GHz xxhash32 : 8197.00 cycle/hash, 0.500 cycle/byte, 5.996 Gb/s @3GHz HighwayHash64_portable: 41895.27 cycle/hash, 2.557 cycle/byte, 1.173 Gb/s @3GHz HighwayHash64_pure_c : 53296.11 cycle/hash, 3.253 cycle/byte, 0.922 Gb/s @3GHz
关于内部结构的一点点为了更深入地研究细节，根据Merkle-Damgård方案 （“擦管”版本）构建了t1ha，并从数据大小和种子值上进行了增强。 在主压缩循环内部，使用256位状态，输入块的大小相同。 此外，对于每个数据操作数，有两个带有异花授粉的注入点。 压缩周期完成后，256位状态被压缩为128位。
执行上述操作时，将使用64位运算，并将其混合到混频器ARX（加法旋转-异或）和MUX / MRX（加法旋转-异或）中。 重要的是，所有这些计算都必须以确保并行执行大多数操作以及将u-op紧密打包到管道和x86_64执行单元中的方式构建。 因此，对于长密钥，几乎以最大的哈希率实现了足够好的质量。
值得注意的是，压缩循环仅在足够大的块上运行。 如果数据较少，则中间的128位状态将仅由密钥大小和salt值组成。
然后，将数据的剩余尾部与64位状态的一半交替混合在64位的部分中。 最后，将状态混合并同时压缩为64位结果。 这里t1ha的一个重要特征是使用基于宽乘法的混频器（两个64位乘法器的128位乘积）。 这允许高质量混合，具有良好的雪崩效果和较少的操作。 尽管宽乘法是一个相对昂贵的操作，但较少的此类操作允许t1ha以创纪录的低处理器周期数处理短键。
应当注意，基于宽乘法和异或的混频器并不是完美的。 尽管t1ha通过了所有SMHasher测试，但作者理解非注入性的后果。 但是，最终的质量似乎在合理程度上是足够的，并且t1ha线的开发计划已经反映了提供更高质量选项的意图。
您可以在此处找到更多信息和源代码。
感谢您的阅读！