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

algorithm, c, hash, python

Solution

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

Problem

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

Original source