Golang如何对比两个对象切片查找重名不同类型的重叠值

需求说明 #

给定两个存储*Column结构体的切片，检测规则如下：

• 若两个切片中存在Name字段值相同，但对应Type字段值不一致的项，返回true（存在类型冲突）
• 若不存在上述冲突项，返回false
• 要求实现逻辑性能尽可能优

附基础结构体定义与测试样例：

package main

import (
    "fmt"
)

type Column struct {
    Name string `json:"name"`
    Type string `json:"type"`
}

func main() {
    a := []*Column{
        {Name: "a", Type: "int"},
        {Name: "b", Type: "int"},
    }
    b := []*Column{
        {Name: "a", Type: "int"},
        {Name: "c", Type: "string"},
    }
    c := []*Column{
        {Name: "a", Type: "string"},
        {Name: "d", Type: "int"},
    }
    // 预期：check(a,b)返回false，check(b,c)返回true
}

最优实现思路 #

避免双层循环带来的O(mn)时间复杂度，采用哈希表做映射，将整体时间复杂度控制在O(m+n)：

• 优先选择长度更短的切片构建哈希映射，key存储Name字段值，value存储对应的Type字段值，减少哈希表扩容开销、降低内存占用
• 遍历第二个切片，对每个元素直接查哈希表：如果存在同名键，直接比对Type值，发现不一致立刻返回结果，无需遍历剩余元素
• 全程无额外冗余遍历，遇到冲突可提前终止，性能最优

完整实现代码 #

func check(obj1, obj2 []*Column) bool {
    // 保证obj1始终是长度更短的切片，压缩map构建成本
    if len(obj1) > len(obj2) {
        obj1, obj2 = obj2, obj1
    }

    // 预分配map容量，避免动态扩容损耗
    nameTypeMap := make(map[string]string, len(obj1))
    for _, col := range obj1 {
        nameTypeMap[col.Name] = col.Type
    }

    for _, col := range obj2 {
        if t, ok := nameTypeMap[col.Name]; ok && t != col.Type {
            return true
        }
    }

    return false
}

结果验证 #

• 传入切片a和b：两者重名的Name="a"项Type均为int，无冲突，返回false，符合预期
• 传入切片b和c：两者重名的Name="a"项Type分别为int和string，存在冲突，返回true，符合预期

内容的提问来源于stack exchange，提问作者Tech-geek