如何在JavaScript中使用两个对象数组执行内部连接？

Question

我有两个对象数组：

var a = [
  {id: 4, name: 'Greg'},
  {id: 1, name: 'David'},
  {id: 2, name: 'John'},
  {id: 3, name: 'Matt'},
]

var b = [
  {id: 5, name: 'Mathew', position: '1'},
  {id: 6, name: 'Gracia', position: '2'},
  {id: 2, name: 'John', position: '2'},
  {id: 3, name: 'Matt', position: '2'},
]

我想对这两个数组a和b进行内连接，并创建一个像这样的第三个数组（如果位置属性不存在，则变为null）：

var result = [{
  {id: 4, name: 'Greg', position: null},
  {id: 1, name: 'David', position: null},
  {id: 5, name: 'Mathew', position: '1'},
  {id: 6, name: 'Gracia', position: '2'},
  {id: 2, name: 'John', position: '2'},
  {id: 3, name: 'Matt', position: '2'},
}]

我的方法：

function innerJoinAB(a,b) {
    a.forEach(function(obj, index) {
        // Search through objects in first loop
        b.forEach(function(obj2,i2){
        // Find objects in 2nd loop
        // if obj1 is present in obj2 then push to result.
        });
    });
}

但时间复杂度是O(N^2)。我该如何使其达到O(N)？我的朋友告诉我可以使用reducers和Object.assign。

我无法理解这个。请帮助我。

- TechnoCorner

---

你有两个对象数组。看起来你需要将一个数组的所有值复制到一个新的数组中，然后将第二个（以及随后的）数组合并到其中。Array.prototype.reduce 可能是一个好的开始。主键是什么，id吗？由于你正在使用数组来保存对象，很可能你还想创建一个ID到数组索引的索引，这样你可以轻松地找到ID，而不必每次迭代数组。 - RobG

PS内连接可能不是正确的术语，因为据我理解，它只会给出两个集合中都有匹配项的结果集（因此您的示例只会给出ID为2和3的行）。这更像是一种典型的合并操作。 - Marty

@NicholasSmith 这是 JavaScript，不是 JSON。 - Hamms

根据您的输出示例，您需要的是完全外连接，而不是内连接。 - svenema

全外连接 - 是的，这个问题是关于全外连接的。例如，请参考 Different Types of SQL JOINs，图片：https://i.imgur.com/yhYDsI2.png。 - Henke

Answer 1

我不知道如何在这里使用`reduce`帮助，但是您可以使用一个`Map`以O(n)的时间复杂度完成相同的任务：

const a = [
  {id: 4, name: 'Greg'},
  {id: 1, name: 'David'},
  {id: 2, name: 'John'},
  {id: 3, name: 'Matt'}];

const b = [
  {id: 5, name: 'Mathew', position: '1'},
  {id: 6, name: 'Gracia', position: '2'},
  {id: 2, name: 'John', position: '2'},
  {id: 3, name: 'Matt', position: '2'}];

var m = new Map();
// Insert all entries keyed by ID into the Map, filling in placeholder
// 'position' since the Array 'a' lacks 'position' entirely:
a.forEach(function(x) { x.position = null; m.set(x.id, x); });

// For values in 'b', insert them if missing, otherwise, update existing values:
b.forEach(function(x) {
    var existing = m.get(x.id);
    if (existing === undefined)
        m.set(x.id, x);
    else
        Object.assign(existing, x);
});

// Extract resulting combined objects from the Map as an Array
var result = Array.from(m.values());

console.log(JSON.stringify(result));

.as-console-wrapper { max-height: 100% !important; top: 0; }

由于Map的访问和更新是O(1)（平均情况下 - 由于哈希冲突和重新哈希，可能会更长），因此这使得O(n+m)（其中n和m分别是a和b的长度；您提供的朴素解决方案将使用相同的n和m含义，时间复杂度为O(n*m)）。

- ShadowRanger

---

这里有一个问题：如果在数组a中设置了位置，但是在b中没有复制，那么它将会丢失。 - Gerrit0

@Gerrit0：我在评论中注意到了这个假设（即a始终缺少position）。您可以轻松地将在处理a时设置x.position的集合条件，但OP提供的输入表明a从未具有position，而b则总是具有。同样，这假定id本身是唯一的（不需要将name作为键的一部分，因为假定如果id匹配，则name将匹配）。 - ShadowRanger

这对我来说看起来像是左连接，而不是内连接。 - phil

@phil：同意。原帖要求内连接，但他们想要的输出是左连接。我提供了一个答案，可以产生他们想要的输出，因为很明显他们使用了错误的术语。 - ShadowRanger

Answer 2

解决这个问题的其中一种方法。

const a = [
  {id: 4, name: 'Greg'},
  {id: 1, name: 'David'},
  {id: 2, name: 'John'},
  {id: 3, name: 'Matt'},
];

const b = [
  {id: 5, name: 'Mathew', position: '1'},
  {id: 6, name: 'Gracia', position: '2'},
  {id: 2, name: 'John', position: '2'},
  {id: 3, name: 'Matt', position: '2'},
];

const r = a.filter(({ id: idv }) => b.every(({ id: idc }) => idv !== idc));
const newArr = b.concat(r).map((v) => v.position ? v : { ...v, position: null });

console.log(JSON.stringify(newArr));

.as-console-wrapper { max-height: 100% !important; top: 0; }

- kind user

---

请注意，这个算法的时间复杂度仍为 O(N^2)（技术上说是 O(N*M)，其中 N 和 M 分别代表两个数组的长度）。 - Hamms

此外，它使用“名称”作为主键，这可能不是预期的，因为名称可能是非唯一的。 - Felix Dombek

@FelixDombek 请提供更多信息。 - kind user

在filter的那一行，我认为你应该比较id而不是名字。 - Felix Dombek

@FelixDombek 同意，但在这种特殊情况下，这并没有什么区别(: 无论如何，我已经改变了它。 - kind user

Answer 3

如果你放弃使用null条件（社区中很多人都说使用null是不好的），那么就有一个非常简单的解决方案。

let a = [1, 2, 3];
let b = [2, 3, 4];

a.filter(x => b.includes(x)) 

// [2, 3]

- Stephen

---

1和4怎么样？ - montelof

喜欢全外连接吗？它应该是[].concat( a.filter(x => !b.includes(x)), b.filter(x => !a.includes(x)) ) - Stephen

Answer 4

为了降低时间复杂度，使用更多的内存是不可避免的。

var a = [
  {id: 4, name: 'Greg'},
  {id: 1, name: 'David'},
  {id: 2, name: 'John'},
  {id: 3, name: 'Matt'},
]

var b = [
  {id: 5, name: 'Mathew', position: '1'},
  {id: 6, name: 'Gracia', position: '2'},
  {id: 2, name: 'John', position: '2'},
  {id: 3, name: 'Matt', position: '2'},
]     

var s = new Set();
var result = [];
b.forEach(function(e) {
    result.push(Object.assign({}, e));
    s.add(e.id);
});
a.forEach(function(e) {
    if (!s.has(e.id)) {
      var temp = Object.assign({}, e);
      temp.position = null;
      result.push(temp);
    }
});
console.log(result);

更新

正如@Blindman67所提到的：“将搜索移动到本地代码中并不会减少问题的复杂性。” 我已经查阅了《ECMAScript® 2016语言规范》关于Set.prototype.has()和Map.prototype.get()的内部程序，不幸的是，它们似乎都要遍历它们拥有的所有元素。

Set.prototype.has ( value )#

The following steps are taken:

    Let S be the this value.
    If Type(S) is not Object, throw a TypeError exception.
    If S does not have a [[SetData]] internal slot, throw a TypeError exception.
    Let entries be the List that is the value of S's [[SetData]] internal slot.
    Repeat for each e that is an element of entries,
        If e is not empty and SameValueZero(e, value) is true, return true.
    Return false. 

http://www.ecma-international.org/ecma-262/7.0/#sec-set.prototype.has

Map.prototype.get ( key )#

The following steps are taken:

    Let M be the this value.
    If Type(M) is not Object, throw a TypeError exception.
    If M does not have a [[MapData]] internal slot, throw a TypeError exception.
    Let entries be the List that is the value of M's [[MapData]] internal slot.
    Repeat for each Record {[[Key]], [[Value]]} p that is an element of entries,
        If p.[[Key]] is not empty and SameValueZero(p.[[Key]], key) is true, return p.[[Value]].
    Return undefined. 

http://www.ecma-international.org/ecma-262/7.0/#sec-map.prototype.get

也许我们可以使用 Object，它可以直接通过属性名访问其属性，例如哈希表或关联数组:

var a = [
  {id: 4, name: 'Greg'},
  {id: 1, name: 'David'},
  {id: 2, name: 'John'},
  {id: 3, name: 'Matt'},
]

var b = [
  {id: 5, name: 'Mathew', position: '1'},
  {id: 6, name: 'Gracia', position: '2'},
  {id: 2, name: 'John', position: '2'},
  {id: 3, name: 'Matt', position: '2'},
]     

var s = {};
var result = [];
b.forEach(function(e) {
    result.push(Object.assign({}, e));
    s[e.id] = true;
});
a.forEach(function(e) {
    if (!s[e.id]) {
      var temp = Object.assign({}, e);
      temp.position = null;
      result.push(temp);
    }
});
console.log(result);

- Yichong

---

你误解了规范。Set在文档中描述的是基本逻辑，而不是实际的实现策略。get和has需要是次线性的，所以最坏情况下它们是O(log n)，建议的实现是哈希表，是O(n)的。请阅读整个 Set 文档中的早期部分： - ShadowRanger

集合对象必须使用哈希表或其他机制来实现，这些机制在平均情况下提供的访问时间是子线性的，与集合中元素数量成比例。此集合对象规范中使用的数据结构仅旨在描述集合对象所需的可观察语义，而不是可行的实现模型。 - ShadowRanger

一个问题 @Y.C 为什么你使用了 result.push(Object.assign({}, e)); 为什么我们不能只是 push result.push(e); 它会得到相同的结果吗？ - TechnoCorner

@ShadowRanger 在JS中最常用的是 obj.property，如果每次使用 . 运算符都需要进行搜索，那将是非常糟糕的，几乎不可能实现。因此，我非常确定 . 运算符具有直接访问对象属性的能力。 - Yichong

@Y.C.：鉴于绝大多数对象最多只有几十个属性，二分查找的时间复杂度为O(log n)，只需要进行少量测试（例如32个属性只需进行约6次测试）；实际上，由于碰撞的存在，哈希表在大多数情况下也必须执行少量测试，因此差距不会太大。请注意，我并不认为他们真的这样做了，但是，我认为任何人都没有用除哈希表以外的任何东西来实现Map或Set；你不能仅凭直觉攻击一种方法，而不将自己的方法置于同样的批评之下。 - ShadowRanger

Answer 5

把搜索移至本地代码并不能减少问题的复杂性。搜索仍然必须完成。

此外，需要将未定义的属性置为空是我不喜欢使用 null 的众多原因之一。

因此，如果没有 null，解决方案将如下所示：

var a = [
  {id: 4, name: 'Greg',position: '7'},
  {id: 1, name: 'David'},
  {id: 2, name: 'John'},
  {id: 3, name: 'Matt'},
]

var b = [
  {id: 5, name: 'Mathew', position: '1'},
  {id: 6, name: 'Gracia', position: '2'},
  {id: 2, name: 'John', position: '2'},
  {id: 3, name: 'Matt', position: '2'},
]


function join (indexName, ...arrays) {
    const map = new Map();
    arrays.forEach((array) => {
        array.forEach((item) => {
            map.set(
                item[indexName],
                Object.assign(item, map.get(item[indexName]))
            );
        })
    })
    return [...map.values()];
}

并且被调用为

const joinedArray = join("id", a, b);

加入默认值会更加复杂，但它应该会很方便，因为它可以连接任意数量的数组并自动将缺失的属性设置为提供的默认值。

在连接后进行默认值测试可以节省一些时间。

function join (indexName, defaults, ...arrays) {
    const map = new Map();
    arrays.forEach((array) => {
        array.forEach((item) => {
            map.set(
                item[indexName], 
                Object.assign( 
                    item, 
                    map.get(item[indexName])
                )
            );
        })
    })
    return [...map.values()].map(item => Object.assign({}, defaults, item));

}

使用

标签

const joinedArray = join("id", {position : null}, a, b);

你可以添加...

    arrays.shift().forEach((item) => {  // first array is a special case.
        map.set(item[indexName], item);
    });

我通常会在函数开头加入这段代码以节省一些时间，但我觉得没有这段额外的代码更加优雅。

- Blindman67

Answer 6

这里尝试着提供一个更通用的连接函数，它可以接受 N 个对象，并根据主键 id 进行合并。

如果性能至关重要，最好使用像 ShadowRanger 提供的特定版本，它不需要动态构建所有属性键的列表。

此实现假定任何缺失的属性都应设置为 null，并且每个输入数组中的每个对象具有相同的属性（尽管属性可能在数组之间不同）。

var a = [
    {id: 4, name: 'Greg'},
    {id: 1, name: 'David'},
    {id: 2, name: 'John'},
    {id: 3, name: 'Matt'},
];
var b = [
    {id: 5, name: 'Mathew', position: '1'},
    {id: 600, name: 'Gracia', position: '2'},
    {id: 2, name: 'John', position: '2'},
    {id: 3, name: 'Matt', position: '2'},
];

console.log(genericJoin(a, b));

function genericJoin(...input) {
    //Get all possible keys
    let template = new Set();
    input.forEach(arr => {
        if (arr.length) {
            Object.keys(arr[0]).forEach(key => {
                template.add(key);
            });
        }
    });

    // Merge arrays
    input = input.reduce((a, b) => a.concat(b));

    // Merge items with duplicate ids
    let result = new Map();
    input.forEach(item => {
        result.set(item.id, Object.assign((result.get(item.id) || {}), item));
    });

    // Convert the map back to an array of objects
    // and set any missing properties to null
    return Array.from(result.values(), item => {
        template.forEach(key => {
            item[key] = item[key] || null;
        });
        return item;
    });
}

- Gerrit0

Answer 7

根据我所做的广泛研究，没有办法将两个列表的连接减少到O(n*m)以外。

我理解大多数数据库使用的经典解决方案是从较小的列表创建索引，然后扫描该索引。这本质上只是尽可能地将O(n*m)“工作”向下推送到解释器链中。也就是说，您的操作系统/处理器API可能有一种非常优化的方式来编排列表比较，因此您可以从它们执行工作中获得性能提升。这在技术上使其成为O(n*m + n)，但仍应该是最有效的。

var a = [
  {id: 4, name: 'Greg'},
  {id: 1, name: 'David'},
  {id: 2, name: 'John'},
  {id: 3, name: 'Matt'},
]

var b = [
  {id: 5, name: 'Mathew', position: '1'},
  {id: 6, name: 'Gracia', position: '2'},
  {id: 2, name: 'John', position: '2'},
  {id: 3, name: 'Matt', position: '2'},
]

const idx = a.reduce(prev, _ => {
    prev[_.id] = _
}, {})

const result = b.reduce(prev, _ => {
  if( idx[_] !== undefined ){
    prev.push([_, idx[_.id])
}, [])

再次强调，据我所知，这可能是经典解决方案。但愿我错了。

- Jamie Marshall

Answer 8

这是一个通用的O(n*m)解决方案，其中n是记录数，m是键数。这仅适用于有效的对象键。如果需要，您可以将任何值转换为base64并使用它。

const join = ( keys, ...lists ) =>
    lists.reduce(
        ( res, list ) => {
            list.forEach( ( record ) => {
                let hasNode = keys.reduce(
                    ( idx, key ) => idx && idx[ record[ key ] ],
                    res[ 0 ].tree
                )
                if( hasNode ) {
                    const i = hasNode.i
                    Object.assign( res[ i ].value, record )
                    res[ i ].found++
                } else {
                    let node = keys.reduce( ( idx, key ) => {
                        if( idx[ record[ key ] ] )
                            return idx[ record[ key ] ]
                        else
                            idx[ record[ key ] ] = {}
                        return idx[ record[ key ] ]
                    }, res[ 0 ].tree )
                    node.i = res[ 0 ].i++
                    res[ node.i ] = {
                        found: 1,
                        value: record
                    }
                }
            } )
            return res
        },
        [ { i: 1, tree: {} } ]
         )
         .slice( 1 )
         .filter( node => node.found === lists.length )
         .map( n => n.value )

join( [ 'id', 'name' ], a, b )

这与Blindman67的答案基本相同，只是它添加了一个索引对象来标识要连接的记录。记录存储在数组中，索引存储给定键集的记录位置以及它在多少个列表中被找到。

每次遇到相同的键集时，在树中找到节点，更新其索引处的元素，并将其被找到的次数加1。

最后，使用切片从数组中删除idx对象，删除在每个集合中未找到的任何元素。这使它成为内部连接，您可以删除此过滤器并进行完全外部连接。

最后，将每个元素映射到其值，然后您就有了合并的数组。

- Snowbldr