JavaScript Map()如何在保留顺序、不全量重建时替换/更新键

在使用对象作为键的Map()中，是否存在可替换/更新键的方法，能够不丢失条目原有顺序，且尽可能无需重建整个Map？

我尝试了3种实现方法，目标是将map中的键obj2替换为obj4，同时维持原始条目顺序：

const map = new Map(),
      obj1 = ["o1"],
      obj2 = ["o2"],
      obj3 = ["o3"],
      obj4 = ["o4"];

map.set(obj1, 1);
map.set(obj2, 2);
map.set(obj3, 3);

console.log("original: " + [...map], "expected result: o1,1,o4,2,o3,3");
console.log("1. 直接替换对象引用 - 无效: " + [...func1(new Map(map), obj4, obj2)]);
console.log("2. 新增键再删除旧键 - 顺序错误: " + [...func2(new Map(map), obj4, obj2)]);
console.log("3. 全量重建Map - 结果正确: " + [...func3(new Map(map), obj4, obj2)]);

//#1 直接替换对象引用 - 无效
function func1(map, _new, _old)
{
  let obj = map.get(_old);
  obj = _new; // 仅替换了变量存储的引用，不会修改Map本身存储的内容
  return map;
}

//#2 新增键再删除旧键 - 顺序错误
function func2(map, _new, _old)
{
  map.set(_new, map.get(_old));
  map.delete(_old)
  return map;
}

//#3 全量重建Map - 结果正确
function func3 (map, _new, _old) 
{
  for(let i = 0, update, entries = [...map]; i < entries.length; i++)
  {
    if (!update && entries[i][0] != _old)
      continue;

    map.delete(entries[i][0]);
    map.set(update ? entries[i][0] : _new, entries[i][1]);
    update = true;
  }
  return map;
}

上述第3种方法可以实现预期效果，但我想了解是否存在效率更高的实现方式？

原生Map没有提供直接修改键、同时保留原有插入位置的内置API。Map的条目顺序严格和插入顺序绑定，只要调用set()传入之前不存在的键，新条目就会被加到队列末尾，这也是第二个方法顺序错乱的根本原因。

第三种方法逻辑是对的，本质是从旧键所在位置开始，把后面所有条目删掉再按原顺序重新插回去，效率和Map总长度、旧键的位置直接挂钩：如果旧键在Map最开头，相当于要重建整个Map；如果旧键在最后一位，只需要操作两个条目，开销很小。

如果要进一步提效，可以根据使用场景选方案：

• 如果只是偶尔做键替换，直接用优化版的局部重建逻辑就行，不需要遍历全量条目做判断，定位到旧键位置后再操作后续条目即可，比原有实现少很多无效开销：

function replaceMapKey(map, newKey, oldKey) {
  if (!map.has(oldKey) || newKey === oldKey) return map
  const entryList = [...map]
  const replaceIndex = entryList.findIndex(([key]) => key === oldKey)
  if (replaceIndex === -1) return map
  // 从待替换位置开始，删除后面所有原有条目
  for (let i = replaceIndex; i < entryList.length; i++) {
    map.delete(entryList[i][0])
  }
  // 先插入替换后的新键
  map.set(newKey, entryList[replaceIndex][1])
  // 把后续条目按原顺序插回去
  for (let i = replaceIndex + 1; i < entryList.length; i++) {
    map.set(entryList[i][0], entryList[i][1])
  }
  return map
}

• 如果需要高频替换键，不要直接用原生Map，可以自己封装带顺序存储的结构：额外维护一个键映射表存键到存储节点的引用，再用双向链表维护条目顺序。替换键的时候只需要删掉映射表里的旧键、把新键指向对应节点，再更新节点里存储的键值即可，全程不需要挪动其他条目，时间复杂度是O(1)，性能高很多。

注意：不要尝试直接修改旧键对象本身的属性来“伪装”新键，Map对对象键的匹配是基于引用地址的，只要引用地址不变，不管对象属性怎么改，都还是同一个键；一旦换了引用地址，就必须走新增键的逻辑，没有捷径可走。

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