Hashing on perustietorakenne, joka tallentaa ja hakee tiedot tehokkaasti tavalla, joka mahdollistaa nopean pääsyn. Se sisältää tietojen yhdistämisen tiettyyn indeksiin hash-taulukossa käyttämällä a hash-toiminto joka mahdollistaa tiedon nopean haun avaimensa perusteella. Tätä menetelmää käytetään yleisesti tietokannassa, c kipeät järjestelmät ja erilaiset ohjelmointisovellukset haku- ja hakutoimintojen optimoimiseksi.

Tietorakenteet – Hashing

Sisällysluettelo

• Hash-toiminto
• Mikä on hash-törmäys?
• Törmäyksenratkaisutekniikat
• Hashingin sovellukset
• Helppo ongelma tiivistämisessä
• Keskinkertainen ongelma tiivistyksessä
• Vaikea ongelma tiivistämisessä

Kuinka se toimii:

1. Hash-funktio: Annat tietokohteet hash-toimintoon.
2. Hash koodin: Hajautustoiminto murskaa tiedot ja antaa ainutlaatuisen hash-koodin.
3. Hash-taulukko: Hajakoodi osoittaa sitten tiettyyn paikkaan hash-taulukossa.

Hash-toiminto

The hash-toiminto on funktio, joka vie a avain ja palauttaa an indeksi sisään hash-taulukko . Hajautusfunktion tavoitteena on jakaa avaimet tasaisesti hash-taulukon poikki, minimoiden törmäykset (kun kaksi avainta kartoitetaan samaan indeksiin).

Yleisiä hash-funktioita ovat:

• Jakomenetelmä: Avain % Hash-taulukon koko
• Kertolaskumenetelmä: (Avain * Vakio) % Hash-taulukon koko
• Universaali tiivistys: Hajautustoimintojen perhe, joka on suunniteltu minimoimaan törmäykset

Mikä on hash-törmäys?

Hajautustörmäys tapahtuu, kun kaksi eri avainta kartoitetaan samaan indeksiin hash-taulukossa. Tämä voi tapahtua jopa hyvällä hash-toiminnolla, varsinkin jos hash-taulukko on täynnä tai avaimet ovat samanlaisia.

Hash-törmäysten syyt:

• Huono hajautustoiminto: Hajautustoiminto, joka ei jaa avaimia tasaisesti hash-taulukossa, voi johtaa useampaan törmäykseen.
• Korkea kuormituskerroin: Korkea kuormituskerroin (avainten suhde hash-taulukon kokoon) lisää törmäysten todennäköisyyttä.
• Samanlaiset avaimet: Arvoltaan tai rakenteeltaan samanlaiset avaimet törmäävät todennäköisemmin.

Törmäyksenratkaisutekniikat

On olemassa kahdenlaisia ​​törmäyksenratkaisutekniikoita:

1. Avoin osoite:
   • Lineaarinen mittaus: Etsi tyhjä paikka peräkkäin
   • Neliöllinen mittaus: Etsi tyhjä paikka neliöfunktiolla
2. Suljettu osoite:
   • Ketjutus: Tallenna törmäysavaimet linkitettyyn luetteloon tai binäärihakupuuhun kussakin hakemistossa
   • Cuckoo Hashing: Käytä useita hajautusfunktioita avainten jakamiseen

Hashingin sovellukset

Hash-taulukoita käytetään monenlaisissa sovelluksissa, mukaan lukien:

• Tietokannat: Tietojen tallentaminen ja haku yksilöllisten avainten perusteella
• Välimuisti: Usein käytettyjen tietojen tallentaminen nopeampaa hakua varten
• Symbolitaulukot: Tunnisteiden yhdistäminen niiden arvoihin ohjelmointikielissä
• Verkkoreititys: Tietopakettien parhaan polun määrittäminen

Mitä Hashing on?

Hakemistokartoitus (tai triviaali hajautus)

Erillinen ketjutus törmäyskäsittelyä varten

Avaa osoitus törmäyskäsittelyä varten

Double Hashing

Kuormituskerroin ja uudelleentarkistus

Helppo ongelma tiivistämisessä

• Selvitä, onko taulukko toisen taulukon osajoukko
• Unioni ja kahden linkitetyn luettelon leikkaus
• Kun annetaan taulukko A[] ja luku x, tarkista, onko A[]:ssa pari, jonka summa on x
• Suurin etäisyys saman elementin kahden esiintymisen välillä taulukossa
• Laske maksimipisteet samalla rivillä
• Yleisin elementti taulukossa
• Etsi ainoa toistuva elementti väliltä 1 - n-1
• Kuinka tarkistaa, ovatko kaksi annettua joukkoa erillisiä?
• Kahden joukon ei-päällekkäinen summa
• Tarkista, ovatko kaksi taulukkoa yhtä suuret vai eivät
• Etsi alueen puuttuvat elementit
• Erillisiä elementtejä sisältävien osajoukkojen vähimmäismäärä
• Poista vähimmäismäärä elementtejä siten, että molemmissa taulukoissa ei ole yhteistä elementtiä
• Etsi pareja annetulla summalla siten, että parin elementit ovat eri riveillä
• Laske parit annetulla summalla
• Laske nelinkertaiset neljästä lajitetusta taulukosta, joiden summa on yhtä suuri kuin annettu arvo x
• Lajittele elementit taajuuden mukaan
• Etsi kaikki parit (a, b) taulukosta siten, että a % b = k
• Ryhmittele sanat samalla merkkijoukolla
• taulukon k:s erillinen (tai ei-toistuva) elementti.

Keskinkertainen tiivistysongelma

• Etsi reittisuunnitelma annetusta lippuluettelosta
• Etsi jokaisen työntekijän alta olevien työntekijöiden lukumäärä
• Pisin alitaulukko, jonka summa on jaollinen k:llä
• Etsi suurin aliryhmä, jonka summa on 0
• Pisin Kasvava peräkkäinen osajakso
• Laske erilliset elementit jokaisessa k-koon ikkunassa
• Etsi alitaulukko annetulla summalla | Sarja 2 (käsittelee negatiivisia numeroita)
• Oman hash-taulukon toteuttaminen erillisellä ketjutuksella Javassa
• Oman hash-taulukon toteuttaminen avoimella osoitteiden lineaarisella luotauksella C++:ssa
• Vähimmäislisäys palindromin muodostamiseksi permutaatioineen
• Suurin mahdollinen ero taulukon kahden osajoukon välillä
• Lajittelu triviaalilla hash-funktiolla
• Pienin alitaulukko, jossa on k erillistä numeroa

Vaikea ongelma tiivistämisessä

• Kloonaa binääripuu satunnaisten osoittimien avulla
• Suurin aliryhmä, jossa on yhtä monta 0:ta ja 1:tä
• Kaikki yksilölliset kolmoset, jotka summautuvat tiettyyn arvoon
• Palindromi-alijonokyselyt
• Aluekyselyt taulukkoelementtien taajuuksille
• Lisättävät elementit, jotta kaikki alueen elementit ovat taulukossa
• Cuckoo Hashing – Pahimmassa tapauksessa O(1) Haku!
• Laske alitaulukot, joissa on yhteensä samat erilliset elementit kuin alkuperäinen taulukko
• Suurin matriisi kahdesta annetusta taulukosta pitäen järjestyksen samana
• Etsi tietyn taulukon kaikkien yksilöllisten alitaulukoiden summan summa.
• Recamanin sekvenssi
• Pisimmän tiukan bitonisen osasekvenssin pituus
• Etsi kaikki päällekkäiset alipuut
• Selvitä, onko binäärimatriisissa suorakulmio, jonka kulmat ovat 1

Pikalinkit:

• 'Harjoitteluongelmat' hashingissa
• 20 parasta hajautustekniikkaan perustuvaa haastattelukysymystä
• 'Videot' hashingista