使用Map来提升匹配速度

我们经常会遇到这样一个场景：对两个列表中的数据进行相互匹配。最近，小明就遇到了这样一个问题：用户会上传订单产品和订单PDF的数据，这两种信息分别存放到数据库的两张表中。订单产品有id，name和pdfId三个字段；订单PDF有id，name和productId三个字段。其中，id是自增字段，name为唯一索引，pdfId和productId默认为0。

为了说明问题背景，本文主要使用 Javascript 来演示（因为Javascript相比Java，具有更好的可读性）：

const pdfs = [
  { id: 1, name: 'a', productId: 0 },
  { id: 2, name: 'b', productId: 0 },
  { id: 3, name: 'c', productId: 0 },
  { id: 4, name: 'd', productId: 0 }
]
const products = [
  { id: 81, name: 'a', pdfId: 0 },
  { id: 82, name: 'x', pdfId: 0 },
  { id: 83, name: 'c', pdfId: 0 },
  { id: 84, name: 'b', pdfId: 0 }
]

对于上面的两个数组（列表），如何通过某种算法来让它们相互匹配，并设置正确的 productId 和 pdfId 字段的值呢？

方法一：嵌套循环法

// 1 pdf match product
pdfs.forEach(pdf => {
  const matched = products.find(prod => prod.name === pdf.name)
  if (matched) {
    pdf.productId = matched.id
  }
})

// 2 product match pdf
products.forEach(prod => {
  const matched = pdfs.find(pdf => pdf.name === prod.name)
  if (matched) {
    prod.pdfId = matched.id
  }
})

这种方式具有极其出色的可读性。但如果直接上生产，那极有可能出事故，为什么呢？

因为在真实的环境中，用户上传的数据量是不确定的。在一个订单中，用户可能会上传几十个产品，也有可能上传几千个产品。如果在一个订单中，用户上传了2000份PDF和2000份产品信息。然后，用上面的算法对这4000份数据进行匹配，将会导致一个可怕的性能问题。

因为上面的算法的时间复杂度为：O(n × m)。也就是说，外层循环：2000次，内层 find：每次最多遍历2000个产品或pdf，最坏的情况将进行 2000 × 2000 = 4,000,000 次比较。

对于2000份PDF和2000份产品而言，这种算法在我的电脑上进行单向匹配（pdf match product），需要大约20ms的时间，如果相互匹配，需要40ms。我的电脑CPU为 intel i5 4核心，node.js版本20.19.6。

方法二：Map索引法

小明虚心请教了同事老王，老王说用Map优化，将算法的时间复杂度变成O(n + m)。

优化后的代码如下：

function match2() {
  // 1 pdf match product
  const productMap = new Map()
  products.forEach(product => {
    productMap.set(product.name, product)
  })

  pdfs.forEach(pdf => {
    const matched = productMap.get(pdf.name)
    if (matched) {
      pdf.productId = matched.id
    }
  })

  // 2  product match pdf
  const pdfMap = new Map()
  pdfs.forEach(pdf => {
    pdfMap.set(pdf.name, pdf)
  })

  products.forEach(product => {
    const matched = pdfMap.get(product.name)
    if (matched) {
      product.productId = matched.id
    }
  })
}

其核心思想就是先构建一个Map，然后从Map中查找。Map.get() 的时间复杂度是 O(1)（常数时间）。它不需要遍历，而是通过哈希算法直接定位到内存地址。

对于2000份PDF和2000份产品，现在用优化版进行匹配，只需要2ms左右，比方法一提高了足足20倍左右的速度。

总结

记住一个原则：看到嵌套循环匹配两个集合，第一反应就应该想到用Map优化！