Где я могу найти источник или алгоритм функции хеша() Python?

Ответ 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;
}

Ответ 2

Я рекомендую вам прочитать запись в Википедии для хэш-функций (http://en.wikipedia.org/wiki/Hash_function), чтобы лучше понять хэш-функции. Вы получите много ответов для реализации!

Подводя итог некоторым ключевым моментам (не только для этой конкретной функции, но и для всех хэш-функций):

• В данной записи (в зависимости от потребностей будет число, строка и объект и т.д.) может выдавать результат, который меньше и фиксированной длины. Обычно (не всегда), является целым числом.
• Различные входы производят разные выходы. Поскольку выход меньше, чем вход, ALWAYS будут разными входами, которые производят один и тот же вывод. Это вызов "хэш-коллизия" и должен быть редок, если хеш-функция хорошо разработана.
• Процесс должен быть эффективным, поэтому быстро получить хэш входных данных.
• Для некоторых типов хеш-функций важно, чтобы аналогичные входы генерировали не похожие выходы. Для других это не является обязательным, но обычно это достигается. Поэтому hash("\x02") не 2*hash("\x01")

В основном, хеш-функции используются для использования целого числа вместо полного объекта, с которым вы можете управлять более легко и эффективно.