¿Cómo implementar la relación n: m en Java?

Question

Necesito implementar una relación n: m en Java. El caso de uso es un catálogo.

• un producto puede estar en varias categorías
• una categoría puede contener múltiples productos

Mi solución actual es tener una clase de mapas que tiene dos HashMaps.

• La clave de la primera HashMap es la identificación del producto y el valor es una lista de la categoría ids
• La clave de la segunda HashMap es la categoría ID y el valor es una lista de ID de productos

Esto es totalmente redundante y necesito una clase de configuración que siempre tenga cuidado de que los datos se almacenen/eliminen en ambos hashpes.

Pero esta es la única manera que encontré para hacer la siguiente performant en O (1):

• qué productos sostiene una categoría?
• ¿en qué categorías está un producto?

Quiero evitar escaneos de array completos o algo así en todos los sentidos.

Pero debe haber otra solución más elegante en la que no necesite indexar los datos dos veces.

Por favor en-light me. Solo tengo Java simple, sin base de datos o SQLite o algo disponible. También realmente no quiero implementar una estructura btree si es posible.

Answer 1

Si Categorías asociados con los productos a través de una colección miembro, y versa del vica, entonces se puede obtener el mismo resultado:

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 
} 

La única parte difícil es llenar una estructura de este tipo, donde algunos mapas intermedios podría ser necesario.

Pero el enfoque de usar hashmaps/árboles auxiliares para indexar no es malo. Después de todo, la mayoría de los índices colocados en las bases de datos son, por ejemplo, estructuras de datos auxiliares: coexisten con la tabla de filas; las filas no están necesariamente organizadas en la estructura del índice en sí.

El uso de una estructura externa como esta le permite mantener las optimizaciones y los datos separados unos de otros; eso no es algo malo Especialmente si mañana desea agregar O (1) búsquedas para productos entregados a un proveedor, p.

Editar: Por cierto, parece que lo que quiere es una implementación de un Multimap optimizado para hacer búsquedas inversas en O (1) también.No creo que Guava tenga algo que ver con eso, pero podría implementar la interfaz Multimap para que al menos no tenga que lidiar con el mantenimiento de los HashMaps por separado. En realidad, es más como un BiMap que también es un Multimap que es contradictorio dadas sus definiciones. Estoy de acuerdo con MStodd en que probablemente quiera rodar su propia capa de abstracción para encapsular los dos mapas.

Answer 2

Su solución es perfectamente buena. Recuerde que poner un objeto en un HashMap no hace una copia del objeto, simplemente almacena una referencia a él, por lo que el costo en tiempo y memoria es bastante pequeño.

Answer 3

Me gustaría ir con su primera solución. Tenga una capa de abstracción alrededor de dos hashmaps. Si le preocupa la concurrencia, implemente el bloqueo apropiado para CRUD.

Answer 4

Si puede utilizar una estructura de datos inmutables, el ImmutableMultimap de Guava ofrece un método inverse(), que le permite obtener un conjunto de claves por valor.