这是一个创建于 2395 天前的主题，其中的信息可能已经有所发展或是发生改变。
前提： 假设有 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 去判断是否存在。
 |
1
kingname 2018-05-02 15:39:54 +08:00 via iPhone
你知道集合是可以求交集的吗？你直接求 A 与 B 的交集就可以了。
|
 |
2
zn 2018-05-02 15:49:04 +08:00
要看你的实现了，如果遍历速度、定位速度足够快，那就直接遍历，就是这样么简单粗暴。
|
 |
3
glacer 2018-05-02 16:34:20 +08:00  1
参考 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 做成其他的数据结构，比如平衡树等。 |
 |
4
owenliang 2018-05-02 17:52:17 +08:00
你得说说业务场景，脱离业务谈算法感觉不太对劲。
|
 |
5
davinci 2018-05-02 19:19:21 +08:00
如果内存存的下两个百万集合，直接 hash。如果两个集合都大到内存放不下，可以参考数据库的 hash join 实现。
|
 |
7
shoumu 2018-05-02 20:49:57 +08:00
A、B 集合分别以 ID 进行排序，然后从头到位遍历 Join 即可
|
 |
8
jorneyr 2018-05-03 08:56:13 +08:00
Hash 的方式可以的，百万不算多
|
 |
9
buliugu 2018-05-03 19:11:26 +08:00
bitmap 了解一下
|
Select Language