Hašovanie je základná dátová štruktúra, ktorá efektívne ukladá a získava dáta spôsobom, ktorý umožňuje rýchly prístup. Zahŕňa mapovanie údajov na konkrétny index v hašovacej tabuľke pomocou a hašovacia funkcia ktorý umožňuje rýchle vyhľadávanie informácií na základe ich kľúča. Táto metóda sa bežne používa v databázach, c bolestivé systémy a rôzne programovacie aplikácie na optimalizáciu operácií vyhľadávania a vyhľadávania.

Dátové štruktúry – Hašovanie

Obsah

• Hash funkcia
• Čo je to hash Collision?
• Techniky riešenia kolízie
• Aplikácie hashovania
• Jednoduchý problém s hashovaním
• Stredný problém hashovania
• Ťažký problém s hashovaním

Ako to funguje:

1. Hash funkcia: Svoje dátové položky zadáte do hašovacej funkcie.
2. Hash kód: Hašovacia funkcia spracuje údaje a poskytne jedinečný hašovací kód.
3. Tabuľka hash: Hašovací kód vás potom nasmeruje na konkrétne miesto v hašovacej tabuľke.

Hash funkcia

The hašovacia funkcia je funkcia, ktorá zaberá a kľúč a vráti an index do hash tabuľka . Cieľom hašovacej funkcie je rovnomerne rozložiť kľúče v hašovacej tabuľke, čím sa minimalizujú kolízie (keď sa dva kľúče mapujú na rovnaký index).

Bežné hašovacie funkcie zahŕňajú:

• Spôsob delenia: Kľúč % Veľkosť hash tabuľky
• Metóda násobenia: (Kľúč * Konštantná) % Veľkosť hash tabuľky
• Univerzálne hashovanie: Rodina hašovacích funkcií navrhnutých na minimalizáciu kolízií

Čo je to hash Collision?

Kolízia hash nastane, keď sa dva rôzne kľúče mapujú na rovnaký index v tabuľke hash. To sa môže stať aj pri dobrej hašovacej funkcii, najmä ak je hašovacia tabuľka plná alebo sú kľúče podobné.

Príčiny hašovacích kolízií:

• Slabá hashovacia funkcia: Hašovacia funkcia, ktorá nerozdeľuje kľúče rovnomerne v hašovacej tabuľke, môže viesť k ďalším kolíziám.
• Faktor vysokého zaťaženia: Vysoký faktor zaťaženia (pomer kľúčov k veľkosti hašovacej tabuľky) zvyšuje pravdepodobnosť kolízií.
• Podobné kľúče: Kľúče, ktoré majú podobnú hodnotu alebo štruktúru, majú väčšiu pravdepodobnosť kolízie.

Techniky riešenia kolízie

Existujú dva typy techník riešenia kolízií:

1. Otvoriť Adresovanie:
   • Lineárne snímanie: Postupne vyhľadajte prázdny slot
   • Kvadratické snímanie: Vyhľadajte prázdny slot pomocou kvadratickej funkcie
2. Uzavreté adresovanie:
   • Reťazenie: Uložte kolidujúce kľúče v prepojenom zozname alebo binárnom vyhľadávacom strome pri každom indexe
   • Kukučka hašovanie: Na distribúciu kľúčov použite viacero hašovacích funkcií

Aplikácie hashovania

Hash tabuľky sa používajú v širokej škále aplikácií, vrátane:

• Databázy: Ukladanie a získavanie údajov na základe jedinečných kľúčov
• Ukladanie do vyrovnávacej pamäte: Ukladanie často používaných údajov pre rýchlejšie vyhľadávanie
• Tabuľky symbolov: Mapovanie identifikátorov na ich hodnoty v programovacích jazykoch
• Smerovanie siete: Určenie najlepšej cesty pre dátové pakety

Čo je hashovanie?

Mapovanie indexu (alebo triviálne hašovanie)

Samostatné reťazenie pre zvládanie kolízie

Open Addressing for Collision Handling

Dvojité hashovanie

Faktor zaťaženia a opätovný zásah

Jednoduchý problém s hashovaním

• Zistite, či je pole podmnožinou iného poľa
• Zjednotenie a Priesečník dvoch prepojených zoznamov
• Ak je dané pole A[] a číslo x, skontrolujte pár v A[] so súčtom x
• Maximálna vzdialenosť medzi dvoma výskytmi rovnakého prvku v poli
• Spočítajte maximálny počet bodov na rovnakom riadku
• Najčastejší prvok v poli
• Nájdite jediný opakujúci sa prvok medzi 1 až n-1
• Ako skontrolovať, či sú dve dané množiny disjunktné?
• Neprekrývajúci sa súčet dvoch množín
• Skontrolujte, či sú dve polia rovnaké alebo nie
• Nájdite chýbajúce prvky rozsahu
• Minimálny počet podmnožín s odlišnými prvkami
• Odstráňte minimálny počet prvkov tak, aby v oboch poliach neexistoval žiadny spoločný prvok
• Nájdite dvojice s daným súčtom tak, aby prvky dvojice boli v rôznych riadkoch
• Spočítajte dvojice s daným súčtom
• Spočítajte štvorice zo štyroch zoradených polí, ktorých súčet sa rovná danej hodnote x
• Zoraďte prvky podľa frekvencie
• Nájdite všetky dvojice (a, b) v poli tak, že a % b = k
• Zoskupte slová s rovnakou sadou znakov
• k-tý odlišný (alebo neopakujúci sa) prvok v poli.

Stredný problém hashovania

• Nájdite Itinerár z daného zoznamu lístkov
• Nájdite počet zamestnancov pod každým zamestnancom
• Najdlhšie podpole so súčtom deliteľným k
• Nájdite najväčšie podpole so súčtom 0
• Najdlhšie rastúce po sebe idúce podsekvencie
• Spočítajte odlišné prvky v každom okne veľkosti k
• Nájsť podpole s daným súčtom | Sada 2 (zaobchádza so zápornými číslami)
• Implementácia našej vlastnej tabuľky hash so samostatným reťazením v jazyku Java
• Implementácia vlastnej hash tabuľky s otvoreným adresným lineárnym sondovaním v C++
• Minimálne vloženia na vytvorenie palindrómu s povolenými permutáciami
• Maximálny možný rozdiel dvoch podmnožín poľa
• Triedenie pomocou triviálnej hašovacej funkcie
• Najmenšie podpole s k odlišnými číslami

Ťažký problém s hashovaním

• Klonujte binárny strom pomocou náhodných ukazovateľov
• Najväčšie podpole s rovnakým počtom 0s a 1s
• Všetky jedinečné trojice, ktorých súčet tvorí danú hodnotu
• Dotazy na podreťazec palindrómu
• Rozsahové dotazy na frekvencie prvkov poľa
• Prvky, ktoré sa majú pridať, aby boli všetky prvky rozsahu prítomné v poli
• Hašovanie kukučky – Najhorší prípad O(1) vyhľadávanie!
• Spočítajte podpole, ktoré majú celkom odlišné prvky rovnaké ako pôvodné pole
• Maximálne pole z dvoch daných polí pri zachovaní rovnakého poradia
• Nájsť súčet všetkých jedinečných súčtov čiastkových polí pre dané pole.
• Recamanova sekvencia
• Dĺžka najdlhšej prísnej bitonickej subsekvencie
• Nájsť všetky duplicitné podstromy
• Zistite, či je v binárnej matici obdĺžnik s rohmi ako 1

Rýchle odkazy:

• „Problémy s precvičovaním“ pri hašovaní
• 20 najlepších otázok na pohovor založených na technike hashovania
• „Videá“ o hashovaní