如何在Java中实现n:m关系？

Question

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

• 产品可以分为多个类别
• 一个类别可以容纳多个产品

我目前的解决方案是拥有一个具有两个哈希映射的映射类.

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

这完全是多余的,我需要一个设置类,始终注意在两个哈希映射中存储/删除数据.

但这是我发现在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
}

唯一困难的部分是填充这样的结构,可能需要一些中间地图.

但是使用辅助hashmaps/trees进行索引的方法并不错.毕竟,放在数据库上的大多数索引都是辅助数据结构:它们与行表共存; 行不一定按索引本身的结构组织.

使用这样的外部结构可以使您保持优化和数据彼此分离; 这不是一件坏事.特别是如果明天你想为给定供应商的产品添加O(1)查找,例如

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