Что произойдет, если изменится объект hash?

В Python я знаю, что значение __hash__, возвращаемое для данного объекта, должно быть одинаковым для времени жизни этого объекта. Но, из любопытства, что произойдет, если это не так? Какой хаос это может вызвать?

class BadIdea(object):
  def __hash__(self):
    return random.randint(0, 10000)

Я знаю, что __contains__ и __getitem__ будут вести себя странно, а dicts и sets будут действовать нечетно из-за этого. Вы также можете получить "осиротевшие" значения в dict/set.

Что еще может произойти? Может ли это сбой интерпретатора или повреждение внутренних структур?

Ответ 1

Ваша основная проблема действительно была бы с dicts и sets. Если вы вставляете объект в dict/set, и этот хэш объекта изменяется, то при попытке получить этот объект вы окажетесь в другом месте в базовом массиве dict/set и, следовательно, не найдете объект. Именно поэтому ключи dict всегда должны быть неизменными.

Вот небольшой пример: предположим, что мы помещаем o в dict, а начальный хэш o равен 3. Мы сделали бы что-то вроде этого (небольшое упрощение, но получим точку):

Hash table:

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
|   |   |   | o |   |   |   |   |
+---+---+---+---+---+---+---+---+
              ^
              we put o here, since it hashed to 3

Теперь скажем, что хэш o изменяется на 6. Если мы хотим извлечь o из dict, мы посмотрим на пятно 6, но там ничего нет! Это приведет к ложному отрицанию при запросе структуры данных. В действительности каждый элемент массива выше может иметь "значение", связанное с ним в случае dict, и может быть несколько элементов в одном месте (например, хеш-столкновение). Кроме того, мы обычно принимаем значение хэша по модулю размера массива при выборе места для размещения элемента. Однако, несмотря на все эти детали, приведенный выше пример все еще точно передает то, что может пойти не так, когда хэш-код объекта изменяется.

Может ли это сбой интерпретатора или повреждение внутренних структур?

Нет, этого не произойдет. Когда мы говорим, что изменение хэша объекта является "опасным", мы имеем в виду опасное в том смысле, что оно по существу побеждает цель хэширования и делает код сложным, если не невозможным, рассуждать. Мы не подразумеваем опасность в том смысле, что это может привести к сбоям.

Ответ 2

В Github есть отличная статья: Что происходит, когда вы возитесь с хэшированием. Во-первых, вам нужно знать, что Python ожидает (цитируется из статьи):

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

Вот пример кода, который показывает проблему варианта хэша, с немного другим примером класса, но идея остается той же:

>>> class Bad(object): 
...     def __init__(self, arg): 
...         self.arg = arg 
...     def __hash__(self): 
...         return hash(self.arg) 
... 
>>> Bad(1) 
<__main__.Bad object at ...> 
>>> hash(Bad(1)) 
1 
>>> a = Bad(1) 
>>> b = {a:1} 
>>> a.arg = 2 
>>> hash(a) 
2 
>>> b[a] 
Traceback (most recent call last):
...
KeyError: <__main__.Bad object at ...>

Здесь мы неявно изменили хэш a, изменив аргумент a, который используется для вычисления хэша. В результате объект больше не найден в словаре, который использует хэш для поиска объекта.

Обратите внимание, что Python не мешает мне это делать. Я мог бы сделать это, если захочу, сделав __setattr__ raise AttributeError, но даже тогда я смог бы принудительно изменить его, изменив объект __dict__. Это то, что имеется в виду, когда мы говорим, что Python является языком "соглашающихся взрослых".

Это не приведет к сбою Python, но произойдет непредвиденное поведение с dict/set и все на основе хеша объекта.