Scala中基于公共键合并不等长Map列表的高效函数式实现方案

需求说明 #

需要基于公共键合并多个长度不等的Map列表，仅保留能通过公共键完全匹配的结果。

输入示例 #

val list1 = List(
    Map("ID" -> "123", "NAME" -> "P1", "PID" -> "321"),
    Map("ID" -> "456", "NAME" -> "P2",  "PID" -> "333")
)

val list2 = List(
    Map("ID" -> "123", "ADDRESS" -> "A1")
)

val list3 = List(
    Map("PID" -> "321", "PHONE" -> "2222"), 
    Map("PID" -> "789", "PHONE" -> "4444")
)

期望输出 #

List(
    Map(
        "ID" -> "123", 
        "NAME" -> "P1", 
        "PID" -> "321", 
        "ADDRESS" -> "A1", 
        "PHONE" -> "2222"
    )
)

现有方案问题 #

原方案通过多层flatMap嵌套实现，本质是三重循环，时间复杂度为O(nmk)（n、m、k分别为三个列表的长度），数据量较大时性能会急剧下降，且硬编码键名的写法灵活性差。

原尝试代码（修正了Map取值的语法错误）：

list1
  .flatMap { l1 =>
    list2
      .flatMap { l2 =>
        list3
          .map { l3 =>
            if ((l1("ID") == l2("ID")) && (l1("PID") == l3("PID"))) {
              val data = Map(
                "ID" -> l1("ID"),
                "NAME" -> l1("NAME"),
                "PID" -> l1("PID"),
                "ADDRESS" -> l2("ADDRESS"),
                "PHONE" -> l3("PHONE")
              )
              List(data)
            } else {
              Nil
            }
          }
      }
  }

优化的纯函数式解决方案 #

通过构建哈希索引将查找操作降为O(1)，整体时间复杂度优化为O(n+m+k)，每个列表仅需遍历一次：

// 1. 为list2构建ID到对应Map的索引
val idIndex = list2.map(m => m("ID") -> m).toMap
// 2. 为list3构建PID到对应Map的索引
val pidIndex = list3.map(m => m("PID") -> m).toMap

// 3. 遍历list1，合并匹配的Map
val result = list1.flatMap { item =>
  for {
    addressMap <- idIndex.get(item("ID"))
    phoneMap <- pidIndex.get(item("PID"))
  } yield item ++ addressMap ++ phoneMap
}

方案解释 #

1. 索引构建：将list2和list3分别转换为以关联键（ID、PID）为Key的Map，后续通过键查找对应数据的操作是常数时间。
2. 匹配合并：使用for推导式处理可选值（Option），仅当list2中存在对应ID的Map、且list3中存在对应PID的Map时，才执行合并操作，否则跳过该item。
3. Map合并：Scala的Map++操作会自动合并多个Map的键值对，由于这里各Map的键无重复，无需担心覆盖问题。

运行上述代码即可得到符合预期的输出结果。

内容的提问来源于stack exchange，提问作者Ratan Gupta