Mis on Hashtable?

Arvutiteaduses on räsitabel andmete salvestamiseks mõeldud andmestruktuur, mis koosneb väärtuste loendist, mida nimetatakse võtmeteks ja mis on seotud vastava väärtuste loendiga, mida nimetatakse massiiviks. Näiteks võidakse ettevõtte nimi siduda selle aadressiga. Tavaliselt on massiivi igal väärtusel positsiooninumber, mida nimetatakse räsiks. Räsifunktsioon on üldiselt juhiste komplekt või algoritm, mis seostab iga võtmeväärtuse räsiga – näiteks ühendab ettevõtte nime selle aadressi, telefoninumbri ja ärikategooriaga. Räsifunktsiooni eesmärk on määrata igale võtmele unikaalne vastav väärtus massiivis; seda nimetatakse tavaliselt räsimiseks. Räsifunktsioonid peavad olema korralikult vormindatud, et räsitabel korralikult toimiks.

Räsitabeli toimivus andmekogumil sõltub selle räsifunktsiooni tõhususest. Hea räsifunktsioon tagab tavaliselt võtmete ühtse otsingu ja vastenduste ühtlase jaotuse vastavas massiivis. Räsikokkupõrge toimub siis, kui kaks võtit on määratud samale vastavale väärtusele. Räsikokkupõrke korral käivitatakse räsifunktsioon tavaliselt uuesti, kuni leitakse unikaalne vastav väärtus; selle tulemuseks on tavaliselt pikem räsiaeg. Kuigi räsitabeli võtmete arv on tavaliselt fikseeritud, võivad mõnikord olla võtmed dubleerivad. Sellest hoolimata on hästi läbimõeldud räsitabelil tõhusad räsifunktsioonid, mis vastavad iga võtme unikaalsele vastavale väärtusele massiivis.

Mõnikord võivad räsitabeli ebaefektiivsed räsifunktsioonid tekitada ka vastenduste klastri. Kui räsifunktsioon loob olemasolevate võtmete jaoks vastenduste klastri, võib see pikendada vastavate väärtuste otsimiseks kuluvat aega. See võib aeglustada tulevaste võtmete räsimist, kuna enamik räsifunktsioone otsib tavaliselt massiivi järgmist saadaolevat asukohta. Kui suur väärtuste klaster on juba määratud, võtab uue võtme jaoks määramata väärtuse otsimine tavaliselt palju kauem aega.

Koormustegur on teine ​​mõiste, mis on seotud räsifunktsiooni tõhususega; koormustegur on juba olemasolevate räsimiste arv räsitabelis vastava massiivi üldise suuruse suhtes. Tavaliselt määratakse see juba määratud võtmete arvu jagamisel vastava massiivi suurusega. Koormusteguri suurenedes säilitab hea räsifunktsioon tavaliselt konstantse kokkupõrgete ja klastrite arvu kuni teatud punktini. Sageli saab seda läve kasutada selleks, et määrata, kui tõhus on räsifunktsioon teatud arvu võtmetega ja millal võib olla vaja uut räsifunktsiooni.

Paljud arvutiteaduste teadlased on püüdnud luua täiuslikku räsifunktsiooni – sellist, mis ei tekita kokkupõrkeid ega klastreid, arvestades kasvavat koormustegurit. Teoreetiliselt on täiusliku räsitabeli loomise võti luua täiuslik räsifunktsioon. Üldiselt usuvad teadlased, et täiuslikul räsifunktsioonil peaks olema pidev jõudlus – kokkupõrgete ja klastrite arv – suureneva koormusteguriga. Halvimal juhul võimaldaks täiuslik räsifunktsioon siiski pidevat räsimist ilma läve saavutamata.