Почему и как работают функции Python?

Недавно я попробовал следующие команды в Python:

>>> {lambda x: 1: 'a'}
{<function __main__.<lambda>>: 'a'}

>>> def p(x): return 1
>>> {p: 'a'}
{<function __main__.p>: 'a'}

Успех обоих творений dict указывает на то, что как лямбда, так и регулярные функции хешируются. (Нечто вроде {[]: 'a'} выходит из строя с TypeError: unhashable type: 'list').

Хэш, по-видимому, не обязательно является идентификатором функции:

>>> m = lambda x: 1
>>> id(m)
140643045241584
>>> hash(m)
8790190327599
>>> m.__hash__()
8790190327599

Последняя команда показывает, что метод __hash__ явно определен для lambda s, т.е. это не какая-то автоматическая вещь, которую Python вычисляет на основе типа.

Какова мотивация создания функций hashable? Для бонуса, каков хэш функции?

Ответ 1

Это ничего особенного. Как вы можете видеть, рассматриваете ли вы метод unbound __hash__ для типа функции:

>>> def f(): pass
...
>>> type(f).__hash__
<slot wrapper '__hash__' of 'object' objects>

часть of 'object' objects означает, что она наследует только __hash__ на основе идентификатора от object. Функция == и hash работает по идентичности. Разница между id и hash является нормальной для любого типа, наследующего object.__hash__:

>>> x = object()
>>> id(x)
40145072L
>>> hash(x)
2509067

Вы могли бы подумать, что __hash__ должен быть определен только для неизменяемых объектов, и вы почти правы, но это не содержит ключевой детали. __hash__ должен быть определен только для объектов, где все, что связано с сравнениями ==, неизменно. Для объектов, чей == основан на идентичности, он полностью стандартен для базы hash и для идентичности, так как даже если объекты являются изменяемыми, они не могут быть изменчивыми способом, который изменил бы их личность. Файлы, модули и другие изменяемые объекты с использованием == на основе идентификаторов ведут себя так.

Ответ 2

Может быть полезно, например, создавать наборы объектов функций или индексировать функции dict. Неизменяемые объекты обычно поддерживают __hash__. В любом случае нет внутренней разницы между функцией, определяемой def или lambda, которая является чисто синтаксической.

Используемый алгоритм зависит от версии Python. Похоже, вы используете последнюю версию Python в 64-битной коробке. В этом случае хэш функционального объекта является правильным вращением его id() на 4 бита, причем результат рассматривается как подписанное 64-битное целое число. Правый сдвиг выполняется, потому что адреса объектов (id() results) обычно выравниваются так, что их последние 3 или 4 бита всегда равны 0, а это мягко раздражающее свойство для хэш-функции.

В вашем конкретном примере

>>> i = 140643045241584 # your id() result
>>> (i >> 4) | ((i << 60) & 0xffffffffffffffff) # rotate right 4 bits
8790190327599  # == your hash() result

Ответ 3

Функция хешируется, потому что это обычный, встроенный, не изменяемый объект.

Из Руководство по Python:

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

Hashability позволяет использовать объект как ключ словаря и член набора, поскольку эти структуры данных используют внутреннее значение хэша.

Все неиспользуемые встроенные объекты Pythons являются хешируемыми, в то время как нет изменяемых контейнеров (таких как списки или словари). Объекты, являющиеся экземплярами пользовательских классов, по умолчанию хешируются; все они сравниваются неравномерно (кроме самих себя), и их хэш-значение получается из их id().