Ассоциативные массивы

Ассоциативный массив (словарь, мапа, map/dict/таблица символов) – абстракция, сопоставляющая ключу k значение v. В отличие от обычного массива с адресацией по индексу, доступ в ассоциативном массиве осуществляется по ключу произвольной природы (строка, число, кортеж, объект с корректным сравнением/хешированием).

Ключевые операции:

• PUT(k, v) – вставка/замена значения по ключу.

• GET(k) – получение значения по ключу (или «нет»).

• DELETE(k) – удаление пары по ключу.

• Дополнительно: CONTAINS(k), SIZE(), итерация по парам (k, v).

Связь с ЕГЭ: задачи на подсчёт частот, поиск первого уникального символа, проверку принадлежности элементов множеству, агрегирование по ключу, построение индексов – все они эффективно решаются словарём. Понимание асимптотики и инвариантов напрямую влияет на выбор алгоритмической стратегии в экзаменационных задачах.

Формальная модель и спецификация АТД «Словарь»

Модель: множество пар D ⊆ K × V с инвариантом уникальности ключей:

∀(k,v1),(k,v2) ∈ D  ⇒  v1 = v2.

Спецификация операций:

PUT(k,v):   D := (D \ {(k,*)}) ∪ {(k,v)}

GET(k):     вернуть v, для которого (k,v) ∈ D; иначе ⊥

DELETE(k):  D := D \ {(k,*)}

CONTAINS(k): True ⇔ ∃v: (k,v) ∈ D

Требование детерминированности: последовательные вызовы при фиксированном состоянии должны возвращать одинаковый результат.

Базовые реализации: обзор и сравнение

1.  Хеш-таблица с цепочками (separate chaining)
   

   • Таблица бакетов T[0..m−1], хеш-функция h: K → {0..m−1}.

   • Элемент (k,v) помещается в список (или динамический массив/дерево) T[h(k)].

   • Поиск/вставка/удаление – внутри одного бакета.

   Нагрузка (load factor):

   α = n / m,

   где n – число элементов, m – число бакетов. При равномерном хешировании средняя длина списка ≈ α.

   Оценки: ожидаемо GET/PUT/DELETE = O(1 + α), при поддержке самобалансирующегося дерева в бакете – O(log n) в худшем случае.

2. Открытая адресация (open addressing)
   

   • Все пары хранятся прямо в массиве T[0..m−1].

   • Коллизии разрешаются пробингом – поиском следующей позиции по детерминированной схеме:

   • линейный: h_i(k) = (h(k) + i) mod m;

   • квадратичный;

   • двойное хеширование: h_i(k) = (h(k) + i·g(k)) mod m.

   • Удаление требует меток-надгробий (tombstone), чтобы не разрушить цепочки проб.

   Оценки: при α < 0.7..0.8 – ожидаемо O(1), при высокой нагрузке резкий рост среднего числа проб.

3. Сбалансированные деревья поиска (RB-/AVL-map)
   

   • Хранят пары (k,v) в узлах с упорядочиванием по ключу (тотальный порядок).

   • Операции – O(log n) в худшем случае, плюс естественная упорядоченная итерация и диапазонные запросы.

4. Префиксные структуры (Trie, Radix-tree)
   

   • Эффективны для строковых ключей; время зависит от длины ключа.

   • Часто применяются для словарей префиксов, автодополнения, IP-маршрутизации.

   Итог: для частот и проверки принадлежности – хеш-таблица; для задач «по порядку» (найти следующий/предыдущий, диапазон) – дерево.

Итог: для частот и проверки принадлежности – хеш-таблица; для задач «по порядку» (найти следующий/предыдущий, диапазон) – дерево.

Хеш-функции, коллизии и рехеширование

1. Требования к хеш-функции
   

   • Распределённость: равномерное распределение значений по бакетам.

   • Детерминизм: одинаковый ключ → одинаковый хеш в рамках процесса/таблицы.

   • Стабильность на простых ключах: строки/числа не должны давать «скопления».

   • Дешевизна вычисления.

   Примеры простых числовых схем:

   h_int(x) = ( (x · A) mod 2^w ) >> (w − r)

   где A – нечётная константа, w – размер машинного слова, 2^r = m.

   Для строки s = s0 s1 … s_{L−1} (байты/коды символов) полиномиальный хеш:

   h_str(s) = ( Σ_{i=0..L−1} s_i · p^i ) mod M

   с «хорошими» p и модулем M (обычно степень 2 для скорости + смешивание).

2. Коэффициент загрузки и расширение (rehash)
   

   Правило управления размером:

   Если α = n/m > α_max, увеличить m (обычно в 2 раза) и перераспределить элементы.

   При открытой адресации важно держать α_max ниже (≈0.7), чем при цепочках (≈1.0..2.0).

3. Коллизии и их разрешение
   

   Цепочки: вставка в начало/конец списка; для смягчения худших случаев – хранить в бакете дерево по ключам (Java HashMap → TreeNode при длинных цепочках).

   Открытая адресация: выбор схемы пробинга критичен:

   • линейный пробинг прост, но страдает от «кластеризации»;

   • двойное хеширование существенно снижает кластеры при «хорошем» g(k).

Инварианты корректности и доказательные идеи

• I1 (единственность ключа): внутри структуры не должно быть двух записей с одним и тем же ключом.

• I2 (доступность): если CONTAINS(k)=True, то для данной реализации существует конечная процедура, находящая (k, v) (цепочка в бакете; конечная последовательность проб при открытой адресации).

• I3 (замкнутость при операциях): после PUT/DELETE таблица остаётся в согласованном состоянии (неповреждённые цепочки/проб-цепочки).

• I4 (итерация): каждый элемент будет посещён ровно один раз; «маркеры удаления» не должны попадать в пользовательскую итерацию.

Доказательный набросок (открытая адресация): поиск идёт по той же последовательности проб, что и вставка; пока не встретится пустая ячейка без надгробия, либо ключ. Надгробия сохраняют связь внутри проб-цепочки, препятствуя преждевременному останову.

Ассимптотика и практическая оценка сложности

Пусть α = n/m. При равномерном хешировании:

• Цепочки: ожидание GET/PUT/DELETE ≈ O(1 + α).

• Открытая адресация: ожидание O(1) при α ниже порогов; при приближении к 1 среднее число проб растёт как Θ(1/(1−α)).

• Деревья: O(log n) гарантированно.

• Trie: O(|k|), где |k| – длина ключа.

Итерация по всем элементам – Θ(n + m) для хеш-таблицы (нужно пройти бакеты), Θ(n) для дерева.

Память, порядок итерации, неизменяемость ключей

• Память: хеш-таблица требует дополнительный массив бакетов m и накладные расходы на списки/надгробия. Деревья – память на узлы и балансировочные поля.

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

• Неизменяемость ключей: ключ, уже помещённый в хеш-таблицу, не должен менять хеш или порядок сравнения – иначе элемент «потеряется».

Инженерные правила (чек-лист)

H1  Подбирайте хеш-функцию под тип ключей; избегайте «простых» h(x)=x mod m для структурированных ключей.

H2  Контролируйте коэффициент загрузки α и выполняйте rehash вовремя.

H3  Для открытой адресации используйте двойное хеширование либо квадратичный пробинг; вводите «надгробия» для DELETE.

H4  Для длинных цепочек (цепочки > порога) переключайте бакет на дерево.

H5  Не изменяйте ключи после вставки; для составных ключей делайте их иммутабельными.

H6  Явно определяйте семантику равенства ключей (eq) и совместимость с хешем: eq(a,b) ⇒ hash(a)=hash(b).

H7  Отдавайте предпочтение деревьям при необходимости упорядоченной итерации и диапазонных запросов.

H8  При больших строковых ключах кэшируйте хеш в объекте ключа и/или используйте Trie/Radix.

H9  Для подсчёта частот используйте целочисленные счётчики и ленивая инициализация по умолчанию (0).

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

Типичные ошибки и анти-паттерны

1. Отсутствие рехеша при росте α → лавинообразная деградация времени.

2. Линейный пробинг при α≈0.9 → длинные кластеры, резкий рост задержек.

3. Изменение ключа после вставки → «исчезновение» элемента.

4. Неопределённая совместимость == и hash() → логические дубликаты или неустранимые коллизии.

5. Удаление без надгробий (open addressing) → разрыв проб-цепочек, ложно «нет ключа».

6. Сравнение строк по ссылке, а не по содержимому → ложные неравенства.

7. Опора на порядок итерации хеш-таблицы → нестабильное поведение программы.

Мини-шпаргалка 

Нагрузка:            α = n / m

Полиномиальный хеш:  h_str(s) = ( Σ s_i · p^i ) mod M

Двойное хеширование: h_i(k) = (h(k) + i·g(k)) mod m

Критерий рехеша:     если α > α_max → m := 2m; rehash()

Сложность цепочек:   O(1 + α)  (в среднем)

Open addressing:     среднее число проб ~ Θ(1/(1−α))  при α→1

Неизменяемость:      eq(a,b) ⇒ hash(a)=hash(b)  (контракт хеша)

Связь с ЕГЭ по информатике

• Подсчёт частот/множеств: проверка уникальности, нахождение первого неповторяющегося символа, фильтрация повторов.

• Словари и таблицы символов: быстрый индекс по ключу (слово → количество/позиции).

• Комбинаторные задачи: запоминание уже встреченных конфигураций, мемоизация.

• Строки: карты частот, окна фиксированной длины, проверка анаграмм (сравнение частот).

• Сложность: сравнение алгоритмов O(n log n) (деревья) против ожидаемого O(n) (хеш-таблица).

Пять упражнений 

Упражнение 1. Частоты символов и первый уникальный
Дана строка s.
a) Постройте ассоциативный массив freq: char → int и найдите первый символ с freq[c] = 1.
b) Обоснуйте, почему решение работает за O(|s|) по времени и O(Σ) по памяти (Σ – алфавит).
c) Как модифицировать решение, если алфавит – Unicode (многоязычные тексты)? 

Упражнение 2. Проверка анаграмм
Даны строки a и b.
a) Проверьте, являются ли они анаграммами, сравнив карты частот.
b) Запишите формулу:
∀c  freq_a[c] = freq_b[c]  ⇒  a и b – анаграммы.
c) Оцените сложность и предложите вариант с полиномиальным хешем для сравнения «скользящих» окон (поиск анаграмм-подстрок).

Упражнение 3. Конструктор словаря на открытой адресации
Спроектируйте словарь для целых ключей на массиве T[0..m−1].
a) Определите h(k) и g(k) (двойное хеширование), приведите формулу:
h_i(k) = (h(k) + i·g(k)) mod m,   i = 0,1,2,...
b) Опишите вставку, поиск и удаление (с надгробиями).
c) Выведите условие рехеша по α и оцените ожидаемое число проб.

Упражнение 4. Словарь на RB-дереве: диапазонный поиск
Пусть map – ассоциативный массив на красно-чёрном дереве.
a) Реализуйте запрос «вывести все пары с ключами в [L; R]».
b) Докажите сложность O(log n + k), где k – число найденных элементов.
c) Обсудите, когда дерево предпочтительнее хеша (упорядоченная итерация, «ближайший по ключу»).

Упражнение 5. Дизайн хеш-функции для составного ключа
Ключ – пара (x, y), где x, y – 32-битовые целые.
a) Предложите хеш:
h(x,y) = mix( mix(x) ⊕ (mix(y) << 1) )
где mix – быстрое битовое смешивание (например, умножение на нечётную константу и XOR-сдвиги).
b) Обоснуйте равномерность распределения для случайных x, y.
c) Проведите мысленный эксперимент: что будет при наивном h = x ⊕ y?

Практические рекомендации и гигиена кода

• Контракт хеша: всегда поддерживайте eq(a,b) ⇒ hash(a)=hash(b). Обратное не требуется.

• Неизменяемые ключи: делайте ключи неизменяемыми (строки, кортежи).

• Кэш хеша: для длинных строк кэшируйте хеш внутри объекта.

• Точное измерение: выбирая между hash и деревом, измеряйте реальные данные: распределение ключей важно сильнее «теории».

• Отладка: логируйте коллизии и среднюю длину цепочек/число проб; это ранний индикатор проблем.

Заключение

Ассоциативные массивы – фундаментальный инструмент, предоставляющий семантику доступа по ключу и позволяющий сводить множество задач к ожидаемому O(1) времени. Понимание реализаций (хеш-таблицы, деревья, префиксные структуры), инвариантов и ограничений (коллизии, загрузка, рехеш) даёт возможность осознанно выбирать структуру под конкретную задачу, поддерживая предсказуемое время работы и корректность.

Для ЕГЭ по информатике владение словарями существенно расширяет класс задач, решаемых «в одну проходку»: подсчёт частот, фильтрация повторов, поиск уникальных элементов, группировка по ключам. Строгое понимание асимптотики и инженерных правил повышает шансы на безошибочное и эффективное решение, а также формирует прочный фундамент для дальнейшего изучения алгоритмов и структур данных.