Python 可移植哈希

Question

我正在阅读 pyspark here 的源代码。我对这里的可移植功能感到非常困惑。

def portable_hash(x):
    """
    This function returns consistant hash code for builtin types, especially
    for None and tuple with None.
    The algrithm is similar to that one used by CPython 2.7
    >>> portable_hash(None)
    0
    >>> portable_hash((None, 1)) & 0xffffffff
    219750521
    """
    if x is None:
        return 0
    if isinstance(x, tuple):
        h = 0x345678
        for i in x:
            h ^= portable_hash(i)
            h *= 1000003
            h &= sys.maxint
        h ^= len(x)
        if h == -1:
            h = -2
        return h
    return hash(x)

我可以看到这是一个递归函数。如果输入是元组，则递归循环每个元素。

以下是我的一些问题:

1. 此哈希方法是一对一映射吗？
2. 此函数仅接受 None 和元组并且考虑到可哈希值，我知道列表对象不是hashable，他们是有意还是无意这样做的。
3. 我对哈希没有太多经验，这是一种非常经典的哈希方法吗？如果是，有什么资源可以让我更好地理解它吗？

Answer 1

"is this hash approach an one to one mapping?"

NO 哈希方法是 1 对 1:它们都将 M 个可能的输入映射到 N 个可能的整数结果，其中 M 远大于 N。

"this function only takes None and tuple and hashable values into consideration, I know that list object is not hashable, did they do that intentionally or not."

是的，此函数将除元组和 None 之外的所有内容委托(delegate)给内置的hash。这绝对是 Python 中经过深思熟虑的设计决策(也受到此函数的尊重)，使 list 和 dict 等可变内置函数不可哈希.

"I don't have much experience with hash, is this a very classic hashing approach, if so, is there any resource for me to get a better understanding for it?"

是的，项目的异或哈希，并在执行时修改运行总计，确实是对可哈希项目的容器进行哈希处理的一种非常经典的方法。

有关哈希的更多研究，我会从 http://en.wikipedia.org/wiki/Hash_function 开始.