bild
Skolan för
elektroteknik
och datavetenskap

Uppgift 4 våren 2010

Uppgiften 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.

Hashtabell

Ofta behöver man en datastruktur som kan hantera både insättningar och sökningar effektivt. Då fungerar varken vektorer eller länkade listor:

  • i en osorterad vektor tar sökning linjär tid;
  • i en sorterad vektor kan man använda binärsökning som är mycket effektiv, men då tar istället insättningar linjär tid;
  • i en länkad lista kan man göra insättningar på konstant tid, men sökning blir linjär.
En hashtabell är den enklaste datastruktur som löser detta problem effektivt.

Hashtabeller finns inbyggda i Java i form av klasserna HashMap och HashSet samt metoderna equals och hashCode i klassen Object. För att kunna använda dessa effektivt behöver man förstå hur en hashtabell fungerar. Det ska vi lära oss i den här uppgiften.

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:

LinkedList<Integer>[] table = new LinkedList<Integer>[1000];

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 datastrukturen

Vi 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 hashfunktion

Javas 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
h(s) = Math.abs(s.hashCode() % size),
där size är antalet listor i hashtabellen.

[h(s) = Math.abs(s.hashCode()) % size är fel. Guldstjärna till den som kan räkna ut varför.]

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 Java

Java 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.

public final class Point {
    private final int x;
    private final int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override public boolean equals(Object o) {
        if (!(o instanceof Point))
            return false;
        Point p = (Point) o;
        return p.x == x && p.y == y;
    }

    @Override public int hashCode() {
        return 31*x + y;
    }

    @Override public String toString() {
	return "(" + x + "," + y + ")";
    }
}

Notera speciellt följande egenskaper hos metoden equals som alltid måste gälla:

  • Den är reflexiv: o1.equals(o1).
  • Den är symmetrisk: om o1.equals(o2)o2.equals(o1).
  • Den är transitiv: om o1.equals(o2) och o2.equals(o3)o1.equals(o3).
  • o1.equals(null) returnerar alltid false.
Dessutom måste alltså o1.hashCode()==o2.hashCode() om o1.equals(o2).

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 uppgift

Beräkna tidskomplexiteten i medelfall för sökning, insättning och borttagning i en

  • osorterad vektor,
  • sorterad vektor,
  • osorterad enkellänkad lista,
  • sorterad enkellänkad lista,
  • hashtabell (du kan anta att antalet element är lika med hashtabellens storlek).

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.

Implementationsuppgift

Implementera följande gränssnitt med hjälp av en hashtabell.

/**
 * An interface describing a dictionary of strings.
 * The dictionary cannot contain duplicate strings.
 * 
 * @author Stefan Nilsson
 * @version 2008-01-13
 */
public interface StringDictionary { 
    /**
     * Adds the given string to this table.
     * Returns <code>true</code> if the dictionary
     * did not already contain the given string.
     *
     * Complexity: O(1) expected time.
     */
    public boolean add(String s);

    /**
     * Removes the given string from this dictionary
     * if it is present. Returns <code>true</code> if
     * the dictionay contained the specified element.
     *
     * Complexity: O(1) expected time.
     */
    public boolean remove(String s);

    /**
     * Returns <code>true</code> if the string is
     * in this dictionary.
     *
     * Complexity: O(1) expected time.
     */
    public boolean contains(String s);
 }

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 hashCode() som finns i alla Javaklasser (den deklareras i java.lang.Object) för att implementera din hashfunktion. Som vanligt ska du skriva och lämna in testkod.

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 ArrayList i stället. Då kan man deklarera och skapa hashtabellen på följande sätt:

    ArrayList<List<String>> table = new ArrayList<List<String>>();

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 new LinkedList<String>[size] fungerar inte. StringHash.java är en mall som visar hur man gör för att komma runt problemet.

Copyright © Sidansvarig: Stefan Nilsson <snilsson@nada.kth.se>
Uppdaterad 2010-02-16