Словарь (карта или хэш-таблица) – это структура данных, представляющая набор пар ключ/значение. Вы можете получить доступ ко всем значениям по их ключу. Все значения могут быть любого типа (Int, String, Objects, …). Тем не менее, ключи должны быть хэшируемыми (все примитивные типы реализуют этот протокол). Словари не гарантируют порядок.
Вы должны задаться вопросом, почему ключи должны быть хешируемыми. Предположим, что hashable преобразует любой объект в целое число, которое будет использоваться для определения места хранения значения. Чем лучше хеширование, тем лучше int будет уникальным.
Каждый словарь состоит из массива сегментов (каждый сегмент будет связанным списком, чтобы узнать больше об этом, пожалуйста, обратитесь к соответствующей статье). Допустим, у нас есть только три ведра в нашем предыдущем примере; мы будем использовать ведро с индексом 1. Поскольку это ограниченное количество массивов, нам нужно использовать модуль хэша ключа.
Из-за неуникальности хэширования и модуля это приведет к коллизиям индексов. Это означает, что два разных ключа окажутся в одном сегменте. После того, как мы идентифицировали сегмент, нам нужно линейно проверять его, пока не будет найден правильный ключ.
Хотя словарь является одной из наиболее часто используемых структур данных, мы должны использовать его, когда нам нужен ключевой доступ к его значению. Например, мы хотим подсчитать количество вхождений символа в строку. Наоборот, если вы хотите только проверить наличие элемента, посмотрите на структуру данных Set.
Чтобы установить новую пару ключ/значение.
Вы можете легко перебирать словарь, но это не гарантирует порядок.
Вы можете получить все ключи или все значения, а затем отсортировать их; вы сможете всегда получать один и тот же порядок, но может не совпадать с порядком добавления элементов.
Количество ковшей называется вместимостью; словарь хорошего размера приводит к очень хорошей средней производительности O (1), в то время как одно ведро приводит к производительности простого списка O (n).
Временная сложность:
- доступ по ключу: O(1),
- установить: О(1),
- удалить: О(1),
- содержит: О(1),
- Итерация: O(n),
- пусто: О(1),
- количество: О (1).
