java - 如何实现 n :m relation in Java?

Question

我需要在 Java 中实现一个 n:m 关系。用例是目录。

• 一个产品可以属于多个类别
• 一个类别可以包含多个产品

我目前的解决方案是拥有一个具有两个散列图的映射类。

• 第一个 hashmap 的键是产品 ID，值是类别 ID 列表
• 第二个 hashmap 的键是类别 ID，值是产品 ID 列表

这完全是多余的，我需要一个设置类，它始终注意数据在两个 HashMap 中的存储/删除。

但这是我发现在 O(1) 中实现以下性能的唯一方法:

• 哪些产品属于一个类别？
• 产品属于哪些类别？

我想以各种方式避免全阵列扫描或类似的事情。

但必须有另一个更优雅的解决方案，我不需要对数据进行两次索引。

请点亮我。我只有纯 Java，没有数据库或 SQLite 或其他可用的东西。如果可能的话，我也真的不想实现 btree 结构。

Answer 1

如果您通过成员集合将类别与产品相关联，反之亦然，那么您可以完成同样的事情:

public class Product {
     private Set<Category> categories = new HashSet<Category>();
     //implement hashCode and equals, potentially by id for extra performance
}

public class Category {
     private Set<Product> contents = new HashSet<Product>();
     //implement hashCode and equals, potentially by id for extra performance
}

唯一困难的部分是填充这样的结构，其中可能需要一些中间映射。

但是使用辅助 HashMap /树进行索引的方法并不坏。毕竟，大多数放置在数据库上的索引都是辅助数据结构:它们与行表共存；这些行不一定按照索引本身的结构进行组织。

使用这样的外部结构使您能够将优化和数据彼此分开；那不是坏事。特别是如果明天您想为给定供应商的产品添加 O(1) 查找，例如

编辑: 顺便说一句，看起来您想要的是 Multimap 的实现。也优化为在 O(1) 中进行反向查找。我不认为 Guava 有什么可以做的，但你可以实现 Multimap 接口(interface)，这样至少你不必处理单独维护 HashMaps。 实际上它更像是一个 BiMap 也是一个 Multimap鉴于他们的定义，这是矛盾的。我同意 MStodd 的观点，您可能希望滚动自己的抽象层来封装这两个映射。