Zgoščevanje je temeljna podatkovna struktura, ki učinkovito shranjuje in pridobiva podatke na način, ki omogoča hiter dostop. Vključuje preslikavo podatkov v določen indeks v zgoščeni tabeli z uporabo a hash funkcija ki omogoča hitro iskanje informacij na podlagi njihovega ključa. Ta metoda se pogosto uporablja v bazah podatkov, c bolečih sistemov in različnih aplikacij za programiranje za optimizacijo operacij iskanja in iskanja.

Podatkovne strukture – zgoščevanje

Kazalo

• Funkcija zgoščevanja
• Kaj je Hash Collision?
• Tehnike reševanja trkov
• Aplikacije zgoščevanja
• Enostavna težava pri zgoščevanju
• Srednja težava pri zgoščevanju
• Težka težava pri zgoščevanju

Kako deluje:

1. Funkcija zgoščevanja: Svoje podatke podate v funkcijo zgoščevanja.
2. Hash koda: Zgoščevalna funkcija zdrobi podatke in poda edinstveno zgoščevalno kodo.
3. Zgoščevalna tabela: Zgoščevalna koda vas nato usmeri na določeno mesto v zgoščevalni tabeli.

Funkcija zgoščevanja

The hash funkcija je funkcija, ki sprejme a ključ in vrne an kazalo v zgoščena tabela . Cilj zgoščevalne funkcije je enakomerno porazdeliti ključe po zgoščevalni tabeli, kar zmanjša kolizije (ko se dva ključa preslikata v isti indeks).

Pogoste zgoščevalne funkcije vključujejo:

• Metoda delitve: Ključni % Hash tabele Velikost
• Metoda množenja: (Ključ * Konstanta) % Velikost zgoščene tabele
• Univerzalno zgoščevanje: Družina zgoščevalnih funkcij, zasnovanih za zmanjšanje kolizij

Kaj je Hash Collision?

Do zgoščevalnega trka pride, ko se dva različna ključa preslikata v isti indeks v zgoščevalni tabeli. To se lahko zgodi tudi z dobro zgoščevalno funkcijo, zlasti če je zgoščevalna tabela polna ali so ključi podobni.

Vzroki za trke z zgoščevanjem:

• Slaba funkcija zgoščevanja: Zgoščevalna funkcija, ki ključev ne porazdeli enakomerno po zgoščevalni tabeli, lahko povzroči več kolizij.
• Faktor visoke obremenitve: Visok faktor obremenitve (razmerje med ključi in velikostjo razpršilne tabele) poveča verjetnost kolizij.
• Podobni ključi: Ključi, ki so podobni po vrednosti ali strukturi, bodo bolj verjetno trčili.

Tehnike reševanja trkov

Obstajata dve vrsti tehnik reševanja trkov:

1. Odpri naslavljanje:
   • Linearno tipanje: Zaporedoma poiščite prazno režo
   • Kvadratno sondiranje: Poiščite prazno režo s kvadratno funkcijo
2. Zaprto naslavljanje:
   • Veriženje: Shranite navzkrižne ključe v povezanem seznamu ali binarnem iskalnem drevesu pri vsakem indeksu
   • Cuckoo Hashing: Uporabite več zgoščevalnih funkcij za razdeljevanje ključev

Aplikacije zgoščevanja

Zgoščevalne tabele se uporabljajo v najrazličnejših aplikacijah, vključno z:

• Baze podatkov: Shranjevanje in pridobivanje podatkov na podlagi unikatnih ključev
• Predpomnjenje: Shranjevanje pogosto dostopanih podatkov za hitrejše iskanje
• Tabele simbolov: Preslikava identifikatorjev v njihove vrednosti v programskih jezikih
• Omrežno usmerjanje: Določanje najboljše poti za podatkovne pakete

Kaj je zgoščevanje?

Preslikava indeksa (ali trivialno zgoščevanje)

Ločeno veriženje za obvladovanje trkov

Odpri naslavljanje za obravnavo trkov

Dvojno zgoščevanje

Faktor obremenitve in ponovitev

Enostavna težava pri zgoščevanju

• Ugotovite, ali je matrika podmnožica druge matrike
• Zveza in presečišče dveh povezanih seznamov
• Podana je matrika A[] in število x, preverite par v A[] z vsoto kot x
• Največja razdalja med dvema pojavitvama istega elementa v matriki
• Preštejte največ točk na isti vrstici
• Najpogostejši element v nizu
• Poiščite edini ponavljajoči se element med 1 in n-1
• Kako preveriti, ali sta dve dani množici disjunktni?
• Neprekrivajoča se vsota dveh nizov
• Preverite, ali sta dve matriki enaki ali ne
• Poiščite manjkajoče elemente obsega
• Najmanjše število podmnožic z različnimi elementi
• Odstranite najmanjše število elementov, tako da v obeh nizih ni nobenega skupnega elementa
• Poišči pare z dano vsoto tako, da so elementi para v različnih vrsticah
• Preštejte pare z dano vsoto
• Preštejte četverčke iz štirih razvrščenih nizov, katerih vsota je enaka dani vrednosti x
• Razvrstite elemente po pogostosti
• Poiščite vse pare (a, b) v nizu, tako da je a % b = k
• Združi besede z enakim nizom znakov
• k-ti različni (ali neponavljajoči se) element v nizu.

Srednja težava pri zgoščevanju

• Poiščite načrt poti na danem seznamu vozovnic
• Poiščite število zaposlenih pod vsakim zaposlenim
• Najdaljši podniz z vsoto, deljivo s k
• Poiščite največjo podmatriko z vsoto 0
• Najdaljše naraščajoče zaporedno podzaporedje
• Preštejte različne elemente v vsakem oknu velikosti k
• Poiščite podmatriko z dano vsoto | Niz 2 (obravnava negativna števila)
• Implementacija naše lastne razpršitvene tabele z ločenim veriženjem v Javi
• Implementacija lastne zgoščene tabele z odprtim naslavljanjem linearnega tipanja v C++
• Najmanjše število vstavkov za oblikovanje palindroma z dovoljenimi permutacijami
• Največja možna razlika dveh podmnožic matrike
• Razvrščanje z uporabo trivialne hash funkcije
• Najmanjša podmatrika s k različnimi števili

Težka težava pri zgoščevanju

• Klonirajte binarno drevo z naključnimi kazalci
• Največja podmatrika z enakim številom 0 in 1
• Vsi edinstveni trojčki, ki se seštejejo na dano vrednost
• Poizvedbe o podnizu palindroma
• Poizvedbe obsega za frekvence elementov polja
• Elementi, ki jih je treba dodati, tako da so vsi elementi obsega prisotni v matriki
• Cuckoo Hashing – Najslabši primer O(1) Iskanje!
• Preštejte podnize, ki imajo skupno število različnih elementov, enakih izvirnemu nizu
• Največja matrika iz dveh danih matrik, ki ohranjata enak vrstni red
• Poiščite vsoto vseh edinstvenih vsot podmatric za dano matriko.
• Recamanovo zaporedje
• Dolžina najdaljšega strogega bitonskega podzaporedja
• Poiščite vsa podvojena poddrevesa
• Ugotovite, ali obstaja pravokotnik v binarni matriki z vogali kot 1

Hitre povezave :

• 'Težave v praksi' o zgoščevanju
• 20 najboljših vprašanj za intervju, ki temeljijo na tehniki zgoščevanja
• »Videoposnetki« o zgoščevanju