Föreläsning 14: Hashning

Idén med hashning

Binärsökning i en ordnad vektor går visserligen snabbt, men sökning i en hashtabell är oöverträffat snabbt. Och ändå är tabellen helt oordnad (hash betyder ju hackmat, röra). Låt oss säga att vi söker efter Erik i en hashtabell av längd 10000. Då räknar vi först fram hashvärdet för ordet Erik med hjälp av en hashfunktion. Resultat:
"Erik".hashCode() -> 2168495
Hashvärdets rest vid division med 10000 beräknas nu
2168495 % 10000 -> 8495
och när vi kollar hashtabellens index 8495 hittar vi ordet Erik just där!

Hur kan detta vara möjligt? Ja, det är inte så konstigt egentligen. När Erik skulle läggas in i hashtabellen gjordes samma beräkning och det är därför han lagts in just på platsen med index 8495. Hur hashfunktionen räknar fram sitt stora tal spelar just ingen roll. Huvudsaken är att det går fort, så att inte den tid man vinner på inbesparade jämförelser äts upp av beräkningstiden för hashfunktionen.

Komplexiteten för sökning

Linjär sökning i en oordnad vektor av längd N tar i genomsnitt N/2 jämförelser, binär sökning i en ordnad vektor log N men hashning går direkt på målet och kräver bara drygt en jämförelse. Varför drygt? Det beror på att man aldrig helt kan undvika krockar, där två olika namn hamnar på samma index.

Dimensionering av hashtabellen

Ju större hashtabell man har, desto mindre blir risken för krockar. En tumregel är att man bör ha femtio procents luft i vektorn. Då kommer krockarna att bli få. En annan regel är att tabellstorleken bör vara ett primtal. Då minskar också krockrisken som vi ser i följande exempel.

Hashfunktionen

Oftast gäller det först att räkna om en String till ett stort tal. I Java gör man ingen skillnad på en bokstav och dess nummer i teckentabellen (alfabetet), därför kan ABC uppfattas som 656667. Det man då gör är att multiplicera den första bokstaven med 10000, den andra med 100, den tredje med 1 och slutligen addera talen. På liknande sätt gör metoden hashCode(), men med 256 i stället för 100 - datorn har nämligen lika lätt att multiplicera med tvåpotenser som vi har med tiopotenser.

Om man vill söka på datum eller personnummer kan man använda det som stort heltal utan särskild hashfunktion. Exempel: sexsiffriga datum kan hashas in i hashvektorn med 990323 % size. En olämplig storlek är 10000, ty
990323 % 10000 --> 323
och vi ser att endast 366 av de 10 000 platserna kommer att utnyttjas. Det visar sej att primtalsstorlek ger bäst spridning.

Krockhantering

Det naturliga är att lägga alla namn som hashar till ett visst index som en länkad lista (krocklista). Om man har femtio procents luft i sin vektor blir krocklistorna i regel mycket korta.

Den andra idén är att vid krock lägga posten på första lediga plats. En nackdel blir att man sedan inte kan ta bort poster utan att förstöra hela systemet. En fördel är att man slipper alla referenser.

Javaklassen Hashtable

Hashtable som finns i paketet java.util är en utmärt och lättskött klass med två metoder: put() och get(). Första parametern till put() är söknyckeln, till exempel personens namn. Andra parametern är ett objekt med alla tänkbara data om personen. Metoden get() tar söknyckeln som indata och returnerar dataobjektet om nyckeln finns i hashvektorn, annars returneras null. Exempel:
    Hashtable table = new Hashtable(359);

    // Fixar nyckel och data-objekt...

    table.put(key, data);
	
    // ...

    data = table.get(key);
Sista satsen ovan fungerar bara om objektet data har den allmänna typen Object, men oftast måste man typa om det till aktuell klass. Om objektet har skapats med new Pnyxtr() ser omtypningen ut så här:
    data = (Pnyxtr)table.get(key);

^ Upp till kurssidan.


Sidansvarig: <vahid@nada.kth.se>
Senast ändrad 30 september 2003
Tekniskt stöd: <webmaster@nada.kth.se>