javascript - operador - Es6 Map and Set complex, implementación v8

map set javascript

Question

¿Es una suposición justa que en la recuperación / búsqueda de implementación v8 es O (1)?

(Sé que el estándar no garantiza eso)

Answer 1

¿Es una suposición justa que en la recuperación / búsqueda de implementación v8 es O (1)?

Si. V8 utiliza una variante de tablas hash que generalmente tienen O(1) complejidad O(1) para estas operaciones.

Para obtener más información, puede consultar https://codereview.chromium.org/220293002/ donde OrderedHashTable se implementa en función de https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables .

Answer 2

Para las personas que no quieren cavar en la madriguera del conejo demasiado profundo:

1: Podemos suponer que las buenas implementaciones de tablas hash tienen prácticamente una complejidad de tiempo O (1).
2: Aquí hay un blog publicado por el equipo de V8 que explica cómo se realizó una optimización de memoria en su implementación de tabla hash para Map , Set , WeakSet y WeakMap : Optimización de tablas hash: ocultar el código hash

Basado en 1 y 2: El conjunto y el mapa de V8 get & set & add & has una complejidad de tiempo prácticamente es O (1).