SipHash

SipHash [sip] 是一种具有 128 位种子和 64 位输出的加密伪随机函数。它由 Jean-Philippe Aumasson 和 Daniel J. Bernstein 设计，作为一种快速且安全的密钥哈希算法。它被 Ruby、Perl、OpenDNS、Rust、Redis、FreeBSD 等使用。C 参考实现已根据 CC0 许可证（公共领域）发布。

SipHash 网站的引述

SipHash 是一系列伪随机函数（又称密钥哈希函数），针对短消息的速度进行了优化。目标应用包括网络流量认证和防御哈希泛洪 DoS 攻击。

siphash24 是推荐的性能最佳的变体。它每个消息块使用 2 轮，4 轮最终化。除了参考实现之外，还有其他几种实现可用。有些是单次函数，另一些使用类似于 Merkle-Damgård 构造的方法，带有 init、update 和 finalize 函数。Marek Majkowski 的 C 实现 csiphash [csiphash] 定义了该函数的原型。（注意：k 被分成两个 uint64_t）

uint64_t siphash24(const void *src, unsigned long src_sz, const char k[16])

SipHash 需要 64 位数据类型，并且不兼容纯 C89 平台。

MurmurHash

MurmurHash [murmur] 是 Austin Appleby 开发的一系列非加密密钥哈希函数。Murmur3 是 MurmurHash 的最新且快速的变体。C++ 参考实现已发布到公共领域。它具有 32 位或 128 位输出，带有 32 位种子。（注意：输出参数是一个缓冲区，包含 1 或 4 个字节。）

Murmur3 的函数原型是

void MurmurHash3_x86_32(const void *key, int len, uint32_t seed, void *out)

void MurmurHash3_x86_128(const void *key, int len, uint32_t seed, void *out)

void MurmurHash3_x64_128(const void *key, int len, uint32_t seed, void *out)

128 位变体需要 64 位数据类型，并且不兼容纯 C89 平台。32 位变体完全兼容 C89。

Aumasson、Bernstein 和 Boßlet 已经证明 [sip] [ocert-2012-001] Murmur3 对哈希冲突攻击没有弹性。因此，Murmur3 不能再被视为安全的算法。如果哈希冲突攻击不重要，它仍然可能是一个替代方案。

CityHash

CityHash [city] 是 Geoff Pike 和 Jyrki Alakuijala 为 Google 开发的一系列非加密哈希函数。C++ 参考实现已根据 MIT 许可证发布。该算法部分基于 MurmurHash，并声称更快。它支持 64 位和 128 位输出，带有 128 位种子，以及不带种子的 32 位输出。

带 128 位种子的 64 位 CityHash 的相关函数原型是

uint64 CityHash64WithSeeds(const char *buf, size_t len, uint64 seed0,
                           uint64 seed1)

CityHash 还为长输入提供带有 CRC32 intrinsic 的 SSE 4.2 优化。除 CityHash32 之外的所有变体都需要 64 位数据类型。CityHash32 仅使用 32 位数据类型，但不支持 seeding。

与 MurmurHash 类似，Aumasson、Bernstein 和 Boßlet 已经展示了 [sip] CityHash 中类似的弱点。

DJBX33A

DJBX33A 是 Daniel J. Bernstein 的一个非常简单的乘法和加法算法。它速度快，设置成本低，但对哈希冲突攻击不安全。它的特性使其成为短字符串哈希优化的可行选择。

其他

HMAC、MD5、SHA-1 或 SHA-2 等加密算法太慢，并且设置和最终化成本很高。由于这些原因，它们不被认为适合此目的。现代 AMD 和 Intel CPU 具有 AES-NI（AES 指令集）[aes-ni] 以加速 AES 加密。带有 AES-NI 的 CMAC 可能是一个可行的选择，但它可能太慢，不适合日常操作。（需要测试）

结论

SipHash 提供了速度和安全性的最佳组合。其他著名项目的开发者也得出了相同的结论。

哈希密钥

Python 2.6 到 3.3 的 _Py_HashSecret_t 类型有两个成员，每个成员的长度为 32 位或 64 位。SipHash 需要两个 64 位无符号整数作为密钥。typedef 将更改为 union，保证在所有体系结构上大小为 24 字节。该 union 为 SipHash24 和 FNV 提供 128 位随机密钥，并为可选的短字符串优化和 pyexpat 种子提供额外的 64 位值。额外的 64 位种子确保 pyexpat 或短字符串优化不能泄露 SipHash24 种子的位。

64 位系统上的内存布局

cccccccc cccccccc cccccccc  uc -- unsigned char[24]
pppppppp ssssssss ........  fnv -- two Py_hash_t
k0k0k0k0 k1k1k1k1 ........  siphash -- two PY_UINT64_T
........ ........ ssssssss  djbx33a -- 16 bytes padding + one Py_hash_t
........ ........ eeeeeeee  pyexpat XML hash salt

32 位系统上的内存布局

cccccccc cccccccc cccccccc  uc -- unsigned char[24]
ppppssss ........ ........  fnv -- two Py_hash_t
k0k0k0k0 k1k1k1k1 ........  siphash -- two PY_UINT64_T (if available)
........ ........ ssss....  djbx33a -- 16 bytes padding + one Py_hash_t
........ ........ eeee....  pyexpat XML hash salt

新类型定义

typedef union {
    /* ensure 24 bytes */
    unsigned char uc[24];
    /* two Py_hash_t for FNV */
    struct {
        Py_hash_t prefix;
        Py_hash_t suffix;
    } fnv;
#ifdef PY_UINT64_T
    /* two uint64 for SipHash24 */
    struct {
        PY_UINT64_T k0;
        PY_UINT64_T k1;
    } siphash;
#endif
    /* a different (!) Py_hash_t for small string optimization */
    struct {
        unsigned char padding[16];
        Py_hash_t suffix;
    } djbx33a;
    struct {
        unsigned char padding[16];
        Py_hash_t hashsalt;
    } expat;
} _Py_HashSecret_t;
PyAPI_DATA(_Py_HashSecret_t) _Py_HashSecret;

_Py_HashSecret_t 在 Python/random.c:_PyRandom_Init() 中启动时只初始化一次。

哈希函数定义

实施

typedef struct {
    /* function pointer to hash function, e.g. fnv or siphash24 */
    Py_hash_t (*const hash)(const void *, Py_ssize_t);
    const char *name;       /* name of the hash algorithm and variant */
    const int hash_bits;    /* internal size of hash value */
    const int seed_bits;    /* size of seed input */
} PyHash_FuncDef;

PyAPI_FUNC(PyHash_FuncDef*) PyHash_GetFuncDef(void);

autoconf

一个新的测试被添加到配置脚本中。当它检测到需要对齐内存访问整数的平台时，该测试设置 HAVE_ALIGNED_REQUIRED。当前大多数平台，如 X86、X86_64 和现代 ARM，不需要对齐数据。

一个新选项 --with-hash-algorithm 允许用户在配置步骤中选择哈希算法。

哈希函数选择

宏 Py_HASH_ALGORITHM 的值定义了内部使用的哈希算法。它可以设置为三个值之一：Py_HASH_SIPHASH24、Py_HASH_FNV 或 Py_HASH_EXTERNAL。如果根本未定义 Py_HASH_ALGORITHM，则选择最佳可用算法。在不需要对齐内存访问（未定义 HAVE_ALIGNED_REQUIRED）且具有无符号 64 位整数类型 PY_UINT64_T 的平台上，使用 SipHash24。在没有 64 位数据类型的严格 C89 平台或 SPARC 等体系结构上，选择 FNV 作为回退。可以通过 autoconf 选项选择哈希算法，例如 ./configure --with-hash-algorithm=fnv。

值 Py_HASH_EXTERNAL 允许第三方在编译时提供自己的实现。

实施

#if Py_HASH_ALGORITHM == Py_HASH_EXTERNAL
extern PyHash_FuncDef PyHash_Func;
#elif Py_HASH_ALGORITHM == Py_HASH_SIPHASH24
static PyHash_FuncDef PyHash_Func = {siphash24, "siphash24", 64, 128};
#elif Py_HASH_ALGORITHM == Py_HASH_FNV
static PyHash_FuncDef PyHash_Func = {fnv, "fnv", 8 * sizeof(Py_hash_t),
                                     16 * sizeof(Py_hash_t)};
#endif

sys 模块

sys 模块已经有一个 hash_info 结构序列。更多字段被添加到对象中，以反映活动的哈希算法及其属性。

sys.hash_info(width=64,
              modulus=2305843009213693951,
              inf=314159,
              nan=0,
              imag=1000003,
              # new fields:
              algorithm='siphash24',
              hash_bits=64,
              seed_bits=128,
              cutoff=0)

_Py_HashBytes() (Objects/object.c)

_Py_HashBytes 是一个内部辅助函数，它为 bytes、memoryview 和 datetime 类提供哈希代码。它目前为 unsigned char * 实现 FNV。

该函数被移至 Python/pyhash.c 并修改为通过 PyHash_Func.hash() 使用哈希函数。函数签名已更改为将 const void * 作为第一个参数。 _Py_HashBytes 还处理特殊情况：它将零长度输入映射到 0，并将返回值为 -1 映射到 -2。

bytes_hash() (Objects/bytesobject.c)

bytes_hash 使用 _Py_HashBytes 为 bytes 对象提供 tp_hash 槽函数。该函数将继续使用 _Py_HashBytes，但没有类型转换。

memory_hash() (Objects/memoryobject.c)

memory_hash 为只读内存视图提供 tp_hash 槽函数，如果原始对象也hashable。它是唯一在未来必须支持哈希未对齐内存段的函数。该函数将继续使用 _Py_HashBytes 但没有类型转换。

unicode_hash() (Objects/unicodeobject.c)

unicode_hash 为 unicode 提供 tp_hash 槽函数。目前它为 unsigned char*、Py_UCS2 和 Py_UCS4 实现了 FNV 算法三次。该函数的重新实现必须注意使用正确的长度。由于宏 PyUnicode_GET_LENGTH 返回 unicode 字符串的长度而不是其以八位字节为单位的大小，因此长度必须乘以内部 unicode 种类的大小

if (PyUnicode_READY(u) == -1)
    return -1;
x = _Py_HashBytes(PyUnicode_DATA(u),
                  PyUnicode_GET_LENGTH(u) * PyUnicode_KIND(u));

generic_hash() (Modules/_datetimemodule.c)

generic_hash 作为 _Py_HashBytes 的包装器，用于 date、time 和 datetime 类型的 tp_hash 槽。timedelta 对象由其状态（天、秒、微秒）进行哈希，而 tzinfo 对象不可哈希。date、time 和 datetime 类型的结构体的数据成员未 void* 对齐。这可以通过将四到十个字节复制到对齐缓冲区轻松修复。

哈希值分布

哈希值的良好分布对于 dict 和 set 的性能很重要。SipHash24 和 FNV 都考虑了输入的长度，因此完全由 NULL 字节组成的字符串不会具有相同的哈希值。输入的最后一个字节也倾向于影响哈希值的最低有效位。该属性减少了具有共同前缀的字符串的哈希冲突数量。

典型长度

Serhiy Storchaka 在 [issue16427] 中展示，一个修改后的 FNV 实现，每周期 64 位，能够比当前 FNV 实现快几倍地处理长字符串。

然而，根据统计 [issue19183]，一个典型的 Python 程序以及 Python 测试套件，大约 50% 的哈希比率是 1 到 6 字节的短字符串。只有 5% 的字符串大于 16 字节。

Grand Unified Python 基准测试套件

使用实验性实现和 Grand Unified Python Benchmark Suite 进行的初步测试显示出微小的偏差。基准测试的总运行时间摘要在未修改的 Python 3.4 二进制文件的运行时间 1% 之内。测试在配备 64 位 Linux 安装的 Intel i7-2860QM 机器上运行。解释器使用 GCC 4.7 为 64 位和 32 位编译。

将进行更多基准测试。

可插拔

本 PEP 的初稿使得哈希算法在运行时可插拔。它在一个二进制文件中支持多种哈希算法，以便用户可以在启动时选择哈希算法。核心提交者 [pluggable] 认为这种方法是不必要的复杂。PEP 的后续版本旨在进行编译时配置。

非对齐内存访问

SipHash24 的实现受到了批评，因为它忽略了非对齐内存问题，因此在需要整数类型对齐的体系结构上不起作用。PEP 故意忽略了这种特殊情况，并且不支持在这些平台上使用 SipHash24。除非另有证明，否则根本不认为值得麻烦。所有主要平台，如 X86、X86_64 和 ARMv6+ 都可以处理非对齐内存，几乎没有速度影响，甚至没有影响。[alignmentmyth]

几乎每个块无论如何都是正确对齐的。目前，字节和字符串的数据总是对齐的。只有 memoryview 在极少数情况下可能指向未对齐的块。PEP 实现针对常见情况进行了优化和简化。

ASCII str / 字节哈希冲突

自 PEP 393 实现以来，字节和 ASCII 文本具有相同的内存布局。因此，新的哈希 API 将保持不变

hash("ascii string") == hash(b"ascii string")

对于 ASCII 字符串和 ASCII 字节。相等的哈希值会导致哈希冲突，因此对于带有混合键的字典和集合会造成轻微的速度损失。冲突的原因可以通过例如从字节的哈希值中减去 2 来消除。减去 -2 是因为 hash(b"") == 0 并且 -1 已保留。本 PEP 不改变哈希值。