logo

Hašovanie v JavaScripte

Hašovanie je populárna technika používaná na čo najrýchlejšie ukladanie a získavanie údajov. Hlavným dôvodom používania hašovania je to, že vykonáva vkladanie, mazanie, vyhľadávanie a ďalšie operácie

Prečo používať hashovanie?

Pri hashovaní sa všetky operácie ako vkladanie, vyhľadávanie a mazanie môžu vykonávať v O(1), t.j. v konštantnom čase. Časová zložitosť najhoršieho prípadu pre hašovanie zostáva O(n), ale priemerná časová zložitosť prípadu je O(1).



HashTable

Používa sa na vytvorenie novej hašovacej tabuľky.

Syntax:

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

Základné operácie so syntaxou

Získajte:

Používa sa na vyhľadávanie kľúča v tabuľke hash a vrátenie hodnoty, ktorá je s týmto kľúčom spojená.

Syntax:

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

Vložiť:

Používa sa na vloženie nového páru kľúč – hodnota do hašovacej tabuľky.



Syntax:

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

Vyhľadávanie:

Používa sa na vyhľadávanie hodnoty.

Syntax:

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

Odstrániť:

Používa sa na odstránenie konkrétneho páru kľúč – hodnota z hašovacej tabuľky.

Syntax:

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

Komponenty hashovania v Javascripte

1. Tabuľka hash: Hašovacia tabuľka je zovšeobecnením poľa. Poskytuje funkcionalitu, v ktorej je uložená zbierka údajov takým spôsobom, že v prípade potreby je možné tieto položky neskôr ľahko nájsť. Vďaka tomu je vyhľadávanie prvku veľmi efektívne.



fronta priority java

2. Hash funkcia: Hašovacia funkcia sa používa na transformáciu daného kľúča na špecifický index slotu. používa sa na mapovanie každého možného kľúča do jedinečného indexu slotu. Ak je každý kľúč namapovaný do jedinečného indexu slotu, potom je hašovacia funkcia známa ako dokonalá hašovacia funkcia. Je veľmi ťažké vytvoriť dokonalú hašovaciu funkciu, ale našou úlohou ako programátora je vytvoriť takú hašovaciu funkciu, pomocou ktorej je počet kolízií čo najmenší.

Dobrá hašovacia funkcia by mala mať nasledujúce vlastnosti:

trie dátovú štruktúru
  • Efektívne spočítateľné.
  • Kľúče by mali byť rovnomerne rozdelené (každá pozícia stola je pre každého rovnako pravdepodobná).
  • Mali by minimalizovať kolízie.
  • Mal by mať nízky faktor zaťaženia (počet položiek v tabuľke vydelený veľkosťou tabuľky).

3. Zvládnutie kolízie: Keďže hašovacia funkcia dostane malé číslo pre veľký kľúč, existuje možnosť, že dva kľúče povedú k rovnakej hodnote. Situácia, keď sa novo vložený kľúč mapuje do už obsadeného slotu v hašovacej tabuľke, sa nazýva kolízia a musí sa riešiť pomocou nejakej techniky na riešenie kolízií. Nižšie sú uvedené spôsoby riešenia kolízií:

  • Reťazenie: Cieľom je, aby každá bunka hašovacej tabuľky ukazovala na prepojený zoznam záznamov, ktoré majú rovnakú hodnotu hašovacej funkcie. Reťazenie je jednoduché, ale vyžaduje dodatočnú pamäť mimo stola.
  • Otvoriť Adresovanie: Pri otvorenom adresovaní sú všetky prvky uložené v samotnej hašovacej tabuľke. Každý záznam tabuľky obsahuje záznam alebo NIL. Pri hľadaní prvku skúmame sloty tabuľky jeden po druhom, kým nenájdeme požadovaný prvok alebo nie je jasné, že prvok v tabuľke nie je.

Implementácia s príkladom:

Krok 1: Vytvorte triedu HashTable s počiatočnými vlastnosťami tabuľky a veľkosti.

Krok 2: Pridajte súkromnú funkciu setKey(key) na transformáciu kľúčov na indexy.

Krok 3: Pridajte funkcie insert() a get() na pridávanie a prístup k párom kľúč – hodnota z tabuľky.

Krok 4: Pridajte funkciu remove() na odstránenie kľúča z hašovacej tabuľky.

Príklad 1: Predpokladajme, že musíme uložiť 5 čísel 100, 87, 86, 12, 25 a 9 do hašovacej tabuľky. V tomto prípade vytvoríme funkciu setKey, v ktorej zoberieme hodnotu ako argument a prevedieme ju na index hašovacej tabuľky. Nižšie je uvedená implementácia.

Javascript




// HashTable Implementation> class HashTable {> >constructor() {> >this>.table =>new> Array(10);> >this>.size = 0;> >}> >// private function to convert key to index> >// _ shows that the function is private> >_setKey(key) {> >return> key % 10;> >}> >// insert value in the hashtable> >insert(value) {> >const index =>this>._setKey(value);> >this>.table[index] = value;> >this>.size++;> >}> >get(key) {> >const target =>this>._setKey(key);> >return> this>.table[target];> >}> >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'>);> >}> >delete>(key) {> >const index =>this>._setKey(key);> >if> (>this>.table[index]) {> >this>.table[index] = [];> >this>.size--;> >return> true>;> >}>else> {> >return> false>;> >}> >}> }> const hashExample =>new> HashTable();> // insert> hashExample.insert(100);> hashExample.insert(87);> hashExample.insert(86);> hashExample.insert(12);> hashExample.insert(9);> console.log(hashExample.table);>// ->zobrazuje hašovaciu tabuľku> // search> hashExample.search(87);>// found> hashExample.search(10);>// not found> // delete> hashExample.>delete>(12);> // showing table after deletion> console.log(hashExample.table);>

stiahnite si videá z youtube vlc
>

>

Výkon:

náhodne nie v jave
[ 100,  ,  12,  ,  86,  87,  ,  9 ] The value is found at index : 7 Not found [ 100,  ,  [],  ,  86,  87,  ,  9 ]>

Vo výstupe alebo ukazuje, že tabuľka má 1 alebo 3 po sebe idúce prázdne miesta/indexy.

Príklad 2: Predpokladajme, že chceme uložiť kontaktné čísla 5-člennej rodiny do hašovacej tabuľky. Na tento účel vytvoríme hašovaciu tabuľku veľkosti 10 a uložíme kontaktné údaje. Index sa nastaví pomocou súkromnej funkcie setKey, ktorá prevedie poslednú číslicu čísla kontaktu ako index hašovacej tabuľky.

Javascript




// HashTable Implementation> class HashTable {> >constructor() {> >this>.table =>new> Array(10);> >this>.size = 0;> >}> >// private function to convert key to index> >// _ shows that the function is private> >_setKey(key) {> >const lastDigit = key % 10;> >return> lastDigit;> >}> >// insert value in the hashtable> >insert(value) {> >const index =>this>._setKey(value);> >this>.table[index] = value;> >this>.size++;> >}> >get(key) {> >const target =>this>._setKey(key);> >return> this>.table[target];> >}> >search(value) {> >const index =>this>._setKey(value);> >if> (>this>.table[index] == value)> >console.log(>'The contact number is found at index : '>, index);> >else> >console.log(>'Contact Number not found'>);> >}> >delete>(key) {> >const index =>this>._setKey(key);> >if> (>this>.table[index]) {> >this>.table[index] = [];> >this>.size--;> >return> true>;> >}>else> {> >return> false>;> >}> >}> }> const hashExample =>new> HashTable();> // insert> hashExample.insert(98754525);> hashExample.insert(98747512);> hashExample.insert(94755523);> hashExample.insert(92752521);> hashExample.insert(98556529);> console.log(hashExample.table);>// ->zobrazuje hašovaciu tabuľku> // search> hashExample.search(92752521);>// found> hashExample.search(92755784);>// not found> // delete> hashExample.>delete>(92752521);> // showing table after deletion> console.log(hashExample.table);>

>

>

Výkon:

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

Vo výstupe alebo ukazuje, že tabuľka má 1 alebo 3 po sebe idúce prázdne miesta/indexy.