Nada

LÖSNING TILL DATALOGIÖVNING 8

DIMENSIONERING AV HASHTABELL

Om ni är n personer i gruppen bör hashtabellen vara minst 50% större och gärna ett primtal. Om man inte tar primtal kan det ibland bli delar av tabellen som inte utnyttjas; exempel visades på föreläsningen. Lämplig hashfunktion kan till exempel vara (year+month*day)%size. Se till att inte välja något så svårt att räknare krävs. För bok på tavlan över krockar. Krockmax bör helst vara 2 men 3 är också OK. Annars kanske man skulle välja en annan storlek på tabellen.

KROCKTESTPROGRAM

Raderna i datafilen ser ut så här:
420119-0818 Eriksson, Henrik
och därför krävs Mio.SkipBlanks-anropet. Notera att hashCode() kan ge negativt värde och då blir det negativt även efter det att man gjort %m.
import java.io.*;   //Här finns klassen BufferedInputStream
import java.util.*; //Här finns klassen Hashtable som används i Hash2
class Hash1                                                         { 
  public static void main(String[] args)                            {
    BufferedInputStream fil = Mio.OpenRead(args[0])                 ; 
    System.out.print("Hashtabellens storlek: ")                     ;
    int m=Mio.GetInt()                                              ;
    int[] table = new int[m]                                        ;
    for(int i=0;i<m;i++) table[i]=0                                 ;
    int krockmax=0                                                  ;
    while(!Mio.EOF(fil))                                            {
      String pnr=Mio.GetWord(fil)                                   ;
      Mio.SkipBlanks(fil)                                           ;
      String name=Mio.GetLine(fil)                                  ;
      int index=pnr.hashCode() % m                                  ;
      if (index<0) index=-index                                     ;
      if(++table[index]>krockmax) krockmax++                        ;}
    System.out.println("Krockmax: "+krockmax)                       ;}}

HASHAD DATABAS

Standardklassen Hashtable är jätteenkel och bra. Metoden put(Object key, Object data) tar gärna emot ett stort dataobjekt, inte bara en String som i vårt exempel. Men därför måste man typa dataobjektet till String när man hämtar tillbaka det med get(key). I nästan alla sammanhang är söknyckeln key en String, så man behöver inte gå in på andra fall.
class Hash2                                                         { 
  public static void main(String[] args)                            {
    BufferedInputStream fil = Mio.OpenRead(args[0])                 ; 
    Hashtable deltagare = new Hashtable(359)                        ;
    while(!Mio.EOF(fil))                                            {
      String pnr=Mio.GetWord(fil)                                   ;
      Mio.SkipBlanks(fil)                                           ;
      String name=Mio.GetLine(fil)                                  ;
      deltagare.put(pnr,name)                                       ;}
    while(true)                                                     {
      System.out.print("Personnummer: ")                            ;
      String pnr=Mio.GetLine()                                      ;
      String name=(String)deltagare.get(pnr)                        ;
      if(name==null) System.out.println("Finns inte!")              ;
      else System.out.println(name)                                 ;}}}