(dictionaries=)

Словари. dict#

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

Хэш-таблицы#

По сути дела словари в python реализуют хеш-таблицу — распространенную во многих языках программирования структуру данных. Наиболее близкий аналог к словарям из python в C/C++ — std::unordered_map. Хеш-таблицы хранят пары (ключ, значение) (key, value) и позволяют выполнять следующие три операции:

  1. добавлять элемент по ключу;

  2. удалять элемент по ключу;

  3. искать элемент по ключу.

При хорошей реализации все эти три операции работают очень быстро и даже более того, скорость их работы практически не зависит от количества хранимых элементов. В python словари являются чуть ли не самой ключевой структурой данных — на них много завязано. Поэтому они сильно оптимизированы под скорость, но за это приходиться платить сравнительно большими накладными расходами по памяти.

Работа хеш-таблицы опирается на хеш-функцию. Хеш-функция — функция \(h\), которая на вход принимает произвольный ключ и возвращает целое число в диапазоне \([0, ..., M]\):

\[ h\colon K \to [0, ..., M], \]

где \(K\) — множество ключей, \(M\) — максимальное значение хеш-функции.

Пусть \((k, v)\) — пара (ключ, значение). Идея заключается в том, чтобы хранить все такие пары в обычном массиве \(A\) размера \(M + 1\), где индекс ячейки массива для данной пары \((k, v)\) определяется значением хеш-функции \(h(k)\) от ключа \(k\):

\[ A[h(k)] = (k, v). \]

Такая конструкция позволяет искать пару (ключ, значение) по ключу за время индексации массива \(A\) плюс время вычисления хеш-функции \(h(k)\). Индексация сплошного массива по смещению — очень быстрая операция, а скорость вычисления значения хеш-функции — одно из ключевых требований к хорошей хеш-функции.

В реальности может найтись два таких ключа \(k_1\) и \(k_2\), что значение хеш-функций на них совпадут: \(h(k_1)= h(k_2)\). Такое явление называют коллизией, для разрешения которых разработано множество методов. Эти методы позволяют хранить в хеш-таблице пары с любыми уникальными ключами, но время поиска ключа в таблице замедляется, если встречаются коллизии. В связи с этим минимизация количества коллизий — ещё одно ключевое требование к хорошим хеш-функциям.

На сегодня разработано огромное количество качественных хеш-функций и хеш-таблицы на их основе действительно позволяют делать все объявленные операции за почти константное время \(O(1)\). Конкретная реализация словарей в CPython достаточна изощрена и здесь опускаются её детали. Из всего вышеприведенного важно вынести самое основное:

  • хеш-таблицы хранят пары (ключ, значение);

  • для их работы необходима возможность вычислять значение хеш-функции от ключей, т.е. ключи должны быть хэшируемы (hashable);

  • кроме того, ключи в хеш-таблице должны быть уникальными;

  • хеш-таблицы позволяют очень быстро искать, добавлять и удалять пары (ключ, значение) по ключу.

Note

Любопытный может почитать о том, как устроены словари в CPython в исходном коде для словарей: их поведение очень хорошо описано в комментариях к исходному коду.

Создание словарей#

Как и в случае всех предыдущих контейнеров, создавать словари можно множеством разных способов.

  • Используя фигурные скобки “{}” и помещая внутри пары ключ: значение, отделяя ключ от значения символом двоеточия “:”, и разделяя пары друг от друга запятыми “,”:

my_first_dict = {"language": "python", "version": 3.8, "room": 542}
print(my_first_dict)

{'language': 'python', 'version': 3.8, 'room': 542}

  • Используя конструктор dict:

a_dict_from_iterable = dict([('foo', 100), ('bar', 200)]) # словарь из списка пар (key, value)
a_dict_from_kwargs = dict(foo=100, bar=200)               # используя именованные аргументы
print(a_dict_from_iterable, a_dict_from_kwargs)

{'foo': 100, 'bar': 200} {'foo': 100, 'bar': 200}

  • пустой словарь можно создать, используя пустую пару фигурных скобок “{}” или ничего не передав конструктору dict:

an_empty_dict = dict()                               
another_empty_dict = {}
print(an_empty_dict, another_empty_dict)

{} {}

  • Используя dict comprehensions:

squares = {x: x ** 2 for x in range(10)}
print(squares)

{0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36, 7: 49, 8: 64, 9: 81}

Добавление, поиск и удаление по ключу в dict#

Добавление, удаление и поиск значений по ключу разберем реализовав словарем … англо-русский словарь названий цифр. Ниже создаётся такой словарь.

eng_to_ru = {
    "one": "один",
    "two": "два",
    "three": "три",
    "fou": "четыре",
    "five": "пят",
    "six": "шесть",
    "seven": "семь",
    "eight": "восемь",
    "nine": "девять",
    }
print(eng_to_ru)

{'one': 'один', 'two': 'два', 'three': 'три', 'fou': 'четыре', 'five': 'пят', 'six': 'шесть', 'seven': 'семь', 'eight': 'восемь', 'nine': 'девять'}

Английское название цифры выступает в качестве ключа в нашем словаре, а его перевод выступает в качестве значения. Это позволяет нам по английскому варианту (ключу) быстро найти русский вариант (значение).

Если d — словарь, а key — ключ, то для получения значения по этому ключу используется синтаксис

d[key]

print(eng_to_ru["one"])
print(eng_to_ru["seven"])

один
семь

Код выше находит русскоязычные варианты слов “one” и “seven” в словаре, передавая их в качестве ключа.

Искать таким синтаксисом можно только по существующим ключам. Например, попробуем спросить у словаря перевод слова “four”.

print(eng_to_ru["four"])

---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
Input In [7], in <cell line: 1>()
----> 1 print(eng_to_ru["four"])

KeyError: 'four'

Возникла ошибка KeyError, сигнализирующая об отсутствии переданного ключа в словаре. Она возникла, т.к. при заполнении словаря была совершена опечатка: вместо ключа “four” был введен ключ “fou”.

Эту ошибку можно исправить, т.к. словари изменяемы:

  • в словаре можно изменять значение для уже существующего ключа;

  • добавлять новую пару (ключ, значение);

  • удалять пару (ключ, значение) по ключу.

Используем эти возможности для исправления опечаток в словаре. Для начала обратим внимание, что по ключу “five” находится значение “пят”, а не “пять”.

print(eng_to_ru["five"])

пят

Чтобы изменить значение по ключу, достаточно присвоить по этому ключу новое значение, т.е. если d — словарь, key — ключ, по которому требуется заменить старое значение на новое значение new_value, то используется синтаксис

d[key] = new_value

Воспользуемся этим синтаксисом, чтобы исправить опечатку по ключу “five”.

eng_to_ru["five"] = "пять"
print(eng_to_ru)

{'one': 'один', 'two': 'два', 'three': 'три', 'fou': 'четыре', 'five': 'пять', 'six': 'шесть', 'seven': 'семь', 'eight': 'восемь', 'nine': 'девять'}

Видим, что значение по ключу “five” удалось успешно изменить на “пять”. Осталась ещё опечатка в ключе four.

Словари не предусматривают операции редактирования ключа напрямую. Тем не менее можно добиться схожего эффекта за два шага:

  1. удалить пару (ключ, значение) по неверному ключу.

  2. добавить пару (ключ, значение) по исправленному ключу.

Note

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

Чтобы удалить пару (ключ, значение) из словаря d по ключу key используется синтаксис

del d[key]

Применим этот синтаксис для того, чтобы удалить ключ fou из словаря. Здесь удобно также продемонстрировать, что хоть словари и не являются последовательностью, но их длину, т.е. количество ключей (или количество значение) можно спросить функцией len.

print(len(eng_to_ru))
del eng_to_ru["fou"]
print(len((eng_to_ru)))
print(eng_to_ru)

9
8
{'one': 'один', 'two': 'два', 'three': 'три', 'five': 'пять', 'six': 'шесть', 'seven': 'семь', 'eight': 'восемь', 'nine': 'девять'}

По изменению количества элементов и по содержимому словаря видно, что успешно удалось удалить пару (“fou”, “четыре”).

Чтобы добавить в словарь значение по новому ключу используется тот же синтаксис, что и для изменения значения по уже существующему ключу, т.е. если d — словарь и требуется добавить пару (new_key, new_value), то используется синтаксис

d[new_key] = new_value

И теперь добавим значение "четыре" по верному ключу "four".

eng_to_ru["four"] = "четыре"
print(eng_to_ru)

{'one': 'один', 'two': 'два', 'three': 'три', 'five': 'пять', 'six': 'шесть', 'seven': 'семь', 'eight': 'восемь', 'nine': 'девять', 'four': 'четыре'}

Словари в качестве структур данных#

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

В разделе “Кортежи в качестве записей” кортежи использовались для представления данных о планетах.

planets_tuples = [
    ("Меркурий", 0, 0.0055),
    ("Венера", 0, 0.815),
    ("Земля", 1, 1.),
    ("Марс", 2, 0.107),
    ("Юпитер", 62, 317.8),
    ("Сатурн", 34, 95.2),
    ("Уран", 27, 14.37),
    ("Нептун", 13, 17.15),
]

Трансформируем эти кортежи в словари.

def planet_tuple_to_dictionary(planet):
    name, n_moons, mass = planet
    return {
        "name": name,
        "number of moons": n_moons,
        "mass": mass 
    }

planets_dicts = []
for planet in planets_tuples:
    planets_dicts.append(planet_tuple_to_dictionary(planet))

print(planets_dicts)

[{'name': 'Меркурий', 'number of moons': 0, 'mass': 0.0055}, {'name': 'Венера', 'number of moons': 0, 'mass': 0.815}, {'name': 'Земля', 'number of moons': 1, 'mass': 1.0}, {'name': 'Марс', 'number of moons': 2, 'mass': 0.107}, {'name': 'Юпитер', 'number of moons': 62, 'mass': 317.8}, {'name': 'Сатурн', 'number of moons': 34, 'mass': 95.2}, {'name': 'Уран', 'number of moons': 27, 'mass': 14.37}, {'name': 'Нептун', 'number of moons': 13, 'mass': 17.15}]

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

def print_planet(planet):
    print(f'Планета {planet["name"]} имеет {planet["number of moons"]} спутников. Её масса составляет {planet["mass"]} земных масс.')

for planet in planets_dicts:
    print_planet(planet)

Планета Меркурий имеет 0 спутников. Её масса составляет 0.0055 земных масс.
Планета Венера имеет 0 спутников. Её масса составляет 0.815 земных масс.
Планета Земля имеет 1 спутников. Её масса составляет 1.0 земных масс.
Планета Марс имеет 2 спутников. Её масса составляет 0.107 земных масс.
Планета Юпитер имеет 62 спутников. Её масса составляет 317.8 земных масс.
Планета Сатурн имеет 34 спутников. Её масса составляет 95.2 земных масс.
Планета Уран имеет 27 спутников. Её масса составляет 14.37 земных масс.
Планета Нептун имеет 13 спутников. Её масса составляет 17.15 земных масс.

Методы словаря#

Как и у списков, у словарей есть множество методов для работы с ними. Во-первых, можно проверять наличие ключа словаря, тем же синтаксисом, что проверяется наличие элемента в последовательностях, т.е. вычисление выражения

key in d

вернет True, если в словаре d есть ключ key, и значение False иначе.

print("one" in eng_to_ru)

True

Однако если вам хочется проверить наличие ключа, только потому что вы не уверены, что такой ключ будет присутствовать в словаре и избегаете возбуждение исключения KeyError, то лучше использовать метод get, который возвращает значение по ключу, если таковой присутствует и возвращает заданное значение по умолчанию, если ключ отсутствует.

print(eng_to_ru.get("one", "Перевод не известен!"))
print(eng_to_ru.get("eleven", "Перевод не известен!"))

один
Перевод не известен!

Есть очень похожий метод pop, который работает точно также, но если ключ в словаре присутствует, то пара извлекается из словаря и вызывающему коду возвращается значение из этой пары.

eng_to_ru["zero"] = "ноль"
print(eng_to_ru)
print(eng_to_ru.pop("zero", "Перевод не известен!"))
print(eng_to_ru)

{'one': 'один', 'two': 'два', 'three': 'три', 'five': 'пять', 'six': 'шесть', 'seven': 'семь', 'eight': 'восемь', 'nine': 'девять', 'four': 'четыре', 'zero': 'ноль'}
ноль
{'one': 'один', 'two': 'два', 'three': 'три', 'five': 'пять', 'six': 'шесть', 'seven': 'семь', 'eight': 'восемь', 'nine': 'девять', 'four': 'четыре'}

Итерация по словарю#

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

for key in eng_to_ru:
    print(key, end=" ")

one two three five six seven eight nine four

Если требуются не ключи, а только значения, то удобно использовать метод values.

for value in eng_to_ru.values():
    print(value, end=" ") 

один два три пять шесть семь восемь девять четыре

Если требуются и ключи и значения, то оптимальнее всего воспользоваться методом items, который итерируется сразу по парам (ключ, значение).

for key, value in eng_to_ru.items():
    print(f"{key:6} => {value}")

one    => один
two    => два
three  => три
five   => пять
six    => шесть
seven  => семь
eight  => восемь
nine   => девять
four   => четыре