Jaukšana ir pamata datu struktūra, kas efektīvi uzglabā un izgūst datus tādā veidā, kas nodrošina ātru piekļuvi. Tas ietver datu kartēšanu ar noteiktu indeksu jaucēj tabulā, izmantojot a jaucējfunkcija kas ļauj ātri izgūt informāciju, pamatojoties uz tās atslēgu. Šo metodi parasti izmanto datu bāzēs, c sistēmas un dažādas programmēšanas lietojumprogrammas, lai optimizētu meklēšanas un izguves darbības.

Datu struktūras — jaukšana

Satura rādītājs

• Jaucējfunkcija
• Kas ir Hash sadursme?
• Sadursmju risināšanas metodes
• Jaukšanas lietojumprogrammas
• Vienkārša jaukšanas problēma
• Vidēja problēma ar jaukšanu
• Sarežģīta problēma ar jaukšanu

Kā tas strādā:

1. Jaucējfunkcija: Jūs sniedzat savus datu vienumus jaucējfunkcijā.
2. Hash kods: Jaucējfunkcija sasmalcina datus un piešķir unikālu jaucējkodu.
3. Hash tabula: Pēc tam jaucējkods norāda uz noteiktu vietu jaucēj tabulā.

Jaucējfunkcija

The jaucējfunkcija ir funkcija, kas aizņem a taustiņu un atgriež an rādītājs iekšā hash tabula . Jaucējfunkcijas mērķis ir vienmērīgi sadalīt atslēgas pa jaukšanas tabulu, līdz minimumam samazinot sadursmes (kad divas atslēgas sakrīt ar vienu un to pašu indeksu).

Kopējās jaucējfunkcijas ietver:

• Sadalīšanas metode: Atslēgas % hash tabulas lielums
• Reizināšanas metode: (Taustiņa * konstante) % Hash tabulas lielums
• Universālā jaukšana: Jaukšanas funkciju saime, kas paredzēta sadursmju samazināšanai

Kas ir Hash sadursme?

Jaucējkoda sadursme notiek, ja divas dažādas atslēgas sakrīt ar vienu un to pašu indeksu jaukšanas tabulā. Tas var notikt pat ar labu jaucējfunkciju, it īpaši, ja hash tabula ir pilna vai taustiņi ir līdzīgi.

Hash sadursmju cēloņi:

• Slikta jaucējfunkcija: Jaukšanas funkcija, kas neizdala atslēgas vienmērīgi visā jaucēj tabulā, var izraisīt vairāk sadursmju.
• Augsts slodzes koeficients: Augsts slodzes koeficients (atslēgu attiecība pret jaukšanas tabulas izmēru) palielina sadursmju iespējamību.
• Līdzīgas atslēgas: Atslēgām, kurām ir līdzīga vērtība vai struktūra, ir lielāka iespēja sadurties.

Sadursmju risināšanas metodes

Ir divu veidu sadursmju risināšanas metodes:

1. Atvērta adresācija:
   • Lineārā zondēšana: Secīgi meklējiet tukšu vietu
   • Kvadrātiskā zondēšana: Meklējiet tukšu slotu, izmantojot kvadrātisko funkciju
2. Slēgta adresācija:
   • Ķēdēšana: Glabājiet sadursmes atslēgas saistītā sarakstā vai binārā meklēšanas kokā katrā rādītājā
   • Dzeguzes jaukšana: Izmantojiet vairākas jaucējfunkcijas, lai izplatītu atslēgas

Jaukšanas lietojumprogrammas

Hash tabulas tiek izmantotas visdažādākajās lietojumprogrammās, tostarp:

• Datu bāzes: Datu glabāšana un izguve, pamatojoties uz unikālajām atslēgām
• Kešatmiņa: Bieži piekļūtu datu glabāšana ātrākai izguvei
• Simbolu tabulas: Identifikatoru kartēšana ar to vērtībām programmēšanas valodās
• Tīkla maršrutēšana: Labākā ceļa noteikšana datu paketēm

Kas ir jaukšana?

Indeksa kartēšana (vai triviāla jaukšana)

Atsevišķa ķēde sadursmes apstrādei

Atveriet Addressing for Collision Handling

Dubultā jaukšana

Slodzes koeficients un atkārtota jaukšana

Vienkārša jaukšanas problēma

• Uzziniet, vai masīvs ir cita masīva apakškopa
• Savienība un divu saistītu sarakstu krustpunkts
• Dots masīvs A[] un skaitlis x, pārbaudiet pāri A[] ar summu x
• Maksimālais attālums starp diviem viena elementa gadījumiem masīvā
• Saskaitiet maksimālo punktu skaitu tajā pašā rindā
• Biežākais elements masīvā
• Atrodiet vienīgo atkārtoto elementu no 1 līdz n-1
• Kā pārbaudīt, vai divas dotās kopas ir nesavienojamas?
• Divu komplektu summa, kas nepārklājas
• Pārbaudiet, vai divi masīvi ir vienādi vai nē
• Atrodiet trūkstošos diapazona elementus
• Minimālais apakškopu skaits ar atšķirīgiem elementiem
• Noņemiet minimālo elementu skaitu, lai abos masīvos nepastāvētu kopīgs elements
• Atrodiet pārus ar doto summu tā, lai pāra elementi būtu dažādās rindās
• Skaitīt pārus ar doto summu
• Saskaitiet četrkāršus no četriem sakārtotiem masīviem, kuru summa ir vienāda ar doto vērtību x
• Kārtot elementus pēc biežuma
• Atrodiet visus pārus (a, b) masīvā tā, lai a % b = k
• Grupējiet vārdus ar vienādu rakstzīmju kopu
• k-tais atšķirīgais (vai neatkārtojas) elements masīvā.

Vidēja problēma ar jaukšanu

• Atrodiet maršrutu no noteiktā biļešu saraksta
• Atrodiet darbinieku skaitu zem katra darbinieka
• Garākais apakšgrupa ar summu, kas dalās ar k
• Atrodiet lielāko apakšgrupu ar 0 summu
• Garākais Pieaugošā secīgā secība
• Saskaitiet atšķirīgus elementus katrā k izmēra logā
• Atrast apakšgrupu ar norādīto summu | 2. komplekts (apstrādā negatīvos skaitļus)
• Mūsu pašu hash tabulas ieviešana ar atsevišķu ķēdi Java
• Pašas hash tabulas ieviešana ar atvērtu adresēšanas lineāro zondēšanu programmā C++
• Minimālais ievietojums, lai izveidotu palindromu ar atļautām permutācijām
• Maksimālā iespējamā atšķirība starp divām masīva apakškopām
• Kārtošana, izmantojot triviālo jaucējfunkciju
• Mazākā apakšgrupa ar k atšķirīgiem skaitļiem

Sarežģīta problēma ar jaukšanu

• Klonējiet bināro koku ar nejaušiem rādītājiem
• Lielākais apakšgrupa ar vienādu 0 un 1 skaitu
• Visi unikālie tripleti, kas summējas līdz noteiktai vērtībai
• Palindroma apakšvirknes vaicājumi
• Diapazona vaicājumi masīva elementu frekvencēm
• Elementi, kas jāpievieno, lai visi diapazona elementi būtu masīvā
• Dzeguzes jaukšana — sliktākajā gadījumā O(1) Meklēt!
• Skaitīt apakšmasīvus, kuru kopējais atšķirīgo elementu skaits ir tāds pats kā sākotnējam masīvam
• Maksimālais masīvs no diviem dotajiem masīviem, saglabājot to pašu secību
• Atrodiet visu unikālo apakšmasīvu summu dotajam masīvam.
• Rekamana secība
• Garākās stingrās bitoniskās apakšsecības garums
• Atrodiet visus apakškoku dublikātus
• Atrodiet, vai binārajā matricā ir taisnstūris, kura stūri ir 1

Ātrās saites :

• Jaukšanas prakses problēmas
• 20 populārākie intervijas jautājumi, kuru pamatā ir jaukšanas tehnika
• “Video” par jaukšanu