两个百万集合之间的查找、组合

[1cming]

前提： 假设有 objectX，objectY 两个对象，这两个对象通过其自身属性唯一的 ID 可关联到。 现在 objectX 存在于集合 A 中，objectY 存在于集合 B 中，A、B 的 size 都是百万级别。

操作步骤： step1:对 A 进行遍历 step2:如果 A 中 objectX 的 ID 在 B 集合中可以找到对应的 objectY step3:把 objectX、objectY 合并成一个新的 objectZ 放入到集合 C 中

疑问： 一.百万级别的数据这样操作是否合适？ 二.step1 步骤避免不了，step2 中定位到 objectY 有没有什么好的思路(考虑性能、速度)？ 目前是把集合 B 转换成了 k-v 形式，key 放 ID，用 API 提供的 contains 去判断是否存在。

[kingname]

你知道集合是可以求交集的吗？你直接求 A 与 B 的交集就可以了。

[zn]

要看你的实现了，如果遍历速度、定位速度足够快，那就直接遍历，就是这样么简单粗暴。

[glacer]

参考 MySQL 的 Join 实现：(Nested Loop join)[https://dev.mysql.com/doc/refman/5.7/en/nested-loop-joins.html]
遍历 A 是避免不了的，那我们可以在 B 上做索引来实现加速。
楼主自己想到了将 B 转为 K-V 形式这就相当于 hash 索引，时间复杂度为 O(n)。
当然可以将 B 做成其他的数据结构，比如平衡树等。

[owenliang]

你得说说业务场景，脱离业务谈算法感觉不太对劲。

[davinci]

如果内存存的下两个百万集合，直接 hash。如果两个集合都大到内存放不下，可以参考数据库的 hash join 实现。

[1cming]

@glacer 好的谢谢我看一下

@owenliang 业务场景是特意模糊掉的

@davinci 内存放的下

[shoumu]

A、B 集合分别以 ID 进行排序，然后从头到位遍历 Join 即可

[jorneyr]

Hash 的方式可以的，百万不算多

[buliugu]

bitmap 了解一下