Co je hash tabulka?

Hash tabulka je definována jako datová struktura používaná k rychlému vkládání, vyhledávání a odstraňování párů klíč–hodnota. Funguje na hashovací koncept , kde je každý klíč přeložen hashovací funkcí do odlišného indexu v poli. Index funguje jako úložiště pro odpovídající hodnotu. Jednoduše řečeno, mapuje klíče s hodnotou.

Co je faktor zatížení?

Faktor zatížení hašovací tabulky je určen tím, kolik prvků je v ní uloženo v poměru k velikosti tabulky. Tabulka může být nepřehledná a mít delší dobu vyhledávání a kolize, pokud je faktor zatížení vysoký. Ideální faktor zatížení může být zachován s použitím dobré hashovací funkce a správné změny velikosti tabulky.

Co je hashovací funkce?

Funkce, která převádí klíče na indexy pole, je známá jako hashovací funkce. Klíče by měly být rovnoměrně rozmístěny po celém poli pomocí slušné hashovací funkce, aby se snížily kolize a zajistily se rychlé rychlosti vyhledávání.

• Celočíselný vesmírný předpoklad: Předpokládá se, že klíče jsou celá čísla v určitém rozsahu podle předpokladu celočíselného vesmíru. To umožňuje použití základních hašovacích operací, jako je dělení nebo násobení.
• Hašování podle divize: Tato přímočará hašovací technika používá jako index zbývající hodnotu klíče po jejím vydělení velikostí pole. Když je velikost pole prvočíslo a klíče jsou rovnoměrně rozmístěny, funguje dobře.
• Hašování násobením: Tato přímočará hašovací operace vynásobí klíč konstantou mezi 0 a 1, než vezme zlomkovou část výsledku. Poté je index určen vynásobením zlomkové složky velikostí pole. Funguje také efektivně, když jsou klávesy rovnoměrně rozmístěny.

Výběr hashovací funkce :

Výběr slušné hashovací funkce je založen na vlastnostech klíčů a zamýšlené funkčnosti hashovací tabulky. Použití funkce, která rovnoměrně rozmístí klíče a sníží kolize, je zásadní.

Kritéria, na základě kterých se volí hashovací funkce:

• Aby bylo zajištěno, že počet kolizí bude co nejmenší, měla by dobrá hashovací funkce distribuovat klíče po celé hashovací tabulce jednotným způsobem. To znamená, že pro všechna párování klíčů by měla být pravděpodobnost, že se dva klíče hašují na stejnou pozici v tabulce, spíše konstantní.
• Aby bylo umožněno rychlé hašování a načítání klíčů, měla by být hašovací funkce výpočetně efektivní.
• Mělo by být náročné odvodit klíč z jeho hash hodnoty. Výsledkem je, že pokusy uhodnout klíč pomocí hodnoty hash mají menší šanci na úspěch.
• Hašovací funkce by měla být dostatečně flexibilní, aby se mohla přizpůsobit změnám hašovaných dat. Například hašovací funkce musí nadále správně fungovat, pokud se změní velikost nebo formát hašovaných klíčů.

Techniky řešení kolize :

Ke kolizím dochází, když dva nebo více klíčů ukazuje na stejný index pole. Řetězení, otevřené adresování a dvojité hashování je několik technik pro řešení kolizí.

• Otevřené adresování : kolize se řeší hledáním následujícího prázdného místa v tabulce. Pokud je první slot již obsazen, hashovací funkce je aplikována na následující sloty, dokud jeden nezůstane prázdný. Existují různé způsoby použití tohoto přístupu, včetně dvojitého hashování, lineárního sondování a kvadratického sondování.
• Samostatné řetězení : V samostatném řetězení je k dispozici propojený seznam objektů, které hashují do každého slotu v tabulce hash. Dva klíče jsou zahrnuty v propojeném seznamu, pokud hashují do stejného slotu. Tato metoda je poměrně jednoduchá na použití a dokáže zvládnout několik kolizí.
• Robin Hood hash: Aby se zkrátila délka řetězce, kolize v hašování Robina Hooda se řeší vypnutím kláves. Algoritmus porovnává vzdálenost mezi slotem a obsazeným slotem dvou klíčů, pokud nový klíč hashuje k již obsazenému slotu. Stávající klíč se vymění za nový, pokud je blíže k ideální pozici. Tím se stávající klíč přiblíží k jeho ideální pozici. Tato metoda má tendenci snížit kolize a průměrnou délku řetězu.

Dynamická změna velikosti:

Tato funkce umožňuje rozšiřování nebo smršťování tabulky hash v reakci na změny v počtu prvků obsažených v tabulce. To podporuje faktor zatížení, který je ideální a rychlé vyhledávání.

Implementace hash tabulky

Python, Java, C++ a Ruby jsou jen některé z programovacích jazyků, které podporují hashovací tabulky. Kromě toho, že jsou často součástí standardní knihovny, mohou být použity jako přizpůsobená datová struktura.

Příklad – Počítejte znaky v String geeksforgeeks.

V tomto příkladu používáme hašovací techniku ​​pro uložení počtu řetězce.

#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ýstup:

The count of e is 4>

Analýza složitosti hash tabulky:

Pro operace vyhledávání, vkládání a mazání mají hashovací tabulky průměrnou časovou složitost případu O(1). Tyto operace však mohou v nejhorším případě vyžadovat čas O(n), kde n je počet prvků v tabulce.

Aplikace hash tabulky:

• Hashovací tabulky se často používají k indexování a prohledávání velkých objemů dat. Vyhledávač může použít hašovací tabulku k uložení webových stránek, které indexoval.
• Data jsou obvykle ukládána do mezipaměti prostřednictvím hashovacích tabulek, což umožňuje rychlý přístup k často používaným informacím.
• Hashovací funkce se v kryptografii často používají k vytváření digitálních podpisů, ověřování dat a zaručení integrity dat.
• Hashovací tabulky lze použít pro implementaci databázových indexů, což umožňuje rychlý přístup k datům na základě klíčových hodnot.