java - 多个键具有相同值并且可通过各个键进行搜索的数据结构

Question

我有一个用例，其中我必须维护键值对存储，所有键都是唯一的，并且多个键可以映射到相同的值。此外，它应该可以通过每个单独的键进行搜索。

例如:

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

and so on.

在 K2 上搜索应该返回 V1

它有点类似于多键映射，但可以通过单个键进行搜索。是否有任何数据结构可以让我在 O(1) 内完成此操作。

Answer 1

没有这样的 DS 可以在恒定的 O(1) 时间内给出结果，但 HashMap 应该足够好。对于插入、删除和搜索操作， HashMap 的平均复杂度为 O(1)。如果您使用 JDK8 ，那么频繁冲突对性能的影响也会更小。请参阅:https://dzone.com/articles/hashmap-performance 。

由于只有值的引用存储在映射中，因此即使键和值的数量不匹配，存储也不应该成为一个大问题。

如果键不是 Long、String、Int 等并且是某个自定义对象，请不要忘记重写 hashcode 和 equals 方法。

如果这仍然不能满足您的要求，请查看 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