Hašování je oblíbená technika používaná pro co nejrychlejší ukládání a získávání dat. Hlavním důvodem používání hašování je to, že provádí vkládání, mazání, vyhledávání a další operace

Proč používat hashování?

V hashování lze všechny operace jako vkládání, vyhledávání a mazání provádět v O(1), tj. konstantním čase. Časová složitost nejhoršího případu pro hašování zůstává O(n), ale průměrná časová složitost případu je O(1).

HashTable

Používá se k vytvoření nové hash tabulky.

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í operace se syntaxí

Dostat:

Používá se k vyhledání klíče v tabulce hash a vrácení hodnoty, která je s tímto klíčem spojena.

Syntax:

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

Vložit:

Používá se k vložení nového páru klíč–hodnota do hashovací tabulky.

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

Vyhledávání:

Slouží k vyhledání 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'); } 

Vymazat:

Používá se k odstranění konkrétního páru klíč–hodnota z hašovací tabulky.

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 hašování v Javascriptu

1. Tabulka hash: Hašovací tabulka je zobecněním pole. Poskytuje funkcionalitu, ve které je kolekce dat uložena takovým způsobem, že je v případě potřeby snadné později tyto položky najít. Díky tomu je vyhledávání prvku velmi efektivní.

2. Hashovací funkce: K transformaci daného klíče na konkrétní index slotu se používá hašovací funkce. používá se k mapování každého možného klíče do jedinečného indexu slotu. Pokud je každý klíč namapován do jedinečného indexu slotu, pak je hašovací funkce známá jako perfektní hašovací funkce. Je velmi obtížné vytvořit dokonalou hashovací funkci, ale naším úkolem jako programátora je vytvořit takovou hashovací funkci, s jejíž pomocí je co nejmenší počet kolizí.

Dobrá hashovací funkce by měla mít následující vlastnosti:

• Efektivně vyčíslitelné.
• Klíče by měly být rovnoměrně rozmístěny (každá pozice u stolu je pro každého stejně pravděpodobná).
• Měl by minimalizovat kolize.
• Měl by mít nízký faktor zatížení (počet položek v tabulce dělený velikostí tabulky).

3. Zvládání kolize: Protože hashovací funkce dostane malé číslo pro velký klíč, existuje možnost, že dva klíče vedou ke stejné hodnotě. Situace, kdy se nově vložený klíč mapuje do již obsazeného slotu v hašovací tabulce, se nazývá kolize a musí být řešena pomocí nějaké techniky zpracování kolize. Zde jsou způsoby, jak řešit kolize:

• řetězení: Cílem je, aby každá buňka hashovací tabulky ukazovala na propojený seznam záznamů, které mají stejnou hodnotu hashovací funkce. Řetězení je jednoduché, ale vyžaduje další paměť mimo stůl.
• Otevřít adresu: Při otevřeném adresování jsou všechny prvky uloženy v samotné hashovací tabulce. Každá položka tabulky obsahuje buď záznam, nebo NIL. Při hledání prvku zkoumáme sloty tabulky jeden po druhém, dokud není nalezen požadovaný prvek nebo je jasné, že prvek v tabulce není.

Implementace s příkladem:

Krok 1: Vytvořte třídu HashTable s počátečními vlastnostmi tabulky a velikosti.

Krok 2: Přidejte soukromou funkci setKey(key) pro transformaci klíčů na indexy.

Krok 3: Přidejte funkce insert() a get() pro přidávání a přístup k párům klíč–hodnota z tabulky.

Krok 4: Přidejte funkci remove() pro odstranění klíče z hashovací tabulky.

Příklad 1: Předpokládejme, že musíme uložit 5 čísel 100,87,86,12,25 a 9 do hashtable. V tomto případě vytvoříme funkci setKey, ve které vezmeme hodnotu jako argument a převedeme ji na index hashovací tabulky. Níže je implementace.

Javascript

Výstup:

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

Ve výstupu nebo ukazuje, že tabulka má 1 nebo 3 po sobě jdoucí prázdné prostory/indexy.

Příklad 2: Předpokládejme, že chceme uložit kontaktní čísla 5členné rodiny do hashovací tabulky. Za tímto účelem vytvoříme hashovací tabulku o velikosti 10 a uložíme kontaktní údaje. Index bude nastaven pomocí soukromé funkce setKey, která převede poslední číslici čísla kontaktu jako index hashovací tabulky.

Javascript

Výstup:

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

Ve výstupu nebo ukazuje, že tabulka má 1 nebo 3 po sobě jdoucí prázdné prostory/indexy.