Phenquestions
Tarkime, kad esate didelės aprūpinimo parduotuvės savininkas apskrityje, kurioje gyvenate. Tarkime, kad gyvenate didelėje teritorijoje, kuri nėra komercinė sritis. Šioje srityje ne tik jūs turite maisto prekių parduotuvę; turite keletą konkurentų. Tada jums kyla mintis, kad turėtumėte įrašyti savo klientų telefonų numerius į pratybų sąsiuvinį. Žinoma, pratybų sąsiuvinis yra mažas, todėl negalite įrašyti visų savo klientų telefono numerių.
Taigi nusprendėte įrašyti tik savo nuolatinių klientų telefono numerius. Taigi jūs turite lentelę su dviem stulpeliais. Kairėje esančiame stulpelyje yra klientų vardai, o dešinėje - atitinkami telefono numeriai. Tokiu būdu susiejami klientų vardai ir telefonų numeriai. Dešinysis lentelės stulpelis gali būti laikomas pagrindine maišos lentele. Klientų vardai dabar vadinami klavišais, o telefonų numeriai - reikšmėmis. Atminkite, kad kai klientas eina pervedimą, turėsite atšaukti jo eilutę, leisdami eilutę tuščią arba pakeistą naujo nuolatinio kliento eilute. Taip pat atkreipkite dėmesį, kad laikui bėgant nuolatinių klientų skaičius gali padidėti arba sumažėti, todėl lentelė gali augti arba mažėti.
Tarkime, kad dar vienas žemėlapių sudarymo pavyzdys yra apskrities ūkininkų klubas. Žinoma, ne visi ūkininkai bus klubo nariai. Kai kurie klubo nariai nebus nuolatiniai nariai (dalyvaus ir prisidės). Baras gali nuspręsti įrašyti narių pavardes ir jų pasirinktą gėrimą. Jis sukuria dviejų stulpelių lentelę. Kairiajame stulpelyje jis užrašo klubo narių pavardes. Dešiniajame stulpelyje jis parašo atitinkamą gėrimo pasirinkimą.
Čia yra problema: dešiniajame stulpelyje yra dublikatai. Tai yra, tas pats gėrimo pavadinimas randamas daugiau nei vieną kartą. Kitaip tariant, skirtingi nariai geria tą patį saldų gėrimą arba tą patį alkoholinį gėrimą, o kiti nariai - kitokį saldų ar alkoholinį gėrimą. Advokatas nusprendžia išspręsti šią problemą įterpdamas siaurą stulpelį tarp dviejų stulpelių. Šiame viduriniame stulpelyje, pradedant nuo viršaus, jis sunumeruoja eilutes, prasidedančias nuo nulio (t.e. 0, 1, 2, 3, 4 ir kt.), žemyn, po vieną indeksą eilutėje. Tai išsprendžia jo problemą, nes nario vardas dabar susiejamas su indeksu, o ne su gėrimo pavadinimu. Taigi, kadangi gėrimas identifikuojamas pagal indeksą, kliento vardas priskiriamas atitinkamam indeksui.
Vien vertybių (gėrimų) stulpelis sudaro pagrindinę maišos lentelę. Modifikuotoje lentelėje indeksų stulpelis ir su jais susijusios vertės (su dublikatais arba be jų) sudaro įprastą maišos lentelę - visas maišos lentelės apibrėžimas pateiktas žemiau. Raktai (pirmasis stulpelis) nebūtinai yra maišos lentelės dalis.
Dar kartą paminėkime tinklo serverį, kuriame vartotojas iš savo kliento kompiuterio gali pridėti tam tikrą informaciją, ištrinti dalį informacijos arba pakeisti ją. Yra daug serverio vartotojų. Kiekvienas vartotojo vardas atitinka serveryje saugomą slaptažodį. Tie, kurie prižiūri serverį, gali matyti vartotojo vardus ir atitinkamą slaptažodį, todėl gali sugadinti vartotojų darbą.
Taigi serverio savininkas nusprendžia sukurti funkciją, kuri užšifruoja slaptažodį dar prieš jį saugant. Vartotojas prisijungia prie serverio naudodamas savo įprastą suprantamą slaptažodį. Tačiau dabar kiekvienas slaptažodis saugomas užkoduota forma. Jei kas nors mato užšifruotą slaptažodį ir bando prisijungti naudodamasis juo, jis neveiks, nes prisijungdamas gauna suprantamą serverio slaptažodį, o ne užšifruotą slaptažodį.
Tokiu atveju suprastas slaptažodis yra raktas, o užšifruotas slaptažodis yra reikšmė. Jei užšifruotas slaptažodis yra užšifruotų slaptažodžių stulpelyje, tai stulpelis yra pagrindinė maišos lentelė. Jei prieš šį stulpelį yra kitas stulpelis, kurio indeksai prasideda nuo nulio, todėl kiekvienas užšifruotas slaptažodis yra susietas su indeksu, tada tiek indeksų, tiek užšifruoto slaptažodžio stulpeliai sudaro įprastą maišos lentelę. Raktai nebūtinai yra maišos lentelės dalis.
Atminkite, kad šiuo atveju kiekvienas raktas, kuris yra suprantamas slaptažodis, atitinka vartotojo vardą. Taigi yra vartotojo vardas, atitinkantis raktą, susietą su indeksu, kuris yra susietas su verte, kuri yra užšifruotas raktas.
Maišos funkcijos apibrėžimas, visas maišos lentelės apibrėžimas, masyvo reikšmė ir kita informacija pateikiama žemiau. Kad galėtumėte įvertinti likusią šios pamokos dalį, turite turėti nuorodų (nuorodų) ir susietų sąrašų žinių.
Maišos funkcijos ir maišos lentelės reikšmė
Masyvas
Masyvas yra nuoseklių atminties vietų rinkinys. Visos vietos yra vienodo dydžio. Pirmoje vietoje esanti vertė pasiekiama naudojant indeksą 0; antroje vietoje esanti vertė pasiekiama naudojant indeksą 1; trečia reikšmė pasiekiama naudojant indeksą 2; ketvirtas su indeksu, 3; ir taip toliau. Masyvas paprastai negali padidėti ar susitraukti. Norint pakeisti masyvo dydį (ilgį), reikia sukurti naują masyvą ir atitinkamas reikšmes nukopijuoti į naują masyvą. Masyvo reikšmės visada yra to paties tipo.
Maišos funkcija
Programinėje įrangoje maišos funkcija yra funkcija, kuri ima raktą ir sukuria atitinkamą indeksą masyvo ląstelei. Masyvas yra fiksuoto dydžio (fiksuoto ilgio). Raktų skaičius yra savavališko dydžio, paprastai didesnis nei masyvo dydis. Indeksas, gautas iš maišos funkcijos, vadinamas maišos verte arba santrauka, maišos kodu arba tiesiog maiša.
„Hash“ lentelė
Maišos lentelė yra masyvas su reikšmėmis, kurio indeksai, raktai yra susieti. Raktai yra netiesiogiai susieti su vertėmis. Tiesą sakant, sakoma, kad raktai susieti su reikšmėmis, nes kiekvienas indeksas yra susietas su verte (su kopijomis arba be jų). Tačiau funkcija, atliekanti atvaizdavimą (t.e. maiša) susieja raktus su masyvo indeksais, o ne su reikšmėmis, nes vertėse gali būti dublikatų. Šioje diagramoje pavaizduota maišų lentelė, kurioje nurodomi žmonių vardai ir jų telefono numeriai. Masyvo ląstelės (lizdai) vadinamos grupėmis.
Atkreipkite dėmesį, kad kai kurie kibirai tušti. Maišos lentelės vertės nebūtinai turi būti visose grupėse. Grupių vertės nebūtinai turi būti didėjimo tvarka. Tačiau indeksai, su kuriais jie yra susiję, yra didėjimo tvarka. Rodyklės rodo žemėlapį. Atkreipkite dėmesį, kad raktai nėra masyve. Jie neturi būti jokios struktūros. Maišos funkcija paima bet kurį klavišą ir išmaišo masyvo indeksą. Jei segmente nėra vertės, susietos su indekso maiša, į tą segmentą gali būti įtraukta nauja vertė. Loginis ryšys yra tarp rakto ir indekso, o ne tarp rakto ir su indeksu susijusios vertės.
Masyvo reikšmės, kaip ir šios maišos lentelės, visada yra to paties tipo duomenys. Maišos lentelė (segmentai) gali prijungti raktus prie skirtingų duomenų tipų reikšmių. Šiuo atveju masyvo reikšmės yra visos rodyklės, nurodančios skirtingus reikšmių tipus.
Maišos lentelė yra masyvas su maišos funkcija. Funkcija paima klavišą ir maišo atitinkamą indeksą, todėl masyve susieja raktus su reikšmėmis. Raktai neturi būti maišos lentelės dalis.
Kodėl masyvas, o ne susietas sąrašas „Hash Table“
Maišos lentelės masyvą galima pakeisti susieto sąrašo duomenų struktūra, tačiau kiltų problemų. Pirmasis susieto sąrašo elementas natūraliai yra indekse 0; antrasis elementas natūraliai yra indekse 1; trečiasis natūraliai yra indekse, 2; ir taip toliau. Susieto sąrašo problema yra ta, kad norint gauti vertę, sąrašas turi būti kartojamas, o tam reikia laiko. Prieiga prie masyvo vertės yra atsitiktinė. Kai indeksas yra žinomas, vertė gaunama be iteracijos; ši prieiga yra greitesnė.
Susidūrimas
Maišos funkcija paima raktą ir maišo atitinkamą indeksą, norėdama perskaityti susietą vertę arba įterpti naują vertę. Jei tikslas yra nuskaityti vertę, kol kas nėra problemos (nėra problemos). Tačiau jei tikslas yra įterpti vertę, maišos indeksas jau gali turėti susietą vertę, tai yra susidūrimas; naujos vertės negalima dėti ten, kur jau yra vertė. Yra susidūrimo būdų - žr. Toliau.
Kodėl įvyksta susidūrimas
Pirmiau pateiktame prekių parduotuvės pavyzdyje raktai yra klientų vardai, o gėrimų pavadinimai - vertės. Atkreipkite dėmesį, kad klientų yra per daug, o masyvas yra ribotas ir negali priimti visų klientų. Taigi, masyve saugomi tik nuolatinių klientų gėrimai. Susidūrimas įvyktų, kai nuolatinis klientas tampa nuolatinis. Parduotuvės klientai sudaro didelį rinkinį, o masyvo klientams skirtų kibirų skaičius yra ribotas.
Su maišos lentelėmis įrašomos raktų reikšmės, kurios yra labai tikėtinos. Kai raktas, kuris nebuvo tikėtinas, tapo tikėtinas, greičiausiai įvyktų susidūrimas. Tiesą sakant, susidūrimas visada įvyksta su maišos lentelėmis.
Susidūrimo sprendimo pagrindai
Du susidūrimo sprendimo būdai vadinami atskirais grandinėliais ir atvirais adresais. Teoriškai raktai neturėtų būti duomenų struktūroje arba neturėtų būti maišos lentelės dalis. Tačiau abiem būdais reikalaujama, kad pagrindinis stulpelis būtų prieš maišos lentelę ir taptų visos struktūros dalimi. Vietoje raktų yra raktų stulpelyje, nuorodos į raktus gali būti raktų stulpelyje.
Praktinėje maišos lentelėje yra raktų stulpelis, tačiau šis raktų stulpelis oficialiai nėra maišos lentelės dalis.
Bet kurio sprendimo būdas gali būti tuščias, nebūtinai masyvo pabaigoje.
Atskira grandinė
Atskiroje grandinėje, susidūrus, nauja vertė pridedama dešinėje (ne aukščiau ar žemiau) nuo susidūrusios vertės. Taigi dvi ar trys vertės turi tą patį indeksą. Retai daugiau nei trys turėtų turėti tą patį indeksą.
Ar tikrai daugiau nei viena reikšmė gali turėti tą patį masyvo indeksą? - Ne. Taigi daugeliu atvejų pirmoji indekso vertė yra nuoroda į susieto sąrašo duomenų struktūrą, kurioje laikomos vienos, dvi ar trys susidūrusios vertės. Ši schema yra maišos lentelės, skirtos atskirai susieti klientus ir jų telefono numerius, pavyzdys:
Tušti kibirai pažymėti raide x. Likusiuose laiko tarpsniuose yra nuorodos į susietus sąrašus. Kiekviename susieto sąrašo elemente yra du duomenų laukai: vienas - kliento vardui, kitas - telefono numeriui. Konfliktas kyla dėl raktų: Peterio Joneso ir Suzano Lee. Atitinkamas vertes sudaro du vieno susieto sąrašo elementai.
Konfliktuojantiems raktams vertės įterpimo kriterijus yra tas pats kriterijus, naudojamas vertei surasti (ir perskaityti).
Atidarykite „Adresavimas“
Kai adresas yra atviras, visos reikšmės saugomos grupės masyve. Iškilus konfliktui, naujoji vertė įterpiama į tuščią grupę, atitinkančią konflikto vertę, vadovaujantis tam tikru kriterijumi. Kriterijus, naudojamas įterpiant vertę konfliktuojant, yra tas pats kriterijus, naudojamas vertei surasti (ieškoti ir skaityti).
Ši schema iliustruoja konfliktų sprendimą su atviru adresu:
Maišos funkcija paima raktą, Peterį Jonesą, maišo indeksą, 152, ir išsaugo savo telefono numerį susietame segmente. Praėjus kuriam laikui, maišos funkcija maišo tą patį indeksą 152 nuo rakto Suzano Lee, susidūrusio su Peterio Joneso indeksu. Norėdami tai išspręsti, „Suzan Lee“ vertė saugoma kito indekso 153, kuris buvo tuščias, segmente. Maišos funkcija maišo raktą, Robiną Hudą, indeksą 153, tačiau šis indeksas jau buvo naudojamas ankstesnio rakto konfliktui išspręsti. Taigi Robino Hudo vertė dedama į kitą tuščią grupę, kuri yra indekso 154 vertė.
Konfliktų sprendimo būdai atskiram grandiniui ir atviram adresavimui
Atskira grandinė turi savo konfliktų sprendimo būdus, o atviras kreipimasis taip pat turi savus konfliktų sprendimo būdus.
Atskirų grandinių konfliktų sprendimo būdai
Dabar trumpai paaiškinti atskirų grandinių maišos lentelių metodai:
Atskirkite grandines su susietais sąrašais
Šis metodas yra toks, kaip paaiškinta aukščiau. Tačiau kiekvienas susieto sąrašo elementas nebūtinai turi turėti pagrindinį lauką (pvz.,.g. kliento vardo laukas aukščiau).
Atskirkite grandines su sąrašo galvos ląstelėmis
Taikant šį metodą, pirmasis susieto sąrašo elementas saugomas masyvo segmente. Tai įmanoma, jei masyvo duomenų tipas yra susieto sąrašo elementas.
Atskirkite grandines nuo kitų konstrukcijų
Vietoj susieto sąrašo gali būti naudojama bet kuri kita duomenų struktūra, pvz., Savaime subalansuojantis dvejetainis paieškos medis, palaikantis reikiamas operacijas - žr. Vėliau.
Atviro adresavimo konfliktų sprendimo būdai
Atviro adresavimo konflikto sprendimo būdas vadinamas zondo seka. Dabar trumpai paaiškintos trys gerai žinomos zondo sekos:
Tiesinis zondavimas
Linijiniu zondavimu, kilus konfliktui, ieškoma artimiausio tuščio kibiro, esančio žemiau konflikto. Be to, taikant linijinį zondavimą, raktas ir jo vertė saugomi tame pačiame segmente.
Kvadratinis zondavimas
Tarkime, kad H konflikte įvyksta konfliktas. Kitas tuščias lizdas (segmentas) indekse H + 12 yra naudojamas; jei tai jau užimta, tada kitas tuščias H + 22 naudojamas, jei jis jau užimtas, tada kitas tuščias H + 32 yra naudojamas ir pan. Tam yra variantų.
Dvigubas maišos
Naudojant dvigubą maišymą, yra dvi maišos funkcijos. Pirmasis apskaičiuoja (maišo) indeksą. Jei įvyksta konfliktas, antrasis naudoja tą patį raktą, kad nustatytų, kiek žemyn vertė turėtų būti įterpta. Tai yra daugiau - žiūrėkite vėliau.
Puiki maišos funkcija
Puiki maišos funkcija yra maišos funkcija, dėl kurios negalima susidurti. Tai gali atsitikti, kai raktų rinkinys yra palyginti mažas ir kiekvienas raktas susiejamas su tam tikru skaičiumi maišos lentelėje.
ASCII simbolių rinkinyje didžiosios raidės gali būti susietos su atitinkamomis mažosiomis raidėmis, naudojant maišos funkciją. Raidės kompiuterio atmintyje vaizduojamos kaip skaičiai. ASCII simbolių rinkinyje A yra 65, B yra 66, C yra 67 ir kt. ir a yra 97, b yra 98, c yra 99 ir kt. Norėdami susieti nuo A iki a, pridėkite 32 - 65; Žemėlapyje nuo B iki b pridėkite 32 - 66; Žemėlapyje nuo C iki c pridėkite 32 - 67; ir taip toliau. Čia didžiosios raidės yra raktai, o mažosios - reikšmės. Tai maišos lentelė gali būti masyvas, kurio reikšmės yra susieti indeksai. Atminkite, kad masyvo segmentai gali būti tušti. Taigi masyvo grupės nuo 64 iki 0 gali būti tuščios. Maišos funkcija tiesiog prideda 32 prie didžiųjų raidžių kodo numerio, kad gautų indeksą, taigi ir mažąją raidę. Tokia funkcija yra tobula maišos funkcija.
Maišymas nuo sveikojo iki sveikojo indekso
Yra įvairių skaičių maišos metodų. Vienas iš jų vadinamas „Modulo“ padalijimo metodu (funkcija).
Modulo skyriaus maišos funkcija
Kompiuterių programinės įrangos funkcija nėra matematinė funkcija. Skaičiuojant (programinę įrangą) funkcija susideda iš teiginių rinkinio, prieš kurį pateikiami argumentai. Funkcijos „Modulo padalijimas“ raktai yra sveiki skaičiai ir susieti su segmentų masyvo indeksais. Raktų rinkinys yra didelis, todėl būtų atvaizduojami tik tie raktai, kurie labai tikėtina, kad atsiras veikloje. Taigi susidūrimai įvyksta tada, kai reikia susieti mažai tikėtinus raktus.
Pareiškime,
20/6 = 3R2
20 yra dividendas, 6 yra daliklis, o 3 likęs 2 yra koeficientas. Likusi 2 dalis taip pat vadinama modulo. Pastaba: galima turėti 0 modulį.
Šiam maišymui stalo dydis paprastai yra 2, pvz., Galia.g. 64 = 26 arba 256 = 28, ir pan. Šios maišos funkcijos daliklis yra pagrindinis skaičius, artimas masyvo dydžiui. Ši funkcija padalija raktą iš daliklio ir grąžina modulį. Modulis yra kibirų masyvo indeksas. Susieta segmento vertė yra jūsų pasirinkta vertė (rakto vertė).
Maišomas kintamo ilgio raktas
Čia raktų rinkinio raktai yra skirtingo ilgio tekstai. Skirtingi sveiki skaičiai gali būti išsaugomi atmintyje naudojant tą patį baitų skaičių (angliško simbolio dydis yra baitas). Kai skirtingi raktai yra skirtingo baito dydžio, sakoma, kad jie yra skirtingo ilgio. Vienas iš kintamo ilgio maišos būdų vadinamas „Radix Conversion Hasash“.
„Radix“ konversijos maišos
Stygose kiekvienas kompiuterio simbolis yra skaičius. Šiuo metodu,
Maišos kodas (rodyklė) = x0ak − 1+x1ak − 2+… + Xk − 2a1+xk − 1a0
Kur (x0, x1,…, xk − 1) yra įvesties eilutės simboliai, o a yra radix, e.g. 29 (žiūrėti vėliau). k yra simbolių skaičius eilutėje. Tai yra daugiau - žiūrėkite vėliau.
Raktai ir vertybės
Rakto / vertės poroje vertė nebūtinai turi būti skaičius ar tekstas. Tai taip pat gali būti įrašas. Įrašas yra sąrašas, parašytas horizontaliai. Rakto / vertės poroje kiekvienas raktas iš tikrųjų gali būti susijęs su kitu tekstu ar skaičiumi ar įrašu.
Asociatyvusis masyvas
Sąrašas yra duomenų struktūra, kur sąrašo elementai yra susiję, ir yra sąrašas operacijų, kurios veikia sąraše. Kiekvieną sąrašo elementą gali sudaryti pora elementų. Bendroji maišos lentelė su jos raktais gali būti laikoma duomenų struktūra, tačiau tai yra daugiau sistemos nei duomenų struktūra. Raktai ir jų reikšmės nėra labai priklausomi vienas nuo kito. Jie nėra labai susiję vieni su kitais.
Kita vertus, asociacinis masyvas yra panašus dalykas, tačiau raktai ir jų reikšmės labai priklauso vienas nuo kito; jie yra labai susiję vieni su kitais. Pavyzdžiui, galite turėti asociatyvų vaisių ir jų spalvų masyvą. Kiekvienas vaisius natūraliai turi savo spalvą. Vaisiaus pavadinimas yra raktas; spalva yra vertė. Įterpimo metu kiekvienas raktas įterpiamas su jo verte. Ištrinant, kiekvienas raktas ištrinamas su jo verte.
Asociatyvusis masyvas yra maišos lentelės duomenų struktūra, sudaryta iš raktų / reikšmių porų, kur nėra raktų dublikato. Vertės gali turėti dublikatus. Šioje situacijoje raktai yra struktūros dalis. Tai yra, raktai turi būti saugomi, tuo tarpu, naudojant bendrą skubos lentelę, raktai neturi būti saugomi. Pasikartojančių reikšmių problemą natūraliai išsprendžia segmentų masyvo indeksai. Nepainiokite tarp pasikartojančių verčių ir susidūrimo rodyklėje.
Kadangi asociacinis masyvas yra duomenų struktūra, jis turi bent šias operacijas:
Asociatyviosios masyvo operacijos
įterpti arba pridėti
Tai įterpia naują raktų / reikšmių porą į kolekciją, susiejant raktą su jo verte.
paskirti iš naujo
Ši operacija pakeičia konkretaus rakto vertę į naują.
ištrinti arba pašalinti
Tai pašalina raktą ir jo atitinkamą vertę.
peržiūra
Ši operacija ieško konkretaus rakto vertės ir grąžina vertę (jos nepašalindama).
Išvada
Maišos lentelės duomenų struktūrą sudaro masyvas ir funkcija. Funkcija vadinama maišos funkcija. Funkcija susieja raktus į masyvo reikšmes per masyvo indeksus. Raktai nebūtinai turi būti duomenų struktūros dalis. Raktų rinkinys paprastai yra didesnis nei išsaugotos vertės. Atsiradus susidūrimui, jis išsprendžiamas atskiru grandinės metodu arba atviru adresavimo metodu. Asociatyvusis masyvas yra specialus maišos lentelės duomenų struktūros atvejis.
