Об'єкти, що хешуються

Крім послідовностей в Python є ще дві групи контейнерів — множини та відображення. Але перш ніж детально познайомитись з ними спочатку розглянемо що таке об'єкти, які хешуються.

Серед вбудованих функцій Python є функція hash(), яка повертає хеш для переданого їй об'єкта. Хеш-значенням буде деяке ціле число (int).

Насправді функція hash() викликає магічний метод __hash__() для переданого їй об'єкта. Якщо цей магічний метод об'єктом не реалізовано, то піднімається виняток.

Об'єкт, що хешується (hashable objects) в Python — такий об'єкт, який має хеш-значення, яке ніколи не змінюється на протязі його життєвого цикла і обчислюється магічним методом __hash__(), а також цей об'єкт можна порівнювати з іншими об'єктами (реалізує метод __eq__()).

Рівні об'єкти, що хешуються, повинні мати рівні хеш-значення. Якщо два об'єкта, що хешуються, мають рівні хеш-значення, тоді ці об'єкти можливо рівні. Це дозволяє дуже швидко порівнювати між собою складні по структурі об'єкти.

Якщо нам треба перевірити, що два об'єкта не рівні, і якщо ці об'єкти хешуються, то ми можемо зробити це майже миттєво просто порівнявши хеш-значення цих об'єктів. Якщо хеш-значення не рівні, це означає, що об'єкти точно не рівні.

Якщо нам треба перевірити, що два об'єкта рівні між собою, то ми спочатку порівнюємо хеш-значення цих об'єктів, і якщо останні не рівні, то вже можна стверджувати що і самі об'єкти не рівні і далі вже нічого не перевіряти. Це вже є дуже непоганою оптимізацією. Якщо ж хеш-значення рівні, то далі ми вже порівнюємо значення самих об'єктів.

Все це дозволяє шукати об'єкти, що хешуються, серед інших об'єктів дуже швидко.

Усі стандартні мутабельні об'єкти Python не є такими, що хешуються. Усі стандартні немутабельні об'єкти є такими, що хешуються, якщо вони не містять у собі мутабельних об'єктів.

>>> hash('hello')
1001890812597159072
>>> hash(None)
84759117
>>>

Хеш від цілого числа — завжди саме число, немає сенсу цілим числам співставляти інші цілі числа:

>>> hash(42)
42
>>>

Від мутабельних об'єктів:

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>>

Також у контейнерах не має бути мутабельних об'єктів:

>>> hash((1,2,3))
2528502973977326415
>>> hash((1,[2],3))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>>

Функція hash() містить дві "пасхалки":

>>> hash(float('inf')) # перші цифри числа Пі
314159
>>> hash(float('NaN'))
0
>>>

Трапляються і колізії:

>>> hash(-1), hash(-2)
(-2, -2)
>>>