JS：使用字典比循环数组更快吗？

Question

我正在 Nodejs 中构建一些程序，该程序需要跟踪大量用户的内存。另外，我将有一个按 id 过滤用户的功能。代码看起来像这样：

const users = [
    {
        id: 1,
        name: 'John',
        friends: [3, 6, 8]
    },
    {
        id: 2,
        name: 'Mark',
        friends: [567, 23]
    }
]

function getUserById(userId) {
    const user = users.filter(user => user.id === userId);
    return user[0];
}

问题是，这个版本是否普遍更快（每个键都是用户id）：

const users = {
    1: {
        id: 1,
        name: 'John',
        friends: [3, 6, 8]
    },
    2: {
        id: 2,
        name: 'Mark',
        friends: [567, 23]
    }
}

function getUserById(userId) {
   return users[userId];
}

我的直觉告诉我字典更快。事实是什么？

Answer 1

不保证对象中的键查找时间。它也可能是 O(n)，但如果您多次动态查找某个键，大多数引擎会将其优化为 O(1)。过滤数组的时间复杂度为 O(n)，.find()但平均速度要快两倍：

  return users.find(user => user.id === userId);

现在保证O(log n) 查找的唯一数据结构是Maps：

 const userMap = new Map(users.map(u => [u.id, u]));
 console.log(userMap.get("test"));

但是，如果您计划大规模执行此操作（100k 很大），我宁愿将该任务移至数据库，因为它针对这些任务进行了大幅优化。MongoDB 很容易采用，Redis 会非常快，还有很多其他的。