Mutable, immutable и при чём здесь hashable

В Python довольно часто рядом встречаются понятия mutable, immutable, hashable и unhashable. Особенно когда речь заходит про списки, кортежи, словари и множества. Поначалу между ними легко провести слишком простую связь: изменяемые объекты нельзя хешировать, неизменяемые — можно.

В большинстве повседневных примеров это действительно похоже на правду. Список изменяемый и unhashable, строка неизменяемая и hashable. Но если копнуть немного глубже, выясняется, что это всё-таки разные свойства объекта.

Начнём с mutable и immutable.

Mutable — это объект, который можно изменить после его создания. Самый очевидный пример — обычный список:

numbers = [1, 2, 3]
numbers.append(4)

print(numbers)
# [1, 2, 3, 4]

Здесь список, который изначально содержал три элемента, стал содержать четыре. Причём это всё ещё тот же самый объект.

Можно даже посмотреть на его id:

numbers = [1, 2, 3]

print(id(numbers))

numbers.append(4)

print(id(numbers))

В обоих случаях id будет одинаковым. Мы взяли существующий объект и изменили его.

Со строками всё работает иначе. Строки в Python immutable, то есть после создания изменить сам объект уже нельзя.

Например, сделать так не получится:

name = "cat"
name[0] = "b"

Python выдаст TypeError.

При этом никто не запрещает написать:

name = "cat"
name = "bat"

На первый взгляд кажется, что мы всё-таки изменили строку. Но нет. Переменная `name` раньше ссылалась на строку "cat", а после второго присваивания стала ссылаться на другой объект — строку "bat".

Это довольно важный момент. Immutable не означает, что переменную нельзя поменять. Переменная вообще не является самим объектом. Грубо говоря, это имя, которое на него ссылается. Поменять можно ссылку, но не сам immutable-объект.

То же самое происходит с числами:

x = 10
x += 1

Число 10 не превратилось в 11. В результате операции `x` просто стал ссылаться на другое значение.

К изменяемым встроенным типам относятся, например, list, dict и set. К неизменяемым — int, float, bool, str, bytes, tuple и frozenset.

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

data = {
    (10, 20): "point"
}

Такой словарь совершенно нормален.

А вот такой:

data = {
    [10, 20]: "point"
}

даже не создастся:

TypeError: unhashable type: 'list'

Чтобы понять причину, нужно разобраться с hashable.

У Python есть встроенная функция hash():

hash(42)
hash("hello")
hash((1, 2, 3))

Все эти вызовы работают и возвращают некоторое целое число. Само число обычно нас вообще не интересует. Важно то, что Python может получить для объекта hash и использовать его в хеш-таблицах, на которых построены, в частности, словари и множества.

Например, когда мы пишем:

users = {
    "alice": 25,
    "bob": 31,
}

Python не перебирает каждый ключ словаря с начала до конца каждый раз, когда мы обращаемся к users["alice"]. Hash ключа помогает быстро определить, где искать нужную запись.

Отсюда возникает важное требование: hash объекта должен оставаться стабильным, пока объект используется таким образом.

И тут становится понятно, почему список создаёт проблему.

Представим на секунду, что Python разрешал бы такое:

key = [1, 2]

data = {
    key: "hello"
}

Python вычислил бы hash [1, 2] и на его основе положил запись в определённое место внутри словаря.

А потом мы сделали бы:

key.append(3)

Теперь наш ключ уже [1, 2, 3].

Если hash зависит от содержимого списка, он тоже должен измениться. Получается странная ситуация: запись была положена в словарь с одним hash, а искать её теперь пришлось бы с другим.

Поэтому обычный list просто нельзя хешировать:

hash([1, 2, 3])

закончится ошибкой:

TypeError: unhashable type: 'list'

То же самое происходит с dict и set. Все они изменяемые и поэтому не подходят для обычного хеширования по своему содержимому.

Именно отсюда и берётся удобная ассоциация:

list  → mutable   → unhashable
dict  → mutable   → unhashable
set   → mutable   → unhashable

str   → immutable → hashable
int   → immutable → hashable
bytes → immutable → hashable

Но воспринимать это как строгое правило всё-таки не стоит.

Хороший пример — tuple.

Кортеж изменить нельзя:

point = (10, 20)
point[0] = 100

Получим ошибку. Поэтому вполне логично ожидать, что кортеж можно хешировать:

point = (10, 20)

print(hash(point))

И действительно можно.

Благодаря этому кортежи удобно использовать как ключи словарей. Например, координаты:

places = {
    (40.7128, -74.0060): "New York",
    (51.5074, -0.1278): "London",
}

Но теперь положим внутрь кортежа список:

value = (1, 2, [3, 4])

Сам кортеж всё ещё immutable. Нельзя написать:

value[0] = 100

Но список внутри него никто не запрещает менять:

value[2].append(5)

print(value)
# (1, 2, [3, 4, 5])

А теперь попробуем:

hash(value)

и получим TypeError.

То есть tuple сам по себе immutable, но это ещё не гарантирует, что конкретный кортеж будет hashable. Его элементы тоже должны быть hashable.

С этим связан забавный момент: фраза «кортеж нельзя изменить» иногда воспринимается слишком буквально. Нельзя изменить то, на какие объекты ссылаются позиции кортежа. Но если внутри кортежа лежит mutable-объект, например список, сам этот объект вполне можно изменить.

Похожая история есть у множеств. Обычный set можно менять:

numbers = {1, 2, 3}
numbers.add(4)

Поэтому сам set unhashable и не может быть элементом другого множества.

Но в Python существует frozenset:

numbers = frozenset({1, 2, 3})

print(hash(numbers))

Это уже неизменяемое множество, и его можно хешировать. Поэтому frozenset, в отличие от обычного set, может быть ключом словаря или элементом другого множества.

Есть ещё одно правило, которое хорошо объясняет смысл hashability. Если два hashable-объекта равны:

a == b

то их hash тоже обязан быть одинаковым:

hash(a) == hash(b)

То есть из a == b должно следовать равенство хешей.

А вот наоборот это не работает. Два разных объекта теоретически могут получить одинаковый hash. Это называется коллизией, и Python умеет с такими ситуациями работать.

На практике всё это становится гораздо проще, если не пытаться объединить mutable и hashable в одно понятие.

Mutable и immutable говорят о том, можно ли изменить состояние объекта после его создания.

Hashable и unhashable говорят о том, подходит ли объект для использования в хеш-структурах Python. В первую очередь это означает возможность быть ключом dict или элементом set.

Для стандартных типов отсюда получается довольно знакомая картина. Строки, числа и подходящие кортежи можно использовать как ключи словаря. Списки, словари и множества — нельзя.

data = {
    "name": "Alice",       # str — можно
    42: "answer",          # int — можно
    (10, 20): "point",     # tuple — можно
}

А вот:

data = {
    [10, 20]: "point"
}

не сработает.

И, пожалуй, это тот случай, когда понимание причины полезнее, чем заучивание таблицы типов. Если помнить, зачем словарю вообще нужен hash и почему этот hash должен оставаться стабильным, поведение list, tuple, set и frozenset перестаёт выглядеть набором случайных правил.