Wie man n: m Beziehung in Java einführt?

Question

Ich muss eine n: m-Beziehung in Java implementieren. Der Anwendungsfall ist ein Katalog.

• kann ein Produkt in mehreren Kategorien sein
• eine Kategorie mehrere Produkte

Meine aktuelle Lösung halten kann, ist eine Zuordnung Klasse zu haben, die zwei Hashmaps hat.

• Der Schlüssel des ersten hashmap ist die Produkt-ID und der Wert ist eine Liste der Kategorie ids
• Der Schlüssel zu der zweiten hashmap ist die Kategorie-ID und der Wert ist eine Liste des Produkt-IDs

das ist völlig überflüssig ein ich brauche eine Einstellung Klasse, die immer dafür sorgt, dass die Daten gespeichert werden/in beiden Hashmaps gelöscht.

Aber das ist der einzige Weg, ich folgendes performant in O (1) machen gefunden:

• welche Produkte eine Kategorie hält?
• In welchen Kategorien ist ein Produkt enthalten?

Ich möchte vollständige Array-Scans oder etwas in jeder Hinsicht zu vermeiden.

Aber es muss eine andere, elegantere Lösung sein, wo ich nicht zweimal die Daten zum Index benötigen.

Bitte en-Licht mir. Ich habe nur einfaches Java, keine Datenbank oder SQLite oder etwas verfügbares. Ich möchte auch nicht wirklich eine btree-Struktur implementieren, wenn möglich.

Answer 1

Wenn Sie Associate Kategorien mit Produkten über ein Element Sammlung, und umgekehrt, dann können Sie das Gleiche erreichen:

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 
} 

Der einzige schwierige Teil einer solchen Struktur ist bevölkern, wo einige Zwischen Karten sein könnte erforderlich.

Aber der Ansatz der Verwendung von Hilfs Hashmaps/Bäume für die Indizierung ist nicht schlecht. Schließlich sind die meisten Indizes, die beispielsweise in Datenbanken abgelegt werden, Hilfsdatenstrukturen: Sie koexistieren mit der Tabelle der Zeilen; Die Zeilen sind nicht notwendigerweise in der Struktur des Index selbst organisiert.

eine äußere Struktur verwenden, wie dies Sie Optimierungen und Daten voneinander getrennt zu halten, ermöglicht; Das ist keine schlechte Sache. Insbesondere, wenn Sie morgen O (1) -Look-ups für Produkte hinzufügen möchten, die einem Lieferanten, z.

Edit: By the way, es sieht aus wie das, was Sie wollen, ist eine Implementierung eines Multimap optimierten Reverse-Lookups in O zu tun (1) als auch.Ich glaube nicht, dass Guava etwas zu tun hat, aber Sie könnten die Multimap-Schnittstelle implementieren, so dass Sie sich zumindest nicht mit der separaten Pflege der HashMaps beschäftigen müssen. Eigentlich ist es eher wie eine BiMap, die auch eine Multimap ist, die angesichts ihrer Definitionen widersprüchlich ist. Ich stimme MStodd zu, dass Sie wahrscheinlich Ihre eigene Abstraktionsebene rollen möchten, um die zwei Maps zu kapseln.

Answer 2

Ihre Lösung ist perfekt. Denken Sie daran, dass das Erstellen eines Objekts in einer HashMap keine Kopie des Objekts erstellt. Es wird lediglich ein Verweis darauf gespeichert, sodass die Kosten für Zeit und Arbeitsspeicher ziemlich gering sind.

Answer 3

Ich würde mit Ihrer ersten Lösung gehen. Habe eine Abstraktionsschicht um zwei Hashmaps. Wenn Sie Bedenken wegen Nebenläufigkeit haben, implementieren Sie eine entsprechende Sperre für CRUD.

Answer 4

Wenn Sie eine unveränderbare Datenstruktur verwenden können, bietet Guavas ImmutableMultimap eine inverse()-Methode, mit der Sie eine Sammlung von Schlüsseln nach Wert erhalten können.