Python的哈希函数顺序背后的逻辑是什么？

Question

我们知道,Python的一些数据结构使用哈希表来存储像set或的项目dictionary.所以这些对象没有顺序.但似乎对某些数字序列而言并非如此.

例如,请考虑以下示例:

>>> set([7,2,5,3,6])
set([2, 3, 5, 6, 7])

>>> set([4,5,3,0,1,2])
set([0, 1, 2, 3, 4, 5])

但是,如果我们进行一些小改动,它就没有排序:

>>> set([8,2,5,3,6])
set([8, 2, 3, 5, 6])

所以问题是:Python的哈希函数如何对整数序列起作用？

Answer 1

虽然SO中有很多问题hash及其顺序,但没有人解释哈希函数的算法.

所以你需要知道python如何计算哈希表中的索引.

如果你hashtable.c在CPython源代码中浏览文件,你会在_Py_hashtable_set函数中看到以下几行,它们显示了python计算哈希表键索引的方式:

key_hash = ht->hash_func(key);
index = key_hash & (ht->num_buckets - 1);

因此,整数的哈希值是整数本身*(-1除外),索引基于数据结构的数量和长度(ht->num_buckets - 1),并使用Bitwise和之间(ht->num_buckets - 1)以及数字计算.

现在考虑set使用hash-table 的以下示例:

>>> set([0,1919,2000,3,45,33,333,5])
set([0, 33, 3, 5, 45, 333, 2000, 1919])

33我们有多少:

33 & (ht->num_buckets - 1) = 1

实际上它是:

'0b100001' & '0b111'= '0b1' # 1 the index of 33

在这种情况下注意(ht->num_buckets - 1)是8-1=7或0b111.

并为1919:

'0b11101111111' & '0b111' = '0b111' # 7 the index of 1919

并为333:

'0b101001101' & '0b111' = '0b101' # 5 the index of 333

以及前面的例子:

>>> set([8,2,5,3,6])
set([8, 2, 3, 5, 6])

'0b1000' & '0b100'='0b0' # for 8
'0b110' & '0b100'='0b100' # for 8

_{*类的哈希函数int:}

class int:
    def __hash__(self):
        value = self
        if value == -1:
            value = -2
        return value