时间戳

首页 > 解决方案 > 对多个键具有相同值并可按单个键搜索的数据结构

java - 对多个键具有相同值并可按单个键搜索的数据结构

问题描述

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

例如：

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

and so on.

在 K2 上搜索它应该返回 V1

它有点类似于 Multikeymap 但可以通过单个键进行搜索。是否有任何数据结构可以让我在 O(1) 中执行此操作。

标签： javadata-structurestime-complexityspace-complexity

解决方案

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

由于只有值的引用存储在 Map 中，即使键和值的数量不匹配，存储也不应该是一个大问题。

如果键不是 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

推荐阅读