Что такое по умолчанию hash в python?

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

Я заметил, что mutables явно не сотрясается, поскольку hash({}) вызывает ошибку... но странно, пользовательские классы хешируются:

>>> class Object(object): pass
>>> o = Object()
>>> hash(o)

Итак, знает ли кто-нибудь, как работает эта функция по умолчанию? Понимая это, я хотел бы знать:

Можно ли полагаться на этот хэш по умолчанию, если я помещаю объекты того же типа, что и ключи словаря? например

key1 = MyObject()
key2 = MyObject()
key3 = MyObject()
{key1: 1, key2: 'blabla', key3: 456}

Можно ли полагаться на него, если я использую объекты разных типов в качестве ключей в словаре? например.

{int: 123, MyObject(10): 'bla', 'plo': 890}

И в последнем случае также, как убедиться, что мои пользовательские хэши не сталкиваются с встроенными хэшами? например:

{int: 123, MyObject(10): 'bla', MyObjectWithCustomHash(123): 890}

Ответ 1

На что вы можете положиться: пользовательские объекты имеют по умолчанию hash(), который каким-то образом основан на идентичности объекта. то есть любой объект, использующий хэш по умолчанию, будет иметь постоянное значение для этого хеша за время его существования, а разные объекты могут иметь или не иметь другое значение хэша.

Вы не можете полагаться на какую-либо конкретную связь между значением, возвращаемым id(), и значением, возвращаемым hash(). В стандартной реализации C для Python 2.6 и ранее они были одинаковыми, в Python 2.7-3.2 hash(x)==id(x)/16.

Изменить: изначально я написал, что в версиях 3.2.3 и более поздних версиях или 2.7.3 или новее хеш-значение может быть рандомизировано, а в Python 3.3 отношение всегда будет рандомизировано. Фактически, что рандомизация в настоящее время применима только к хеширующим строкам, так что на самом деле разделение на 16 отношений может продолжаться до сих пор, но не берется на него.

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

Ответ 2

Документация утверждает, что пользовательские объекты полагаются на id() как реализация hash():

Подробности реализации CPython: это адрес объекта в памяти.

Если вы смешиваете пользовательские объекты со встроенными типами, такими как int, они могут быть хеш-коллизиями, но это не проблема, если они одинаково распределены. Не исследуйте слишком много, если вы действительно не столкнетесь с проблемой производительности.

Ответ 3

Хэш по умолчанию для пользовательских классов - это просто вернуть их идентификатор. Это дает частое поведение; использование экземпляра определяемого пользователем класса в качестве словарного ключа позволит получить связанное значение, когда точно такой же объект будет предоставлен снова для поиска значения. например:

>>> class Foo(object):
    def __init__(self, foo):
        self.foo = foo


>>> f = Foo(10)
>>> d = {f: 10}
>>> d[f]
10

Это соответствует равенству по умолчанию для пользовательских классов:

>>> g = Foo(10)
>>> f == g
False
>>> d[g]

Traceback (most recent call last):
  File "<pyshell#9>", line 1, in <module>
    d[g]
KeyError: <__main__.Foo object at 0x0000000002D69390>

Обратите внимание, что даже если f и g имеют одинаковые значения для своих атрибутов, они не равны и поиск g в d не находит значение, хранящееся в f. Кроме того, даже если мы изменим значение f.foo, поиск f в d все еще находит значение:

>>> f.foo = 11
>>> d[f]
10

Предполагается, что экземпляры какого-либо произвольного нового класса должны рассматриваться как неэквивалентные, если только программатор не объявляет условия для двух экземпляров как эквивалентные, определяя __eq__ и __hash__.

И это в значительной степени работает; если я определяю класс Car, я, вероятно, рассмотрю два автомобиля с одинаковыми атрибутами, представляющими два разных автомобиля. Если у меня есть словарь, сопоставляющий автомобили зарегистрированным владельцам, я не хочу искать Алису, когда я смотрю на машину Боба, даже если у Алисы и Боба будут одинаковые автомобили! OTOH, если я определяю класс для представления почтовых кодов, я, вероятно, хочу рассмотреть два разных объекта с тем же кодом, что и взаимозаменяемые представления "той же", и в этом случае, если бы у меня был словарь, переводящий почтовые коды в состояния, Я бы явно хотел найти одно и то же состояние с двумя разными объектами, представляющими один и тот же почтовый код.

Я называю это разницей между типами значений и типами объектов. Типы значений представляют собой некоторое значение, а значение меня волнует, а не каждый индивидуальный идентификатор объекта. Два разных способа достижения одинакового значения одинаково хороши, а "контракт" кода, проходящий вокруг типов значений, обычно просто promises, чтобы дать вам объект с некоторым значением, не указав, какой именно объект он есть. Для типов объектов OTOH каждый отдельный экземпляр имеет свою собственную идентификацию, даже если он содержит точно такие же данные, что и другой экземпляр. "Контракт" кода, проходящего вокруг типов объектов, обычно promises, чтобы отслеживать точные отдельные объекты.

Итак, почему встроенные изменяемые классы не используют свой id как свой хэш? Это потому, что они все контейнеры, и мы обычно рассматриваем контейнеры в основном как типы значений, их значение определяется содержащимися элементами:

>>> [1, 2, 3] == [1, 2, 3]
True
>>> {f: 10} == {f: 10}
True

Но изменяемые контейнеры имеют значение, которое является временным. В некотором заданном списке в настоящее время значение [1, 2, 3], но оно может быть изменено на значение [4, 5, 6]. Если вы можете использовать списки как словарные ключи, тогда нам нужно будет принять решение о том, должен ли поиск использовать значение списка (текущее) или его личность. В любом случае мы можем (очень) удивляться, когда значение объекта, которое в настоящее время используется в качестве словарного ключа, изменяется путем его изменения. Использование объектов в качестве словарных клавиш работает только тогда, когда значение объекта идентично, или когда идентификатор объекта не имеет значения для его значения. Таким образом, ответ, выбранный Python, заключается в том, чтобы объявить изменяемые контейнеры не сотрясаемыми.

Теперь, более конкретные детали в ответ на ваши прямые вопросы:

1) Так как этот хэш по умолчанию в CPython (хотя, по-видимому, только < 2.6, в соответствии с другими ответами/комментариями) сопоставляется с адресом памяти объекта, то в CPython нет двух объектов, использующих хеширование по умолчанию, которые одновременно являются живыми могут столкнуться с хэш-значениями независимо от задействованных классов (и если они хранятся в виде словарного ключа, то они живут). Я также ожидал бы, что другие реализации Python, которые не используют адреса памяти в качестве хэшей, все равно должны иметь мелкие хэш-распределения среди объектов с использованием хэширования по умолчанию. Так что да, вы можете положиться на него.

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

Ответ 4

В Python 3 в подклассах object для id() объекта (от pyhash.c) используется следующая функция

Py_hash_t
_Py_HashPointer(void *p)
{
    Py_hash_t x;
    size_t y = (size_t)p;
    /* bottom 3 or 4 bits are likely to be 0; rotate y by 4 to avoid
       excessive hash collisions for dicts and sets */
    y = (y >> 4) | (y << (8 * SIZEOF_VOID_P - 4));
    x = (Py_hash_t)y;
    if (x == -1)
        x = -2;
    return x;
}

SIZEOF_VOID_P - 8 для 64-битного Python и 4 для 32-разрядного Python.

>>> class test: pass
...
>>> a = test()
>>> id(a)
4325845928
>>> hash(a)
-9223372036584410438

Вы можете видеть, что хэш рассчитывается из id(a) с использованием формулы (id(a) >> 4) | (id(a) << (8 * SIZEOF_VOID_P - 4)), где побитовые операции выполняются на C целых числах. Например, для a, определенного выше:

>>> import numpy
>>> y = numpy.array([4325845928], dtype='int64')
>>> SIZEOF_VOID_P = 8
>>> (y >> 4) | (y << (8 * SIZEOF_VOID_P - 4))
array([-9223372036584410438])

Обратите внимание, что я использую numpy.array(dtype='int64'), так что побитовые операции действуют так же, как в C (если вы выполняете ту же операцию в Python ints, вы получаете другое поведение, потому что они не переполняются). См. fooobar.com/questions/155293/....

Ответ 5

>>> class C(object):
...     pass
... 
>>> c = C()
>>> hash(c) == id(c)
True

См. функцию id

Ответ 6

>>> class C(object):
...     pass
... 
>>> c = C()
>>> hash(c) == id(c)
False
>>> hash(c) == id(c)/16
True

Разделенный на 16 дает True