Согласованная и эффективная реализация двунаправленной структуры данных (Java)

Мне нужна была реализация двунаправленной карты на Java, поэтому я попытался использовать BiMap и BidiMap от Guava и Commons. Однако возможность обратного вида не сохраняется после изменения элемента. Вот пример с BiMap (такое же поведение с BidiMap):

BiMap<Set<String>, Set<String>> map = HashBiMap.create();

Set<String> foo = new HashSet<>();
foo.add("foo");

Set<String> bar = new HashSet<>();
bar.add("bar");

map.put(foo, bar);

map.get(foo); // returns [bar], ok
map.inverse().get(map.get(foo)); // returns [foo], ok

map.get(foo).add("someString");

map.get(foo); // returns [bar, someString], ok
map.inverse().get(map.get(foo)); // returns null, not ok <=

Конечно, такое поведение можно ожидать от реализации с использованием HashMaps, но оно иллюстрирует проблему.

Итак, вопрос в том, существует ли двунаправленная структура данных, которая может справиться с такой ситуацией, с элементами произвольных типов, и при этом иметь лучшую среднюю временную сложность, чем массив пар?

РЕДАКТИРОВАТЬ: я не пытаюсь решить эту проблему или избежать ее, это скорее академический вопрос. Я просто хочу знать, существует ли такая структура данных. То есть структура данных, допускающая двустороннюю привязку, изменяемые ключи и разумную временную сложность.


java dictionary data-structures bidirectional
person Bastien    schedule 31.08.2015    source источник
comment
Вместо того, чтобы менять объект на карте, или вдобавок, возможно, стоит заново добавить его на карту, чтобы заново настроить ключи.   -  person RealSkeptic    schedule 31.08.2015
comment
Или заверните Set<> в какой-нибудь стабильный объект. hashCode и сопоставимость. Например. просто class Wrapper { Set<> wrapped = .. }   -  person zapl    schedule 31.08.2015

Ответы (1)


arrow_upward
3
arrow_downward

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

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

person Marko Topolnik    schedule 31.08.2015
comment
Спасибо, но я не пытаюсь решить эту проблему или избежать ее, это скорее академический вопрос. Я просто хотел знать, существует ли такая структура данных. То есть структура данных, допускающая двустороннюю привязку, изменяемые ключи и разумную временную сложность. - person Bastien; 31.08.2015
comment
Если вы имеете в виду структуру, которая может работать, несмотря на то, что в ее внутренности вмешиваются извне, то, конечно, ее не существует. Структура должна знать, когда вы меняете ключи --- и если это так, то хэш-таблица уже является структурой, удовлетворяющей вашим требованиям. - person Marko Topolnik; 31.08.2015