bild
Skolan för
elektroteknik
och datavetenskap

Hashtabeller

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[] table = new LinkedList[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 “slumpmässig“ funktion.

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: x.equals(x).
  • Den är symmetrisk: om x.equals(y)y.equals(x).
  • Den är transitiv: om x.equals(y) och y.equals(z)x.equals(z).
  • x.equals(null) returnerar alltid false.
Dessutom måste alltså x.hashCode()==y.hashCode() om x.equals(y).

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.

Copyright © Sidansvarig: Stefan Nilsson <snilsson@nada.kth.se>
Uppdaterad 2009-08-03