Maiša reiškia fiksuoto dydžio išvesties generavimo procesą iš kintamo dydžio įvesties naudojant matematines formules, žinomas kaip maišos funkcijos. Ši technika nustato elemento saugojimo indeksą arba vietą duomenų struktūroje.

Need for Hash duomenų struktūros

Duomenų kiekis internete kasdien auga eksponentiškai, todėl sunku juos veiksmingai saugoti. Kasdieniniame programavime šis duomenų kiekis gali būti ne toks didelis, bet vis tiek juos reikia saugoti, pasiekti ir apdoroti lengvai ir efektyviai. Labai paplitusi duomenų struktūra, kuri naudojama tokiam tikslui, yra masyvo duomenų struktūra.

Dabar kyla klausimas, jei „Array“ jau buvo, kam reikėjo naujos duomenų struktūros! Atsakymas į tai slypi žodyje efektyvumas. Nors saugojimas „Array“ užtrunka O(1) laiko, paieška jame užtrunka mažiausiai O(log n) laikas. Atrodo, kad šis laikas yra mažas, tačiau dideliam duomenų rinkiniui tai gali sukelti daug problemų, o tai savo ruožtu daro masyvo duomenų struktūrą neefektyvią.

Taigi dabar mes ieškome duomenų struktūros, kuri galėtų saugoti duomenis ir ieškoti joje pastoviu laiku, t.y. O(1) laikas. Taip atsirado maišos duomenų struktūra. Įdiegus Hash duomenų struktūrą, dabar galima lengvai saugoti duomenis pastoviu laiku ir gauti juos taip pat pastoviu laiku.

Maišos komponentai

Iš esmės yra trys maišos komponentai:

1. Raktas: A Raktas gali būti bet kokia eilutė arba sveikasis skaičius, kuris pateikiamas kaip įvestis maišos funkcijoje, kuri nustato indeksą arba vietą elemento saugojimui duomenų struktūroje.
2. Maišos funkcija: The maišos funkcija gauna įvesties raktą ir grąžina elemento indeksą masyve, vadinamame maišos lentele. Indeksas yra žinomas kaip maišos indeksas .
3. Maišos lentelė: Maišos lentelė yra duomenų struktūra, susiejanti raktus su reikšmėmis naudojant specialią funkciją, vadinamą maišos funkcija. Maiša saugo duomenis asociatyviu būdu masyve, kuriame kiekviena duomenų reikšmė turi savo unikalų indeksą.

Maišos komponentai

Kas yra Susidūrimas?

Maišos keitimo procesas sugeneruoja nedidelį didelio rakto skaičių, todėl yra tikimybė, kad du raktai gali sukurti tą pačią vertę. Situacija, kai naujai įdėtas raktas susietas su jau užimtu, ir jis turi būti tvarkomas naudojant tam tikrą susidūrimo valdymo technologiją.

Susidūrimas Hashing mieste

Maišos privalumai duomenų struktūrose

• Rakto vertės palaikymas: Maiša idealiai tinka diegti raktinių verčių duomenų struktūras.
• Greitas duomenų gavimas: Maiša leidžia greitai pasiekti elementus, kurių sudėtingumas yra nuolatinis.
• Efektyvumas: Įterpimo, ištrynimo ir paieškos operacijos yra labai efektyvios.
• Atminties naudojimo sumažinimas: Maiša reikalauja mažiau atminties, nes elementams saugoti skiria fiksuotą vietą.
• Mastelio keitimas: Maiša gerai veikia esant dideliems duomenų rinkiniams, išlaikant nuolatinį prieigos laiką.
• Sauga ir šifravimas: Maiša yra būtina norint saugiai saugoti duomenis ir patikrinti vientisumą.

Norėdami sužinoti daugiau apie maišą, žr Maišos apdorojimo įvadas – duomenų struktūros ir algoritmų vadovėliai