假設我們有兩個表（想想在 SQL 表中），其中一個的主鍵是另一個的外鍵。我應該撰寫一個簡單的演算法來模擬這兩個表的連接。我想過迭代第一個表中主鍵列中的每個元素，進行第二個回圈，檢查外鍵是否匹配，然后將其存盤在外部陣列或串列中。但是，這需要 O(N*M) 并且我需要找到更好的東西。教科書中有一個提示，它涉及散列，但是，我不確定如何在這里實作散列或如何使它變得更好？
編輯以添加示例：
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 |
我想要做的是撰寫一個演算法，使用散列連接這兩個表，而不是任何復雜的東西，只是一個關于如何做到這一點的簡單想法。
uj5u.com熱心網友回復：
使用主表元素填充 HashMap，使用它們的鍵作為映射鍵，使用整個物件作為值。這只需要對主表進行 1 次傳遞，并且每個添加到 HashMap 的操作都在恒定時間 O(1) 內發生。這類似于創建資料庫索引。
迭代子表，通過從映射中獲取父行，在恒定時間 O(1) 內“加入”到父行。
每個“表”的總運行時間為 1 次，因此 O(n m)。
代碼可能類似于：
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
}
}
uj5u.com熱心網友回復：
將子表的主外鍵讀入映射中，其中鍵是外鍵，值是主鍵。請記住，如果這是一對多關系，一個外鍵可以映射到多個主鍵。
現在迭代母表的主鍵，并為每個主鍵檢查它是否存在于映射中。如果是這樣，您添加一個與陣列有關系的行的主鍵的元組（或者您想保存它）。
時間復雜度為O(n m)。迭代每個表的行一次。由于地圖中的查找是常數，我們不需要添加它。
空間復雜度是O(m)其中m的子表中的行數。與簡單的解決方案相比，這是您用來提高時間復雜度的一些額外空間。
uj5u.com熱心網友回復：
試試這個。
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);
}
輸出：
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]
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/395985.html
下一篇：找出給定演算法的復雜度