Что такое словарь (dictionary) в программировании?

Словарь — это структура данных, которая хранит пары «ключ — значение» и позволяет быстро найти значение по ключу. В основе почти всегда лежит хеш-таблица: у ключа вычисляется хеш, по нему определяется ячейка в массиве, и в неё кладётся значение. Благодаря этому поиск, вставка и удаление в среднем работают за O(1).

В разных языках словарь называют по-своему: dict в Python, Map в Java (HashMap, TreeMap), Object / Map в JavaScript, unordered_map в C++, ассоциативный массив в PHP. Но суть одна — связь «ключ → значение». Ключ должен быть уникальным, а в большинстве языков — неизменяемым (immutable): числа, строки, кортежи в Python. Значением может быть что угодно.

Внутреннее устройство: массив «корзин» (buckets). При вставке берём хеш ключа, берём остаток от деления на размер массива — получаем номер корзины. В корзине может быть связный список или дерево (если много коллизий). Когда число элементов превышает порог (обычно load factor ≈ 0.75), массив расширяется и все элементы перехешируются — это дорогая операция, но амортизированно мы получаем O(1).

Пример на Python:

d = {"name": "Аня", "age": 25}
print(d["name"])       # "Аня"
d["city"] = "Москва"   # добавили
print("age" in d)       # True
del d["age"]            # удалили

В JavaScript аналогично с Map (у Object есть ограничения):

const m = new Map([[1, "один"], [2, "два"]]);
console.log(m.get(1));   // "один"
m.set(3, "три");
m.delete(2);

Важно: словарь не гарантирует порядок (кроме Python 3.7+ и LinkedHashMap). Коллизии — неизбежность: разные ключи могут дать одинаковый хеш. Их разрешают цепочками (chaining) или открытой адресацией. Хороший словарь поддерживает хеш-функцию, которая равномерно распределяет ключи, иначе производительность падает до O(n).

На собеседовании стоит упомянуть, что словарь — это самый частый способ быстро найти данные по идентификатору: пользователи по ID, кеш, подсчёт частот слов, графы. Для джуниора важно понять разницу между списком (поиск O(n)) и словарём (O(1)), и почему мутабельный ключ — это ловушка (после изменения хеш меняется, теряем элемент).