Python 的hash 函数

欢迎大家来到IT世界,在知识的湖畔探索吧!

今天在看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

欢迎大家来到IT世界,在知识的湖畔探索吧!

同时看一下DJB2 的实现

欢迎大家来到IT世界,在知识的湖畔探索吧!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 =  FNV_OFFSET_32 =  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 函数都是相对不安全的，我们直接看代码

欢迎大家来到IT世界,在知识的湖畔探索吧!def siphash(key, message): c = 2 d = 4 v0 = 0x736f6d v1 = 0x646f72616e646f6d v2 = 0x6ce v3 = 0x46573 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。

欢迎大家来到IT世界,在知识的湖畔探索吧!