我在哪里可以找到 Python 的 hash() 函数的源代码或算法? [英] Where can I find source or algorithm of Python's hash() function?

问题描述

<预><代码>>>>hash("x01")128000384>>>hash("x02")256000771>>>hash("x03")384001154>>>hash("x04")512001541

有趣的部分是128000384 x 2 不是256000771，还有其他

我只是想知道该算法是如何工作的，并想从中学习一些东西.

解决方案

如果你下载 Python 的源代码，你一定会找到的！但请记住，哈希函数针对每种对象的实现方式不同.

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

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

static long string_hash(PyStringObject *a){注册 Py_ssize_t len；注册无符号字符 *p;注册长 x；如果 (a->ob_shash != -1)返回 a->ob_shash;len = Py_SIZE(a);p = (unsigned char *) a->ob_sval;x = * p <<7;而 (--len >= 0)x = (1000003*x) ^ *p++;x ^= Py_SIZE(a);如果 (x == -1)x = -2;a->ob_shash = x;返回 x;}

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

Interesting part is 128000384 x 2 is not 256000771, and also others

I am just wondering how that algorithm works and want to learn something on it.

解决方案

If you download the source code of Python, you will find it for sure! But bear in mind the hash function is implemented for each kind of objects differently.

For example, you will find the unicode hash function in Objects/unicodeobject.c in the function unicode_hash. You might have to look a bit more to find the string hash function. Find the structure defining the object you are interested in, and in the field tp_hash, you will find the function that compute the hash code of that object.

For the string object: The exact code is found in Objects/stringobject.c in the function 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;
}

这篇关于我在哪里可以找到 Python 的 hash() 函数的源代码或算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！