面试官：Object和Map的区别，Map的时间复杂度是多少

简述

面试官：说下Object和Map的区别。

我：.........心里想完蛋Map虽然知道这个词，但是平时不用并不熟悉啊，但是也不能直接说出来啊，能说多少就多少吧。嗯......它们都是以键值对形式储存数据，它们的内部操作方法不一样.........，我知道的是这么多了。

面试官：........嗯，好吧。

面试官：那你说下知道key的话，Map的查找的时间复杂度是多少。

我：既然知道键key了，那么查找的复杂度是O(1)。

面试官：嗯，那怎么样才能使得查找复杂度O(1)呢。

我：...........不了解。

在这次面试中问到Map的问题时经常卡壳，而且回答的都只是很浅显，因为平时用到Map的地方相对少，而且过往时问没有碰到问Map的，因此这个ES6后新的数据结构了解的不多，借此机会多多熟悉一下。

Object和Map的区别

想知道第一个问题，那么我们首先需要的是先分别知道Object和Map是什么，这样才更好的比较他们的区别。

Object

在MDN上介绍Object是 JavaScript 的一种数据类型。它用于存储各种键值集合和更复杂的实体。可以通过Object()构造函数或者使用对象字面量的方式创建对象。

const obj = new Object() // 得到一个空对象 {}

const obj2 = {} // 得到一个空对象 {}

Object是由键值对的形式存储数据的，它的键key必须是String类型或者Symbol类型的，其他的会自动转换成String类型；Object的属性值可以是任何类型的数据，包括基本类型（如字符串、数字、布尔值）、对象类型（如Array、Date、RegExp等）和函数类型。

Object方法

下面是Object的一些方法，包括静态方法和实例方法，含有链接，点击方法名称可以跳转到MDN。

静态方法

• Object.assign()
• 将一个或多个源对象的所有可枚举自有属性的值复制到目标对象中。
• Object.create()
• 使用指定的原型对象和属性创建一个新对象。
• Object.defineProperties()
• 向对象添加多个由给定描述符描述的命名属性。
• Object.defineProperty()
• 向对象添加一个由给定描述符描述的命名属性。
• Object.entries()
• 返回包含给定对象自有可枚举字符串属性的所有 [key, value] 数组。
• Object.freeze()
• 冻结一个对象。其他代码不能删除或更改其任何属性。
• Object.fromEntries()
• 从一个包含 [key, value] 对的可迭代对象中返回一个新的对象（Object.entries的反操作）。
• Object.getOwnPropertyDescriptor()
• 返回一个对象的已命名属性的属性描述符。
• Object.getOwnPropertyDescriptors()
• 返回一个包含对象所有自有属性的属性描述符的对象。
• Object.getOwnPropertyNames()
• 返回一个包含给定对象的所有自有可枚举和不可枚举属性名称的数组。
• Object.getOwnPropertySymbols()
• 返回一个数组，它包含了指定对象所有自有 symbol 属性。
• Object.getPrototypeOf()
• 返回指定对象的原型（内部的 [[Prototype]] 属性）。
• Object.hasOwn()
• 如果指定属性是指定对象的自有属性，则返回 true，否则返回 false。如果该属性是继承的或不存在，则返回 false。
• Object.is()
• 比较两个值是否相同。所有 NaN 值都相等（这与==使用的 IsLooselyEqual 和===使用的 IsStrictlyEqual 不同）。
• Object.isExtensible()
• 判断对象是否可扩展。
• Object.isFrozen()
• 判断对象是否已经冻结。
• Object.isSealed()
• 判断对象是否已经封闭。
• Object.keys()
• 返回一个包含所有给定对象自有可枚举字符串属性名称的数组。
• Object.preventExtensions()
• 防止对象的任何扩展。
• Object.seal()
• 防止其他代码删除对象的属性。
• Object.setPrototypeOf()
• 设置对象的原型（即内部 [[Prototype]] 属性）。
• Object.values()
• 返回包含给定对象所有自有可枚举字符串属性的值的数组。

实例方法

• Object.prototype.hasOwnProperty()
• 返回一个布尔值，用于表示一个对象自身是否包含指定的属性，该方法并不会查找原型链上继承来的属性。
• Object.prototype.isPrototypeOf()
• 返回一个布尔值，用于表示该方法所调用的对象是否在指定对象的原型链中。
• Object.prototype.propertyIsEnumerable()
• 返回一个布尔值，指示指定属性是否是对象的可枚举自有属性。
• Object.prototype.toLocaleString()
• 调用 toString() 方法。
• Object.prototype.toString()
• 返回一个代表该对象的字符串。
• Object.prototype.valueOf()
• 返回指定对象的基本类型值

删除Object里面的键值对

在Object中并没有提供方法删除键值对，需要使用delete运算符

let obj = {
    name: '张三',
    age: '100'
}

delete obj.name // true
// 或者
delete obj['name'] // true

console.log(obj) // {age: 100}

Map

Map是也是以键值对形式存储数据的，它的键key可以是任意类型，是一种更加完善的Hash结构实现，创建Map结构通常使用new Map()来实现。

const map = new Map()

map.set(1,2)
console.log(map) Map(1) {1 => 2}

map.get(1) // 2
map.has(1) // 查看是否有该键值 true

设置对象属性同样适用于 Map 对象，但容易造成困扰, 因此并不推荐这样做。

const map = new Map()

map['a'] = 1
console.log(map) // Map(0) {a: 1, size: 0}

map.get('a') // undefined
map.has('a') // false

这种设置属性的方式不会改变 Map 的数据结构。它使用的是通用对象的特性。'a' 的值未被存储在 Map 中，无法被查询到,因此可以看到上面代码的Map的size属性是0。

Map键的唯一性

Map的键key具有唯一性，确定后再次创建会覆盖，Map 的键实际上是跟内存地址绑定的，只要内存地址不一样，就视为两个键，因此可以使用这个方法创建两个同名的键。

const map = new Map();

// 下面代码中使用了一个数组作为Key,但是获取值时返回的确是undefined
// 因为这个是一个引用数据类型，设置的和获取的并不是同一个引用地址，Map将他们视为不同的key
// 因此获取不到值。
map.set(['a'], 555);
map.get(['a']) // undefined

const k1 = ['a'];
const k2 = ['a'];

map.set(k1, 111).set(k2, 222);

map.get(k1) // 111
map.get(k2) // 222

将NaN作为Map的键

NaN也可以作为键。虽然 NaN与任何值甚至与自己都不相等（NaN !== NaN 返回 true），但是因为所有的 NaN 的值都是无法区分的。

Map的迭代

由于Map内置有迭代器iterator，因此可以使用forEach和for of实现迭代，迭代的顺序按插入的顺序进行。

const map = new Map()
map.set(NaN, "not a number")

map.get(NaN) // "not a number"

const otherNaN = Number("foo") // NaN
map.get(otherNaN) // 因为otherNaN的值时NaN，相当于map.get(NaN)，"not a number"

Map的方法

• Map.prototype.clear()
• 移除 Map 对象中所有的键值对。
• Map.prototype.delete()
• 移除 Map 对象中指定的键值对，如果键值对存在并成功被移除，返回 true，否则返回 false。调用 delete 后再调用 map.has(key) 将返回 false。
• Map.prototype.entries()
• 返回一个新的迭代器对象，其包含 Map 对象中所有键值对 [key, value] 二元数组，以插入顺序排列。
• Map.prototype.forEach()
• 以插入顺序为 Map 对象中的每个键值对调用一次 callbackFn。如果为 forEach 提供了 thisArg 参数，则它将作为每一次 callback 的 this 值。
• Map.prototype.get()
• 返回与指定的键 key 关联的值，若不存在关联的值，则返回 undefined。
• Map.prototype.has()
• 返回一个布尔值，用来表明 Map 对象中是否存在与指定的键 key 关联的值。
• Map.prototype.keys()
• 返回一个新的迭代器对象，其包含 Map 对象中所有元素的键，以插入顺序排列。
• Map.prototype.set()
• 在 Map 对象中设置与指定的键 key 关联的值，并返回 Map 对象。
• Map.prototype.values()
• 返回一个新的迭代对象，其中包含 Map 对象中所有的值，并以插入 Map 对象的顺序排列。
• Map.prototype[@@iterator]()
• 返回一个新的迭代器对象，其包含 Map 对象中所有元素 [key, value] 二元数组，以插入顺序排列。

总结-它们的区别

1. 键的类型：Object的键只能是String类型或者Symbol类型，而Map的键可以是任何类型的数据，包括对象、函数、布尔值、数字等。
2. 迭代：Object本身不具备迭代器，默认不能使用for of，而Map内置有迭代器可以的for...of循环和forEach循环进行迭代。
3. 添加键值对的方法：Object使用obj[key] = value来添加键值对，而Map使用map.set(key, value)方法来添加键值对。
4. 删除键值对的方法：Object没有提供删除的方法，需要使用delete obj[key]来删除键值对，而Map可以使用内部方法map.delete(key)方法来删除键值对。
5. 检查键是否存在的方法：Object使用obj.hasOwnProperty(key)来检查键是否存在，而Map使用map.has(key)方法来检查键是否存在。
6. 获取键值对的方法：Object使用obj[key]来获取键值对，而Map使用map.get(key)方法来获取键值对。
7. 遍历键值对的方法：Object使用for...in循环和Object.keys()、Object.values()、Object.entries()等方法来遍历对象的键值对，而Map使用for...of循环和Map.keys()、Map.values()、Map.entries()等方法来遍历它的键值对。
8. 序列化：Object可以使用JSON.stringify进行序列化操作，而Map无法被序列化，因为键可以是任意类型的，而JSON.stringify序列化只支持键为字符串类型，因此JSON序列化会得到{}。
9. Object是无序的，Map是有序的，按照插入的顺序。

Map的时间复杂度

这个问题当时我回答面试官的是O(1),因为当时认为，既然是键值对形式存在的，而且我已经知道键了，那我直接就可以拿到值了，那我当时的答案就是O(1)。

这个回答没错，只是也没有完全对，因为应该需要考虑到Map的情况，在最好的情况下确实是O(1)没错，但是在最坏的情况下应该是O(n)。

因此面试官在我回答O(1)时候，才会问我在什么情况下才是O(1)呢，只是当时不懵，脑袋有点转不过来。

应该答：

面试官： 请说下知道了键，在Map中查找值时间复杂度是多少。

我： 有可能是O(1)，也有可能O(n)

面试官：那在什么情况下时间复杂度为O(1)呢。

我：在Map的结构简单没有冲突的时候，因为这样的话需要的键值直接在Map的第一层，不需要遍历就可以找到准确的值，反之就可能照成O(n)的情况。

面试官问map的时间复杂度一般是想问hash表的冲突问题，map的时间复杂度主要取决于其具体实现方式。在理想情况下，如果能够将键均匀分布在整个哈希表中，避免冲突，那么map的查找、插入和删除操作的时间复杂度可以达到O(1)，即常数时间复杂度。然而，如果哈希函数导致很多键落在同一个桶中，形成链表或红黑树，如果是链表的时间复杂度将退化为O(n)，其中n是链表或树中的条目数量，如果是红黑树那么就是O(logn)。【感谢评论区老哥的点拨】

作者：jun_不见
链接：https://juejin.cn/post/7374685303884562484