java – 在受约束的多对多数据集中有效地查找重复项？

我必须写一个我们的webapp的批量操作版本
让您在更有限的基础上从UI进行操作.所需
操作是将对象分配给类别.一个类别可以有
多个对象但给定对象只能在一个类别中.

该任务的工作流程是：

1)使用浏览器,上传以下表格的文件：

# ObjectID,CategoryID
Oid1,Cid1
Oid2,Cid1
Oid3,Cid2
Oid4,Cid2
[etc.]

该文件很可能有几十到几百行,但是
绝对可以有数千行.

在理想的世界中,给定的对象id只会在文件中出现一次
(反映一个对象只能分配给一个类别的事实)
但由于文件是在我们控制范围之外创建的,因此无法保证
这实际上是正确的,处理必须处理这种可能性.

2)服务器将接收文件,解析它,预处理它
???并显示如下页面：

723 objects to be assigned to 126 categories
142 objects not found
 42 categories not found

Do you want to continue?

[Yes]     [No]

3)如果用户单击是按钮,服务器将
???实际上做的工作.

因为我不想在步骤(2)和(3)中解析文件,因为
(2)的一部分,我需要建立一个能够生存的容器
请求并保留有用的数据表示形式
轻松提供数据以填充“预览”页面并将让我
有效地完成实际工作. (显然我们有会议,我们
通常保持很少的内存会话状态.)

有一个存在的

assignObjectsToCategory(Set<ObjectId> objectIds,CategoryId categoryId)

通过UI完成分配时使用的功能.它是
非常希望批量操作也使用此API
除了简单之外,它还有许多其他业务逻辑
分配,我们需要相同的业务逻辑来运行这个批量
分配已完成.

最初,如果文件“非法”指定,那就没关系了
给定对象的多个类别 – 可以分配
对象与文件关联的类别之一对应
用.

因此,当我经历过时,我最初认为在步骤(2)中
文件我会建立并放入交叉请求容器中
Map< CategoryId,Set< ObjectId>> (特别是HashMap快速
查找和插入)然后什么时候做我能做的工作
只需在地图上迭代,并为每个CategoryId拉出
关联的Set< ObjectId>并将它们传递给assignObjectsToCategory().

但是,有关如何处理重复的ObjectId的要求已更改.
他们现在要处理如下：

>如果ObjectId在文件中出现多次,并且
所有时间都与相同的CategoryId相关联,分配
该类别的对象.
>如果ObjectId在文件中出现多次,并且
与不同的CategoryId相关联,考虑到这一点
错误并在“预览”页面上提及它.

这似乎弄乱了我的Map< CategoryId,Set< ObjectId>>战略
因为它没有提供检测ObjectId I的好方法
刚读出的文件已经与CategoryId相关联.

所以我的问题是如何最有效地检测和跟踪这些
重复的ObjectIds？

我想到的是使用“前进”和“反向”地图：

public CrossRequestContainer
{
    ...

    Map<CategoryId,Set<ObjectId>> objectsByCategory;  // HashMap
    Map<ObjectId,List<CategoryId>> categoriesByObject; // HashMap
    Set<ObjectId> illegalDuplicates;

    ...
}

然后,当读入每个(ObjectId,CategoryId)对时,它会
放入两张地图.一旦文件被完全读入,我
能做：

for (Map.Entry<ObjectId,List<CategoryId>> entry : categoriesByObject.entrySet()) {
    List<CategoryId> categories = entry.getValue();
    if (categories.size() > 1) {
        ObjectId object = entry.getKey();
        if (!all_categories_are_equal(categories)) {
            illegalDuplicates.add(object);
            // Since this is an "illegal" duplicate I need to remove it
            // from every category that it appeared with in the file.
            for (CategoryId category : categories) {
                objectsByCategory.get(category).remove(object);
            }
        }
    }
}

当这个循环结束时,objectsByCategory将不再包含任何“非法”
duplicates和illegalDuplicates将包含所有“非法”重复项
根据需要报告.然后,我可以遍历objectsByCategory,获取Set< ObjectId>对于每个类别,并调用assignObjectsToCategory()来执行分配.

但是,虽然我认为这会有效,但我担心两次存储数据,特别是
当输入文件很大时.而且我也担心我会遗漏一些东西：效率
这将非常缓慢.

有没有办法做到这一点,不会使用双内存,但仍然可以快速运行？
我错过了一些即使使用双内存仍会运行很多的东西
比我预期的要慢？

Map<CategoryId,Set<ObjectId>> objectsByCategory;  // HashMap
Map<ObjectId,CategoryId> categoryByObject; // HashMap
Map<ObjectId,Set<CategoryId>> illegalDuplicates;  // HashMap