哈希图和时间复杂度
Hashmaps and Time Complexity
- 我的理解是
ES6 Map对象可以在Javascript中实现一个Hashmap。 正确吗？
indexOf 数组中的方法具有 O(n) 时间复杂度。- Maps 中的
has 方法是否具有 O(1) 时间复杂度？如果是，为什么？ JS如何一步一步找到Map对象中的元素？它与 indexOf 有何不同？如果没有 O(1) 那么 Es6 Map 不是真正的 Hashmap...
我的理解是 ES6 Map 对象可以在 Javascript 中实现一个 Hashmap。对吗？
不，它的措辞方式不正确。当你说 implement 时，你让我想起了像 java 这样的界面和语言。在 Java 中，有 interface map 然后有不同的实现，如 hashmap、treemap 等
在 javascript 的情况下，您可以使用 map（或者甚至可以使用数组）来实现 hashmap（或 hashtable）算法。
请注意，在某些浏览器（如 v8）中，地图已经使用散列 table 构建，因此它已经是一个散列图。不幸的是，ECMAScript 2015 规范（参见 https://262.ecma-international.org/6.0/#sec-map-objects ）没有指定或规定确切的实现。相反，它是完全开放的，允许每个浏览器或 java 脚本引擎有一个兼容的实现。
Map object must be implemented using either hash tables or other
mechanisms that, on average, provide access times that are sublinear
on the number of elements in the collection. The data structures used
in this Map objects specification is only intended to describe the
required observable semantics of Map objects. It is not intended to be
a viable implementation model.
如果使用hashtable，则为hashmap（与java不完全相同），但底层实现取决于实际浏览器。
Note/FYI：google's V8 engine 中的映射建立在散列 tables 之上。
数组中的 indexOf 方法具有 O(n) 时间复杂度。
是的。在随机未排序的数组中，您不能比 O(n) 做得更好。
Maps 中的 has 方法是否具有 O(1) 时间复杂度？
通常是的。考虑到地图使用 hashtables（或类似 hashtables 的东西）。
此外，必须有：
- 下降哈希函数，它是常数时间且计算时间不长
- 没有太多冲突，因为我们将不得不遍历具有相同哈希码的多个项目。
O(1) 并不总能得到保证，O(N) 的最坏情况不太可能发生。
看看@hashmaps 和 hashtables 背后的理论：
- https://en.wikipedia.org/wiki/Hash_table
- https://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm
JS如何一步一步找到Map对象中的元素？
Map 使用规范中指定的散列table（或类似机制）。
因此，当请求一个对象时，会计算一个哈希值。
然后具体位置在一个内部table中定位。
这是关于散列 tables 的基本理论以及为什么它们通常是 O(1)。
请注意，如果有很多碰撞，性能可以向 O(N) 移动。
参见： from Hash table runtime complexity (insert, search and delete)
Hash tables are O(1) average and amortized case complexity, however it suffers from O(n) > worst case time complexity. [And I think this is where your confusion is]
那个优秀的答案列出了最坏情况的情况。
它与 indexOf
的工作方式有何不同
Hashtables 使用散列并在 table/array 中进行查找。
相反，indexOf 在 array/collection/string 中逐步搜索。参见：https://262.ecma-international.org/5.1/#sec-15.4.4.14
如果没有 O(1) 那么 Es6 Map 不是真正的 Hashmap
这是不正确的。哈希图的最坏情况性能为 O(N)。
有一篇关于 hashmap/hashtable 的优秀维基百科文章和优秀的 table：（来自：https://en.wikipedia.org/wiki/Hash_table ）
- https://en.wikipedia.org/wiki/Hash_table
- Hash table runtime complexity (insert, search and delete)
- 我的理解是
ES6 Map对象可以在Javascript中实现一个Hashmap。 正确吗？ indexOf数组中的方法具有 O(n) 时间复杂度。- Maps 中的
has方法是否具有 O(1) 时间复杂度？如果是，为什么？ JS如何一步一步找到Map对象中的元素？它与indexOf有何不同？如果没有 O(1) 那么Es6 Map不是真正的Hashmap...
我的理解是 ES6 Map 对象可以在 Javascript 中实现一个 Hashmap。对吗？
不，它的措辞方式不正确。当你说 implement 时，你让我想起了像 java 这样的界面和语言。在 Java 中，有 interface map 然后有不同的实现，如 hashmap、treemap 等
在 javascript 的情况下，您可以使用 map（或者甚至可以使用数组）来实现 hashmap（或 hashtable）算法。
请注意，在某些浏览器（如 v8）中，地图已经使用散列 table 构建，因此它已经是一个散列图。不幸的是，ECMAScript 2015 规范（参见 https://262.ecma-international.org/6.0/#sec-map-objects ）没有指定或规定确切的实现。相反，它是完全开放的，允许每个浏览器或 java 脚本引擎有一个兼容的实现。
Map object must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements in the collection. The data structures used in this Map objects specification is only intended to describe the required observable semantics of Map objects. It is not intended to be a viable implementation model.
如果使用hashtable，则为hashmap（与java不完全相同），但底层实现取决于实际浏览器。
Note/FYI：google's V8 engine 中的映射建立在散列 tables 之上。
数组中的 indexOf 方法具有 O(n) 时间复杂度。
是的。在随机未排序的数组中，您不能比 O(n) 做得更好。
Maps 中的 has 方法是否具有 O(1) 时间复杂度？
通常是的。考虑到地图使用 hashtables（或类似 hashtables 的东西）。 此外，必须有：
- 下降哈希函数，它是常数时间且计算时间不长
- 没有太多冲突，因为我们将不得不遍历具有相同哈希码的多个项目。
O(1) 并不总能得到保证，O(N) 的最坏情况不太可能发生。
看看@hashmaps 和 hashtables 背后的理论：
- https://en.wikipedia.org/wiki/Hash_table
- https://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm
JS如何一步一步找到Map对象中的元素？
Map 使用规范中指定的散列table（或类似机制）。 因此，当请求一个对象时，会计算一个哈希值。 然后具体位置在一个内部table中定位。 这是关于散列 tables 的基本理论以及为什么它们通常是 O(1)。 请注意，如果有很多碰撞，性能可以向 O(N) 移动。
参见： from Hash table runtime complexity (insert, search and delete)
Hash tables are O(1) average and amortized case complexity, however it suffers from O(n) > worst case time complexity. [And I think this is where your confusion is]
那个优秀的答案列出了最坏情况的情况。
它与 indexOf
的工作方式有何不同Hashtables 使用散列并在 table/array 中进行查找。 相反，indexOf 在 array/collection/string 中逐步搜索。参见：https://262.ecma-international.org/5.1/#sec-15.4.4.14
如果没有 O(1) 那么 Es6 Map 不是真正的 Hashmap
这是不正确的。哈希图的最坏情况性能为 O(N)。 有一篇关于 hashmap/hashtable 的优秀维基百科文章和优秀的 table：（来自：https://en.wikipedia.org/wiki/Hash_table ）
- https://en.wikipedia.org/wiki/Hash_table
- Hash table runtime complexity (insert, search and delete)