Python 的hash 函数
今天在看python的hash 函数源码的时候，发现针对不同的数据类型python 实现了不同的hash 函数，今天简单介绍源码中提到的hash 函数。（
https://github.com/python/cpython/blob/main/Python/pyhash.c）
- 针对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 的实现上
- 针对文件的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
- 最后介绍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。