Hašování je základní datová struktura, která efektivně ukládá a získává data způsobem umožňujícím rychlý přístup. Zahrnuje mapování dat na konkrétní index v hašovací tabulce pomocí a hashovací funkce který umožňuje rychlé vyhledání informací na základě jeho klíče. Tato metoda se běžně používá v databázích, C bolavé systémy a různé programovací aplikace pro optimalizaci operací vyhledávání a vyhledávání.

Datové struktury – hashování

Obsah

• Hashovací funkce
• Co je to hash Collision?
• Techniky řešení kolize
• Aplikace hashování
• Snadný problém s hashováním
• Střední problém hashování
• Těžký problém s hashováním

Jak to funguje:

1. Hashovací funkce: Své datové položky poskytujete do hashovací funkce.
2. Hash kód: Hashovací funkce zpracovává data a poskytuje jedinečný hash kód.
3. Tabulka hash: Hašovací kód vás pak nasměruje na konkrétní místo v hašovací tabulce.

Hashovací funkce

The hashovací funkce je funkce, která přebírá a klíč a vrátí an index do hashovací tabulka . Cílem hašovací funkce je rozmístit klíče rovnoměrně po celé hašovací tabulce, čímž se minimalizují kolize (když se dva klíče mapují na stejný index).

Mezi běžné hashovací funkce patří:

• Metoda dělení: Klíč % Velikost hash tabulky
• Metoda násobení: (Klíč * Konstantní) % Velikost hash tabulky
• Univerzální hashování: Řada hašovacích funkcí navržených tak, aby minimalizovaly kolize

Co je to hash Collision?

Ke kolizi hash dochází, když se dva různé klíče mapují na stejný index v tabulce hash. To se může stát i s dobrou hashovací funkcí, zejména pokud je hashovací tabulka plná nebo jsou klíče podobné.

Příčiny hašovacích kolizí:

• Špatná hashovací funkce: Hašovací funkce, která nerozděluje klíče rovnoměrně po hashovací tabulce, může vést k většímu počtu kolizí.
• Faktor vysokého zatížení: Vysoký faktor zatížení (poměr klíčů k velikosti hashovací tabulky) zvyšuje pravděpodobnost kolizí.
• Podobné klíče: Klíče, které mají podobnou hodnotu nebo strukturu, se s větší pravděpodobností střetnou.

Techniky řešení kolize

Existují dva typy technik řešení kolizí:

1. Otevřít adresu:
   • Lineární sondování: Postupně vyhledejte prázdný slot
   • Kvadratické sondování: Vyhledejte prázdný slot pomocí kvadratické funkce
2. Uzavřené adresování:
   • řetězení: Uložte kolidující klíče do propojeného seznamu nebo binárního vyhledávacího stromu v každém indexu
   • Hašování kukačky: K distribuci klíčů použijte více hashovacích funkcí

Aplikace hashování

Hash tabulky se používají v celé řadě aplikací, včetně:

• Databáze: Ukládání a načítání dat na základě jedinečných klíčů
• Ukládání do mezipaměti: Ukládání často používaných dat pro rychlejší vyhledávání
• Tabulky symbolů: Mapování identifikátorů na jejich hodnoty v programovacích jazycích
• Směrování sítě: Určení nejlepší cesty pro datové pakety

Co je hashování?

Indexové mapování (nebo triviální hašování)

Samostatné řetězení pro zvládání kolize

Otevřete Addressing for Collision Handling

Dvojité hašování

Load Factor a Rehashing

Snadný problém s hashováním

• Zjistěte, zda je pole podmnožinou jiného pole
• Sjednocení a Průnik dvou propojených seznamů
• Je-li dané pole A[] a číslo x, zkontrolujte pár v A[] se součtem x
• Maximální vzdálenost mezi dvěma výskyty stejného prvku v poli
• Spočítejte maximální počet bodů na stejném řádku
• Nejčastější prvek v poli
• Najděte jediný opakující se prvek mezi 1 až n-1
• Jak zkontrolovat, zda jsou dvě dané množiny disjunktní?
• Nepřekrývající se součet dvou sad
• Zkontrolujte, zda jsou dvě pole stejná nebo ne
• Najděte chybějící prvky rozsahu
• Minimální počet podmnožin s odlišnými prvky
• Odstraňte minimální počet prvků tak, aby v obou polích neexistoval žádný společný prvek
• Najděte dvojice s daným součtem tak, aby prvky dvojice byly v různých řádcích
• Spočítejte dvojice s daným součtem
• Počítejte čtyřnásobky ze čtyř seřazených polí, jejichž součet se rovná dané hodnotě x
• Seřaďte prvky podle frekvence
• Najděte všechny dvojice (a, b) v poli tak, že a % b = k
• Seskupte slova se stejnou sadou znaků
• k-tý odlišný (nebo neopakující se) prvek v poli.

Střední problém hashování

• Najděte itinerář z daného seznamu vstupenek
• Najděte počet zaměstnanců pod každým zaměstnancem
• Nejdelší podpole se součtem dělitelným k
• Najděte největší podpole se součtem 0
• Nejdelší rostoucí po sobě jdoucí dílčí sekvence
• Počítejte odlišné prvky v každém okně velikosti k
• Najít podpole s daným součtem | Sada 2 (zpracovává záporná čísla)
• Implementace naší vlastní hashovací tabulky se samostatným řetězením v Javě
• Implementace vlastní hash tabulky s otevřeným adresním lineárním sondováním v C++
• Minimální inzerce k vytvoření palindromu s povolenými permutacemi
• Maximální možný rozdíl dvou podmnožin pole
• Řazení pomocí triviální hashovací funkce
• Nejmenší podpole s k odlišnými čísly

Těžký problém s hashováním

• Klonujte binární strom pomocí náhodných ukazatelů
• Největší podpole se stejným počtem 0s a 1s
• Všechny jedinečné trojice, jejichž součet tvoří danou hodnotu
• Palindromové podřetězcové dotazy
• Rozsahové dotazy na frekvence prvků pole
• Prvky, které mají být přidány, aby všechny prvky rozsahu byly přítomny v poli
• Kukaččí hašování – nejhorší případ O(1) vyhledávání!
• Počítejte podpole, která mají celkem odlišné prvky stejné jako původní pole
• Maximální pole ze dvou daných polí při zachování stejného pořadí
• Najít součet všech jedinečných součtů dílčích polí pro dané pole.
• Recamanova sekvence
• Délka nejdelší přísné bitonické subsekvence
• Najít všechny duplicitní podstromy
• Zjistěte, zda je v binární matici obdélník s rohy jako 1

Rychlé odkazy :

• „Procvičování problémů“ při hašování
• 20 nejčastějších otázek pohovoru založených na hashovací technice
• „Videa“ na hashování