Supongamos que tenemos dos tablas (piense como en las tablas SQL), donde la clave principal en una de ellas es la clave externa en la otra. Se supone que debo escribir un algoritmo simple que imite la unión de estas dos tablas. Pensé en iterar sobre cada elemento en la columna de clave principal en la primera tabla, tener un segundo ciclo donde verifica si la clave externa coincide, luego almacenarlo en una matriz o lista externa. Sin embargo, esto requeriría O(N*M) y necesito encontrar algo mejor. Hay una pista en el libro de texto de que implica hash, sin embargo, no estoy seguro de cómo se podría implementar hash aquí o cómo lo mejoraría.
Editando para agregar un ejemplo:
Table Employees |ID (Primary Key)| Name | Department| |:---------------|:----:|----------:| | 1 | Jack | IT | | 2 | Amy | Finance | Table Transactions |Sold Product| Sold By(Foreign Key)| Sold To| |:-----------|:-------------------:|-------:| | TV | 1 | Mary | | Radio | 1 | Bob | | Mobile | 2 | Lisa |Lo que quiero hacer es escribir un algoritmo que una estas dos tablas usando hash, y nada complejo, solo una idea simple de cómo hacerlo.
Lea las claves principal y externa de la tabla secundaria en un mapa donde las claves son las claves externas y los valores son las claves principales. Tenga en cuenta que una clave externa puede asignarse a varias claves principales si se trata de una relación de uno a varios.
Ahora itere sobre las claves principales de la tabla madre y para cada clave principal verifique si existe en el mapa. Si es así, agrega una tupla de las claves principales de las filas que tienen una relación con la matriz (o como quiera guardarla).
La complejidad del tiempo es O(n + m) . Iterar sobre las filas de cada tabla una vez. Dado que la búsqueda en el mapa es constante, no necesitamos agregarlo.
La complejidad del espacio es O(m) donde m es el número de filas en la tabla secundaria. Este es un espacio adicional que usa en comparación con la solución ingenua para mejorar la complejidad del tiempo.
Rellene un HashMap con los elementos de la tabla principal, utilizando sus claves como la clave del mapa y el objeto completo como el valor. Esto requiere solo 1 paso sobre la tabla principal y cada operación para agregar al HashMap ocurre en tiempo constante O (1). Esto es similar a crear un índice de base de datos.
Itere sobre la tabla secundaria, "uniéndose" a la fila principal en tiempo constante O (1) al obtener el padre del mapa.
El tiempo de ejecución total es 1 paso sobre cada "tabla", por lo que O (n + m).
El código podría ser algo como:
class Parent { int id; // other fields, getters etc } class Child { int parentId; // other fields, getters etc } void join(List<Parent> parents, List<Child> children) { Map<Integer, Parent> parentMap = parents.stream() .collect(toMap(Parent::getKey, p -> p)); // FYI toMap collects to a HashMap for (Child child : children) { Parent parent = parentMap.get(child.getParentId()); // not sure what “join” means, but you now have child and its parent } }Prueba esto.
record Employees(int id, String name, String department) {} record Transactions(String soldProduct, int soldBy, String soldTo) {} record Joined(String soldProduct, int soldBy, String soldTo, String name, String department) {} public static void main(String[] args) { List<Employees> employees = List.of( new Employees(1, "Jack", "IT"), new Employees(2, "Amy", "Finance")); List<Transactions> transactions = List.of( new Transactions("TV", 1, "Mary"), new Transactions("Radio", 1, "Bob"), new Transactions("Mobile", 2, "Lisa")); Map<Integer, Employees> mapEmployee = employees.stream() .collect(Collectors.toMap(Employees::id, Function.identity())); List<Joined> joined = transactions.stream() .map(t -> { Employees e = mapEmployee.get(t.soldBy()); return new Joined(t.soldProduct(), t.soldBy(), t.soldTo(), e.name(), e.department()); }) .toList(); for (Joined e : joined) System.out.println(e); }producción:
Joined[soldProduct=TV, soldBy=1, soldTo=Mary, name=Jack, department=IT] Joined[soldProduct=Radio, soldBy=1, soldTo=Bob, name=Jack, department=IT] Joined[soldProduct=Mobile, soldBy=2, soldTo=Lisa, name=Amy, department=Finance]