Uppgift 4 våren 2010Uppgiften ska lämnas till din övningsledare på övningen den 19/2. Glöm inte försättsbladet (pdf) och att alla papper ska häftas samman eller lämnas in i en plastficka. För godkänt måste du ha gjort samtliga deluppgifter. Det är tillåtet att göra enstaka fel och misstag men det är viktigt att du försöker lösa samtliga uppgifter. Om du kör fast med någon uppgift så finns det som vanligt hjälp att få på labbarna. HashtabellOfta behöver man en datastruktur som kan hantera både insättningar och sökningar effektivt. Då fungerar varken vektorer eller länkade listor:
Hashtabeller finns inbyggda i Java i form
av klasserna Grundläggande idéIdén är att kombinera de bästa egenskaperna hos vektorer och listor. Ett exempel får illustrera hur detta kan gå till. Anta att vi vill lagra ungefär 1000 slumpmässigt valda positiva heltal (av typen int). En länkad lista duger inte eftersom en sökning i listan blir för dyr. Istället sprider vi ut talen över flera korta listor. Det kan vi till exempel göra genom att låta alla tal som slutar på 000 hamna i en lista, alla som slutar på 001 i en annan, och så vidare. På det sättet får vi 1000 listor. I Java skulle vi kunna deklarera en sådan datastruktur på följande sätt:
En insättning av elementet n sker i två steg: vi extraherar de tre sista sifforna, hash = n % 1000, och sätter sedan in elementet i listan table[hash] (en lista som vi eventuellt först måste skapa) med metodanropet table[hash].addFirst(n).En insättning kan alltså göras på konstant tid. En sökning efter elementet n kan implementeras så här: table[n%1000].contains(n).Eftersom talen är slumpmässigt valda så vet vi att det finns ungefär lika många element i varje lista. Det finns tusen listor och tusen element så vi kan räkna med att listan table[n%1000] innehåller få element. En sökning i listan kommer därför att gå snabbt. Vi säger att den förväntade söktiden är O(1). Den kompletta datastrukturenVi vill generalisera idén ovan så att den fungerar för mer komplicerade element som dessutom inte är slumpmässigt valda. För att datastrukturen ska bli effektiv krävs att antalet element i varje lista är litet. Antalet listor måste därför vara av samma storleksordning som antalet element. Dessutom måste elementen fördelas så att det hamnar ungefär samma antal i varje lista. Det enda vi behöver ändra är funktionen, den så kallade hashfunktionen, som väljer ut i vilken lista ett element hör hemma. Hashfunktionen i exemplet ovan är h(n) = n % 1000. Den tar ett element (positivt heltal) som indata och producerar ett tal i intervallet 0..999. En hashfunktion är en funktion h från E till 0..size-1, där E är mängden av alla möjliga element och size är antalet listor i hashtabellen. Vi vill att funktionen ska vara “slumpmässig“: det ska vara osannolikt att olika element avbildas på samma värde, det ska alltså vara ovanligt att h(e1) = h(e2) när e1 ≠ e2. Exempel på en hashfunktionJavas implementation av hashfunktion för strängar är ett bra exempel. Metoden hashCode i klassen String beräknar värdet s[0]*31n-1 + s[1]*31n-2 + ... + s[n-1]med hjälp av int-aritmetik, där s[i] är det i:te tecknet i strängen och n är strängens längd. Metoden kan användas som hashfunktion på följande sätt
där size är antalet listor i hashtabellen.
[ Notera att funktionen hashCode beror på samtliga tecken i strängen och att värdet ändras om man kastar om ordningen på tecknen i strängen. Två egenskaper man kan önska sig av en god hashfunktion. Hashtabeller i JavaJava har en inbyggd hashfunktion, hashCode, som deklareras i klassen Object och överskuggas av mera specifika implementationer i de flesta dataklasser, t.ex. String, Double och Integer. Denna metod används internt i klasserna HashMap och HashSet. Implementationen av hashCode och equals i klassen Object är, med nödvändigthet, grovt tillyxad. Om variablerna o1 och o2 refererar till objekt av klassen Object så gäller o1.equals(o2) om och endast om o1==o2, dvs om båda variablerna refererar till samma objekt. Om o1 refererar till ett objekt av klassen Object så returnerar o1.hashCode() ett värde som är entydigt bestämt av objektet o1, det skulle till exempel kunna vara adressen i minnet där objektet lagras. Om man designar egna objekt som ska lagras i en HashMap eller HashSet så vill man oftast göra nya implementationer av metoderna hashCode och equals. Det finns flera krav på dessa metoder: bland annat krävs att två objekt som är lika, när de jämförs med metoden equals, också måste ha samma hashCode. De kompletta reglerna hittar man i dokumentationen för Object. Här är ett exempel på en dataklass som implementerar dessa två metoder på ett korrekt sätt.
Notera speciellt följande egenskaper hos metoden equals som alltid måste gälla:
Jag rekommenderar att man, om möjligt, designar dataklasser så att objekten är oföränderliga (immutable): de får sitt värde i konstruktorn och detta värde kan sedan aldrig ändras. Klasserna String, Double och Integer är exempel på oföränderliga klasser. Vår klass Point har också denna egenskap. Nyckelordet final garanterar att x- och y-koordinaterna förblir oförändrade. Varning: Föränderliga dataklasser kan ställa till med många problem. Om man till exempel sätter in ett objekt i en hashtabell och därefter ändrar dess tillstånd så ändras sannolikt även hashvärdet och objektet har därmed hamnat i fel lista i hashtabellen. En sådan bugg kan vara svår att upptäcka. Skriftlig uppgiftBeräkna tidskomplexiteten i medelfall för sökning, insättning och borttagning i en
Låt n vara antalet element i datastrukturen och presentera lösningen i en tabell med tre rader och fem kolumner. Som vanligt ska du också motivera dina svar. ImplementationsuppgiftImplementera följande gränssnitt med hjälp av en hashtabell.
Hashtabellens storlek (antalet listor) ska anges när
man skapar en ny tabell. Använd gärna din implementation av
länkade listor från föregående uppgift och använd gärna metoden
Den här uppgiften bjuder på oväntade problem eftersom vektorer
och generiska typer fungerar dåligt tillsammans i Java. Det finns
två (någorlunda bra) lösningar på problemet. Antingen undviker
man vektorer och använder en
Om man hellre vill använda vektorer, till exempel av
effektivitetsskäl, så dyker det upp oväntade problem.
Man kan nämligen inte skapa en vektor av stränglistor
i Java på ett typsäkert sätt. Följande, till synes
naturliga, kod |