SipHash

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

来自 SipHash 网站的引用

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

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 位种子。（注意：out 参数是具有 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 本质的 SSE 4.2 优化。除 CityHash32 外的所有变体都需要 64 位数据类型。CityHash32 仅使用 32 位数据类型，但它不支持播种。

与 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 将更改为联合体，在所有架构上保证大小为 24 字节。联合体为 SipHash24 和 FNV 提供 128 位随机密钥，以及 64 位的可选小型字符串优化和 pyexpat 种子。额外的 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 是一个内部辅助函数，它为字节、内存视图和日期时间类提供哈希代码。它目前为 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 为字节对象提供 tp_hash 插槽函数。该函数将继续使用 _Py_HashBytes，但无需类型转换。

memory_hash() (Objects/memoryobject.c)

memory_hash 为只读内存视图提供 tp_hash 插槽函数，如果原始对象也是可散列的。这是将来唯一必须支持散列未对齐内存段的函数。该函数将继续使用 _Py_HashBytes，但无需类型转换。

unicode_hash() (Objects/unicodeobject.c)

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

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* 对齐。这可以通过使用 memcpy() 将 4 到 10 个字节复制到对齐的缓冲区来轻松修复。

哈希值分布

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

典型长度

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

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

Grand Unified Python 基准测试套件

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

将进行更多基准测试。

可插拔

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

未对齐内存访问

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

几乎每个块都已正确对齐。目前，字节和 str 的数据始终对齐。只有内存视图在极少数情况下才能指向未对齐的块。PEP 实现针对常见情况进行了优化和简化。

ASCII str/bytes 哈希冲突

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

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

用于 ASCII 字符串和 ASCII 字节。相等的哈希值会导致哈希冲突，因此会导致包含混合密钥的字典和集合的性能略有下降。可以通过例如从字节的哈希值中减去 2 来消除冲突的原因。-2 因为 hash(b"") == 0 并且 -1 已保留。PEP 不会更改哈希值。