Инъективные двусторонние отображения

Question

Я часто имею дело с отображениями, которые являются инъективными. В терминологии программирования это можно выразить в виде словаря, в котором все значения являются уникальными, а также, конечно, все ключи.

Существует ли структура данных с эффективным использованием памяти для инъективных отображений со всеми свойствами сложности времени, которые вы ожидаете от словарей?

Например:

d = {1: 'a', 2: 'b', 3: 'c', 4: 'd', 5: 'e'}

d.get(2) = 'b'  # this works with a normal dictionary
d.get('b', reverse=True) = 2  # but this is not possible

Кажется, что все решения в двухсторонней / обратной карте требуют использования или объединения двух наборов отображений, уделяя особое внимание упрощению операций с двусторонней картой. Это хорошо для небольших словарей, которые аккуратно помещаются в памяти, но не подходят для больших словарей.

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

Я понимаю, что словари используют хеш-таблицу, в которой используется тип данных ассоциативного массива. По определению, ассоциативные массивы реализуют сопоставления ключ -> значение с уникальными ключами. Возможно ли теоретически или на практике создать интеллектуальное инъективное отображение, которое позволяет осуществлять обратный поиск?

Если это невозможно, я был бы признателен за объяснение, почему такую ​​конструкцию трудно или невозможно реализовать с той же эффективностью, что и словари.

Обновить

После обсуждения с @rpy (см. Комментарии ниже) будет полезна любая информация о том, как настроить словарный объект Python с использованием совершенной обратимой хеш-функции. Но, конечно, рабочая реализация была бы идеальной (я уже попробовал совершенство).

Answer 1

Чистый ответ на ваш вопрос: НЕТ (для любой эффективной реализации)

Вы выдвигаете два требования, которые не могут быть выполнены одновременно:

1. Не используйте дополнительную память для обратного отображения
2. Не добавляйте дополнительное время для выполнения (обратного) поиска

Почему эти два ограничения запрещают решение?

Отображения - это пары значений (кортежи). Самая тривиальная реализация будет:

Последовательный поиск всех кортежей на совпадение.

Это будет иметь одинаковую сложность для прямого и обратного отображения.
Тем не менее, это явно нарушает ожидание time-complexity properties you expect from dictionaries:

Если вы допустите сложность O(n), то последовательный поиск набора кортежей даст вам правильное решение.

Обычно реализации словаря пытаются достичь сложности O(1) или, по крайней мере, O(n*log(n)). Это достигается путем введения дополнительных данных для ускорения поиска, таких как хеши или деревья. К сожалению, такие средства помогают только для одного направления, поскольку они имеют дело либо с ключами (случай прямого сопоставления), либо со значениями (случай обратного сопоставления).

Таким образом, как только вам нужно уменьшить сложность поиска (это также относится и к сложности модификации, но словари обычно ориентированы на быстрый поиск), вам потребуется добавить данные для достижения скорости.

Вся проблема сводится к классическому компромиссу памяти и скорости.

РЕДАКТИРОВАТЬ:

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

Вычислите хеш-значение для ключа и одно для значения и зарегистрируйте кортеж под обоими хеш-значениями. Таким образом, вы можете взять ключ или значение, идентифицировать соответствующий кортеж и вернуть правильный результат. Это будет работать даже для неинъективных случаев, когда вы разрешаете возвращать наборы совпадающих кортежей.

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