Загадочная функция hash в Python: почему hash(-1) и hash(-2) одинаковы?

Вопрос на интервью

За кулисами hash(): Оптимизация и CPython

Дело в том, что поведение функции hash() для целых чисел в Python (точнее, в реализации CPython, которая является самой распространенной) имеет свои особенности, связанные с оптимизацией. Чтобы понять суть, нужно рассмотреть несколько моментов.
 

1. Интернирование небольших целых чисел
 

Python, стремясь к эффективности, интернирует небольшие целые числа в диапазоне от -5 до 256 включительно. Это означает, что для каждого целого числа из этого диапазона создается только один объект в памяти. Когда вы присваиваете переменной значение, например, -1, Python не создает новый объект, а повторно использует уже существующий интернированный объект -1.

Оператор is проверяет идентичность объектов, то есть ссылаются ли две переменные на один и тот же объект в памяти. Именно поэтому hash(-1) is hash(-2) возвращает True, так как оба вызова hash() возвращают один и тот же интернированный объект -2.
 

2. Хэш-функция для целых чисел в CPython
 

Реализация хэш-функции для целых чисел в CPython определена таким образом, что hash(x) == x для всех целых чисел, кроме -1. Для -1 сделано исключение: hash(-1) == -2.

Почему -1 является исключением? Предотвращение коллизий!

Основная причина такого исключения для -1 заключается в предотвращении потенциальных коллизий хэшей с объектами других типов. Хэш-значения играют ключевую роль в работе словарей (dictionaries) и множеств (sets) – структур данных, которые полагаются на уникальные хэш-значения для быстрого поиска и хранения элементов.

Представьте себе ситуацию, когда у вас есть пользовательский класс, и его метод __hash__ возвращает -1:
 

class MyObject:
    def __hash__(self):
        return -1

obj = MyObject()

print(hash(obj))  # Выводит -1

Исходный код CPython: как реализован hash()

Чтобы понять, как это реализовано в CPython, давайте заглянем в его исходный код. 

Почему именно исходный код? Потому что именно там находится окончательный ответ на вопрос, как реализована та или иная функция. Документация описывает поведение, но исходный код показывает как это поведение достигается.

Файл longobject.c
 

Исходный код CPython находится на GitHub. Нам нужно найти файл, который отвечает за реализацию целых чисел и их хэширование. Этот файл называется longobject.c (раньше, до Python 3, он мог называться intobject.c). Файл расположен в каталоге Objects/ репозитория CPython.

В файле longobject.c найдите функцию с именем long_hash. Эта функция отвечает за вычисление хэша для целых чисел (тип long в C, который используется для представления целых чисел произвольной длины в Python). Для старых версий Python (до 3) функция может называться int_hash

Вот вариант кода long_hash (код может немного отличаться в зависимости от версии Python):
 

static Py_hash_t
long_hash(PyObject *obj)
{
    PyLongObject *v = (PyLongObject *)obj; // Преобразуем PyObject в PyLongObject
    Py_uhash_t x; // Переменная для хранения хэш-значения (беззнаковый тип)
    Py_ssize_t i; // Индекс для перебора цифр числа
    int sign;    // Знак числа

    if (_PyLong_IsCompact(v)) { // Проверяем, является ли число "компактным"
        x = (Py_uhash_t)_PyLong_CompactValue(v); // Получаем компактное значение
        if (x == (Py_uhash_t)-1) { // Проверяем, равно ли значение -1
            x = (Py_uhash_t)-2; // Если равно, то меняем на -2 (ключевой момент!)
        }
        return x; // Возвращаем хэш-значение
    }
    // Дальше идет обработка "некомпактных" чисел (больших чисел)
    i = _PyLong_DigitCount(v); // Получаем количество цифр в числе
    sign = _PyLong_NonCompactSign(v); // Получаем знак числа
    x = 0; // Инициализируем хэш-значение нулем
    while (--i >= 0) { // Перебираем цифры числа с конца
        /* ... (сложные вычисления хэша для больших чисел) ... */
    }
    x = x * sign; // Учитываем знак числа
    if (x == (Py_uhash_t)-1) // Проверяем, равно ли итоговое хэш-значение -1
        x = (Py_uhash_t)-2; // Если равно, то меняем на -2 (ключевой момент!)
    return (Py_hash_t)x; // Возвращаем хэш-значение
}

Объяснение кода

1. static Py_hash_t long_hash(PyObject *obj): Функция принимает PyObject, который представляет собой общий тип объекта в Python. Затем она преобразует его в PyLongObject, который представляет целое число Python. Тип Py_hash_t — это тип, используемый для хранения хэш-значения.
    

2. if (_PyLong_IsCompact(v)): Эта проверка определяет, является ли целое число «компактным». «Компактные» целые числа — это целые числа, которые можно представить в виде одного машинного слова (например, long в C). Интернированные числа, такие как -1 и -2, будут компактными. Для компактных чисел используется более быстрый способ вычисления хэша.
    

3. x = (Py_uhash_t)_PyLong_CompactValue(v);: Если число компактное, то _PyLong_CompactValue(v) возвращает его значение как целое число без знака (Py_uhash_t). Это значение присваивается переменной x.
    

4. if (x == (Py_uhash_t)-1): Вот здесь и происходит магия! Эта проверка смотрит, равно ли вычисленное хэш-значение -1.
    

5. x = (Py_uhash_t)-2;: Если хэш-значение равно -1, то оно заменяется на -2. Это и есть причина, почему hash(-1) возвращает -2!
    

6. return x;: Функция возвращает вычисленное (и, возможно, измененное) хэш-значение.
    

7. // Дальше идет обработка «некомпактных» чисел (больших чисел): Если число не является «компактным» (то есть, это большое число, требующее больше памяти для представления), то используется более сложный алгоритм для вычисления хэша.
    

8. while (--i >= 0) { ... }: Этот цикл проходит по «цифрам» большого числа и выполняет серию операций, чтобы создать хэш. Алгоритм включает в себя битовые сдвиги и операции по модулю, чтобы получить хорошо распределенное хэш-значение.
    

9. x = x * sign;: После вычисления хэш-значения оно умножается на знак числа.
    

10. if (x == (Py_uhash_t)-1): Даже для больших чисел происходит проверка, чтобы итоговое хэш-значение не равнялось -1. Если это так, оно также меняется на -2.

Последствия и что нужно помнить