如何高效实现基于字段前缀匹配的两个Map合并？

嘿，这个问题确实有很好的优化空间，暴力遍历的O(n*m)复杂度在数据量上去之后肯定会拖慢性能，咱们可以通过预处理把时间复杂度降到接近线性的水平，下面给你两种可行的优化方案：

前缀树是处理前缀匹配问题的经典数据结构，它可以让我们把所有fullName的预处理时间控制在O(m)（m是mapPersonsWithFullName的条目数），之后每个firstName的查询时间只和其长度以及匹配到的fullName数量有关，整体时间复杂度为O(m + n + k)（n是mapPersonsWithFirstName的条目数，k是匹配到的总条目数）。

1. 实现简单的前缀树节点 #

class TrieNode {
    private final Map<Character, TrieNode> children = new HashMap<>();
    private final List<String> matchingFullNames = new ArrayList<>();

    // 插入fullName时，更新所有前缀节点的匹配列表
    public void insert(String fullName) {
        TrieNode current = this;
        for (char c : fullName.toCharArray()) {
            current.matchingFullNames.add(fullName);
            current = current.children.computeIfAbsent(c, k -> new TrieNode());
        }
        // 最后一个字符节点也要添加当前fullName（自身也是自己的前缀）
        current.matchingFullNames.add(fullName);
    }

    // 查询所有以指定前缀开头的fullName
    public List<String> findMatches(String prefix) {
        TrieNode current = this;
        for (char c : prefix.toCharArray()) {
            current = current.children.get(c);
            if (current == null) {
                return Collections.emptyList();
            }
        }
        return new ArrayList<>(current.matchingFullNames);
    }
}

2. 编写优化后的核心函数 #

import java.util.*;

public class PersonMatcher {
    public static Map<Integer, PersonWithFirstNameAndFullName> myFunction(
            Map<Integer, PersonWithFirstName> mapPersonsWithFirstName,
            Map<Integer, PersonWithFullName> mapPersonsWithFullName) {

        // 第一步：构建前缀树
        TrieNode root = new TrieNode();
        for (PersonWithFullName person : mapPersonsWithFullName.values()) {
            root.insert(person.fullName);
        }

        // 第二步：遍历每个PersonWithFirstName，查询匹配结果
        Map<Integer, PersonWithFirstNameAndFullName> result = new HashMap<>();
        for (Map.Entry<Integer, PersonWithFirstName> entry : mapPersonsWithFirstName.entrySet()) {
            int id = entry.getKey();
            PersonWithFirstName firstNamePerson = entry.getValue();
            List<String> matchedFullNames = root.findMatches(firstNamePerson.firstName);

            PersonWithFirstNameAndFullName combinedPerson = new PersonWithFirstNameAndFullName();
            combinedPerson.firstName = firstNamePerson.firstName;
            combinedPerson.fullNames = matchedFullNames;

            result.put(id, combinedPerson);
        }

        return result;
    }

    // 题目中的类定义（调整为可测试的格式）
    static class PersonWithFirstName {
        String firstName;
        public PersonWithFirstName(String firstName) {
            this.firstName = firstName;
        }
    }

    static class PersonWithFullName {
        String fullName;
        public PersonWithFullName(String fullName) {
            this.fullName = fullName;
        }
    }

    static class PersonWithFirstNameAndFullName {
        String firstName;
        List<String> fullNames;
    }

    // 测试示例
    public static void main(String[] args) {
        Map<Integer, PersonWithFirstName> mapPersonsWithFirstName = new HashMap<>();
        Map<Integer, PersonWithFullName> mapPersonsWithFullName = new HashMap<>();
        mapPersonsWithFirstName.put(1, new PersonWithFirstName("bob"));
        mapPersonsWithFirstName.put(2, new PersonWithFirstName("alice"));
        mapPersonsWithFullName.put(1, new PersonWithFullName("bobjohnson"));
        mapPersonsWithFullName.put(2, new PersonWithFullName("bobjames"));

        Map<Integer, PersonWithFirstNameAndFullName> result = myFunction(mapPersonsWithFirstName, mapPersonsWithFullName);

        // 打印验证结果
        for (Map.Entry<Integer, PersonWithFirstNameAndFullName> entry : result.entrySet()) {
            System.out.printf("%d: { firstName: \"%s\", fullNames: %s }%n",
                    entry.getKey(),
                    entry.getValue().firstName,
                    entry.getValue().fullNames);
        }
    }
}

如果不想实现自定义的数据结构，这种方案更简单，利用排序后的列表结合二分查找来定位匹配范围，时间复杂度为O(m log m + n log m)，比暴力法高效很多。

import java.util.*;

public class PersonMatcher {
    public static Map<Integer, PersonWithFirstNameAndFullName> myFunctionWithSort(
            Map<Integer, PersonWithFirstName> mapPersonsWithFirstName,
            Map<Integer, PersonWithFullName> mapPersonsWithFullName) {

        // 提取所有fullName并排序
        List<String> sortedFullNames = new ArrayList<>();
        for (PersonWithFullName person : mapPersonsWithFullName.values()) {
            sortedFullNames.add(person.fullName);
        }
        Collections.sort(sortedFullNames);

        Map<Integer, PersonWithFirstNameAndFullName> result = new HashMap<>();
        for (Map.Entry<Integer, PersonWithFirstName> entry : mapPersonsWithFirstName.entrySet()) {
            int id = entry.getKey();
            String firstName = entry.getValue().firstName;

            // 找到第一个匹配的起始位置
            int start = Collections.binarySearch(sortedFullNames, firstName);
            start = start < 0 ? -start - 1 : start;

            // 用"firstName + 最大字符"作为上界，找到第一个不匹配的位置
            String upperBound = firstName + Character.MAX_VALUE;
            int end = Collections.binarySearch(sortedFullNames, upperBound);
            end = end < 0 ? -end - 1 : end;

            // 截取匹配的子列表
            List<String> matchedFullNames = new ArrayList<>(sortedFullNames.subList(start, end));

            PersonWithFirstNameAndFullName combinedPerson = new PersonWithFirstNameAndFullName();
            combinedPerson.firstName = firstName;
            combinedPerson.fullNames = matchedFullNames;

            result.put(id, combinedPerson);
        }

        return result;
    }

    // 同样包含题目中的类定义和测试代码（和方案一一致，这里省略）
}

• 前缀树：适合需要频繁查询的场景，预处理一次后查询效率极高，空间复杂度取决于所有fullName的总字符数。
• 排序+二分：实现简单，无需自定义数据结构，适合一次性查询的场景，空间复杂度为O(m)。

内容的提问来源于stack exchange，提问作者Matt C.