Информатика · объяснение и практика

Обратный словарь: почему одинаковые значения теряют записи

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

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Структуры данных · Учебная карта

Главная мысль

Выражение {value: key for key, value in d.items()} меняет роли ключей и значений, но сохраняет все исходные записи только при допустимых уникальных значениях. Если два исходных ключа имеют одно значение, оно станет одним новым ключом, а позднее присваивание заменит прежнее. Для обратного поиска всех соответствий строят словарь списков. Это не хеш-коллизия: новые ключи действительно равны.

Одна итоговая запись скрывает два источника

Пусть d = {"Ася": "театр", "Борис": "хор", "Вера": "театр"}. При обращении сначала появляется пара "театр": "Ася", затем "хор": "Борис". Когда обрабатывается Вера, ключ "театр" уже есть. Его значение становится "Вера". В итоге получаются две записи вместо трёх, и имя Аси невозможно восстановить только из полученного обратного словаря.

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

Для нескольких ответов нужна группа

Если вопрос звучит «кто выбрал театр?», ответ может содержать несколько имён. В явном цикле создают result = {}, а для каждой пары получают список группы, создавая его при первом появлении категории. Затем добавляют имя в этот список. Например, result.setdefault(club, []).append(name) на указанных данных сохранит для театра ["Ася", "Вера"], а для хора ["Борис"].

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

Пример

Код товара связан с цветом: {"P": "синий", "Q": "красный", "R": "синий"}. Нужно по цвету получить все коды. Почему обычное обращение пары недостаточно?

Ключ "синий" создаётся дважды, и поздний код R заменит P. Для всех кодов нужен результат вида {"синий": ["P", "R"], "красный": ["Q"]}. Здесь сохраняются три исходные связи в двух группах. Совпавший цвет не является случайным совпадением хешей: это одно и то же значение ключа.

Проверьте равенство и допустимость будущих ключей

Новые ключи должны быть хешируемыми. Если исходные значения — обычные списки, прямое обращение вызовет TypeError. Нельзя молча превратить любой список в строку и считать задачу неизменной: формат представления способен поменять смысл равенства. Для чисел также учитывают обычное равенство Python: один, единица с десятичной точкой и True могут обозначать один ключ, хотя записи имеют разный тип.

Прежде чем строить обратное соответствие, решите, нужен ли один представитель, все представители или ошибка при неоднозначности. Для первого случая укажите правило выбора; для второго храните группы; для третьего проверяйте повтор до присваивания. Один и тот же короткий синтаксис не удовлетворяет всем трём контрактам. Результат нужно проверять именно по требуемой сохранности связей между объектами, а не по внешней компактности нового словаря.

От чтения к действию

А теперь — вы

Значения двух разных исходных ключей — одна и та же строка. Что гарантирует простое обращение {v:k for k,v in d.items()}?

Частые вопросы

Хеш-коллизия всегда удаляет одно имя?

Нет. Разные неравные ключи словарь различает. Потеря здесь возникает из-за равенства нового ключа и обычной замены его значения.

Можно оставить только последнее имя?

Да, если это явно требуемое правило. Для поиска всех исходных имён такое сокращение неверно.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться