Хэш-таблица с обоими значениями как ключ

Question

Есть ли структура данных, основанная на хешировании, где я могу искать элемент в O (1) раз как по ключу, так и по значению.

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

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

Надеюсь, я достаточно ясен!

Answer 1

Вы ищете bidirectional map. Here - статья, описывающая реализацию в C++. Обратите внимание, что двунаправленная карта в основном состоит из двух карт, объединенных в один объект. Нет более эффективного решения, чем это, хотя по простой причине:

Карта в основном несвязанный ориентированный график (ключ, значение) -пары. Каждая пара представлена ​​ребром. Если вы хотите, чтобы карта была двунаправленной, вы набрали вдвое больше краев, что удвоило бы объем требуемой памяти.

C++ и Java STL не предоставляют никаких классов для этой цели. В Java вы можете использовать Googles Guava library, в C++ библиотека boost предоставляет двунаправленные карты.

Answer 2

Структура данных, которая соответствует вашим потребностям, называется двунаправленной картой.

Я предполагаю, что вы ищете существующую реализацию, а не указатели, как ее реализовать :) Поскольку вы не указали язык программирования, это текущая ситуация для Java - такой структуры данных в Java API. Однако есть интерфейс Google Guava bi-directional map с несколькими реализациями. Из документов:

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

В качестве альтернативы, имеется коллекция BidiMap из коллекций Apache.

Для C++ взгляните на Boost.Bimap.

Для Python взгляните на bidict.

В C#, как и на других языках, официальной реализации не существует, но вот где Jon Skeet comes in.