Нахождение значений только с одним ключом в паре ключ / значение с точки зрения сложности времени: Java

Question

Я хочу получить значения из пары ключ / значение Java (карта с отображением «один ко многим»), имеющей только один соответствующий ключ, без зацикливания всех значений в карте и превращения его в сложность O(n). Структура данных «ключ / значение» будет выглядеть следующим образом:

K1 -> V1, V2
K2 -> V1, V2, V3
K3 -> V1
K4 ->
K5 -> V4, V2

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

Answer 1

Учитывая мои вышеупомянутые предположения в моих комментариях, самый простой способ сделать это, который приходит на ум быстро, - это иметь две структуры.Либо две карты, где ключи в одной являются значениями в другой, и наоборот, либо иметь два отсортированных списка, для которых вы можете выполнить двоичный поиск, и результат, который вы найдете, имеет ссылку на сестринский элемент вдругой список;это даст вам o (log (n)).

Если вы используете две зеркальные карты, как упомянуто выше, вы можете получить o (1), если они оба HashMap s.Вы можете иметь HashMap и HashMap, а затем иметь структуру, которая инкапсулирует их синхронизацию.

Answer 2

Не могли бы вы быть более конкретным?
Какие свойства описывают ваши ключи и значения? Предполагая, что ваши ключи уникальны, вы можете иметь несколько значений, сопоставленных с ключом, используя LinkedList или ArrayList. Чтобы получить все значения, вам просто нужно взять ссылку на конкретную структуру данных, но в тот или иной момент вам обязательно нужно будет просмотреть список, так что, да, вам потребуется O (n) времени, если вы хотите проверить каждый элемент на что-то. С другой стороны, вы могли бы использовать двоичное дерево или красно-черное дерево (или что-то еще) для своих значений, делая поиск среди них намного более эффективным (как я уже говорил, это зависит от свойств вашего значения).

Answer 3

В гугле Google есть очень хороший класс BiMap, где вы можете искать ключи и значения (он поддерживается двумя Картами).

http://code.google.com/p/guava-libraries/

отредактировано: после уточнения. Я думаю, что мой ответ не сильно изменится. У Guava также очень приятный интерфейс MultiMap (и несколько его реализаций), который вы, скорее всего, можете использовать для своих целей.