El hashing és una tècnica popular que s'utilitza per emmagatzemar i recuperar dades el més ràpid possible. El motiu principal de l'ús de la funció hash és que realitza operacions d'inserció, supressió, cerca i altres

Per què utilitzar Hashing?

En hash, totes les operacions com inserir, cercar i suprimir es poden realitzar en O(1), és a dir, en temps constant. La complexitat de temps del pitjor cas per a l'hashing continua sent O(n) però la complexitat mitjana del temps del cas és O(1).

HashTable

S'utilitza per crear una taula hash nova.

Sintaxi:

// 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;  } }>

Operacions bàsiques amb sintaxi

Aconseguir:

S'utilitza per cercar una clau dins de la taula hash i retornar el valor associat amb aquesta clau.

Sintaxi:

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

Insereix:

S'utilitza per inserir un parell clau-valor nou dins de la taula hash.

Sintaxi:

// 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++; }>

Cerca:

S'utilitza per buscar un valor.

Sintaxi:

// 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'); }>

Suprimeix:

S'utilitza per suprimir un parell clau-valor concret de la taula hash.

Sintaxi:

// 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;  } }>

Components de hashing en Javascript

1. Taula hash: Una taula hash és una generalització de la matriu. Ofereix la funcionalitat en què s'emmagatzema una col·lecció de dades de manera que sigui fàcil trobar aquests elements més endavant si cal. Això fa que la recerca d'un element sigui molt eficient.

fent executable un script de shell

2. Funció hash: Una funció hash s'utilitza per transformar una clau determinada en un índex de ranura específic. s'utilitza per assignar totes i cadascuna de les claus possibles en un índex de ranura únic. Si cada clau està assignada a un índex de ranura únic, la funció hash es coneix com a funció hash perfecta. És molt difícil crear una funció hash perfecta, però la nostra feina com a programador és crear aquesta funció hash amb l'ajuda de la qual el nombre de col·lisions sigui el mínim possible.

Una bona funció hash hauria de tenir les propietats següents:

• Eficaçment computable.
• S'han de distribuir uniformement les claus (cada posició de la taula és igual de probable per a cadascuna).
• S'han de minimitzar les col·lisions.
• Hauria de tenir un factor de càrrega baix (el nombre d'elements de la taula dividit per la mida de la taula).

3. Gestió de col·lisions: Com que una funció hash ens obté un nombre petit per a una clau gran, hi ha la possibilitat que dues claus donin el mateix valor. La situació en què una clau recentment inserida s'assigna a una ranura ja ocupada a la taula hash s'anomena col·lisió i s'ha de gestionar mitjançant alguna tècnica de gestió de col·lisions. A continuació es mostren les maneres de gestionar les col·lisions:

• Encadenat: La idea és fer que cada cel·la de la taula hash apunti a una llista enllaçada de registres que tinguin el mateix valor de funció hash. L'encadenament és senzill, però requereix memòria addicional fora de la taula.
• Adreça oberta: En l'adreçament obert, tots els elements s'emmagatzemen a la mateixa taula hash. Cada entrada de la taula conté un registre o NIL. Quan busquem un element, examinem les ranures de la taula una per una fins que es troba l'element desitjat o queda clar que l'element no és a la taula.

Implementació amb exemple:

Pas 1: Creeu una classe HashTable amb propietats inicials de taula i mida.

Pas 2: Afegiu una funció privada setKey(key) per transformar les claus en índexs.

Pas 3: Afegiu les funcions insert() i get() per afegir i accedir a parells clau-valor des de la taula.

seleni

Pas 4: Afegiu una funció remove() per eliminar una clau de la taula hash.

Exemple 1: Suposem que hem d'emmagatzemar 5 números 100,87,86,12,25 i 9 en una taula hash. En aquest cas, crearem una funció setKey en la qual agafarem el valor com a argument i el convertirem en un índex de la taula hash. A continuació es mostra la implementació.

Javascript

cadenes d'ordenació java

>

>

Sortida:

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

A la sortida o mostra que la taula té 1 o 3 espais/índexs buits consecutius.

Exemple 2: Suposem que volem emmagatzemar els números de contacte d'una família de 5 membres en una taula hash. Per a això, crearem una taula hash de mida 10 i emmagatzemarem les dades de contacte. L'índex s'establirà mitjançant la funció privada setKey que convertirà l'últim dígit del número de contacte com a índex de la taula hash.

gestor de tasques linux

Javascript

bous vs bou

>

>

Sortida:

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

A la sortida o mostra que la taula té 1 o 3 espais/índexs buits consecutius.