c - Where can I find source or algorithm of Python's hash() function?

Question

>>> 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.

Answer 1

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;
}