执行连接在O（n）的时间？ [英] Perform Joins in O(n) time?

问题描述

有没有办法加入2表中的线性时间？我听说这可以通过另一种数据结构（哈希表）来完成，但我不知道如何可以做到这一点。我总是想知道一个加入将涉及跨产品，因此它是O（n ^ 2）。

is there a way to Join 2 tables in linear time? I heard this can be done by having another data structure (Hashtable), but I'm not sure how this can be done. I was always wondering a Join will involve a cross-product and hence it is O(n^2).

推荐答案

算法：

通过表A哈希循环中的所有项目，将它们添加到加入阵列。
通过表B中循环，检查每一个项目，如果它的哈希表中（查看 - O（1）），如果没有，添加到加入表

Loop through table A. Hash all Items, Add them to the Join array.
Loop through table B, check each item if it's in the hash table (Check - O(1)), if not, add to the Join table.

这篇关于执行连接在O（n）的时间？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！