java - 合并 n 个列表中的 HashMap

Question

我会尽力描述我的问题，但请询问是否有没有意义的事情。

• 我的列表数量有限
• 每个列表包含有限数量的联系人
• 每个联系人都表示为一个 HashMap
• 每个列表都链接到一个提供商
• 同一联系人可能出现在多个提供商中(因此存在多个列表)。
• 我需要一个“主”列表，其中包含其他列表中的所有唯一条目

我正在寻找一种有效的方法来将这些列表合并到没有重复的主列表中。例如，如果同一个联系人出现在多个列表中(多个HashMap对应于同一个人)，我想将所有HashMap合并为一个，并将合并后的HashMap放入主列表中。这里的简单“putall”是行不通的，因为我需要重新键入内容才能有效地访问它们(例如，提供商一为我提供了键入为“emails”的电子邮件地址列表，提供商 2 为我提供了键入为“emailList”的相同信息)。

合并各个 HashMap 是两个问题中比较容易的一个，因为我知道这些键并且可以轻松合并它们。

让我摸不着头脑的问题是列表的高效扫描...除了在嵌套循环中线性遍历每个列表、获取下一个 HashMap、检查它是否已存在于母列表中并合并/创建一个新列表之外，没有其他方法了吗...？

Answer 1

第一次观察 - 使用 HashMap 来表示你的联系人的味道 "object denial" 。

您需要设计并实现一个 Contact 类来表示联系人。如果没有这个类(class)，您的任务就会比实际需要的困难得多。

该类需要所有联系人关键字段的 getter，并且需要基于关键字段实现 equals、hashcode 和 Comparable。非关键字段也需要 getter(以及可选的 setter)。

这样，合并过程就变成了(伪代码):

// If you haven't already done so
convert the master list of HashMaps to a list of Contact objects and sort it.
create an empty "new master" list

for each list of contact HashMaps:
    convert the list of HashMaps to a merge list of Contact objects
    sort the merge list
    iterate the sorted master and merge lists in parallel:
        if a master Contact matches a merge Contact:
            merge the two Contacts and add to the new master list
            advance both iterators
        if a master Contact has no corresponding merge Contact:
            copy the master Contact to the new master list
            advance the master iterator.
        if a merge Contact has no corresponding master Contact:
            add the merge Contact to the new master list.
            advance the merge iterator

各个阶段的性能特征应该是:

• 将 N 个 HashMap 转换为 Contact 对象 - O(N)。
• 创建 N 个联系人列表 - O(N)
• 对 N 个联系人列表进行排序 - O(NlogN)
• 合并 2 个排序列表 - O(M + N)。

整体性能应该优于O(NlogN)，其中N是主和合并Customer对象的总数。