Hajautustaulujen törmäysten ratkaisutekniikat

Abstract

Hajautustaulu on laajalti käytössä oleva tehokas tietorakenne, joka parhaimmillaan tarjoaa avain-arvo-parien vakioaikaista tallennusta, hakua ja poistoa. Tallennusoperaatiossa hajautusfunktiolla lasketaan tiivistearvo, jonka perusteella avain-arvo-pari tallennetaan tauluun. Mikään hajautusfunktio ei kuitenkaan ole niin hyvä, että jokainen tiivistearvo olisi ainutlaatuinen. Eri parien välillä tapahtuu väistämättä törmäyksiä eli samalle paikalle yritetään lisätä kahta eri paria. Törmäysten välttämiseksi on kehitetty erilaisia ratkaisutekniikoita.

Tässä työssä käydään läpi hajautustaulujen törmäysten ratkaisutekniikoita tavoitteena löytää tehokkaimmat vaihtoehdot tutkittujen ratkaisujen joukosta. Tekniikoista valikoitiin mukaan joitakin yleisesti tunnettuja vanhempia sekä vähemmän tunnettuja uudempia tekniikoita. Työhön valitut tekniikat ovat lineaarinen kokeilu, hyppytekniikat, käkihajautus, ruutuhyppelyhajautus, pariton-parillinen hajautus, erillisketjutus sekä taulukkorakenne. Työssä esitetään tekniikoiden perustoiminta ja käydään läpi kirjallisuuskatsauksen keinoin niiden suoriutuminen verrattuna toisiinsa eri tahojen suorittamissa kokeissa. Lähteinä työssä on käytetty sekä eri tekniikoiden alkuperäisjulkaisuja että yleisesti eri tekniikoita esitteleviä ja vertailevia tutkimuksia. Työ ei ota kantaa rinnakkaisiin hajautustauluihin, vaan keskittyy hajautustauluihin, jotka eivät huomioi rinnakkaisuutta.

Tutkimuksesta ei saatu suoraan selvitettyä parasta ratkaisutekniikkaa. Tehokkuus riippuu monesta tekijästä eikä parhaiten pärjänneiden tekniikoiden välillä ole suoritettu kokeita. Tuloksista voidaan kuitenkin todeta parhaiten pärjänneiksi tekniikoiksi ruutuhyppelyhajautus, pariton-parillinen hajautus, erilllisketjutus sekä taulukkorakenne. Näistä taulukko pärjää tekstisyötteiden osalta parhaiten, mutta ruutuhyppelyn sekä pariton-parillinen hajautuksen ja erillisketjutuksen paremmuudesta ei saatu selkoa. Tässä työssä annetaan ehdotukseksi tehdä jatkotutkimusta keskittyen vain näihin algoritmeihin ja selvittää, missä olosuhteissa mikäkin on tehokkain vaihtoehto.