如何高效将对象数组中的值迁移至另一数组键？

问题 #

现有如下键值对象，change 对象指示要执行添加操作：

let change = {key: 23, value: 3}
    
let obj = {
  22: [7, 4, 2, 3],
  23: [1, 5, 6],
}
    
obj[change.key].push(change.value)
    
console.log(obj)

执行后结果为：

{
  22: [7, 4, 2, 3],
  23: [1, 5, 6, 3],
}

但实际需要的效果是移除原数组22中的3，再将其添加到23的数组中，最终结果如下：

{
  22: [7, 4, 2],
  23: [1, 5, 6, 3],
}

已知所有键和值均唯一，问是否存在无需全量扫描对象来查找值3所在位置的高效实现方式？

目前想到的方法是使用find：

let fromKey = Object.keys(obj).find(key => obj[key].includes(change.value));
obj[fromKey] = obj[fromKey].filter(item => item !== change.value)

但认为当值的数量增多且分布较广时，该方法效率较低。

愿意重构对象结构，后续使用场景如下：

let change = {key: 23, value: 3}
    
let obj = {
  22: [7, 4, 2, 3],
  23: [1, 5, 6],
}

let vals = {
  1: 'a',
  2: 'b',
  3: 'c',
  4: 'd',
  5: 'e',
  6: 'f',
  7: 'g',

}
    
obj[change.key].push(change.value)
    
for (let k in obj) {
  let list = obj[k]
  for (let v of list) {
    console.log(k+': '+vals[v])
  }
}

高效解决方案 #

因为所有值都是唯一的，最直接的高效方式是维护一个反向映射表，记录每个值对应的所属键。这样不需要扫描整个对象，直接通过值拿到它原来的键，时间复杂度为O(1)。

重构后的结构 #

新增一个valueToKey对象存储值到键的映射，和原数据同步维护：

let change = {key: 23, value: 3}
    
let obj = {
  22: [7, 4, 2, 3],
  23: [1, 5, 6],
}

// 反向映射表：值 -> 所属键
let valueToKey = {
  7: 22,
  4: 22,
  2: 22,
  3: 22,
  1: 23,
  5: 23,
  6: 23,
}

let vals = {
  1: 'a',
  2: 'b',
  3: 'c',
  4: 'd',
  5: 'e',
  6: 'f',
  7: 'g',
}

执行移动操作的代码 #

// 1. 直接通过反向映射拿到值原来的键
const fromKey = valueToKey[change.value];
// 2. 从原数组中删除目标值（值唯一，找到索引直接删除）
const index = obj[fromKey].indexOf(change.value);
if (index !== -1) {
  obj[fromKey].splice(index, 1);
}
// 3. 将值添加到目标数组
obj[change.key].push(change.value);
// 4. 更新反向映射表
valueToKey[change.value] = change.key;

执行后obj的结果符合预期：

{
  22: [7, 4, 2],
  23: [1, 5, 6, 3],
}

适配后续使用场景 #

原有的遍历逻辑完全不需要修改，因为obj的结构和之前一致，遍历代码可直接复用：

for (let k in obj) {
  let list = obj[k]
  for (let v of list) {
    console.log(k+': '+vals[v])
  }
}

优势说明 #

• 移动操作的时间复杂度从原方案的O(n)（n为对象键的数量）降到O(1)（反向映射查找）+ O(m)（m为原数组长度，因值唯一，indexOf实际效率极高；若数组极大，还可将数组改为Set进一步优化删除效率）
• 仅需在添加/删除值时同步更新valueToKey，额外内存开销极小，换来操作效率的大幅提升

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