一个不值一提的小问题：
有个地方使用 hash 方法来做哈希计算，将字符串转换成一个数值，但是发现改用 Python 3 之后，这个值每次运行都不一样了。

python2 -c 'print(hash("abc"))'
# 1453079729188098211
python2 -c 'print(hash("abc"))'
# 1453079729188098211

python2 -Rc 'print(hash("abc"))'
# 7010515968084336677
python2 -Rc 'print(hash("abc"))'
# -3698090625334563725

python3 -c 'print(hash("abc"))'
# -6072654259988304161
python3 -c 'print(hash("abc"))'
# -2316344332102300602

在 SO 上看一些解释（参考资料部分有链接），让我很感兴趣 Python 底层的实现。

另一篇文章：如何正确的将字符串转换成数字？

哈希

hash(object)
Return the hash value of the object (if it has one). Hash values are integers. They are used to quickly compare dictionary keys during a dictionary lookup. Numeric values that compare equal have the same hash value (even if they are of different types, as is the case for 1 and 1.0).

内置的 hash 方法顾名思义，就是获取对象的哈希值，输入一个对象，输出一个整数。

Python 中的哈希实现

哈希这个词的意义就是计算一个对象的指纹，有很多实现方式，包括我们最常见的 MD5, SHA 系列。对于 Python 来说，标准库 hashlib 就包含了这些常用的实现。

print(hashlib.algorithms_available)
{'sha3_512', 'sm3', 'ripemd160', 'sha1', 'blake2b', 'sha512_224', 'sha3_256', 'shake_128', 'md4', 'sha384', 'sha256', 'shake_256', 'whirlpool', 'sha3_224', 'blake2s', 'sha3_384', 'sha512', 'md5-sha1', 'sha512_256', 'sha224', 'md5'}
print(sys.hash_info)
sys.hash_info(width=64, modulus=2305843009213693951, inf=314159, nan=0, imag=1000003, algorithm='siphash24', hash_bits=64, seed_bits=128, cutoff=0)

hash 函数

hash 方法最终是调用对象的 __hash__ 方法，

Python2.7

2.7 的实现是每种类型分别实现，最后通过函数指针 tp_hash (typedef long (*hashfunc)(PyObject *);) 加入到
_typeobject 中，例如：

str 类型的实现

static long
string_hash(PyStringObject *a)
{
    register Py_ssize_t len;
    register unsigned char *p;
    register long x;

#ifdef Py_DEBUG
    assert(_Py_HashSecret_Initialized);
#endif
    if (a->ob_shash != -1)
        return a->ob_shash;
    len = Py_SIZE(a);
    /*
      We make the hash of the empty string be 0, rather than using
      (prefix ^ suffix), since this slightly obfuscates the hash secret
    */
    if (len == 0) {
        a->ob_shash = 0;
        return 0;
    }
    p = (unsigned char *) a->ob_sval;
    x = _Py_HashSecret.prefix;
    x ^= *p << 7;
    while (--len >= 0)
        x = (1000003*x) ^ *p++;
    x ^= Py_SIZE(a);
    x ^= _Py_HashSecret.suffix;
    if (x == -1)
        x = -2;
    a->ob_shash = x;
    return x;
}

int 类型的实现

static long
int_hash(PyIntObject *v)
{
    /* XXX If this is changed, you also need to change the way
       Python's long, float and complex types are hashed. */
    long x = v -> ob_ival;
    if (x == -1)
        x = -2;
    return x;
}

我们重点看 str, unicode, buffer 类型都使用的这个 _Py_HashSecret，这是在 random 模块中初始化的时候赋值的：

random 模块初始化

typedef struct {
    long prefix;
    long suffix;
} _Py_HashSecret_t;

_Py_HashSecret_t _Py_HashSecret;

void *secret = &_Py_HashSecret;
Py_ssize_t secret_size = sizeof(_Py_HashSecret_t);

By default, hash randomization is disabled, and only enabled if PYTHONHASHSEED is set to non-empty or if "-R" is provided at the command line:

memset(secret, 0, secret_size); // 哈希密钥采用全 0 初始化
// 对于 C 字符串，0 是结束，所以这里是空字符串
// 为啥不直接对 secret.prefix 和 secret.suffix 赋值？

如果有配置 PYTHONHASHSEED，

// 采用线性同余方法 (Linear Congruent Generator, LCG) 产生伪随机数
// 填充到密钥中
lcg_urandom(seed, (unsigned char*)secret, secret_size);

static void
lcg_urandom(unsigned int x0, unsigned char *buffer, size_t size)
{
    size_t index;
    unsigned int x;
    x = x0;
    for (index=0; index < size; index++) {
        x *= 214013;
        x += 2531011;
        /* modulo 2 ^ (8 * sizeof(int)) */
        buffer[index] = (x >> 16) & 0xff;
    }
}

Python3.9

也是按类型实现哈希算法，哈希初始化的机制差不多（_Py_HashRandomization_Init）

不过 Hash 的实现多了好多种，在 _Py_HashSecret_t 类型的定义就可以看出来：分别包含了 fnv, siphash, djbx33a, expat 四个结构体。

另外增加了一个随机 seed 的选项，并且，这是默认的（可以通过环境变量和启动参数指定）。

// 禁用
memset(secret, 0, secret_size);
// 使用指定的 seed
lcg_urandom(config->hash_seed, secret, secret_size);
// 使用随机 seed
pyurandom(secret, secret_size, 0, 0);

改成使用随机种子的好处，当然是为了避免哈希碰撞攻击。

siphash

Python 默认的哈希算法是 siphash，是从 3.4 开始的，之前都是 fnv。
具体情况可以参考 PEP 456: Secure and interchangeable hash algorithm。

typedef struct {
    Py_hash_t (*const hash)(const void *, Py_ssize_t);
    const char *name;
    const int hash_bits;
    const int seed_bits;
} PyHash_FuncDef;

// 默认：
define Py_HASH_ALGORITHM Py_HASH_SIPHASH24
static PyHash_FuncDef PyHash_Func = {pysiphash, "siphash24", 64, 128};

static uint64_t
siphash24(uint64_t k0, uint64_t k1, const void *src, Py_ssize_t src_sz) {
    uint64_t b = (uint64_t)src_sz << 56;
    const uint8_t *in = (const uint8_t*)src;

    uint64_t v0 = k0 ^ 0x736f6d6570736575ULL;
    uint64_t v1 = k1 ^ 0x646f72616e646f6dULL;
    uint64_t v2 = k0 ^ 0x6c7967656e657261ULL;
    uint64_t v3 = k1 ^ 0x7465646279746573ULL;

    uint64_t t;
    uint8_t *pt;

    while (src_sz >= 8) {
        uint64_t mi;
        memcpy(&mi, in, sizeof(mi));
        mi = _le64toh(mi);
        in += sizeof(mi);
        src_sz -= sizeof(mi);
        v3 ^= mi;
        DOUBLE_ROUND(v0,v1,v2,v3);
        v0 ^= mi;
    }

    t = 0;
    pt = (uint8_t *)&t;
    switch (src_sz) {
        case 7: pt[6] = in[6]; /* fall through */
        case 6: pt[5] = in[5]; /* fall through */
        case 5: pt[4] = in[4]; /* fall through */
        case 4: memcpy(pt, in, sizeof(uint32_t)); break;
        case 3: pt[2] = in[2]; /* fall through */
        case 2: pt[1] = in[1]; /* fall through */
        case 1: pt[0] = in[0]; /* fall through */
    }
    b |= _le64toh(t);

    v3 ^= b;
    DOUBLE_ROUND(v0,v1,v2,v3);
    v0 ^= b;
    v2 ^= 0xff;
    DOUBLE_ROUND(v0,v1,v2,v3);
    DOUBLE_ROUND(v0,v1,v2,v3);

    /* modified */
    t = (v0 ^ v1) ^ (v2 ^ v3);
    return t;
}

参考资料与拓展阅读

• StackOverflow, hash function in Python 3.3 returns different results between sessions
• Janis Lesinskis' Blog, TIL: Python hashing implementation details