El estándar ECMAScript 2015 , conocida como la ES6, hay muchas nuevas JavaScript-colecciones tales como
Map, Set, WeakMapy WeakSet. Parecen ser una gran adición a las capacidades estándar de JavaScript. Se utilizan ampliamente en varias bibliotecas, en aplicaciones, en el núcleo de Node.js. Hoy hablaremos sobre la colección Map, trataremos de averiguar los detalles de su implementación en V8 y sacaremos algunas conclusiones prácticas basadas en el conocimiento adquirido.
El estándar ES6 no proporciona una indicación clara del enfoque que se debe tomar para implementar el soporte de la estructura de datos
Map. Solo da algunas pistas sobre posibles formas de implementarlo. También contiene información sobre lo esperado deMapMétricas de rendimiento:
el objeto Map debe implementarse mediante tablas hash u otros mecanismos que, en promedio, brinden acceso sublineal a los elementos de la colección. Las estructuras de datos utilizadas en la especificación del mapa solo están destinadas a describir la semántica observable de los objetos del mapa. No fueron concebidos como un modelo real para la implementación de estos objetos.
Como puede ver, la especificación da mucha libertad a quienes crean motores JS. Pero al mismo tiempo, no existen pautas específicas con respecto al enfoque específico utilizado para la implementación
Map, su rendimiento y las características de consumo de memoria. Si las estructuras de datos se utilizan en una parte crítica de su aplicaciónMapy si escribe grandes cantidades de información en dichas estructuras de datos, entonces un conocimiento sólido de la implementación Mapserá sin duda de gran beneficio para usted.
Tengo experiencia en el desarrollo de Java, estoy acostumbrado a las colecciones de Java, donde puede elegir entre diferentes implementaciones de la interfaz
Mape incluso ajustar la implementación seleccionada si la clase correspondiente lo admite. Además, en Java, siempre puede leer el código fuente abierto de cualquier clase de la biblioteca estándar y familiarizarse con su implementación (por supuesto, puede cambiar en nuevas versiones, pero solo en la dirección de aumentar la eficiencia). Por eso no pude resistirme a estudiar la forma en que funcionan los objetos Mapen V8.
Antes de comenzar, quiero señalar que lo que se discutirá a continuación se refiere al motor V8 8.4, que está integrado en la nueva versión de desarrollo de Node.js (más precisamente, estamos hablando de la confirmación 238104c). No necesita esperar nada fuera de la especificación.
El algoritmo detrás de la implementación del mapa
En primer lugar, diré que las estructuras de datos se
Mapbasan en tablas hash. A continuación, supongo que sabe cómo funcionan las tablas hash. Si no está familiarizado con las tablas hash, primero debe leer sobre ellas ( aquí , por ejemplo) y solo luego continuar leyendo este artículo.
Si tiene una experiencia significativa con los objetos
Map, es posible que ya haya notado una contradicción. Es decir, no se garantiza que las tablas hash devuelvan elementos en un orden constante al iterar sobre ellos. Y la especificación ES6 establece que para implementar un objeto, Mapes necesario, al atravesarlo, devolver los elementos en el orden en que se le agregaron. Como resultado, el algoritmo "clásico" para la implementaciónMapNo encaja. Pero existe la sensación de que, con algunos cambios, todavía se puede utilizar.
V8 utiliza las llamadas " tablas hash deterministas " propuestas por Tyler Close. El siguiente pseudocódigo, basado en TypeScript, demuestra las estructuras de datos básicas que se utilizan para implementar tales tablas hash:
interface Entry {
key: any;
value: any;
chain: number;
}
interface CloseTable {
hashTable: number[];
dataTable: Entry[];
nextSlot: number;
size: number;
}
Aquí la interfaz
CloseTablerepresenta una tabla hash. Contiene una matriz hashTablecuyo tamaño es equivalente al número de contenedores de hash. El elemento de matriz con el índice Ncorresponde al N-ésimo contenedor de hash y almacena el índice de su elemento principal que está en la matriz dataTable. Y esta matriz contiene los registros de la tabla en el orden en que se insertaron en ella. Las entradas son presentadas por la interfaz Entry. Finalmente, cada entrada tiene una propiedad chainque apunta a la siguiente entrada en la cadena de entradas del contenedor de hash (o, más exactamente, en una lista enlazada individualmente).
Cada vez que se inserta un nuevo registro en la tabla, se almacena en el elemento de matriz
dataTablecon índicenextSlot... Este proceso también requiere actualizar los datos en el contenedor hash correspondiente, lo que hace que el registro insertado se convierta en el nuevo último elemento de la lista enlazada individualmente.
Cuando se elimina un registro de una tabla, se elimina
dataTable(por ejemplo, escribiendo en sus propiedades keyy valuevalores undefined). Luego, la entrada que la precede y la siguiente se vinculan directamente entre sí. Como habrá notado, esto significa que todas las entradas eliminadas continúan ocupando espacio en el dataTable.
Ahora, la última pieza de nuestro rompecabezas. Cuando una tabla está llena de registros (tanto actuales como eliminados), se debe volver a procesar (reconstruir) con un aumento en su tamaño. El tamaño de la mesa se puede cambiar hacia abajo.
Con este enfoque, atravesar la estructura de datos
Mapequivale a atravesar una matriz dataTable. Esto asegura que se conserva el orden en el que se insertan los registros en la tabla y que se cumple el estándar. Con esto en mente, esperaría que la mayoría (si no todos) de los motores JS usen tablas hash deterministas como uno de los mecanismos de implementación subyacentes Map.
Investigación práctica del algoritmo
Echemos un vistazo a algunos ejemplos para ayudarnos a explorar el algoritmo en la práctica. Supongamos que tenemos
CloseTable2 contenedores hash ( hastTable.length), cuya capacidad total es de 4 elementos ( dataTable.length). Esta tabla se llena con el siguiente contenido:
// , -,
// , , function hashCode(n) { return n; }
table.set(0, 'a'); // => - 0 (0 % 2)
table.set(1, 'b'); // => - 1 (1 % 2)
table.set(2, 'c'); // => - 0 (2 % 2)
La representación interna de la tabla obtenida en este ejemplo podría verse así:
const tableInternals = {
hashTable: [0, 1],
dataTable: [
{
key: 0,
value: 'a',
chain: 2 // <2, 'c'>
},
{
key: 1,
value: 'b',
chain: -1 // -1
},
{
key: 2,
value: 'c',
chain: -1
},
//
],
nextSlot: 3, //
size: 3
}
Si elimina un registro con el método
table.delete(0), la tabla hash tendrá el siguiente aspecto:
const tableInternals = {
hashTable: [0, 1],
dataTable: [
{
key: undefined, //
value: undefined,
chain: 2
},
{
key: 1,
value: 'b',
chain: -1
},
{
key: 2,
value: 'c',
chain: -1
},
//
],
nextSlot: 3,
size: 2 //
}
Si agregamos un par de registros más a la tabla, será necesario aplicar un hash. Discutiremos este proceso en detalle a continuación.
Se puede aplicar el mismo enfoque al implementar estructuras de datos
Set. La única diferencia es que estas estructuras de datos no necesitan una propiedad value.
Ahora que hemos descubierto qué hay detrás de los objetos
Mapen V8, estamos listos para seguir adelante.
Detalles de implementacion
La implementación de la estructura de datos
Mapen V8 se escribe en C ++, después de lo cual se da acceso al código JS a los mecanismos correspondientes. La mayor parte del código relacionado con Mapestá en las clases OrderedHashTabley OrderedHashMap. Ya sabemos cómo funcionan estas clases. Si desea echar un vistazo a su código usted mismo, puede encontrarlo aquí , aquí y aquí .
Dado que estamos especialmente interesados en los detalles prácticos de la implementación
Mapen V8, primero debemos comprender cómo se establece la capacidad de la mesa.
Capacidad de la mesa
En V8, la capacidad de la tabla hash (estructura de datos
Map) es siempre una potencia de dos. Si hablamos de la tasa de utilización de los contenedores de hash, siempre está representado por el número 2. Es decir, la capacidad máxima de la tabla 2 * number_of_bucketses 2 veces el número de contenedores de hash. Al crear un objeto vacío, Maphay 2 contenedores hash en su tabla hash interna. Como resultado, la capacidad de dicho objeto es igual a 4 registros.
Existe una limitación en la capacidad máxima de objetos
Map. En sistemas de 64 bits, esto será aproximadamente 16,7 millones de registros. Esta limitación se debe a las peculiaridades de representar estructuras de datos Mapen el montón. Hablaremos de ello más tarde.
Y finalmente, el factor de aumentar o disminuir la tabla también está siempre representado por la multiplicación de algún número por 2. Esto significa que después de agregar 4 registros a la tabla descrita, la siguiente operación de inserción causará la necesidad de volver a lavar la tabla, durante la cual el tamaño de la tabla aumentará en dos. veces. Con una disminución en el tamaño de la mesa, en consecuencia, puede volverse 2 veces más pequeña.
Para asegurarme de que lo que vi en el código fuente funciona exactamente como lo entendí, modifiqué el código del motor V8 integrado en Node.js, de modo que una
Mapnueva propiedad que bucketscontenga información sobre el número de contenedores de hash. Puede encontrar los resultados de esta modificación aquí... En este ensamblado especial de Node.js, se puede ejecutar el siguiente script:
const map = new Map();
let prevBuckets = 0;
for (let i = 0; i < 100; i++) {
if (prevBuckets !== map.buckets) {
console.log(`size: ${i}, buckets: ${map.buckets}, capacity: ${map.buckets * 2}`);
prevBuckets = map.buckets;
}
map.set({}, {});
}
Este script simplemente inserta
Map100 registros en la estructura de datos . Esto es lo que se muestra en la consola después de iniciarla:
$ ./node /home/puzpuzpuz/map-grow-capacity.js
size: 0, buckets: 2, capacity: 4
size: 5, buckets: 4, capacity: 8
size: 9, buckets: 8, capacity: 16
size: 17, buckets: 16, capacity: 32
size: 33, buckets: 32, capacity: 64
size: 65, buckets: 64, capacity: 128
Como puede ver, cuando la mesa está llena, con cada cambio de tamaño, aumenta 2 veces. Ahora intentemos reducir la tabla quitando elementos de ella:
const map = new Map();
for (let i = 0; i < 100; i++) {
map.set(i, i);
}
console.log(`initial size: ${map.size}, buckets: ${map.buckets}, capacity: ${map.buckets * 2}`);
let prevBuckets = 0;
for (let i = 0; i < 100; i++) {
map.delete(i);
if (prevBuckets !== map.buckets) {
console.log(`size: ${map.size}, buckets: ${map.buckets}, capacity: ${map.buckets * 2}`);
prevBuckets = map.buckets;
}
}
Esto es lo que generará este script:
$ ./node /home/puzpuzpuz/map-shrink-capacity.js
initial size: 100, buckets: 64, capacity: 128
size: 99, buckets: 64, capacity: 128
size: 31, buckets: 32, capacity: 64
size: 15, buckets: 16, capacity: 32
size: 7, buckets: 8, capacity: 16
size: 3, buckets: 4, capacity: 8
size: 1, buckets: 2, capacity: 4
Aquí, nuevamente, puedes ver que el tamaño de la tabla se reduce cada vez que tiene menos
number_of_buckets / 2elementos.
Función hash
Hasta ahora, no hemos abordado la cuestión de cómo V8 calcula los códigos hash para las claves almacenadas en los objetos
Map. Y esta es una pregunta importante.
Para los valores que se pueden clasificar como numéricos, se utiliza alguna función hash conocida con una baja probabilidad de colisión.
Para los valores de cadena, se calcula un código hash en función de los propios valores. Después de eso, este código se almacena en caché en el encabezado interno.
Y finalmente, para los objetos, los hashes se calculan en función de un número aleatorio, y lo que sucede se almacena en caché en el encabezado interno.
Complejidad temporal de las operaciones con objetos Map
La mayoría de las operaciones realizadas en estructuras de datos
Map, como seto delete, requieren buscar a través de estas estructuras de datos. Como en el caso de las tablas hash "clásicas", la complejidad temporal de la búsqueda en nuestro caso es O(1).
Imagínese el peor de los casos, cuando la mesa está llena, es decir, ocupada
Ndesde los Nasientos. En este caso, todos los registros pertenecen a un solo contenedor hash y el registro requerido se encuentra al final de la cadena de registros. En un escenario como este, deberá seguir los pasos necesarios para encontrar esta entrada N.
Por otro lado, en el mejor de los casos, cuando la tabla está llena y solo hay 2 registros en cada contenedor de hash, encontrar un registro requerirá solo 2 pasos.
Algunas operaciones en tablas hash son muy rápidas, pero este no es el caso de las operaciones hash. La complejidad temporal de la operación hash es
O(N). Requiere que se asigne una nueva tabla hash en el montón. Además, el refrito se realiza según sea necesario, como parte de las operaciones para insertar o eliminar elementos de la tabla. Por tanto, por ejemplo, la llamada map.set()puede resultar mucho más "cara" de lo esperado. Afortunadamente, la operación hash rara vez se realiza.
Consumo de memoria
Por supuesto, la tabla hash subyacente
Mapdebe almacenarse en el montón de alguna manera. Se almacena en lo que se denomina "almacenamiento auxiliar". Y aquí tenemos otro dato interesante. La tabla completa (y, por lo tanto, todo lo que se coloca Map) se almacena en una única matriz de longitud fija. La estructura de esta matriz se muestra en la siguiente figura.
Matriz utilizada para almacenar estructuras de datos de mapas en la memoria Las
partes individuales de la matriz tienen los siguientes propósitos:
- Encabezado: contiene información general, como la cantidad de contenedores de hash o la cantidad de elementos eliminados
Map. - Detalles del contenedor de hash: aquí es donde almacenamos los datos sobre los contenedores que corresponden a la matriz
hashTablede nuestro ejemplo. - Entradas de la tabla hash: aquí es donde se almacenan los datos correspondientes a la matriz
dataTable. Es decir, contiene información sobre las entradas de la tabla hash. Cada registro ocupa tres celdas en la matriz. Uno almacena la clave, el segundo almacena el valor y el tercero almacena el "puntero" al siguiente registro de la cadena.
Si hablamos del tamaño de la matriz, entonces se puede estimar aproximadamente como
N * 3,5. Aquí Nestá la capacidad de la mesa. Para entender lo que esto significa en términos de consumo de memoria, imaginemos que tenemos un sistema de 64 bits y la función de compresión de puntero del V8 está desactivada . En este caso, se necesitan 8 bytes para almacenar cada elemento de la matriz. Como resultado Map, se necesitan 29 MB de memoria dinámica para almacenar una estructura de datos que contiene aproximadamente 1 millón de registros.
Salir
En este artículo, cubrimos muchas cosas relacionadas con la estructura de datos
Mapen JavaScript. Resumamos:
- V8
Maputiliza tablas hash deterministas para la implementación . Es muy probable que esta estructura de datos también se implemente en otros motores JS. - Los mecanismos que soportan el trabajo
Mapse implementan en C ++, luego de lo cual se presentan como una API accesible desde JavaScript. - Si hablamos de la complejidad temporal de las operaciones realizadas con objetos
Map, entonces ellas, así como cuando se trabaja con tablas hash "clásicas", tienen complejidadO(1). En este caso, la complejidad temporal de la operación hash esO(N). - 64-
Map1 29 , . - , ,
Set.
Map JavaScript-?
