Cyan4973/xxHash
GitHub: Cyan4973/xxHash
一种极速非加密哈希算法库，处理速度达到内存带宽极限，提供32位、64位和128位三种变体，适用于高性能散列计算场景。
Stars: 11162 | Forks: 905
# xxHash - 极速哈希算法
xxHash 是一种极速哈希算法，处理速度达到 RAM 的速度极限。
代码具有高度可移植性，并且在所有平台（小端/大端）上生成相同的哈希值。
该库包含以下算法：
- XXH32：使用 32 位算术生成 32 位哈希
- XXH64：使用 64 位算术生成 64 位哈希
- XXH3（自 `v0.8.0` 起）：使用向量化算术生成 64 位或 128 位哈希。
128 位变体称为 XXH128。
所有变体均已成功通过 [SMHasher](https://code.google.com/p/smhasher/wiki/SMHasher) 测试套件，
该套件用于评估哈希函数的质量（碰撞、分散性和随机性）。
我们还[提供了](https://github.com/Cyan4973/xxHash/tree/dev/tests)额外的测试，以更全面地评估 64 位哈希的速度和碰撞特性。
|分支 |状态 |
|------------|---------|
|release | [](https://github.com/Cyan4973/xxHash/actions?query=branch%3Arelease+) |
|dev | [](https://github.com/Cyan4973/xxHash/actions?query=branch%3Adev+) |
## 基准测试
基准测试的参考系统使用 Intel i7-9700K CPU，运行 Ubuntu x64 20.04。
[开源基准测试程序] 使用 `clang` v10.0 并加上 `-O3` 标志进行编译。
| 哈希名称 | 宽度 | 带宽 (GB/s) | 小数据速度 | 质量 | 备注 |
| --------- | ----- | ---------------- | ----- | --- | --- |
| __XXH3__ (SSE2) | 64 | 31.5 GB/s | 133.1 | 10
| __XXH128__ (SSE2) | 128 | 29.6 GB/s | 118.1 | 10
| _RAM 顺序读取_ | N/A | 28.0 GB/s | N/A | N/A | _供参考_
| City64 | 64 | 22.0 GB/s | 76.6 | 10
| T1ha2 | 64 | 22.0 GB/s | 99.0 | 9 | 稍差的 [碰撞]
| City128 | 128 | 21.7 GB/s | 57.7 | 10
| __XXH64__ | 64 | 19.4 GB/s | 71.0 | 10
| SpookyHash | 64 | 19.3 GB/s | 53.2 | 10
| Mum | 64 | 18.0 GB/s | 67.0 | 9 | 稍差的 [碰撞]
| __XXH32__ | 32 | 9.7 GB/s | 71.9 | 10
| City32 | 32 | 9.1 GB/s | 66.0 | 10
| Murmur3 | 32 | 3.9 GB/s | 56.1 | 10
| SipHash | 64 | 3.0 GB/s | 43.2 | 10
| FNV64 | 64 | 1.2 GB/s | 62.7 | 5 | 雪崩效应较差
| Blake2 | 256 | 1.1 GB/s | 5.1 | 10 | 加密型
| SHA1 | 160 | 0.8 GB/s | 5.6 | 10 | 加密型但已破解
| MD5 | 128 | 0.6 GB/s | 7.8 | 10 | 加密型但已破解
注 1：小数据速度是对算法在小数据上效率的_粗略_评估。如需更详细的分析，请参阅下一段。
注 2：某些算法的特征是速度_快于 RAM_。在这种情况下，只有当输入已经存在于 CPU 缓存（L3 或更好）中时，它们才能发挥全速潜力。否则，它们将受限于 RAM 的速度极限。
### 小数据
在大数据上的表现只是问题的一部分。
哈希在哈希表和布隆过滤器等结构中也非常有用。
在这些用例中，经常需要对大量小数据（从几个字节开始）进行哈希。
在这种情况下，算法的性能可能会有很大差异，因为算法的某些部分（例如初始化或终结化）会成为固定成本。
分支预测失败的影响也变得更加显著。
XXH3 的设计初衷就是在长输入和小输入上都有出色的性能，
如下图所示：
如需更详细的分析，请访问 wiki：
https://github.com/Cyan4973/xxHash/wiki/Performance-comparison#benchmarks-concentrating-on-small-data-
## 质量
速度并不是唯一重要的属性。
生成的哈希值必须遵循出色的分散性和随机性属性，
以便可以使用它的任何子部分来最大程度地分散表或索引，
并按照[生日悖论]将冲突数量减少到理论上的最低水平。
`xxHash` 已经用 Austin Appleby 出色的 SMHasher 测试套件进行了测试，
并通过了所有测试，确保了合理的质量水平。
它还通过了[更新的 SMHasher 分支]的扩展测试，这些测试包含了额外的场景和条件。
最后，xxHash 提供了自己的[大规模碰撞测试器](https://github.com/Cyan4973/xxHash/tree/dev/tests/collisions)，
能够生成并比较数十亿个哈希，以测试 64 位哈希算法的极限。
在这方面，xxHash 也表现出与[生日悖论]一致的良好结果。
更详细的分析记录[在 wiki 中](https://github.com/Cyan4973/xxHash/wiki/Collision-ratio-comparison)。
### 构建修饰符
以下宏可以在编译时设置以修改 `libxxhash` 的行为。它们通常默认禁用。
- `XXH_INLINE_ALL`：将所有函数设为 `inline`，实现被直接包含在 `xxhash.h` 中。
内联函数有利于提高速度，特别是对于小键。
当键的长度表示为_编译时常量_时，它_非常有效_，
观察到的性能提升在 +200% 左右。
详情请参阅[这篇文章](https://fastcompression.blogspot.com/2018/03/xxhash-for-small-keys-impressive-power.html)。
- `XXH_PRIVATE_API`：与 `XXH_INLINE_ALL` 结果相同。保留它是为了向后兼容。
这个名字强调了 `XXH_*` 符号名将不会被导出。
- `XXH_STATIC_LINKING_ONLY`：允许访问内部状态声明，这是静态分配所必需的。
由于 ABI 更改的风险，与动态链接不兼容。
- `XXH_NAMESPACE`：使用 `XXH_NAMESPACE` 的值为所有符号添加前缀。
此宏只能使用可编译的字符集。
在多次包含 xxHash 源代码的情况下，这对于规避符号命名冲突非常有用。
客户端应用程序仍然使用常规函数名，
因为符号通过 `xxhash.h` 自动转换。
- `XXH_FORCE_ALIGN_CHECK`：当输入对齐时，使用更快的直接读取路径。
当哈希的输入碰巧在 32 或 64 位边界上对齐时，
对于无法从非对齐地址加载内存的架构，此选项可以带来显著的性能提升。
对于具有良好非对齐内存访问性能的平台（对齐和非对齐访问使用相同的指令），它有（轻微的）不利影响。
此选项在 `x86`、`x64` 和 `aarch64` 上自动禁用，并在所有其他平台上启用。
- `XXH_FORCE_MEMORY_ACCESS`：默认方法 `0` 使用可移植的 `memcpy()` 表示法。
方法 `1` 使用 gcc 专用的 `packed` 属性，这可以为某些目标提供更好的性能。
方法 `2` 强制非对齐读取，这不符合标准，但有时可能是提取更好读取性能的唯一方法。
方法 `3` 使用字节移位操作，这最适合不对 `memcpy()` 进行内联的旧编译器或没有字节交换指令的大端系统。
- `XXH_CPU_LITTLE_ENDIAN`：默认情况下，字节顺序由编译时解析的运行时测试确定。
如果由于某种原因，编译器无法简化运行时测试，则可能会损失性能。
通过将此宏设置为 1，可以跳过自动检测并直接声明架构为小端序。
将其设置为 0 则声明为大端序。
- `XXH_ENABLE_AUTOVECTORIZE`：对于 XXH32 和 XXH64，可以根据 CPU 向量能力和编译器版本触发自动向量化。
注意：对于 `clang` 的较新版本，往往更容易触发自动向量化。
对于 XXH32，SSE4.1 或等效指令（NEON）就足够了，而 XXH64 需要 AVX512。
不幸的是，自动向量化通常对 XXH 性能不利。
因此，xxhash 源代码默认尝试阻止自动向量化。
话虽如此，系统在演进，这一结论也并非一成不变。
例如，据报道，较新的 Zen4 CPU 更有可能通过向量化来提高性能。
因此，如果您偏爱或想测试向量化代码，可以启用此标志：
它将移除阻止向量化的保护代码，从而使 XXH32 和 XXH64 更有可能被自动向量化。
- `XXH32_ENDJUMP`：用单个跳转切换 XXH32 的多分支终结化阶段。
这通常对性能不利，尤其是在对随机大小的输入进行哈希时。
但根据确切的架构和编译器，跳转可能会在小输入上提供稍好的性能。默认禁用。
- `XXH_IMPORT`：MSVC 专用：只应在动态链接时定义，因为它可以防止链接错误。
- `XXH_NO_STDLIB`：禁用对 `` 函数的调用，特别是 `malloc()` 和 `free()`。
`libxxhash` 的 `XXH*_createState()` 将始终失败并返回 `NULL`。
但一次性哈希（如 `XXH32()`）或使用静态分配状态的流式传输仍然按预期工作。
对于没有动态分配的嵌入式环境，此构建标志非常有用。
- `XXH_memcpy`, `XXH_memset`, `XXH_memcmp`：在编译时将 `memcpy()`、`memset()` 和 `memcmp()` 重定向到某些用户选择的符号。
重定向所有 3 个可消除包含 `` 标准库的需要。
- `XXH_NO_EXTERNC_GUARD`：当在 C++ 模式下编译 `xxhash.h` 时，移除 `extern "C" { .. }` 块保护。
- `XXH_DEBUGLEVEL`：设置为任何 >= 1 的值时，启用 `assert()` 语句。
这会（略微）减慢执行速度，但可能有助于在调试会话期间发现错误。
#### 二进制文件大小控制
- `XXH_NO_XXH3`：从生成的二进制文件中移除与 `XXH3`（64 位和 128 位）相关的符号。
`XXH3` 是 `libxxhash` 大小最大的贡献者，
因此对于不使用 `XXH3` 的应用程序，这有助于减小二进制文件大小。
- `XXH_NO_LONG_LONG`：移除对依赖 64 位 `long long` 类型的算法的编译，
其中包括 `XXH3` 和 `XXH64`。
仅编译 `XXH32`。
适用于没有 64 位支持的目标（架构和编译器）。
- `XXH_NO_STREAM`：禁用流式 API，将库限制为仅一次性变体。
- `XXH_NO_INLINE_HINTS`：默认情况下，xxHash 使用 `__attribute__((always_inline))` 和 `__forceinline` 以牺牲代码大小为代价来提高性能。
将此宏定义为 1 会将所有内部函数标记为 `static`，从而允许编译器决定是否对函数进行内联。
这在针对最小二进制文件大小进行优化时非常有用，
并且在 GCC 和 Clang 上使用 `-O0`、`-Os`、`-Oz` 或 `-fno-inline` 编译时会自动定义。
根据编译器版本，要使用 `-Og` 成功编译，可能也需要它。
- `XXH_SIZE_OPT`：`0`：默认，针对速度进行优化
`1`：`-Os` 和 `-Oz` 的默认值：禁用一些以大小优化为代价的速度技巧
`2`：使代码尽可能小，性能可能会受到严重影响
#### XXH3 专用的构建修饰符
- `XXH_VECTOR`：手动选择向量指令集（默认：在编译时自动选择）。可用的指令集有 `XXH_SCALAR`、`XXH_SSE2`、`XXH_AVX2`、`XXH_AVX512`、`XXH_NEON` 和 `XXH_VSX`。编译器可能需要额外的标志以确保正确的支持（例如，x_64 上的 `gcc` 需要 `-mavx2` 来支持 `AVX2`，或 `-mavx512f` 来支持 `AVX512`）。
- `XXH_PREFETCH_DIST`：选择预取距离。用于针对特定硬件平台的底层适配。仅限 XXH3。
- `XXH_NO_PREFETCH`：禁用预取。某些平台或情况在不进行预取的情况下可能会表现得更好。仅限 XXH3。
#### `xxhsum` CLI 的构建修饰符
- `XXH_1ST_SPEED_TARGET`：选择一个以 MB/s 表示的初始速度目标，用于基准测试模式下的第一次速度测试。基准测试将在后续迭代中调整目标，但第一次测试是通过定位此速度“盲目”进行的。目前保守地设置为 10 MB/s，以支持非常慢的（模拟）平台。
#### Makefile 变量
使用 `make` 编译命令行界面 `xxhsum` 时，还可以设置以下环境变量：
- `DISPATCH=1`：使用 `xxh_x86dispatch.c`，在运行时于 `scalar`、`sse2`、`avx2` 或 `avx512` 指令集之间进行选择。此选项仅对 `x86`/`x64` 系统有效。当检测到目标为 `x86`/`x64` 时，它默认被启用。可以通过使用 `DISPATCH=0` 强制关闭。
- `LIBXXH_DISPATCH=1`：相同的思路，在 `libxxhash` 内部实现了运行时向量扩展检测器。此参数默认禁用。启用后（仅对 `x86`/`x64` 系统有效），在 `xxh_x86dispatch.h` 中发布的新符号将变得可用。在撰写本文时，需要包含 `xxh_x86dispatch.h` 才能访问带有运行时向量扩展检测的符号。
- `NODE_JS=1`：使用 Emscripten 为 Node.js 编译 `xxhsum` 时，这会链接 `NODERAWFS` 库以实现不受限制的文件系统访问，并修补 `isatty` 以使命令行实用程序能够正确检测终端。这确实使得二进制文件特定于 Node.js。
### 构建 xxHash - 使用 vcpkg
你可以使用 [vcpkg](https://github.com/Microsoft/vcpkg) 依赖管理器下载并安装 xxHash：
```
git clone https://github.com/Microsoft/vcpkg.git
cd vcpkg
./bootstrap-vcpkg.sh
./vcpkg integrate install
./vcpkg install xxhash
```
vcpkg 中的 xxHash 端口由 Microsoft 团队成员和社区贡献者保持最新。如果版本过期，请在 vcpkg 仓库中[创建 issue 或 pull request](https://github.com/Microsoft/vcpkg)。
### 示例
最简单的示例是将 xxhash 64 位变体作为一次性函数调用，
从单个缓冲区生成哈希值，并从 C/C++ 程序中调用：
```
#include "xxhash.h"
(...)
XXH64_hash_t hash = XXH64(buffer, size, seed);
}
```
流式传输变体要复杂一些，但它允许增量提供数据：
```
#include "stdlib.h" /* abort() */
#include "xxhash.h"
XXH64_hash_t calcul_hash_streaming(FileHandler fh)
{
/* create a hash state */
XXH64_state_t* const state = XXH64_createState();
if (state==NULL) abort();
size_t const bufferSize = SOME_SIZE;
void* const buffer = malloc(bufferSize);
if (buffer==NULL) abort();
/* Initialize state with selected seed */
XXH64_hash_t const seed = 0; /* or any other value */
if (XXH64_reset(state, seed) == XXH_ERROR) abort();
/* Feed the state with input data, any size, any number of times */
(...)
while ( /* some data left */ ) {
size_t const length = get_more_data(buffer, bufferSize, fh);
if (XXH64_update(state, buffer, length) == XXH_ERROR) abort();
(...)
}
(...)
/* Produce the final hash value */
XXH64_hash_t const hash = XXH64_digest(state);
/* State could be re-used; but in this example, it is simply freed */
free(buffer);
XXH64_freeState(state);
return hash;
}
```
### 许可证
库文件 `xxhash.c` 和 `xxhash.h` 采用 BSD 许可。
实用程序 `xxhsum` 采用 GPL 许可。
### 其他编程语言
除了 C 参考版本之外，
感谢出色的贡献者，
xxHash 还可以通过许多不同的编程语言使用。
它们被[列在这里](http://www.xxhash.com/#other-languages)。
### 打包状态
许多发行版都捆绑了包管理器，
这使得 xxhash 可以作为 `libxxhash` 库
和 `xxhsum` 命令行界面轻松安装。
[](https://repology.org/project/xxhash/versions)
### 特别感谢
- Takayuki Matsuoka，又名 @t-mat，创建了 `xxhsum -c` 并在早期 xxh 版本发布期间提供了大力支持
- Mathias Westerdahl，又名 @JCash，引入了 `XXH64` 的第一个版本
- Devin Hussey，又名 @easyaspi314，对 `XXH3` 和 `XXH128` 进行了令人难以置信的底层优化
标签：C/C++, 事务性I/O, 哈希算法, 客户端加密, 数据结构, 非加密哈希