Python 的hash 函数（python中hashmap的方法）

今天在看python的hash 函数源码的时候，发现针对不同的数据类型python 实现了不同的hash 函数，今天简单介绍源码中提到的hash 函数。（
https://github.com/python/cpython/blob/main/Python/pyhash.c）

1. 针对short string 类型， python 用的是DJBX33A hash

DJBX33A是DJB（Daniel J. Bernstein）哈希函数的一种变体，专门设计用于快速计算和提供良好的分布特性， 我们来看一下DJBX33A

def djbX33A_hash(key):
    hash_value = 5381  # 初始哈希值

    for char in key:
        hash_value = (hash_value * 33) ^ ord(char)

    return hash_value

同时看一下DJB2 的实现

def djb2_hash(key):
    hash_value = 5381  # Initial hash value

    for char in key:
        hash_value = ((hash_value << 5) + hash_value) + ord(char)
    return hash_value

这个hash 函数用在很多的hashmap 的实现上

2. 针对文件的hash， python使用的是FNV hash。 我们看一下FNV hash 的具体实现

def fnv_hash(key):
    FNV_PRIME_32 = 16777619
    FNV_OFFSET_32 = 2166136261

    hash_value = FNV_OFFSET_32

    for char in key:
        hash_value = (hash_value ^ ord(char)) * FNV_PRIME_32

    return hash_value

3. 最后介绍python 默认的hash SipHash， 上面两种hash 函数都是相对不安全的，我们直接看代码

def siphash(key, message):
    c = 2
    d = 4
    v0 = 0x736f6d6570736575
    v1 = 0x646f72616e646f6d
    v2 = 0x6c7967656e657261
    v3 = 0x7465646279746573

    def rotl(x, b):
        return ((x << b) & 0xffffffffffffffff) | (x >> (64 - b))

    def sip_round():
        v0 += v1
        v1 = rotl(v1, 13)
        v1 ^= v0
        v0 = rotl(v0, 32)

        v2 += v3
        v3 = rotl(v3, 16)
        v3 ^= v2

        v0 += v3
        v3 = rotl(v3, 21)
        v3 ^= v0

        v2 += v1
        v1 = rotl(v1, 17)
        v1 ^= v2
        v2 = rotl(v2, 32)

    k0 = int.from_bytes(key[:8], 'little')
    k1 = int.from_bytes(key[8:16], 'little')

    m = len(message)
    last_chunk = m % 8
    b = m // 8 * 8

    v3 ^= k1
    v2 ^= k0
    v1 ^= k1
    v0 ^= k0

    for i in range(b // 8):
        mi = int.from_bytes(message[i*8:(i+1)*8], 'little')
        v3 ^= mi
        for _ in range(d):
            sip_round()
        v0 ^= mi

    mi = (last_chunk << 56) | int.from_bytes(message[b:], 'little')
    v3 ^= mi
    for _ in range(d):
        sip_round()
    v0 ^= mi

    v2 ^= 0xff

    for _ in range(c):
        sip_round()

    hash_value = v0 ^ v1 ^ v2 ^ v3

    return hash_value

最后我们给出python的PEP 456 – Secure and interchangeable hash algorithm | peps.python.orgFollowing system colour schemeSelected dark colour schemeSelected light colour scheme，这篇PEP可以很好的了解的python关于hash的具体事现,以及python的开发者是如何从众多的hash 函数中选择最优的hash function。