Čo je tabuľka hash?

Hash tabuľka je definovaná ako dátová štruktúra používaná na rýchle vkladanie, vyhľadávanie a odstraňovanie párov kľúč – hodnota. Funguje na hašovací koncept , kde je každý kľúč preložený pomocou hašovacej funkcie na odlišný index v poli. Index funguje ako miesto uloženia pre zodpovedajúcu hodnotu. Jednoducho povedané, mapuje kľúče s hodnotou.

Čo je faktor zaťaženia?

Faktor zaťaženia hašovacej tabuľky je určený počtom prvkov, ktoré sa tam nachádzajú v pomere k veľkosti tabuľky. Tabuľka môže byť neprehľadná a môže mať dlhšie časy vyhľadávania a kolízie, ak je faktor zaťaženia vysoký. Ideálny faktor zaťaženia sa dá udržať pomocou dobrej hašovacej funkcie a správnej zmeny veľkosti tabuľky.

Čo je hashovacia funkcia?

Funkcia, ktorá prekladá kľúče na indexy poľa, je známa ako hašovacia funkcia. Kľúče by mali byť rovnomerne rozmiestnené po poli prostredníctvom slušnej hašovacej funkcie, aby sa znížili kolízie a zabezpečili sa rýchle rýchlosti vyhľadávania.

• Predpoklad celočíselného vesmíru: Predpokladá sa, že kľúče sú celé čísla v určitom rozsahu podľa predpokladu celočíselného vesmíru. To umožňuje použitie základných hašovacích operácií, ako je delenie alebo násobenie.
• Hašovanie podľa delenia: Táto jednoduchá hašovacia technika využíva zostávajúcu hodnotu kľúča po jej vydelení veľkosťou poľa ako index. Keď je veľkosť poľa prvočíslo a kľúče sú rovnomerne rozmiestnené, funguje dobre.
• Hašovanie násobením: Táto priama hašovacia operácia vynásobí kľúč konštantou medzi 0 a 1 predtým, ako vezme zlomkovú časť výsledku. Potom sa index určí vynásobením zlomkovej zložky veľkosťou poľa. Funguje efektívne aj vtedy, keď sú tlačidlá rovnomerne rozmiestnené.

Výber hašovacej funkcie :

Výber slušnej hašovacej funkcie je založený na vlastnostiach kľúčov a zamýšľanej funkčnosti hašovacej tabuľky. Používanie funkcie, ktorá rovnomerne rozdeľuje kľúče a znižuje kolízie, je kľúčové.

Kritériá, na základe ktorých sa vyberá hašovacia funkcia:

• Aby sa zabezpečilo, že počet kolízií bude minimálny, dobrá hašovacia funkcia by mala distribuovať kľúče v celej hašovacej tabuľke jednotným spôsobom. To znamená, že pre všetky párovania kľúčov by mala byť pravdepodobnosť, že sa dva kľúče hašujú na rovnakú pozíciu v tabuľke, pomerne konštantná.
• Na umožnenie rýchleho hashovania a získavania kľúčov by funkcia hash mala byť výpočtovo efektívna.
• Malo by byť náročné odvodiť kľúč z jeho hash hodnoty. Výsledkom je, že pokusy uhádnuť kľúč pomocou hodnoty hash majú menšiu šancu na úspech.
• Hašovacia funkcia by mala byť dostatočne flexibilná, aby sa prispôsobila zmenám hašovaných údajov. Napríklad, hašovacia funkcia musí pokračovať v správnom fungovaní, ak sa hashované kľúče zmenia vo veľkosti alebo formáte.

Techniky riešenia kolízie :

Ku kolíziám dochádza, keď dva alebo viac kľúčov ukazuje na rovnaký index poľa. Reťazenie, otvorené adresovanie a dvojité hashovanie je niekoľko techník na riešenie kolízií.

• Otvorené adresovanie : kolízie sa riešia hľadaním nasledujúceho prázdneho miesta v tabuľke. Ak je prvý slot už obsadený, hašovacia funkcia sa použije na nasledujúce sloty, kým jeden nezostane prázdny. Existujú rôzne spôsoby použitia tohto prístupu, vrátane dvojitého hashovania, lineárneho sondovania a kvadratického sondovania.
• Samostatné reťazenie : V samostatnom reťazení je prítomný prepojený zoznam objektov, ktoré hašujú do každého slotu v hašovacej tabuľke. Dva kľúče sú zahrnuté v prepojenom zozname, ak sú hashované do rovnakého slotu. Táto metóda je pomerne jednoduchá na použitie a dokáže zvládnuť niekoľko kolízií.
• Robin Hood hashuje: Aby sa skrátila dĺžka reťazca, kolízie v hašovaní Robina Hooda sa riešia vypnutím kľúčov. Algoritmus porovnáva vzdialenosť medzi slotom a obsadeným slotom dvoch kľúčov, ak nový kľúč hashuje k už obsadenému slotu. Existujúci kľúč sa vymení za nový, ak je bližšie k ideálnemu slotu. To približuje existujúci kľúč k jeho ideálnemu slotu. Táto metóda má tendenciu znižovať kolízie a priemernú dĺžku reťaze.

Dynamická zmena veľkosti:

Táto funkcia umožňuje, aby sa hašovacia tabuľka rozširovala alebo zmenšovala v reakcii na zmeny v počte prvkov obsiahnutých v tabuľke. To podporuje faktor zaťaženia, ktorý je ideálny a rýchly čas vyhľadávania.

obsahuje python

Implementácia hash tabuľky

Python, Java, C++ a Ruby sú len niektoré z programovacích jazykov, ktoré podporujú hašovacie tabuľky. Okrem toho, že sú často súčasťou štandardnej knižnice, môžu byť použité ako prispôsobená dátová štruktúra.

Príklad – Počítajte znaky v String geeksforgeeks.

V tomto príklade používame hašovaciu techniku ​​na uloženie počtu reťazca.

#include  using namespace std; int main() {  //initialize a string  string s='geeksforgeeks';    // Using an array to store the count of each alphabet   // by mapping the character to an index value  int arr[26]={0};    //Storing the count  for(int i=0;i

public class CharacterCount {  public static void main(String[] args) {  // Initialize a string  String s = 'geeksforgeeks';  // Using an array to store the count of each alphabet  // by mapping the character to an index value  int[] arr = new int[26];  // Storing the count  for (int i = 0; i < s.length(); i++) {  arr[s.charAt(i) - 'a']++;  }  // Search the count of the character  char ch = 'e';  // Get count  System.out.println('The count of ' + ch + ' is ' + arr[ch - 'a']);  } }>

# Initialize a string s = 'geeksforgeeks' # Using a list to store the count of each alphabet # by mapping the character to an index value arr = [0] * 26 # Storing the count for i in range(len(s)): arr[ord(s[i]) - ord('a')] += 1 # Search the count of the character ch = 'e' # Get count print('The count of ', ch, ' is ', arr[ord(ch) - ord('a')])>

using System; class Program {  static void Main(string[] args) {  //initialize a string  string s = 'geeksforgeeks';  // Using an array to store the count of each alphabet   // by mapping the character to an index value  int[] arr = new int[26];  //Storing the count  for (int i = 0; i < s.Length; i++) {  arr[s[i] - 'a']++;  }  //Search the count of the character  char ch = 'e';  // get count  Console.WriteLine('The count of ' + ch + ' is ' + arr[ch - 'a']);  } }>

// Initialize a string const s = 'geeksforgeeks'; // Using an array to store the count of each alphabet // by mapping the character to an index value const arr = Array(26).fill(0); // Storing the count for (let i = 0; i < s.length; i++) {  arr[s.charCodeAt(i) - 'a'.charCodeAt(0)]++; } // Search the count of the character const ch = 'e'; // Get count console.log(`The count of ${ch} is ${arr[ch.charCodeAt(0) - 'a'.charCodeAt(0)]}`);>

Výkon:

The count of e is 4>

Analýza zložitosti hašovacej tabuľky:

Pre operácie vyhľadávania, vkladania a vymazávania majú hašovacie tabuľky časovú zložitosť priemerného prípadu O(1). Tieto operácie však môžu v najhoršom prípade vyžadovať čas O(n), kde n je počet prvkov v tabuľke.

Aplikácie hash tabuľky:

• Hash tabuľky sa často používajú na indexovanie a vyhľadávanie veľkých objemov údajov. Vyhľadávací nástroj môže použiť hašovaciu tabuľku na uloženie webových stránok, ktoré indexoval.
• Údaje sa zvyčajne ukladajú do vyrovnávacej pamäte prostredníctvom hašovacích tabuliek, čo umožňuje rýchly prístup k často používaným informáciám.
• Hash funkcie sa často používajú v kryptografii na vytváranie digitálnych podpisov, overovanie údajov a zaručenie integrity údajov.
• Hašovacie tabuľky možno použiť na implementáciu databázových indexov, čo umožňuje rýchly prístup k údajom na základe kľúčových hodnôt.