代码之家 › 专栏 › 技术社区 › The Surrican

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

hashmap hashtable indexing data-structures java

6

The Surrican · 技术社区 · 15 年前

用例是一个目录。

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

我目前的解决方案是有一个映射类,它有两个hashmaps。

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

但这是我找到的唯一方法 O(一) :

什么产品属于一个类别?

我想在任何方面都避免全阵列扫描之类的。

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

请把我点着。我只有普通的Java,没有数据库或SQLite或其他可用的东西。如果可能的话,我也不想实现btree结构。

4 回复 | 直到 9 年前

1

6

Mark Peters 15 年前

如果通过成员集合将类别与产品关联,反之亦然,则可以完成相同的任务:

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
}

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

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

编辑: 顺便说一下,看起来您想要的是 Multimap 优化以在O(1)中进行反向查找。我不认为番石榴可以做到这一点,但是你可以实现Multimap接口,这样至少你不必单独维护HashMaps。

2

3

Paul Tomblin 15 年前

你的解决方案非常好。记住,将一个对象放入HashMap并不能复制该对象,它只是存储对它的引用,所以时间和内存上的开销都很小。

3

1

MStodd 15 年前

我同意你的第一个解决方案。在两个hashmaps周围有一个抽象层。如果您担心并发性,请为CRUD实现适当的锁定。

4

0

shmosel 9 年前

如果你能使用一个不可变的数据结构,番石榴 ImmutableMultimap 提供 inverse() 方法,它使您能够按值获取密钥集合。