From: Mikko J Rauhala Date: Tue, 8 May 2001 15:54:00 +0300 (EEST) -------------------------------------------------------------------------- 2a) Mikä ja millainen on ns. hajautin? Millä perusteilla hajauttimen hyvyyttä voidaaan arvioida? Anna esimerkkejä huonoista ja hyvistä hajauttimista. -------------------------------------------------------------------------- Arvostelusta: Tehtävästä annettiin pisteitä hajauttimen olemuksen yleisen ymmärtämisen esilletuonnin perusteella. Olennaisia asioita esimerkiksi seuraavat: Hajautusfunktio eli hajautin on kuvaus h: avaimet -> [ 0,...,alue-1] Täten hajautinta voidaan käyttää avaimen kotiosoitteen (indeksin h(avain)) löytämiseen hajautustaulussa, jonka koko on ym. alue. Hyvä hajautin kuvaa avaimet mahdollisimman tasaisesti indekseille 0, .., alue-1. Tähän liittyy luonnollisesti se, että hajauttimen tulisi käyttää koko hajautusaluetta hyväkseen, ts. hajauttimen tulisi tavoittaa kaikki indeksit. Hajauttimen hyvyys riippuu sekä itse funktiosta että avainten joukon ominaisuuksista. Lisäksi hajautusfunktion arvon tulisi olla toki itsessään nopea laskea. Hyvistä ja huonoista hajauttimista on käynyt esimerkeiksi vaikkapa suositut merkkijonohajauttimet, joissa merkkijono hajautetaan 1) ensimmäisen merkin mukaan (huono; pieni saavutettava alue, epätasainen) 2) kaikkien merkkikoodien summan mukaan (parempi, joskin anagrammit hajautuvat samoin eikä suurta aluetta saada kovin hyvin täytettyä tälläkään) 3) kaikkien tai n:n ensimmäisen merkkikoodin sijainnin mukaan painotetun summan mukaan (hyvä; rajoitettuna hieman heikkenee, mutta laskenta vastaavasti halventuu) Syytä on ollut esittää myös syitä, miksi mikäkin hajautin on hyvä tai huono. Lisäksi voidaan mainita, että kun hajautin perustuu jakojäännöksen laskemiseen, alueen kooksi kannattaa valita jokin alkuluku. -------------------------------------------------------------------------- 2b) Rajapintaluokka Hashable on määritelty seuraavasti: public interface Hashable { public int hash(int taulunKoko); } Suljetussa hajautuksessa käytetään lineaarista törmäyksenselvitysstrategiaa. Ohjelmoi metodi: public void insert(Hashable arvo) lisää "arvon" hajautustauluun; jos jo löytyi, mikään ei muutu Kuvaile hajautuksen toteutuksen yksityiskohtia sen verran, että operaation toteutus on ymmärrettävä. -------------------------------------------------------------------------- Täydet pisteet on saanut selkeästi ajatuksellisesti toimivasta ratkaisusta, jossa on korkeintaan lieviä syntaktisia virheitä. Pienistä mokista on yleisesti ottaen sakotettu piste jos selkeästi oikeaa ajatusta on kuitenkin taustalla nähtävissä, ja yhden pisteen on voinut saada vähän sinne päin olevasta ratkaisusta. Jos ei ole edes yrittänyt saada aikaan törmäyksenselvitystä, ei ole saanut pisteitäkään. Tyypillisiä sakotettavia virheitä ovat olleet esimerkiksi haku pelkästään kotiosoitteesta hajautustaulun loppuun tai tapauksen, jossa arvo on jo taulussa, jättäminen käsittelemättä. Esimerkkiratkaisu voisi olla vaikkapa seuraava kurssimateriaalista kopioitu insert; törmäyksenselvitys on vain muutettu alkuperäisessä mallissa olleesta neliöivästä vaadituksi lineaariseksi: private int etsiKoti(Hashable arvo) { int omaKoti = arvo.hash(taulu.length); int indeksi = omaKoti; int yrityksiä = 1; do { if (taulu[indeksi]==null || // löytyi vapaa taulu[indeksi].alkio.equals(arvo)) // löytyi haettu avain return indeksi; indeksi = (omaKoti + yrityksiä) % taulu.length; ++yrityksiä; } while (yrityksiä < taulu.length); // kaikki mahdollisuudet varmasti käytetty, ei voi mitään: throw new RuntimeException("Virhe: Hajautustaulu on täynnä!"); } public void insert(Hashable arvo) { int indeksi = etsiKoti(arvo); if (taulu[indeksi]==null) { // uusi taulu[indeksi] = new Alkio(arvo); return; } if (taulu[indeksi].poistettu) { // poistettu avain, sopii taulu[indeksi].alkio = arvo; // korvata uudella oliolla taulu[indeksi].poistettu = false; // ja tämä on syytä myös tehdä! } // jos kumpikaan ei tärpännut, arvo oli jo taulussa, ja aktiivisena }