Nada

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 Henrik i en hashtabell av längd 10000. Då räknar vi först fram hashfunktionen för ordet Henrik och det ger detta resultat.
"Henrik".hashCode() -> 831180685
Hashvärdets rest vid division med 10000 beräknas nu
831180685 % 10000 -> 685
och när vi kollar hashtabellens index 685 hittar vi Henrik just där!

Hur kan detta vara möjligt? Ja, det är inte så konstigt egentligen. När Henrik skulle läggas in i hashtabellen gjordes samma beräkning och det är därför han lagts in just på 685. 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 ASCII-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 1000 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 pekare.

Javaklassen Hashtable

Hashtable är en utmärt och lättskött klass med två anrop, 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 har söknyckeln som indata och returnerar dataobjektet om nyckeln finns i hashvektorn, annars returneras null.
    Hashtable table = new Hashtable(359);
      - - -
    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 det har skapats med new Pnyxtr() ser omtypningen ut så här:
    data=(Pnyxtr)table.get(key);

Sidansvarig: <henrik@nada.kth.se>
Senast ändrad 14 mars 2000
Tekniskt stöd: <webmaster@nada.kth.se>