Artículo original escrito por Nathan Sebhastian
Artículo original JavaScript Hash Table – Associative Array Hashing in JS
Traducido y adaptado por Santiago Yanguas
Las tablas hash son una estructura de datos que permite crear una lista de valores emparejados, por lo tal, se puede recuperar un determinado valor usando la llave de ese valor para el índice, que se pone en la tabla de antemano.
Una tabla hash transforma una llave en un índice entero, usando una función hash, el índice decidirá dónde almacenar el par llave/valor en la memoria:
Normalmente se utiliza una tabla hash por su rapidez en las operaciones de búsqueda, inserción y eliminación:
Hash Table time complexity in Big O Notation | ||
---|---|---|
Algorithm | Average | Worst case |
Space | O(n) | O(n) |
Search | O(1) | O(n) |
Insert | O(1) | O(n) |
Delete | O(1) | O(n) |
Fuente de Wikipedia
Este tutorial te ayudará a entender la implementación de la tabla Hash en JavaScript, así como la forma de construir tu propia clase de tipo tabla Hash.
En primer lugar, veamos las clases Object
y Map
de JavaScript.
Cómo usar las tablas hash con clases objetos y Map en JavaScript
El ejemplo más común de una tabla hash en JavaScript es el tipo de datos Object
, donde se puede emparejar el valor de la propiedad del objeto, con una llave que encuentra aquella propiedad.
En el siguiente ejemplo, la llave Nathan
se empareja con el valor del número de teléfono "555-0182"
y la llave Jane
se empareja con el valor "315-0322"
:
El tipo Object
de JavaScript es un tipo especial de implementación de tabla hash por dos razones:
- Tiene propiedades añadidas por la clase
Object
. Las llaves que introduzcas pueden entrar en conflicto y sobrescribir las propiedades por defecto heredadas de la clase. - El tamaño de la tabla hash no es rastreado. Es necesario contar manualmente cuántas propiedades son definidas por el programador en lugar de ser heredadas del prototipo.
Por ejemplo, el prototipo Object
tiene el método hasOwnProperty()
que permite comprobar si una propiedad es heredada:
JavaScript no bloquea un intento de sobrescribir el método hasOwnProperty()
, lo que puede causar un error como este:
Para solucionar estas deficiencias, JavaScript creó otra implementación de la estructura de datos de la tabla hash que se llama Map
.
Al igual que Object
, Map
permite almacenar pares llave-valor dentro de la estructura de datos. Aquí hay un ejemplo de Map
en acción:
A diferencia del tipo Object
, Map
requiere que utilices los métodos set()
y get()
para definir y recuperar cualquier valor de par de llaves que quieras añadir a la estructura de datos.
Tampoco se pueden sobrescribir las propiedades heredadas de la clase Map
. Por ejemplo, el siguiente código intentó sobrescribir el valor de la propiedad size
a false
:
Como puedes ver en el código anterior, no puedes añadir una nueva entrada al objeto Map
sin utilizar el método set()
.
La estructura de datos Map
también es iterable, lo que significa que se puede hacer un bucle sobre los datos de la siguiente manera:
Ahora que has aprendido cómo JavaScript implementa las Tablas Hash en forma de estructuras de datos Object
y Map
, vamos a ver cómo puedes crear tu propia implementación de la Tabla Hash.
Cómo implementar una estructura de datos tipo tabla hash en JavaScript
Aunque JavaScript ya tiene dos implementaciones de tablas hash, escribir tu propia implementación de tablas hash es una de las preguntas más comunes en las entrevistas de JavaScript.
Puedes implementar una tabla hash en JavaScript en tres pasos:
- Crear una clase
TablaHash
con propiedades iniciales detabla
ytamano
. - Añadir una función
hash()
para transformar las llaves en índices. - Añade los métodos
set()
yget()
para añadir y recuperar pares llave/valor de la tabla.
Bien, empecemos por crear la clase TablaHash
. El código siguiente creará una tabla con un arreglo de tamaño 127
:
Todos sus pares llave/valor se almacenarán dentro de la propiedad de la tabla
.
Cómo escribir un método hash()
A continuación, hay que crear el método hash()
que aceptará un valor llave
y lo transformará en un índice.
Una forma sencilla de crear el hash sería sumar el código ASCII de los caracteres de la clave utilizando el método charCodeAt()
como sigue. Observe que el método se nombra con _
para indicar que es una función privada de la clase:
Como la clase TablaHash
solo tiene 127 espacios, esto significa que el método _hash()
debe devolver un número entre 0 y 127
.
Para asegurarse de que el valor del hash no excede el tamaño del espacio, es necesario utilizar el operador módulo como se muestra a continuación:
Ahora que tienes el método _hash()
completado, es el momento de escribir los métodos set()
y get()
.
Cómo escribir el método set()
Para establecer el par llave/valor en tu tabla hash, necesitas escribir un método set()
que acepte (llave, valor)
como parámetros:
- El método
set()
llamará al método_hash()
para obtener el valor delíndice
. - El par
[llave, valor]
se asignará a latabla
en elíndice
especificado. - Entonces, la propiedad de
tamaño
se incrementará en uno.
Ahora que el método set()
está completo, vamos a escribir el método get()
para recuperar un valor por su clave.
Cómo escribir el método get()
Para obtener un determinado valor de la tabla hash, es necesario escribir un método get()
que acepte un valor llave
como parámetro:
- El método llamará al método
_hash()
para recuperar de nuevo elíndice
de la tabla. - Devuelve el valor almacenado en la
tabla[índice]
.
De este modo, el método get()
devolverá el par llave/valor
o undefined
cuando no haya ningún par llave/valor almacenado en el índice
especificado.
Hasta aquí todo bien. Vamos a añadir otro método para eliminar el par llave/valor de la tabla hash a continuación.
Cómo escribir el método remover()
Para eliminar un par llave/valor de la tabla hash, es necesario escribir un método remover()
que acepte un valor llave
como parámetro:
- Recuperar el
índice
correcto mediante el método_hash()
. - Comprueba si la
tabla[índice]
tiene un valor verdadero y la propiedadlength
es mayor que cero. Asigna el valorundefined
alíndice
correcto y decrementa la propiedad detamaño
en uno si es así. - Si no, simplemente devuelve
false
Con esto, ya tienes un método remover()
que funciona. Veamos si la clase Tabla Hash
funciona correctamente.
Cómo testear la implementación de la tabla hash
Es hora de probar la implementación de la Tabla hash. Aquí está el código completo para la implementación de la Tabla hash de nuevo:
Para probar la clase TablaHash
, voy a crear una nueva instancia de la clase
y establecer algunos pares llave/valor como se muestra a continuación. Los pares llave/valor de abajo son solo valores numéricos arbitrarios emparejados con nombres de países sin ningún significado especial:
A continuación, vamos a intentar recuperarlos mediante el método get()
:
Por último, intentemos eliminar uno de estos valores con el método remover()
:
Muy bien, todos los métodos funcionan como se esperaba. Intentemos otra inserción con una nueva instancia de TablaHash
y recuperemos esos valores:
¡Uy! Parece que nos hemos metido en un problema. ?
Cómo manejar la colisión en los índices
A veces, la función hash de una tabla hash puede devolver el mismo número de índice
. En el caso de prueba anterior, la cadena "España"
y "ǻ"
devuelven ambas el mismo valor hash
porque el número 507
es la suma del código ASCII de ambas.
El mismo valor hash
hará que el índice colisione, sobrescribiendo la entrada anterior con la nueva.
En este momento, los datos almacenados en nuestra implementación de la tabla hash tienen el siguiente aspecto:
Para manejar la colisión del número de índice
, es necesario almacenar el par llave/valor en un segundo arreglo para que el resultado final sea el siguiente:
Para crear el segundo arreglo, hay que actualizar el método set()
para que lo haga:
- Busque en la
tabla[índice]
y realice un bucle sobre los valores del arreglo. - Si la llave en uno de los arreglos es igual a la
llave
pasada al método, reemplaza el valor en el índice1
y detiene cualquier ejecución posterior con la sentenciareturn
. - Si no se encuentra ninguna
llave
que coincida, añade un nuevo arreglo de llave-valor al segundo arreglo. - Si no, inicializa un nuevo arreglo y coloca el par llave/valor en el
índice
especificado. - Cada vez que se llama a un método
push()
, se incrementa la propiedadtamaño
en uno.
El código completo del método set()
será el siguiente:
A continuación, actualizamos el método get()
para que también compruebe el arreglo de segundo nivel con un bucle for
y devuelva el par llave/valor correcto:
Por último, hay que actualizar el método remover()
para que haga un bucle sobre el array de segundo nivel y elimine el array con el valor de la llave
correcta utilizando el método splice()
:
Con esto, tu clase TablaHash
podrá evitar cualquier colisión de números de índice y almacenar el par llave/valor dentro del arreglo de segundo nivel.
Como extra, vamos a añadir un método mostrar
que mostrará todos los pares llave/valor almacenados en la tabla hash. Solo tienes que utilizar el método forEach()
para iterar sobre la tabla y map()
los valores a una cadena como se muestra a continuación:
Aquí está el código completo de la clase TablaHash
de nuevo con el caso previsto de colisiones aplicada para su referencia:
Puedes probar la implementación creando una nueva instancia de TablaHash
y haciendo algunas inserciones y eliminaciones:
Ahora no hay colisión dentro de la instancia de TablaHash
. ¡Buen trabajo!
Conclusión
En este tutorial, has aprendido ¿qué es una tabla hash?... y cómo JavaScript la utiliza para crear la estructura de datos Object
y Map
.
También has aprendido cómo implementar tu propia clase TablaHash
y cómo evitar que los índices clave de la tabla hash colisionen utilizando la técnica de encadenamiento.
Utilizando una estructura de datos tabla hash, podrás crear un arreglo asociativo con operaciones rápidas de búsqueda, inserción y borrado ? .
Gracias por leer este tutorial
Si quieres aprender más sobre JavaScript, puedes visitar mi sitio en sebhastian.com, donde he publicado más de 100 tutoriales sobre programación con JavaScript, todos con explicaciones fáciles de entender y ejemplos de código.
Los tutoriales incluyen manipulación de cadenas, manipulación de fechas, métodos de arreglos y objetos, soluciones de algoritmos de JavaScript, y muchos más.