一尘不染

在哪里可以找到Python的hash()函数的源代码或算法?

algorithm

>>> hash("\x01")
128000384
>>> hash("\x02")
256000771
>>> hash("\x03")
384001154
>>> hash("\x04")
512001541

有趣的部分是128000384 x 2没有256000771,也有其他

我只是想知道该算法如何工作,并想学习一些东西。


阅读 422

收藏
2020-07-28

共1个答案

一尘不染

如果您下载Python的源代码,则可以肯定找到它!但是请记住,哈希函数对每种对象的实现方式不同。

例如,您可以在函数中找到unicode哈希Objects/unicodeobject.c函数unicode_hash。您可能需要多看一些才能找到字符串哈希函数。找到定义您感兴趣的对象的结构,然后在该字段中tp_hash,找到用于计算该对象的哈希码的函数。

对于字符串对象Objects/stringobject.c在函数中可以找到确切的代码string_hash

static long string_hash(PyStringObject *a)
{
    register Py_ssize_t len;
    register unsigned char *p;
    register long x;

    if (a->ob_shash != -1)
        return a->ob_shash;
    len = Py_SIZE(a);
    p = (unsigned char *) a->ob_sval;
    x = *p << 7;
    while (--len >= 0)
        x = (1000003*x) ^ *p++;
    x ^= Py_SIZE(a);
    if (x == -1)
        x = -2;
    a->ob_shash = x;
    return x;
}
2020-07-28