Хэш для лямбда-функции в Python

Ответ 1

Два объекта не гарантируют хеш с тем же значением, если они не сравнивают равные [1].

Функции Python (включая lambdas) не сравниваются одинаково, даже если они имеют идентичный код [2]. Например:

>>> (lambda: 1) == (lambda: 1)
False

Реализация, это поведение связано с тем, что функциональные объекты не предоставляют свой собственный оператор равенства. Вместо этого они наследуют значение по умолчанию, которое использует идентификатор объекта, то есть его адрес. Из документа :

Если не определена операция __cmp__(), __eq__() или __ne__(), класс экземпляры сравниваются по идентификатору объекта ( "адрес" ).

Вот что происходит в вашем конкретном примере:

fn = lambda: 1  # New function is allocated at address A and stored in fn.
fn = lambda: 1  # New function is allocated at address B and stored in fn.
                # The function at address A is garbage collected.
fn = lambda: 1  # New function is allocated at address A and stored in fn.
                # The function at address B is garbage collected.
fn = lambda: 1  # New function is allocated at address B and stored in fn.
                # The function at address A is garbage collected.
...

Так как адрес A всегда хэшируется до одного значения и адрес B к другому, вы видите hash(fn) чередующиеся между двумя значениями. Это чередующееся поведение, однако, является артефактом реализации и может измениться в один день, если, например, сборщик мусора должен был вести себя несколько иначе.

Следующее проницательное замечание было внесено в @ruakh:

Стоит отметить, что невозможно написать общий процесс для определения эквивалентности двух функций. (Это последствие неразрешимости проблемы ).) Кроме того, две функции Python могут вести себя по-разному, даже если их код идентичен (поскольку они могут быть замыканиями, ссылающимися на переменные с переменными, но идентичными именами). Поэтому имеет смысл, что Функции Python не перегружают оператор равенства: нет способа для реализации чего-либо лучше, чем идентификатор объекта по умолчанию сравнение.

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

[2] Вызов ваших лямбдов, а затем хэширование результата, конечно, всегда будет давать одинаковое значение, так как hash(1) всегда одно и то же в одной программе:

>>> (lambda: 1)() == (lambda: 1)()
True

Ответ 2

Хеш объекта функции lambda основан на его адресе памяти (в CPython это возвращает функция id). Это означает, что любые два объекта функции будут иметь разные хэши (при условии, что нет хеш-коллизий), даже если функции содержат один и тот же код.

Чтобы объяснить, что происходит в вопросе, сначала обратите внимание, что запись fn = lambda: 1 создает новый объект функции в памяти и связывает с ним имя fn. Следовательно, эта новая функция будет иметь другое значение хэша для любых существующих функций.

Повторяя fn = lambda: 1, вы получаете переменные значения для хэшей, потому что, когда fn привязано к вновь созданному объекту функции, функция, которую ранее указывал fn, представляет собой мусор, собранный Python. Это связано с тем, что больше нет ссылок на него (поскольку имя fn теперь указывает на другой объект).

Затем интерпретатор Python повторно использует этот старый адрес памяти для следующего нового функционального объекта, созданного путем записи fn = lambda: 1.

Такое поведение может различаться между различными системами и реализациями Python.

Ответ 3

Каждый раз, когда вы выполняете fn = lambda: 1, создается новый объект функции, а старый объект, привязанный к имени fn, помечен для удаления. Но Python не просто освобождает объект, передавая его обратно в ОС. Чтобы минимизировать системные вызовы для распределения памяти и минимизировать фрагментацию памяти, Python пытается переработать память, когда это возможно. Итак, когда вы создаете fn = lambda: 1 в третий раз, когда интерпретатор замечает, что он получил блок RAM, который достаточно большой для нового функционального объекта, и поэтому он использует этот блок. И, таким образом, ваш третий fn заканчивается в этом блоке ОЗУ и, следовательно, имеет тот же идентификатор, что и первый fn, так как идентификатор объектов CPython является их адресом памяти.

(Как уже упоминалось, хэш любого типа объекта, который не обеспечивает конкретную реализацию __hash__, основан на его идентификаторе в CPython. И если класс не определяет метод __cmp__ или __eq__ он не должен определять операцию __hash__).

Ответ 4

Решение о равности двух функций невозможно, так как это надмножество проблемы остановки.

В идеальном мире сравнение (и, следовательно, хэширование) функций приведет к ошибке типа. Python, по-видимому, не нравится, и вместо этого предпочитает использовать личность функций для сравнения (и, следовательно, хеширования) их.