Maiša yra pagrindinė duomenų struktūra, kuri efektyviai saugo ir nuskaito duomenis taip, kad būtų galima greitai pasiekti. Tai apima duomenų susiejimą su konkrečiu indeksu maišos lentelėje, naudojant a maišos funkcija kuri leidžia greitai gauti informaciją pagal jos raktą. Šis metodas dažniausiai naudojamas duomenų bazėse, c sistemos ir įvairios programavimo programos, skirtos optimizuoti paieškos ir paieškos operacijas.

Duomenų struktūros – maiša

Turinys

• Maišos funkcija
• Kas yra maišos susidūrimas?
• Susidūrimo sprendimo būdai
• Maišos pritaikymas
• Lengva maišos problema
• Vidutinė maišos problema
• Sunki maišos problema

Kaip tai veikia:

1. Maišos funkcija: Savo duomenų elementus pateikiate maišos funkcijoje.
2. Maišos kodas: Maišos funkcija sutrinka duomenis ir suteikia unikalų maišos kodą.
3. Maišos lentelė: Tada maišos kodas nukreipia jus į konkrečią vietą maišos lentelėje.

Maišos funkcija

The maišos funkcija yra funkcija, kuriai reikia a Raktas ir grąžina an indeksas į maišos lentelė . Maišos funkcijos tikslas yra tolygiai paskirstyti raktus maišos lentelėje, sumažinant susidūrimus (kai du raktai susieti su tuo pačiu indeksu).

Įprastos maišos funkcijos apima:

• Padalijimo būdas: Raktas % maišos lentelės dydis
• Daugybos metodas: (Raktas * pastovus) % maišos lentelės dydis
• Universali maiša: Maišos funkcijų šeima, skirta sumažinti susidūrimų skaičių

Kas yra maišos susidūrimas?

Maišos susidūrimas įvyksta, kai du skirtingi raktai susiejami su tuo pačiu indeksu maišos lentelėje. Taip gali nutikti net ir naudojant gerą maišos funkciją, ypač jei maišos lentelė pilna arba klavišai panašūs.

Hash susidūrimų priežastys:

• Prasta maišos funkcija: Maišos funkcija, kuri netolygiai paskirsto raktus maišos lentelėje, gali sukelti daugiau susidūrimų.
• Didelis apkrovos koeficientas: Didelis apkrovos koeficientas (raktų ir maišos lentelės dydžio santykis) padidina susidūrimų tikimybę.
• Panašūs klavišai: Didesnė tikimybė susidurti raktams, kurių vertė ar struktūra yra panaši.

Susidūrimo sprendimo būdai

Yra dviejų tipų susidūrimo sprendimo būdai:

1. Atviras adresas:
   • Linijinis zondavimas: Iš eilės ieškokite tuščios vietos
   • Kvadratinis zondavimas: Ieškokite tuščios vietos naudodami kvadratinę funkciją
2. Uždaras adresas:
   • Sujungimas: Išsaugokite susidūrimo raktus susietame sąraše arba dvejetainėje paieškos medyje kiekviename indekse
   • Gegutės maišymas: Norėdami platinti raktus, naudokite kelias maišos funkcijas

Maišos pritaikymas

Maišos lentelės naudojamos įvairiose srityse, įskaitant:

• Duomenų bazės: Duomenų saugojimas ir gavimas pagal unikalius raktus
• Talpykla: Saugoti dažnai pasiekiamus duomenis, kad būtų galima greičiau juos gauti
• Simbolių lentelės: Identifikatorių susiejimas su jų reikšmėmis programavimo kalbomis
• Tinklo maršrutas: Geriausio duomenų paketų kelio nustatymas

Kas yra Hashing?

Indekso atvaizdavimas (arba trivialus maišymas)

Atskira grandinėlė, skirta valdyti susidūrimą

Atidarykite susidūrimo valdymo adresavimą

Dvigubas maišas

Apkrovos koeficientas ir pakartojimas

Lengva maišos problema

• Raskite, ar masyvas yra kito masyvo poaibis
• Sąjunga ir dviejų susietų sąrašų sankirta
• Duotas masyvas A[] ir skaičius x, patikrinkite, ar nėra poros A[], kurios suma yra x
• Didžiausias atstumas tarp dviejų to paties elemento atvejų masyve
• Suskaičiuokite didžiausius taškus toje pačioje eilutėje
• Dažniausias masyvo elementas
• Raskite vienintelį pasikartojantį elementą nuo 1 iki n-1
• Kaip patikrinti, ar du duoti rinkiniai yra nesusiję?
• Nepersidengianti dviejų rinkinių suma
• Patikrinkite, ar du masyvai yra vienodi, ar ne
• Raskite trūkstamus diapazono elementus
• Minimalus poaibių su skirtingais elementais skaičius
• Pašalinkite minimalų elementų skaičių, kad abiejuose masyve nebūtų bendro elemento
• Raskite poras su nurodyta suma, kad poros elementai būtų skirtingose ​​eilutėse
• Suskaičiuokite poras su nurodyta suma
• Suskaičiuokite keturgubus iš keturių surūšiuotų masyvų, kurių suma lygi nurodytai reikšmei x
• Rūšiuoti elementus pagal dažnį
• Raskite visas poras (a, b) masyve, kad a % b = k
• Grupuokite žodžius su tuo pačiu simbolių rinkiniu
• k-tas atskiras (arba nesikartojantis) masyvo elementas.

Vidutinė maišos problema

• Raskite maršrutą iš pateikto bilietų sąrašo
• Raskite darbuotojų skaičių pagal kiekvieną darbuotoją
• Ilgiausia pogrupė, kurios suma dalijasi iš k
• Raskite didžiausią pogrupį su 0 suma
• Ilgiausia Didėjanti seka iš eilės
• Suskaičiuokite skirtingus elementus kiekviename k dydžio lange
• Rasti pogrupį su nurodyta suma | 2 rinkinys (tvarko neigiamus skaičius)
• Savo maišos lentelės įdiegimas su atskira grandine „Java“.
• Savo maišos lentelės įdiegimas su atviru adresavimo linijiniu zondavimu C++
• Minimalūs įterpimai, kad susidarytų palindromas su permutacijomis
• Didžiausias galimas dviejų masyvo pogrupių skirtumas
• Rūšiavimas naudojant trivialią maišos funkciją
• Mažiausias pogrupis su k skirtingais skaičiais

Sunki maišos problema

• Klonuokite dvejetainį medį atsitiktiniais rodyklėmis
• Didžiausias pogrupis su vienodu 0 ir 1 skaičiumi
• Visi unikalūs trejetai, kurių suma yra nurodyta
• Palindromo poeilutės užklausos
• Masyvo elementų dažnių diapazono užklausos
• Elementai, kuriuos reikia pridėti, kad visi diapazono elementai būtų masyve
• Cuckoo Hashing – blogiausiu atveju O(1) paieška!
• Suskaičiuokite pogrupius, kurių bendras atskiras elementas yra toks pat kaip ir pradinis masyvas
• Didžiausias masyvas iš dviejų nurodytų masyvų, išlaikant tą pačią tvarką
• Raskite visų unikalių pomasyvo sumų sumą tam tikram masyvei.
• Recamano seka
• Ilgiausios griežtos bitoninės posekos ilgis
• Rasti visus pasikartojančius pomedžius
• Raskite, ar dvejetainėje matricoje yra stačiakampis, kurio kampai lygūs 1

Greitos nuorodos :

• „Praktikos problemos“ dėl maišos
• 20 populiariausių interviu klausimų, pagrįstų maišymo technika
• „Vaizdo įrašai“ apie maišą