Python добавить значение в словарь по ключу. Словари и их методы в Python
В языке программирования Python словари (тип dict) представляют собой еще одну разновидность структур данных наряду со списками и кортежами. Словарь - это изменяемый (как список) неупорядоченный (в отличие от строк, списков и кортежей) набор элементов "ключ:значение".
"Неупорядоченный" – значит, что последовательность расположения пар не важна. Язык программирования ее не учитывает, в следствие чего обращение к элементам по индексам невозможно.
В других языках структуры, схожие со словарями, называются по-другому. Например, в Java подобный тип данных называется отображением.
Чтобы представление о словаре стало более понятным, проведем аналогию с обычным словарем, например, англо-русским. На каждое английское слово в таком словаре есть русское слово-перевод: cat – кошка, dog – собака, table – стол и т. д. Если англо-русский словарь описать с помощью Python, то английские слова можно сделать ключами, а русские – их значениями:
{ "cat" : "кошка" , "dog" : "собака" , "bird" : "птица" , "mouse" : "мышь" }
Обратите внимание на фигурные скобки, именно с их помощью определяется словарь. Синтаксис словаря на Питоне описывается такой схемой:
Часто при выводе словаря последовательность пар "ключ:значение" не совпадает с тем, как было введено:
>>> a = { "cat" : "кошка" , "dog" : "собака" , "bird" : "птица" , "mouse" : "мышь" } >>> a {"dog": "собака", "cat": "кошка", "bird": "птица", "mouse": "мышь"}
Поскольку в словаре не важен порядок пар, то интерпретатор выводит их так, как ему удобно. Тогда как получить доступ к определенному элементу, если индексация не возможна в принципе? В словаре доступ к значениям осуществляется по ключам, которые заключаются в квадратные скобки (по аналогии с индексами списков):
>>> a[ "cat" ] "кошка" >>> a[ "bird" ] "птица"
Словари, как и списки, являются изменяемым типом данных: позволительно изменять, добавлять и удалять элементы (пары "ключ:значение"). Изначально словарь можно создать пустым (например, d = {}) и потом заполнить его элементами. Добавление и изменение имеет одинаковый синтаксис: словарь[ключ] = значение. Ключ может быть как уже существующим (тогда происходит изменение значения), так и новым (происходит добавление элемента словаря). Удаление элемента осуществляется с помощью встроенной оператора del языка Python.
>>> a[ "elephant" ] = "бегемот" # добавляем >>> a[ "table" ] = "стол" # добавляем >>> a {"dog": "собака", "cat": "кошка", "mouse": "мышь", "bird": "птица", "table": "стол", "elephant": "бегемот"} >>> a[ "elephant" ] = "слон" # изменяем >>> del a[ "table" ] # удаляем >>> a {"dog": "собака", "cat": "кошка", "mouse": "мышь", "bird": "птица", "elephant": "слон"}
В словаре не может быть двух элементов с одинаковыми ключами. Однако могут быть одинаковые значения у разных ключей.
Ключом может быть любой неизменяемый тип данных. Значением – любой тип данных. Значения словарей вполне могут быть структурами, например, другими словарями или списками.
>>> nums = { 1 : "one" , 2 : "two" , 3 : "three" } >>> person = { "name" : "Tom" , 1 : [ 30 , 15 , 16 ] , 2 : 2.34 , ("ab" , 100 ) : "no" }
Перебор элементов словаря в цикле for
Элементы словаря перебираются в цикле for также, как элементы других сложных объектов. Однако "по-умолчанию" извлекаются только ключи:
>>> nums >>> for i in nums: ... print (i) ... 1 2 3
Но по ключам всегда можно получить значения:
>>> for i in nums: ... print (nums[ i] ) ... one two three
С другой стороны у словаря как класса есть метод items(), который создает особую структуру, состоящую из кортежей. Каждый кортеж включает ключ и значение:
>>> n = nums.items () >>> n dict_items([(1, "one"), (2, "two"), (3, "three")])
В цикле for можно распаковывать кортежи, таким образом сразу извлекая как ключ, так и его значение:
>>> for key, value in nums.items () : ... print (key, "is" , value) ... 1 is one 2 is two 3 is three
Методы словаря keys() и values() позволяют получить отдельно перечни ключей и значений. Так что если, например, надо перебрать только значения или только ключи, лучше воспользоваться одним из этих методов:
>>> v_nums = >>> for v in nums.values () : ... v_nums.append (v) ... >>> v_nums ["one", "two", "three"]
Методы словаря
Кроме рассмотренных выше трех методов items(), keys() и values() словари обладают еще восемью. Это методы clear(), copy(), fromkeys(), get(), pop(), popitem(), setdefault(), update().
Метод clear() удаляет все элементы словаря, но не удаляет сам словарь. В итоге остается пустой словарь:
>>> a {"dog": "собака", "cat": "кошка", "mouse": "мышь", "bird": "птица", "elephant": "слон"} >>> a.clear () >>> a {}
Словарь – это изменяемый тип данных. Следовательно, как и список он передается в функцию по ссылке. Поэтому иногда, чтобы избежать нежелательного изменения глобального словаря его копируют. Это делают и с другими целями.
>>> nums2 = nums.copy () >>> nums2[ 4 ] = "four" >>> nums {1: "one", 2: "two", 3: "three"} >>> nums2 {1: "one", 2: "two", 3: "three", 4: "four"}
Метод fromkeys() позволяет создать словарь из списка, элементы которого становятся ключами. Применять метод можно как классу dict, так и к его объектам:
>>> a = [ 1 , 2 , 3 ] >>> c = dict .fromkeys (a) >>> c {1: None, 2: None, 3: None} >>> d = dict .fromkeys (a, 10 ) >>> d {1: 10, 2: 10, 3: 10} >>> c {1: None, 2: None, 3: None}
Метод get() позволяет получить элемент по его ключу:
>>> nums.get (1 ) "one"
Равносильно nums .
Метод pop() удаляет из словаря элемент по указанному ключу и возвращает значение удаленной пары. Метод popitem() не принимает аргументов, удаляет и возвращает произвольный элемент.
>>> nums.pop (1 ) "one" >>> nums {2: "two", 3: "three"} >>> nums.popitem () (2, "two") >>> nums {3: "three"}
С помощью setdefault() можно добавить элемент в словарь:
>>> nums.setdefault (4 , "four" ) "four" >>> nums {3: "three", 4: "four"}
Равносильно nums = "four" , если элемент с ключом 4 отсутствует в словаре. Если он уже есть, то nums = "four" перезапишет старое значение, setdefault() – нет.
С помощью update() можно добавить в словарь другой словарь:
>>> nums.update ({ 6 : "six" , 7 : "seven" } ) >>> nums {3: "three", 4: "four", 6: "six", 7: "seven"}
Также метод обновляет значения существующих ключей. Включает еще ряд особенностей.
Практическая работа
Создайте словарь, связав его с переменной school, и наполните данными, которые бы отражали количество учащихся в разных классах (1а, 1б, 2б, 6а, 7в и т. п.). Внесите изменения в словарь согласно следующему: а) в одном из классов изменилось количество учащихся, б) в школе появился новый класс, с) в школе был расформирован (удален) другой класс. Вычислите общее количество учащихся в школе.
Создайте словарь, где ключами являются числа, а значениями – строки. Примените к нему метод items(), полученный объект dict_items передайте в написанную вами функцию, которая создает и возвращает новый словарь, "обратный" исходному, т. е. ключами являются строки, а значениями – числа.
Словари – это изменяемый неупорядоченный тип данных, состоящий из коллекций произвольных объектов в формате «ключ: значение». Также словари называются хэш-таблицами или ассоциативными массивами.
Обычно словари используются для хранения связанных между собой данных; например, пара может состоять из имени пользователя и его ID. Элементы словарей берутся в фигурные скобки { }.
Словарь выглядит так:
Чтобы отделить ключ от значения, в словарях используются символы двоеточия. Пары «ключ: значение» отделяются друг от друга запятыми.
Ключи всегда находятся слева от двоеточия. Ключ может быть представлен любым неизменяемым типом данных. В приведённом выше примере содержатся такие ключи:
- ‘username’
- ‘online’
- ‘followers’
В данном случае ключи выражены строками.
Слева от двоеточия находятся значения. Значение может выражаться любым типом данных. В словаре выше мы видим такие значения:
- ‘8host-blog’
Первый ключ представлен строкой, второй – логическим значением, а третий – целым числом.
Читайте также:
Попробуйте отобразить словарь 8host:
print(8host)
{"username": "8host-blog", "followers": 987, "online": True}
Обратите внимание: порядок пар «ключ: значение» изменился. Это произошло потому, что словари являются неупорядоченным типом данных. В отличие от списков и кортежей, словари не сохраняют порядок своих элементов и, соответственно, не индексируются.
Читайте также:
В словарях пары всегда расположены в случайном порядке. Однако сами пары «ключ: значение» всегда остаются неизменными, благодаря чему и осуществляется доступ к данным.
Доступ к элементам словаря
Поскольку элементы словаря не упорядочены, к ним невозможно получить доступ по индексу. Чтобы получить доступ к значению, нужно вызвать соответствующий ключ.
Доступ к данным по ключу
Словари могут стать важной частью разработанной в Python программы.
К примеру, чтобы вывести только имя пользователя в приведённом выше словаре, нужно ввести:
print(8host["username"])
8host-blog
Словари ведут себя как базы данных, потому что для доступа к значению используется ключ, а не индекс.
Таким же образом можно вызвать и остальные значения этого словаря:
print(8host["followers"])
987
print(8host["online"])
True
Доступ к данным с помощью функций
Доступ к значениям можно получить не только с помощью ключей, но и при помощи функций.
- dict.keys() – выводит ключи словаря.
- dict.values() – выводит значения словаря.
- dict.items() – выводит пары в виде кортежа (ключ, значение).
Попробуйте использовать функцию dict.keys(), чтобы получить ключи словаря. Передайте переменную 8host.keys() функции print().
print(8host.keys())
dict_keys(["followers", "username", "online"])
Ключи возвращаются в виде итерируемого объекта класса dict_keys и отображаются в формате списка.
С помощью этой функции можно создавать запросы. К примеру, так можно просмотреть одинаковые ключи в двух словарях:
8host = {"username": "8host-blog", "online": True, "followers": 987}
jesse = {"username": "Jesse", "online": False, "points": 723}
for common_key in 8host.keys() & jesse.keys():
print(сайтmon_key], jesse)
Словари 8host и jesse содержат данные о профилях пользователей.
Эти профили отличаются: первый – профиль для социальных сетей, второй – профиль для игр. Однако у них совпадают два ключа: username и online. Чтобы убедиться в этом, запустите программу, и она выдаст:
8host-blog Jesse
True False
Но этот пример продемонстрировал, что dict.keys () можно использовать для поиска общих ключей в разных словарях (особенно в больших словарях). Конечно, можно улучшить программу и сделать вывод более удобным для чтения.
Функция dict.values() используется аналогичным образом и возвращает значения заданного словаря. Например:
8host = {"username": "8host-blog", "online": True, "followers": 987}
print(8host.values())
dict_values()
Методы keys() и values() возвращают неотсортированные ключи или значения словаря 8host в виде объектов dict_keys и dict_values соответственно.
Чтобы запросить все элементы словаря, используйте функцию items():
print(8host.items())
dict_items([("online", True), ("username", "8host-blog"), ("followers", 987)])
Эта функция возвращает объект dict_items, который состоит из пар (ключ, значение), представленных в виде кортежей.
Возвращенные списки можно итерировать с помощью цикла for. К примеру, так можно вывести каждый ключ и значение заданного словаря в более удобном для чтения формате:
for key, value in 8host.items():
print(key, "is the key for the value", value)
online is the key for the value True
followers is the key for the value 987
username is the key for the value 8host-blog
Цикл for выполнил итерацию списков ключей и значений и вывел результат построчно.
Редактирование словарей
Словари являются изменяемым типом данных, потому их можно редактировать. В данном разделе вы узнаете, как добавлять и удалять элементы словарей.
Добавление и изменение элементов словарей
Для добавления элементов используется такой синтаксис:
dict = value
Попробуйте добавить в словарь новую пару. Например:
usernames = {"8host": "8host-blog", "Jamie": "jamie54"}
usernames["Drew"] = "iam-drew"
print(usernames)
{"Drew": "iam-drew", "8host": "8host-blog", "Jamie": "jamie54"}
Как видите, в словаре появилась новая пара ‘Drew’: ‘iam-drew’.
Этот же синтаксис можно использовать для изменения значений, присвоенных ключам. Для этого нужно сослаться на требуемый ключ и передать ему новое значение.
Давайте рассмотрим словарь drew, который содержит данные об одном из пользователей этой сети. Предположим, сегодня количество его подписчиков заметно увеличилось, потому нужно обновить значение его ключа ‘followers’. Чтобы убедиться, что значение было изменено, используйте функцию print().
drew = {"username": "iam-drew", "online": True, "followers": 305}
drew["followers"] = 342
print(drew)
{"username": "iam-drew", "followers": 342, "online": True}
Как видите, значение ключа followers было изменено.
Этот метод позволяет добавлять данные в словарь путём пользовательского ввода. Создайте простую программу для командной строки, usernames.py, которая позволит пользователям добавлять данные в словарь.
# Определить исходный словарь
usernames = {"8host": "8host-blog", "Jamie": "jamie54"}
# Добавить цикл while
while True:
# Запросить имя
print("Enter a name:")
# Присвоить его переменной
name = input()
# Проверить, есть ли такое имя в словаре и вывести результат
if name in usernames:
print(usernames + " is the username of " + name)
# Если имени нет…
else:
# Вывести на экран
print("I don\"t have " + name + "\"s username, what is it?")
# Добавить имя пользователя для такого имени
username = input()
# Присвоить имя пользователя ключу
usernames = username
# Сообщить об обновлении данных
print("Data updated.")
Запустите программу с помощью командной строки:
python usernames.py
Она выведен на экран:
Enter a name:
8host
8host-blog is the username of 8hosts
Enter a name:
Jesse
I don"t have Jesse"s username, what is it?
Jesse
Data updated.
Enter a name:
Чтобы остановить программу, нажмите CTRL + C.
Сегодня я расскажу о таком типе данных, как словари , о работе со словарями, операциях над ними, методах, о генераторах словарей.
Словари в Python - неупорядоченные коллекции произвольных объектов с доступом по ключу. Их иногда ещё называют ассоциативными массивами или хеш-таблицами.
Чтобы работать со словарём, его нужно создать. Создать его можно несколькими способами. Во-первых, с помощью литерала:
>>> d = {} >>> d {} >>> d = { "dict" : 1 , "dictionary" : 2 } >>> d {"dict": 1, "dictionary": 2}Во-вторых, с помощью функции dict :
>>> d = dict (short = "dict" , long = "dictionary" ) >>> d {"short": "dict", "long": "dictionary"} >>> d = dict ([(1 , 1 ), (2 , 4 )]) >>> d {1: 1, 2: 4}В-третьих, с помощью метода fromkeys:
>>> d = dict . fromkeys ([ "a" , "b" ]) >>> d {"a": None, "b": None} >>> d = dict . fromkeys ([ "a" , "b" ], 100 ) >>> d {"a": 100, "b": 100}В-четвертых, с помощью генераторов словарей, которые очень похожи на .
>>> d = { a : a ** 2 for a in range (7 )} >>> d {0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36}Теперь попробуем добавить записей в словарь и извлечь значения ключей:
>>> d = { 1 : 2 , 2 : 4 , 3 : 9 } >>> d [ 1 ] 2 >>> d [ 4 ] = 4 ** 2 >>> d {1: 2, 2: 4, 3: 9, 4: 16} >>> d [ "1" ] Traceback (most recent call last): File "", line 1, in d["1"] KeyError : "1"Как видно из примера, присвоение по новому ключу расширяет словарь, присвоение по существующему ключу перезаписывает его, а попытка извлечения несуществующего ключа порождает исключение. Для избежания исключения есть специальный метод (см. ниже), или можно .
Что же можно еще делать со словарями? Да то же самое, что и с другими объектами: , (например, ), а также специальные методы словарей.
Методы словарей
dict.clear () - очищает словарь.
dict.copy () - возвращает копию словаря.
classmethod dict.fromkeys (seq[, value]) - создает словарь с ключами из seq и значением value (по умолчанию None).
dict.get (key[, default]) - возвращает значение ключа, но если его нет, не бросает исключение, а возвращает default (по умолчанию None).
dict.items () - возвращает пары (ключ, значение).
dict.keys () - возвращает ключи в словаре.
dict.pop (key[, default]) - удаляет ключ и возвращает значение. Если ключа нет, возвращает default (по умолчанию бросает исключение).
dict.popitem () - удаляет и возвращает пару (ключ, значение). Если словарь пуст, бросает исключение KeyError. Помните, что словари неупорядочены.
dict.setdefault (key[, default]) - возвращает значение ключа, но если его нет, не бросает исключение, а создает ключ с значением default (по умолчанию None).
dict.update () - обновляет словарь, добавляя пары (ключ, значение) из other. Существующие ключи перезаписываются. Возвращает None (не новый словарь!).
dict.values () - возвращает значения в словаре.
На Stack Overflow.
В статье рассматривается реализация CPython версии 2.7. Все примеры были подготовлены в 32-битной версии Python на 64-битной ОС, для другой версии значения будут отличаться.
Словарь в Python
Словарь в Python является ассоциативным массивом, то есть хранит данные в виде пар (ключ, значение). Словарь – измененяемый тип данных. Это значит, что в него можно добавлять элементы, изменять их и удалять из словаря. Он также предоставляет операцию поиска и возвращения элемента по ключу.Инициализация и добавление элементов:
>>> d = {} # то же самое, что d = dict()
>>> d["a"] = 123
>>> d["b"] = 345
>>> d["c"] = 678
>>> d
{"a": 123, "c": 678, "b": 345}
Получение элемента:
>>> d["b"]
345
Удаление элемента:
>>> del d["c"]
>>> d
{"a": 123, "b": 345}
Ключами словаря могут быть значения только hashable типов, то есть типов, у которых может быть получен хэш (для этого у них должен быть метод __hash__()). Поэтому значения таких типов, как список (list), набор (set) и собственно сам словарь (dict), не могут быть ключами словаря:
>>> d = 1
Traceback (most recent call last):
File "
Реализация
Словарь в Python реализован в виде хэш-таблицы. Как известно, реализация хэш-таблицы должна учитывать возможность появления коллизий – ситуаций, когда разные ключи имеют одинаковое значение хэша. Должен быть способ вставки и извлечения элементов с учётом коллизий. Существует несколько способов разрешения коллизий, например метод цепочек и метод открытой адресации. В Python используется метод открытой адресации. Разработчики предпочли метод открытой адресации методу цепочек ввиду того, что он позволяет значительно сэкономить память на хранении указателей, которые используются в хэш-таблицах с цепочками.В рассматриваемой реализации каждая запись (PyDictEntry) в хэш-таблице словаря состоит из трёх элементов – хэш, ключ и значение.
Typedef struct {
Py_ssize_t me_hash;
PyObject *me_key;
PyObject *me_value;
} PyDictEntry;
Структура PyDictObject выглядит следующим образом:
#define PyDict_MINSIZE 8
typedef struct _dictobject PyDictObject;
struct _dictobject {
PyObject_HEAD
Py_ssize_t ma_fill;
Py_ssize_t ma_used;
Py_ssize_t ma_mask;
PyDictEntry *ma_table;
PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
PyDictEntry ma_smalltable;
};
При создании нового объекта словаря его размер равен 8. Это значение определяется константой PyDict_MINSIZE. Для хранения хэш-таблицы в PyDictObject были введены переменные ma_smalltable и ma_table. Переменная ma_smalltable с предвыделенной памятью размером PyDict_MINSIZE (то есть 8) позволяет небольшим словарям (до 8 объектов PyDictEntry) храниться без дополнительного выделения памяти. Эксперименты, проведённые разработчиками, показали, что этого размера вполне достаточно для большинства словарей: небольших словарей экземпляров и обычно небольших словарей, созданных для передачи именованных аргументов (kwargs). Переменная ma_table соответствует ma_smalltable для маленьких таблиц (то есть для таблиц из 8 ячеек). Для таблиц большего размера память ma_table выделяется отдельно. Переменная ma_table не может быть равна NULL.
Если кому-то вдруг захочется изменить значение PyDict_MINSIZE, это можно сделать в исходниках, а затем пересобрать Python. Значение рекомендуется делать равным степени двойки, но не меньше четырёх.
Ячейка в хэш-таблице может иметь три состояния
1) Неиспользованная (me_key == me_value == NULL)Данное состояние означает, что ячейка не содержит и ещё никогда не содержала пару (ключ, значение).
После вставки ключа «неиспользованная» ячейка переходит в состояние «активная».
Это состояние – единственный случай, когда me_key = NULL и является начальным состоянием для всех ячеек в таблице.
2) Активная (me_key != NULL и me_key != dummy и me_value != NULL)
Означает, что ячейка содержит активную пару (ключ, значение).
После удаления ключа ячейка из состояния «активная» переходит в состояние «пустая» (то есть me_key = dummy, а
dummy = PyString_FromString("
Это единственное состояние, когда me_value != NULL.
3) Пустая (me_key == dummy и me_value == NULL)
Это состояние говорит о том, что ячейка ранее содержала активную пару (ключ, значение), но она была удалена, и новая активная пара ещё не записана в ячейку.
Так же как и при состоянии «неиспользованная», после вставки ключа ячейка из состояния «пустая» переходит в состояние «активная».
«Пустая» ячейка не может вернуться в состояние «неиспользованная», то есть вернуть me_key = NULL, так как в данном случае последовательность проб в случае коллизии не будет иметь возможность узнать, были ли ячейки «активны».
Переменные-члены структуры
ma_fill – число ненулевых ключей (me_key != NULL), то есть сумма «активных» и «пустых» ячеек.ma_used – число ненулевых и не «пустых» ключей (me_key != NULL, me_key != dummy), то есть число «активных» ячеек.
ma_mask – маска, равная PyDict_MINSIZE - 1.
ma_lookup – функция поиска. По умолчанию при создании нового словаря используется lookdict_string. Так сделано потому, что разработчики посчитали, что большинство словарей содержат только строковые ключи.
Основные тонкости
Эффективность хэш-таблицы зависит от наличия «хороших» хэш-функций. «Хорошая» хэш-функция должна вычисляться быстро и с минимальным количеством коллизий. Но, к сожалению, наиболее часто используемые и важные хэш-функции (для строкового и целого типов) возвращают достаточно регулярные значения, что приводит к коллизиям. Возьмём пример: >>> map(hash, )
>>> map(hash, ["abca", "abcb", "abcc", "abcd", "abce"])
Для целых чисел хэшами являются их значения, поэтому подряд идущие числа будут иметь подряд идущие хэши, а для строк подряд идущие строки имеют практически подряд идущие хэши. Это не обязательно плохо, напротив, в таблице размером 2**i взятие i младших бит хэша как начального индекса таблицы выполняется очень быстро, и для словарей, проиндексированных последовательностью целых чисел, коллизий не будет вообще:
То же самое будет почти полностью соблюдаться, если ключи словаря – это «подряд идущие» строки (как в примере выше). В общих случаях это дает более чем случайное поведение, что и требуется.
Взятие только i младших бит хэша в качестве индекса также уязвимо к коллизиям: например, возьмём список в качестве набора ключей. Так как целые являются их собственными хэшами и это вписывается в словарь размера 2**15 (так как 20000 < 32768), последние 15 бит от каждого хэша все будут равны 0.
>>> map(lambda x: "{0:016b}".format(x), )
["0000000000000000", "10000000000000000", "100000000000000000", "110000000000000000", "1000000000000000000", "1010000000000000000", "1100000000000000000", "1110000000000000000", ...]
Получится, что все ключи будут иметь один и тот же индекс. То есть для всех ключей (кроме первого) произойдут коллизии.
Примеры специально подобранных «плохих» случаев не должны влиять на обычные случаи, так что просто оставим взятие последних i бит. Всё остальное отдаётся на откуп методу разрешения коллизий.
Метод разрешения коллизий
Процедура выбора подходящей ячейки для вставки элемента в хэш-таблицу называется пробирование, а рассматриваемая ячейка-кандидат – проба.Обычно ячейка находится с первой попытки (и это действительно так, ведь коэффициент заполнения хэш-таблицы держится ниже 2/3), что позволяет не тратить время на пробирование и делает расчет начального индекса очень быстрым. Но давайте рассмотрим, что случится, если произойдёт коллизия.
Первая часть метода разрешения коллизий заключается в расчёте индексов таблицы для пробирования с помощью формулы:
J = ((5 * j) + 1) % 2**i
Для любого начального j в пределах вызов данной формулы 2**i раз вернёт каждое число в пределах ровно один раз. Например:
>>> j = 0
>>> i = 3
>>> for _ in xrange(0, 2**i):
... print j,
... j = ((5 * j) + 1) % 2**i
...
0 1 6 7 4 5 2 3
Вы скажете, что это ничем не лучше использования линейного пробирования с постоянным шагом, ведь в данном случае ячейки в хэш-таблице также просматриваются в определенном порядке, но это не единственное отличие. В общих случаях, когда хэш значения ключей идут подряд, данный метод лучше линейного пробирования. Из примера выше можно проследить, что для таблицы размером 8 (2**3) порядок индексов будет следующим:
0 -> 1 -> 6 -> 7 -> 4 -> 5 -> 2 -> 3 -> 0 -> … (затем идут повторения)
Если произойдёт коллизия для пробы с индексом, равным 5, то следующий индекс пробы будет 2, а не 6, как в случае линейного пробирования с шагом +1, поэтому для ключа, добавляемого в будущем, индекс пробы которого будет равен 6, коллизии не произойдёт. Линейное пробирование в данном случае (при последовательных значениях ключей) было бы плохим вариантом, так как происходило бы много коллизий. Вероятность же того, что хэш значения ключей будут идти в порядке 5 * j + 1, намного меньше.
Вторая часть метода разрешения коллизий заключается в использовании не только младших i бит хэша, но и остальных бит тоже. Это реализовано с использованием переменной perturb следующим образом:
J = (5 * j) + 1 + perturb
perturb >>= PERTURB_SHIFT
затем j % 2**i используется как следующий индекс пробы
где:
perturb = hash(key)
PERTURB_SHIFT = 5
После этого последовательность проб будет зависеть от каждого бита хэша. Псевдослучайное изменение очень эффективно, потому что быстро увеличивает различия в битах. Так как переменная perturb – беззнаковая, то, если пробирование выполняется достаточно часто, переменная perturb в конечном итоге становится и остаётся равной нулю. В этот момент (который достигается очень редко) результат j снова становится равен 5 * j + 1. Далее поиск происходит точно так же, как в первой части метода, и свободная ячейка в конечном счете будет найдена, поскольку, как было сказано ранее, каждое число в диапазоне будет возвращено ровно один раз, и мы уверены, что всегда есть по крайней мере одна «неиспользованная» ячейка.
Выбор «хорошего» значения для PERTURB_SHIFT – это вопрос балансировки. Если сделать его малым, то старшие биты хэша будут влиять на последовательность проб по итерациям. Если же сделать его большим, то в действительно «плохих» случаях старшие биты хэша будут оказывать влияние только на ранних итерациях. В результате экспериментов, которые провёл один из разработчиков Python – Тим Питерс, значение PERTURB_SHIFT было выбрано равным 5, так как это значение оказалось «лучшим». То есть показало минимальное общее число коллизий как для нормальных, так и для специально подобранных «плохих» случаев, хотя значения 4 и 6 не были значительно хуже.
Историческая справка: Один из разработчиков Python, Реймер Берендс, предлагал идею использования подхода расчёта индексов таблицы, основанного на многочленах, который затем был улучшен Кристианом Тисмером. Этот подход также показал отличные результаты по возникновению коллизий, но требовал больше операций, а также дополнительной переменной для хранения многочлена таблицы в структуре PyDictObject. В экспериментах Тима Питерса текущий, используемый в Python метод оказался быстрее, показывая в равной степени хорошие результаты по возникновению коллизий, но требовал меньше кода и использовал меньше памяти.
Инициализация словаря
Когда вы создаёте словарь, вызывается функция PyDict_New. В этой функции последовательно выполняются следующие операции: происходит выделение памяти для нового объекта словаря PyDictObject. Переменная ma_smalltable очищается. Переменные ma_used и ma_fill приравниваются 0, ma_table становится равной ma_smalltable. Значение ma_mask приравнивается PyDict_MINSIZE - 1. Функция для поиска ma_lookup делается равной lookdict_string. Возвращается созданный объект словаря.Добавление элемента
При добавлении элемента в словарь или изменении значения элемента в словаре вызывается функция PyDict_SetItem. В этой функции берётся значение хэша и вызывается функция insertdict, а также функция dictresize, если таблица заполняется на 2/3 от текущего размера.В свою очередь в функции insertdict происходит вызов lookdict_string (или lookdict, если в словаре есть не строковый ключ), в которой происходит поиск свободной ячейки в хэш-таблице для вставки. Эта же функция используется для нахождения ключа при извлечении.
Начальный индекс пробы в этой функции рассчитывается как хэш ключа, поделённый по модулю на размер таблицы (таким образом, происходит взятие младших бит хэша). То есть:
>>> PyDict_MINSIZE = 8
>>> key = 123
>>> hash(key) % PyDict_MINSIZE
>>> 3
В Python это реализовано с использованием логической операции «И» и маски. Маска равна следующему значению: mask = PyDict_MINSIZE - 1.
>>> PyDict_MINSIZE = 8
>>> mask = PyDict_MINSIZE - 1
>>> key = 123
>>> hash(key) & mask
>>> 3
Так получаются младшие биты хэша:
2**i = PyDict_MINSIZE, отсюда i = 3, то есть достаточно трёх младших бит.
hash(123) = 123 = 1111011 2
mask = PyDict_MINSIZE - 1 = 8 - 1 = 7 = 111 2
index = hash(123) & mask = 1111011
2 & 111
2 = 011
2 = 3
После того как индекс рассчитан, выполняется проверка ячейки по индексу, и если она «неиспользованная», то в неё добавляется запись (хэш, ключ, значение). Но если эта ячейка занята, из-за того, что другая запись имеет тот же хэш (то есть произошла коллизия), выполняется сравнение хэша и ключа вставляемой записи и записи в ячейке. Если хэш и ключ для записей совпадают, то считается, что запись уже существует в словаре, и выполняется её обновление.
Это объясняет хитрый момент, связанный с добавлением равных по значению, но разных по типу ключей (к примеру, float, int и complex):
>>> 7.0 == 7 == (7+0j)
True
>>> d = {}
>>> d="float"
>>> d
{7.0: "float"}
>>> d="int"
>>> d
{7.0: "int"}
>>> d="complex"
>>> d
{7.0: "complex"}
>>> type(d.keys())
То есть тот тип, который был добавлен в словарь первым, и будет типом ключа, несмотря на обновление. Это объясняется тем, что реализация хэша для float значений возвращает хэш от int, если дробная часть равна 0.0. Пример расчёта хэша для float, переписанный на Python:
Def float_hash(float_value):
...
fractpart, intpart = math.modf(float_value)
if fractpart == 0.0:
return int_hash(int(float_value)) # использовать хэш int
...
А хэш от complex возвращает хэш от float. В данном случае возвращается хэш только действительной части, так как мнимая часть равна нулю:
Def complex_hash(complex_value):
hashreal = float_hash(complex_value.real)
if hashreal == -1:
return -1
hashimag = float_hash(complex_value.imag)
if hashimag == -1:
return -1
res = hashreal + 1000003 * hashimag
res = handle_overflow(res)
if res == -1:
res = -2
return res
Пример:
>>> hash(7)
7
>>> hash(7.0)
7
>>> hash(7+0j)
7
Ввиду того, что и хэши, и значения для всех трёх типов равны, выполняется простое обновление значения найденной записи.
Замечание по поводу добавления элементов: Python запрещает добавление элементов в словарь во время итерации, поэтому при попытке добавить новый элемент произойдёт ошибка:
>>> d = {"a": 1}
>>> for i in d:
... d["new item"] = 123
...
Traceback (most recent call last):
File "
Вернёмся к процедуре добавления элемента в словарь. После успешного добавления или обновления записи в хэш-таблице происходит сравнение следующей записи-кандидата на вставку. Если хэш или ключ у записей не совпадают, начинается пробирование. Происходит поиск «неиспользованной» ячейки для вставки. В данной реализации Python используется случайное (а если переменная perturb равна нулю – квадратичное) пробирование. Как было описано выше, при случайном пробировании индекс следующей ячейки выбирается псевдослучайным образом. Запись добавляется в первую найденную «неиспользованную» ячейку. То есть два ключа a и b, у которых hash(a) == hash(b), но a != b могут легко существовать в одном словаре. В случае если ячейка по начальному индексу пробы «пустая», произойдёт пробирование. И если первая найденная ячейка будет «нулевая», то «пустая» ячейка будет использована заново. Это позволяет перезаписать удалённые ячейки, сохраняя ещё неиспользованные.
Получается, что индексы добавляемых в словарь элементов зависят от уже находящихся в нём элементов, и порядок ключей для двух словарей, состоящих из одного и того же набора пар (ключ, значение), может быть разным и определяется очерёдностью добавления элементов:
>>> d1 = {"one": 1, "two": 2, "three": 3, "four": 4, "five": 5}
>>> d2 = {"three": 3, "two": 2, "five": 5, "four": 4, "one": 1}
>>> d1 == d2
True
>>> d1.keys()
["four", "three", "five", "two", "one"]
>>> d2.keys()
["four", "one", "five", "three", "two"]
Это объясняет, почему словари в Python при выводе содержимого отображают хранимые пары (ключ, значение) не в порядке их добавления в словарь. Словари выводят их в порядке расположения в хэш-таблице (то есть в порядке индексов).
Рассмотрим пример:
>>> d = {}
>>> d["habr"] = 1
Произошла вставка по индексу 5. Переменные ma_fill и ma_used стали равны 1.
>>> d["python"] = 2
Произошла вставка по индексу 0. Переменные ma_fill и ma_used стали равны 2.
>>> d["dict"] = 3
Произошла вставка по индексу 4. Переменные ma_fill и ma_used стали равны 3.
>>> d["article"] = 4
Произошла вставка по индексу 1. Переменные ma_fill и ma_used стали равны 4.
>>> d["!!!"] = 5
Произошло следующее:
hash("!!!") = -1297030748
i = -1297030748 & 7 = 4
Но как видно из таблицы, индекс 4 уже занят записью с ключом "dict". То есть произошла коллизия. Начинается пробирование:
perturb = -1297030748
i = (i * 5) + 1 + perturb
i = (4 * 5) + 1 + (-1297030748) = -1297030727
index = -1297030727 & 7 = 1
Новый индекс пробы равен 1, но данный индекс тоже занят (записью с ключом "article"). Произошла ещё одна коллизия, продолжаем пробирование:
perturb = perturb >> PERTURB_SHIFT
perturb = -1297030748 >> 5 = -40532211
i = (i * 5) + 1 + perturb
i = (-1297030727 * 5) + 1 + (-40532211) = -6525685845
index = -6525685845 & 7 = 3
Новый индекс пробы равен 3, и, так как он не занят, происходит вставка записи с ключом "!!!" в ячейку с третьим индексом. В данном случае запись была добавлена после двух проб из-за произошедших коллизий. Переменные ma_fill и ma_used стали равны 5.
>>> d
{"python": 2, "article": 4, "!!!": 5, "dict": 3, "habr": 1}
Пробуем добавить шестой элемент в словарь.
>>> d[";)"] = 6
После добавления шестого элемента таблица будет заполнена на 2/3, а соответственно, произойдёт изменение её размера. После того как размер изменится (в данном случае увеличится в 4 раза), произойдёт полная перестройка хэш-таблицы с учётом нового размера – все «активные» ячейки будут перераспределены, а «пустые» и «неиспользованные» ячейки будут проигнорированы.
Размер хэш-таблицы теперь равен 32, а переменные ma_fill и ma_used стали равны 6. Как видно, порядок элементов полностью поменялся:
>>> d {"!!!": 5, "python": 2, "habr": 1, "dict": 3, "article": 4, ";)": 6}
Поиск элемента
Поиск записи в хэш-таблице словаря происходит аналогично, начинаясь с ячейки i, где i зависит от хэша ключа. Если хэш и ключ не совпадают с хэшом и ключом найденной записи (то есть была коллизия и надо найти подходящую запись) – начинается пробирование, которое продолжается, пока не будет найдена запись, для которой хэш и ключ совпадают. Если же все ячейки были просмотрены, но запись не найдена, возвращается ошибка. >>> d = {"a": 123, "b": 345, "c": 678}
>>> d["x"]
Traceback (most recent call last):
File "
Коэффициент заполнения хэш-таблицы
Размер таблицы изменяется, когда она заполняется на 2/3. То есть для начального размера хэш-таблицы словаря, равного 8, изменение произойдёт после того, как будет добавлен 6 элемент. >>> 8 * 2.0 / 3
5.333333333333333
При этом происходит перестройка хэш-таблицы с учётом её нового размера, а соответственно, меняются и индексы всех записей.
Значение 2/3 от размера было выбрано как оптимальное, для того чтобы пробирование не занимало слишком много времени, то есть вставка новой записи происходила быстро. Увеличение этого значения приводит к тому, что словарь плотнее заполняется записями, что в свою очередь увеличивает количество коллизий. Уменьшение же увеличивает разреженность записей в ущерб увеличения занимаемых ими кэш-линий процессора и в ущерб увеличения общего объема памяти. Проверка заполнения таблицы происходит в весьма чувствительном ко времени участке кода. Попытки сделать проверку более сложной (например, изменяя коэффициент заполнения для разных размеров хэш-таблицы) уменьшали производительность.
Проверить, что размер словаря действительно изменяется, можно так:
>>> d = dict.fromkeys(range(5))
>>> d.__sizeof__()
248
>>> d = dict.fromkeys(range(6))
>>> d.__sizeof__()
1016
В примере возвращается размер всего объекта PyDictObject для 64-битной версии ОС.
Начальный размер таблицы равен 8. Таким образом, когда число заполненных ячеек будет равно 6 (то есть больше 2/3 от размера), размер таблицы увеличится до 32. Затем, когда число будет равно 22, увеличится до 128. При 86 увеличится до 512, при 342 – до 2048 и так далее.
Коэффициент увеличения размера таблицы
Коэффициент увеличения размера таблицы при достижении максимального уровня заполнения равен 4, если размер таблицы меньше 50000 элементов, и 2 – для таблиц большего размера. Такой подход может быть полезен приложениям с ограничениями по памяти.Увеличение размера таблицы улучшает среднюю разреженность, то есть разбросанность записей по таблице словаря (уменьшая коллизии), за счёт увеличения объема потребляемой памяти и скорости итераций, а также уменьшает количество дорогостоящих операций выделения памяти при изменении размера для растущего словаря.
Обычно добавление элемента в словарь может увеличить его размер в 4 или 2 раза в зависимости от текущего размера словаря, но также возможно, что размер словаря уменьшится. Такая ситуация может произойти, если ma_fill (количество ненулевых ключей, сумма «активных» и «пустых» ячеек) намного больше ma_used (количество «активных» ячеек), то есть много ключей было удалено.
Удаление элемента
При удалении элемента из словаря вызывается функция PyDict_DelItem.Удаление из словаря происходит по ключу, хотя в действительности освобождения памяти не происходит. В этой функции вычисляется хэш значение ключа, а затем происходит поиск записи в хэш-таблице с использованием всё той же функции lookdict_string или lookdict. В случае если запись с таким ключом и хэшем найдена, ключ этой записи выставляется в состояние «пустой» (то есть me_key = dummy), а значение записи – в NULL (me_value = NULL). После этого переменная ma_used уменьшится на единицу, а ma_fill останется без изменения. Если же запись не найдена, возвращается ошибка.
>>> del d["!!!"]
После удаления переменная ma_used стала равна 4, а ma_fill осталась равной 5, так как ячейка не была удалена, а всего лишь была помечена как «пустая» и продолжает занимать ячейку в хэш-таблице.
Рандомизация хэшей
При запуске python можно воспользоваться ключом -R, чтобы использовать псевдослучайную «соль». В этом случае хэш значения таких типов, как строки, buffer, bytes, и объекты datetime (date, time и datetime) будут непредсказуемыми между вызовами интерпретатора. Данный способ предложен в качестве защиты от DoS атак.Это четвертый пост об идиомах в Питона. Теперь пришло время узнать, что же такое словари в Python. Вы наверняка знаете, что это такая структура данных, тип которой обычно обозначают как dict. Пост же несколько подробнее расскажет о словарях: о том, как их перебирать или получать значение по ключу.
Работа со словарями Python
Вообще, словарями в Python называют коллекции произвольных объектов с доступом по ключу. При этом коллекции неупорядоченные. По-другому словари можно называть ассоциативными массивами или хеш-таблицами. Словарь может выглядеть, например, так:
Dict = {"ключ1": 1, "ключ2": 2}
Конечно же, существует куча способов работы со словарями, и все они не поместятся в этот пост. Но некоторые полезные идиомы, пожалуй, стоит упомянуть.
Цикл по ключам словаря Python
Одна из базовых операций, которая требуется при работе со словарями — это цикл по его ключам. Наверняка вы будете часто использовать такую операцию, поэтому стоит обратить внимание на правильный и красивый способ ее выполнения.
#Не перебирайте ключи так for k in dic.keys(): print(k) #Делайте это так for k in dic: print(k)
Как видите. для цикла по ключам словаря не нужно использовать метод dictionary.keys() . Все что нужно — это ссылка на словарь.
Цикл по паре ключ-значение Python
Еще одна нужная операция, которая почти всегда требуется при работе со словарями — это цикл по паре ключ:значение. Конечно же, в Python есть несколько быстрых и простых способ построить такой цикл.
#цикл можно построить так for k in dic: print(k) print(dic[k]) #или вот так for k, val in dic.items(): print(k) print(val)
В примере показано два способа перебора пар ключ-значение в словаре. Первый перебирает ключи словаря, а значения извлекает по ключу. Второй пример пробегает по словарю, распаковывая ключи и значения в две переменные.
Использование dictionary.get() для получения значений
Если нужно получить значение по ключу, но при этом неизвестно, существует такой ключ или нет — используйте метод dictionary.get() .
#Использование get() для получения значения val = dic.get("key1", "na")
Если ключ «key1» существует в словаре dic, то переменной будет присвоено значение в соответствии с ключом. В противном случае переменная получит значение второго аргумента функции get() .
Удаление элементов из словаря Python по критериям
Вероятно, если бы перед вами встала такая задача, то в мыслях сразу бы возникли циклы и условные операторы. Но в Питоне все это не требуется! Смотрите:
#Удаление элементов из словаря по критериям dic = {k: dic[k] for k in dic if not len(k) < 5}
Синтаксис очень простой: {ключ: значение for ключ in словарь [условия]}. Пример выше создаст новый словарь, которые содержит все пары ключ-значение, в которых ключ имеет длину менее 5.
Объединение двух списков в словарь
Например, у вас есть список имен и список фамилий. Но вы хотите иметь словарь из пар фамилия-имя. Что делать в такой ситуации? Объединять списки в словарь, конечно же!
#Объединение двух списков в словарь f_names = ["Ivan", "Anton", "Oleg", "Petr"] l_names = ["Petrov", "Sidorov", "Ivanov", "Skripkin"] names = dict(zip(f_names, l_names))
Эта идиома принимает на вход два списка: f_names и l_names, а затем формирует из них словарь из пар фамилия-имя. Это быстро и просто, как и в других . Если вас заинтересует метод zip() — почитайте о нем подробнее в документации.
На этом все. Надеюсь, несколько описанных идиом помогут вам эффективнее использовать словари в Python, сделать ваш код более читабельным и элегантным. Кстати, если интересно — можете почитать еще об одной структуре данных в Питоне — о .
Спасибо Jamal Moir за замечательные советы.