Hashtabeller

Hashing

• Hashtabeller
• Hash-funksjoner
• Kollisjonshåndtering
• Hash-funksjoner og Hash-tabeller i Java API

Hashing er en effektiv måte å strukturere en mengde elementer når vi er avhengige av så rask søketid som mulig. Under visse antagelser vil hashing gi oss søketider av konstant orden, noe som i utgangspunktet strider mot den teoretiske beste søketid, dvs. logaritmisk (jfr. binærsøk).

Hashing er svært mye brukt i praksis, så mye at alle Javaobjekter har en metode som de arver fra Object som heter int hashCode(). På denne metoden er det mulig å lage hashstrukturer av alle typer Javaobjekter.

Vi ser på prinsippene som ligger til grunn for bruk av hashtabeller, hashfunksjoner og ulike former for kollisjonshåndtering.

Hashtabeller

• Effektiv måte å strukturere en mengde elementer når vi er avhengige av så rask søketid som mulig. Under visse antagelser vil hashing gi oss søketider av konstant orden.
• Ingen støtte for operasjoner som finnMinste/finnStørste, eller utskrift av tabellen i sortert rekkefølge.
• D.v.s. hashtabeller og søketrær har ulike egenskaper og anvendelser.
• Eksempler på anvendelser:
  • Kompilatorer bruker hashtabeller til å holde orden på deklarerte variabler i kildekoden (symboltabell).
  • Stavekontroller

Idé

Lagrer elementene i en tabell, og lar en del av verdien til hvert element - kalt nøkkel - bestemme posisjonen i tabellen.

Eksempel

Anta at vi skal lagre informasjon om 10 personer. Hvis hver person har en entydig id mellom 0 og 9 kan vi enkelt lagre dataene i en tabell med plass til 10 elementer ved å la personenes id bestemme tabellposisjonen.

Når vi skal søke etter en person, kan vi bare slå opp i tabellen med personens id som indeks.

Hashfunksjoner

En hashfunksjon er en funksjon som gitt et objekt og tabellstørrelse tilordner et heltall som skal kunne brukes som som indeks i tabellen, d.v.s. ligger i intervallet 0-n-1.

En god hashfunskjon skal:

• Være rask rask å beregne
• Kunne gi alle mulige verdier fra 0-n-1
• Gi en god fordeling utover tabellindeksene

Eksempel:

En teknikk som beskrives i læreboka er såkalt folding, hvor nøkkelen deles opp i flere deler som deretter legges sammen, evt etterfulgt av divisjon/ utrrekk av siffere for å få en indeks til tabellen.

Vi prøver teknikken på input-sekvens: 1983, 2312, 6543, 2134, 3498, 7654, 1234, 5678, 6789 og tabell med størrelse 13.

Perfekte hashfunksjoner

• n objekter
• tabell med n plasser
• Den perfekte hashfunskjonen sørger for at alle nøkkelverdiene gir forskjellige indekser, d.v.s. at vi ikke får kollisjoner.
• I praksis søker vi funksjoner som gir en så jevn fordeling som mulig.
• En hashfunksjon består som regel av to deler:
  • Del 1 tilordner et (stort) heltall til objektet
  • Del 2 finner posisjonen i tabellen, f.eks. ved bruk av %-operatoren.

Heltall som nøkler

Rest etter heltallsdivisjon med n (tabellens lengde), d.v.s.

		k=nokkelverdi%n
	

gir et resultat i intervallet 0-n-1.

Det er en fordel om tabellens lengde er et primtall.

Strenger som nøkler

Bruker gjerne ascii/unicode-verdiene til et utvalg eller alle tegnene i strengen til å generere hash-kodene. Nedenfor 2 eksempler. Hvor godt vil disse funksjonene spre nøklene hvis vi har som utgangspunkt at nøklene er max 8 tegn og består av tegn i det engelske alfabetet (asciiverdi max 127) og at tabellen har plass til over 10.000 elementer?

hash1

    public static int hash1(String s, int tabellLengde){        
        int hashKode= 0; 
        
        for (int i=0; i<s.length(); i++)
            hashKode += s.charAt(i); 
        
        return hashKode%tabellLengde; 
    }
    

hash2

    
    public static int hash2(String s, int tabellLengde){        
        return ( s.charAt(0)+27*s.charAt(1)+ 729 * s.charAt(2)) % tabellLengde; 
    }
    

hashCode() i klassen Object

Metoden hashCode() i klassen Object arves av alle klasser. Den returnerer et heltall som er basert på minneplasseringen til objektet. Det betyr i praksis at to objekter med samme innhold vil returnere forskjellige hashkoder.

Det er derfor en fordel å overstyre denne metoden for klasser som skal brukes i hashtabeller. Metodens signatur:

 
	public int hashCode()
	

Følgende regler må overholdes når vi lager egne versjoner av hashCode:

1. hashCode() brukt på samme objekt mer enn en gang i løpet av samme kjøring skal returnere samme verdi.
2. Hvis to objekter er like slik det er definert av klassen equals, skal hashCode returnere samme verdi for disse to objektene.
3. Ulike objekter (igjen mhp. equals-metoden) trenger ikke å få ulike verdier fra hashCode (men det er en fordel om de får de, mhp. å unngå kollisjoner).

hashCode() i klassen String

Strenger brukes ofte som nøkler i hashtabeller. Klassen String har definert sin egen versjon av hashCode-metoden. Denne metoden tilordner altså et heltall til hvert String-objekt.

Denne metoden deler strengen opp i enklet-tegn, og basert på kodene til tegnene i strengen konstrueres et nytt, stort heltall.

Hvis s er en tabell som inneholder de ntegnene i strengen, beregnes koden på følgende måte:

s[0]*37^n-1 + s[1]*37^n-2 + ...+s[n-1],

det vil si at hvert tegn inngår som om det skulle vært et siffer i et tallsystem med 37 som grunntall.

hashCode i klassene Integer og Double

Wrapper-klassene Integer og Double har også sine egne versjoner av hashCode-metoden, og disse returnerer tallverdien som er "pakket inn" i objektet.

Hashtabeller i Java Collections API

• Finnes flere implementasjoner av hashtabeller, blant andre
  • HastSet
  • HashMap
• Alle implementasjonene baserer seg på resultatet fra hashCode-metoden til objektene som lagres. Dette heltallet prosseseres ved å finne rest etter heltallsdivisjon med tabellens lengde for å produsere en indeks som ligger innenfor tabellen.

Hashtabeller i Java Collections API

• Finnes flere implementasjoner av hashtabeller, blant andre
  • HastSet
  • HashMap
• Alle implementasjonene baserer seg på resultatet fra hashCode-metoden til objektene som lagres. Dette heltallet prosseseres ved å finne rest etter heltallsdivisjon med tabellens lengde for å produsere en indeks som ligger innenfor tabellen.

Eksempel 1

Bruker Object sin hash-metode:

/*
 * Person1.java
 */

package hashing;

import java.util.HashSet;

public class Person1 {

    private int id; 
    private String navn; 
    
    
    public Person1(int id, String navn) {
        this.id = id; 
        this.navn=navn; 
    }
    
    public String toString() {
        return ""+id+", "+ navn;
    }
    
    public static void main(String [] args)    {
        Person1 p1 = new Person1(4168, "Emma");
        Person1 p2 = new Person1(3209, "Albert");
        Person1 p3 = new Person1(4168, "Emma"); 
        
        
        // Skriver ut hash-kodene: 
        System.out.println("p1.hasCode()=" + p1.hashCode() +
                "\tp2.hashCode()=" + p2.hashCode()+
                "\tp3.hashCode()=" + p3.hashCode());
        
        // Legger inn i HashSet: 
        HashSet<Person1> h = new HashSet<Person1>(); 
        h.add(p1);
        h.add(p2);
        
        
        // S��ker etter person: 
        if (h.contains(p3))
            System.out.println(""+p3 + " finnes!");
        else 
            System.out.println(""+p3 + " finnes ikke!");
            
        
    }
    
}

Eksempel 2

Overstyrer hashCode-metoden til Object og gir den eget innhold:

/*
 * Person2.java
 */

package hashing;

import java.util.HashSet;

public class Person2 {

    private int id; 
    private String navn; 
    
    
    public Person2(int id, String navn) {
        this.id = id; 
        this.navn=navn; 
    }
    
    // Overstyrer hashCode fra klassen Object:    
    public int hashCode(){
        return id;
    }
                
    // Overstyrer equals fra klassen Object: 
    public boolean equals(Object rhs){
        Person2 p = (Person2)rhs;
        return id == p.id;
    }
    
    public String toString() {
        return ""+id+", "+ navn;
    }
    
    public static void main(String [] args)    {
        Person2 p1 = new Person2(4168, "Emma");
        Person2 p2 = new Person2(3209, "Albert");
        Person2 p3 = new Person2(4168, "Emma"); 
        
        
        // Skriver ut hash-kodene: 
        System.out.println("p1.hasCode()=" + p1.hashCode() +
                "\tp2.hashCode()=" + p2.hashCode()+
                "\tp3.hashCode()=" + p3.hashCode());
        
        // Legger inn i HashSet: 
        HashSet<Person2> h = new HashSet<Person2>(); 
        h.add(p1);
        h.add(p2);
        
        
        // S��ker etter person: 
        if (h.contains(p3))
            System.out.println(""+p3 + " finnes!");
        else 
            System.out.println(""+p3 + " finnes ikke!");
        
    }
    
}

Eksempel 3

Bruker String sim hashCode-metode:

/*
 * Person3.java
 */

package hashing;

import java.util.HashMap;
import java.util.HashSet;

public class Person3 {
    private int id;
    private String navn;
    
    
    public Person3(int id, String navn) {
        this.id = id;
        this.navn=navn;
    }
        
    public int hashCode(){
        // Bruker String sin hash-metode: 
        return navn.hashCode();                
    }
    
    
    // Overstyrer equals fra klassen Object:
    public boolean equals(Object rhs){
        Person3 p = (Person3)rhs;
        return id == p.id;
    }
    
    public String toString() {
        return ""+id+", "+ navn;
    }
    
    public static void main(String [] args)    {
        Person3 p1 = new Person3(4168, "Emma");
        Person3 p2 = new Person3(3209, "Albert");
        
        // Skriver ut hash-kodene:
        System.out.println("p1.hasCode()=" + p1.hashCode() +
                "\tp2.hashCode()=" + p2.hashCode());                
        
        // Legger inn i HashMap:        
        HashMap<String,Person3> hm = new HashMap<String,Person3>(); 
        hm.put("Emma", p1);
        hm.put("Albert", p2);
        
        // S��ker etter person:
        if (hm.containsKey("Emma"))
            System.out.println("Emma finnes: " + hm.get("Emma"));
        else
            System.out.println("Emma finnes ikke!");        
        
        // Kan bli negativ: 
        String test = "abcdef";
        int kode = test.hashCode();
        System.out.println(""+test+" sin hashCode: " +kode );
        
        
    }        
}

Kollisjonshåndtering

• Hvis to nøkler mappes til samme stedet i en tabell, får vi det som kalles for en kollisjon.
• Det finnes flere måter å håndtere kollisjoner på. Vi skiller mellom
  1. Lukket addresering.
     Objektet plaaseres alltid på den posisjonen som returneres av hashfunksjonen.
  2. Åpen adressering.
     Hvis posisjonen som returneres av hashfunksjonen er opptatt, prøver vi alternative posisjoner helt til vi finner en som er ledig.
     • Lineær søking
     • Kvadratisk søking
     • Dobbel hashing

Lukket addresering - "separate chaining"

• Vedlikeholder tabell med lenkede lister.
• Hashfunksjonen forteller oss hvilken lenket liste et nytt element skal settes inn i (ved innsetting) eller finnes i (ved søking).
• Dårlige hashfunksjoner gir lange lister og ineffektive søk.
• Hvis hashfunksjonen er god, blir listene korte, og vi har fremdeles søketider med konstant orden.

Belastningsfaktor

Belastningsfaktoren (loadfactor) defineres som forholdet mellom antallet elementer som er lagret i hashtabellen (N) og tabellens størrelse (M) (l=N/M).

Antall operasjoner som utføres i et søk etter elementer i hashtabellen kan uttrykkes som funksjon av belastningsfaktoren.

Belastningsfaktor større enn 1 betyr at tabellen er full, og at lengden på noen av listene kan være lange hvis ikke hashfunksjonen som benyttes er optimal. Da vil søkene gå tregt.

Hvis man ikke på forhånd vet størrelsen på datasettet som skal lagres i tabellen, utvides gjerne tabellen når belastningsfaktoren når en viss grense. Hash-klassene i Java-API-et opererer med en default belastningsfaktor på 0.75. Hvis denne grensen overskrides, utføres en rehash.

Rehashing

• Når tabellen begynner å bli full, tar operasjonene lang tid.
• Lage ny, større tabell.
• Hash-verdier for hvert element må beregnes på nytt, kan ikke bare kopiere over elementene fra den gamle tabellen. Hvorfor?
• Operasjon med lineær arbeidsmengde.

Åpen addressering

Alternativ strategi: Hvis plassen et element x ble hashet til er opptatt, legger vi det et annet sted i tabellen.

Vi prøver cellene h₀(x), h₁(x), h₂(x) , hvor h_i(x) = (hash(x) + f(i))%n, f(0) =0 .

hash er hashfunksjonen, og funksjonen f bestemmer hvor elementet skal legges når vi får en kollisjon.

Lineær søking

• Hvis nytt element hashes til allerede okkupert posisjon i tabellen, plasseres den i nærmeste tomme celle.
• Svarer til f(i) =i
• Starter i posisjonen etter den som elementet ble hashet til, og søker sekvensielt til vi finner en tom posisjon. Når vi slutten på tabellen uten å finne en tom celle, starter vi på begynnelsen igjen (wraparound). Plasserer elementet i den tomme cellen.
• Søk utføres på tilsvarende måte. Vi starter i posisjonen elementet ble hashet til. Finner vi ikke elementet vi søker etter, leter vi videre helt til vi enten finner elementet eller en tom celle.
• Problem: Har en tendens til å ende opp med "klynger" av elementer", som gjør at operasjonene for innsetting/søk blir lite effektive
• Kan ikke slette elementer på vanlig måte. Hvorfor?

Åpen adressering - kvadratisk søking

• Samme prinsipp som for lineær søking, men bruker kvadratiske hopp.
• Eksempel: f(i) = i ²
• Hvis objektet hashes til posisjon i, leter vi først i posisjon i+1, deretter posisjon i+4, i+9, i+16 osv. Generelt posisjon i+k² , for k=1, 2, 3,....
• Ingen garanti for å finne en ledig posisjon på denne måten når tabellen er mer enn halvfull. Lengden på tabellen bør være et primtall!

Dobbel hashing

• Bruker en sekundær hashfunksjon når den primære resulterer i en kollisjon
• Eksempel: f(i) = i* hash₂(x), hash₂(x) = 7-x%7

Hashtabeller vs. binære søketrær

1. Gjennomsnittlig arbeidesmengde for innsetting og søk i BST er O(logN). For hashtabeller er den O(1).
2. BST har flere muligheter enn innsetting og søk, f.eks. finne minste/største element.
3. Sortert input gjør BST skjeve. Balansert BST komplisert struktur, dyr å implementere.
4. Hvis vi ikke har behov for sortert/ordnet output, og hvis input-data er sortert, er hashtabeller et godt alternativ.

Hashfunksjoner brukt i andre sammenhenger

• Autentisering ved hjelp av passord:
  1. Når det opprettes passord, lagres hashkoden til passordet.
  2. Selve hashfunksjonen er kjent.
  3. Når du logger inn, kjøres passordet gjennom hashfunksjonen, og hashkoden sammenliknes med det som ligger på fil.
  4. For at dette skal være sikkert, må man ikke kunne regne seg tilbake til passordet dersom man kjenner hashkoden.
  5. Hashfunksjoner som fungerer på denne måten kalles kryptografiske hashfunksjoner.
• Kontroll av integritet
  1. Brukes til å kontrollere at en mengde data, for eksempel en fil, ikke er endret (med vilje (ondsinnet) eller ved et uhell (feil på disk, overføringsfeil,...).
  2. Regner ut en hashkode til originalen. Regner ut hashkoden til det som skal være likt og sammenlikner.
  3. For at dette skal virke, må sannsynligheten for kollisjoner være liten. For å unngå ondsinnede feil, må den i tillegg være kryptografisk.

Brukt på disse måtene kalles gjerne hashkodene for sjekksummer eller "digests" (sammendrag).