Hashing es una técnica popular que se utiliza para almacenar y recuperar datos lo más rápido posible. La razón principal detrás del uso de hash es que realiza inserción, eliminación, búsqueda y otras operaciones.

¿Por qué utilizar Hashing?

En hash, todas las operaciones como insertar, buscar y eliminar se pueden realizar en O(1), es decir, en tiempo constante. La complejidad temporal del peor caso para el hash sigue siendo O(n), pero la complejidad temporal promedio del caso es O(1).

Tabla de picadillo

Se utiliza para crear una nueva tabla hash.

Sintaxis:

// function to delete a key from the hashtable  delete (key) {  const index = this._setKey(key);  if (this.table[index]) {  this.table[index] = [];  this.size--;  return true;  } else {  return false;  } } 

Operaciones básicas con sintaxis

Conseguir:

Se utiliza para buscar una clave dentro de la tabla hash y devolver el valor asociado con esa clave.

Sintaxis:

// function inside hashtable class to  // access a value using its key get(key) {  const target = this._setKey(key);  return this.table[target]; } 

Insertar:

Se utiliza para insertar un nuevo par clave-valor dentro de la tabla hash.

Sintaxis:

// function to insert a value in the  // hash table using setKey function insert(value) {  const index = this._setKey(value);  this.table[index] = value;  this.size++; } 

Buscar:

Se utiliza para buscar un valor.

Sintaxis:

// search a value (by getting its  // key using setKey function) search(value){  const index = this._setKey(value);  if(this.table[index]==value)  console.log('The value is found at index : ',index);  else  console.log('Not found'); } 

Borrar:

Se utiliza para eliminar un par clave-valor particular de la tabla hash.

Sintaxis:

// function to delete a key from the hashtable  delete (key) {  const index = this._setKey(key);  if (this.table[index]) {  this.table[index] = [];  this.size--;  return true;  } else {  return false;  } } 

Componentes de Hashing en Javascript

1. Tabla hash: Una tabla hash es una generalización de la matriz. Proporciona la funcionalidad en la que se almacena una colección de datos de tal manera que sea fácil encontrar esos elementos más adelante si es necesario. Esto hace que la búsqueda de un elemento sea muy eficiente.

2. Función hash: Se utiliza una función hash para transformar una clave determinada en un índice de ranura específico. se utiliza para asignar todas y cada una de las claves posibles en un índice de ranura único. Si cada clave se asigna a un índice de ranura único, entonces la función hash se conoce como función hash perfecta. Es muy difícil crear una función hash perfecta, pero nuestro trabajo como programadores es crear dicha función hash con la ayuda de la cual el número de colisiones sea el menor posible.

Una buena función hash debería tener las siguientes propiedades:

• Computable eficientemente.
• Debe distribuir uniformemente las claves (cada posición de la tabla es igualmente probable para cada una).
• Debe minimizar las colisiones.
• Debe tener un factor de carga bajo (el número de elementos de la tabla dividido por el tamaño de la mesa).

3. Manejo de colisiones: Dado que una función hash nos proporciona un número pequeño para una clave grande, existe la posibilidad de que dos claves den como resultado el mismo valor. La situación en la que una clave recién insertada se asigna a una ranura ya ocupada en la tabla hash se denomina colisión y debe manejarse mediante alguna técnica de manejo de colisiones. Las siguientes son las formas de manejar las colisiones:

• Encadenamiento: La idea es hacer que cada celda de la tabla hash apunte a una lista vinculada de registros que tienen el mismo valor de función hash. El encadenamiento es simple pero requiere memoria adicional fuera de la tabla.
• Direccionamiento abierto: En el direccionamiento abierto, todos los elementos se almacenan en la propia tabla hash. Cada entrada de la tabla contiene un registro o NIL. Al buscar un elemento, examinamos las ranuras de la tabla una por una hasta encontrar el elemento deseado o queda claro que el elemento no está en la tabla.

Implementación con ejemplo:

Paso 1: Cree una clase HashTable con propiedades iniciales de tabla y tamaño.

Paso 2: Agregue una función privada setKey(key) para transformar claves en índices.

Paso 3: Agregue las funciones insert() y get() para agregar y acceder a pares clave-valor desde la tabla.

Etapa 4: Agregue una función remove() para eliminar una clave de la tabla hash.

Ejemplo 1: Supongamos que tenemos que almacenar 5 números 100,87,86,12,25 y 9 en una tabla hash. En este caso, crearemos una función setKey en la que tomaremos el valor como argumento y lo convertiremos a un índice de la tabla hash. A continuación se muestra la implementación.

JavaScript

Producción:

[ 100,  ,  12,  ,  86,  87,  ,  9 ] The value is found at index : 7 Not found [ 100,  ,  [],  ,  86,  87,  ,  9 ] 

En la salida o muestra que la tabla tiene 1 o 3 espacios/índices vacíos consecutivos.

Ejemplo 2: Supongamos que queremos almacenar los números de contacto de una familia de 5 miembros en una tabla hash. Para ello, crearemos una tabla hash de tamaño 10 y almacenaremos los datos de contacto. El índice se establecerá utilizando la función privada setKey que convertirá el último dígito del número de contacto como índice de la tabla hash.

JavaScript

Producción:

[ ,  92752521,  98747512,  94755523,  ,  98754525,  ,  98556529 ] The contact number is found at index : 1 Contact Number not found [ ,  [],  98747512,  94755523,  ,  98754525,  ,  98556529 ] 

En la salida o muestra que la tabla tiene 1 o 3 espacios/índices vacíos consecutivos.