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

Question

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

Например:

(K1,K2,K3) -> V1
(K3,K4) -> V2
(K5) -> V3

and so on.

Поиск на К2 должен вернуть V1

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

Answer 1

Нет такого DS, который мог бы давать результаты в постоянном времени O (1), но HashMap должен быть достаточно хорошим.Средняя сложность хэш-карты составляет O (1) для операций вставки, удаления и поиска.И если вы используете JDK8, то влияние частых коллизий на производительность также будет меньше.См .: https://dzone.com/articles/hashmap-performance.

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

И не забудьте переопределить хэш-код и методы равенства, если ключ не Long, String, Int и т. Д. И является каким-то пользовательским объектом.

Если это все еще не соответствует вашим требованиям,затем проверьте эти ссылки из библиотек Guava и Apache Commons Collection, но вам, возможно, придется собрать некоторую информацию об их числах производительности:

1. https://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/keyvalue/MultiKey.html
2. https://google.github.io/guava/releases/19.0/api/docs/com/google/common/collect/Table.html