View All Pages

F7 Hashning, strängkopiering i C

  • kopiera strängar i C
  • hur assemblerkod ser ut
  • hur inkluderad C-kod ser ut
  • dubbellänkade listor
  • Introduktion till hashning - pythons dictionary
  • Idén med hashning
  • Komplexiteten för sökning
  • Dimensionering av hashtabellen
  • Hashfunktionen
  • Krockhantering

Jämföra sorterade filer

För att felsöka olika utdata från olika varianter av p2 kan man först sortera utdata och använda diff för att se skillnaden.

sort fil1.txt > sorted1.txt
sort fil2.txt > sorted2.txt
diff sort1.txt sort2.txt

 

Kopiera strängar i C

char * s1 = "Hej";
char * s2 = "Då";
s1 = s2;

s1 sätts att peka på samma sak som s2, någon kopiering har inte skett. Först behöver vi allokera minnet att kopiera till. Den klassiska implementationen för att kopiera ser ut så här:

char* stringcopy(char * d, char * s) // copy to destination from source 
{
  while (*d++ = *s++) ;
}

//...

char str[4];
char * s = "Hej";
stringcopy(str, s);

Funktionen stringcopy finns under namnet strcpy i <string.h> man kan även använda strncpy som inte är lika beroende av att källsträngen är avslutad med '\0'.

Assemblerkod

Man kan kompilera till assembler (maskinkod i textformat) med flaggan -S

På https://godbolt.org/ Links to an external site. kan man se hur assemblerkod ser ut i C och var hårdkodade strängar och funktioner hamnar. Koden är färgkodad så att man kan se vad en kodrad i C motsvarar i assembler

hur inkluderad C-kod ser ut

Om du kompilerar med flaggan -E så ser du hur filen ser ut efter alla #include

gcc -E mittprogram.c

Dubbellänkade listor

Dubbellänkade listor har både en previous- och next-pekare. De kostar en pekare extra men är enklare att traversera. Man måste komma ihåg att sätta både prev och next när man sätter in ett nytt element i listan samt att uppdatera båda sina grannar.

Introduktion till hashning - pythons dictionary

Med Pythons inbyggda dictionary har man möjlighet att skapa en uppslagslista. Man bygger upp den genom att lägga in nycklar och tillhörande värden:

  telefonnummer={}
  telefonnummer["Linda Kann"] = "08-7909276"
  telefonnummer["CSC-service"] = "08-790 7146"
  ---

Sedan kan man slå upp i listan:

   namn = input("Vem vill du ringa till? ")
   try:
       print("Telefonnumret är ", telefonnummer[namn])
   except KeyError:
       print(namn,"finns inte med i telefonlistan")

Här är det varken linjärsökning eller binärsökning som används för att hitta nyckeln, utan en ännu snabbare sökmetod: hashning.

Idén med hashning

Binärsökning i en sorterad lista/array/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 Lyckan i en hashtabell av längd 10000. Då räknar vi först fram hashfunktionen för ordet Lyckan och det ger detta resultat.

   hash("Lyckan") -> 1076540772

Hashvärdets rest vid division med 10000 beräknas nu

   1076540772 % 10000 -> 772

och när vi kollar hashtabellens index 772 hittar vi Lyckan just där!

Hur kan detta vara möjligt? Ja, det är inte så konstigt egentligen. När Lyckan skulle läggas in i hashtabellen gjordes samma beräkning och det är därför hon lagts in just på 772. Hur hashfunktionen räknar fram sitt 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 lista/vektor av längd N tar i genomsnitt N/2 jämförelser, binär sökning i en sorterad lista/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 det är svårt att 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 minst femtio procents luft i tabellen, dvs att

λ=antalinlagdaobjekthashtabellensstorlek=0.5λ=antalinlagdaobjekthashtabellensstorlek=0.5

 Då kommer krockarna att bli få.

Hashfunktioner

Oftast gäller det först att räkna om en sträng till ett stort tal. Funktionen ord(tkn) i Python konverterar ett tecken till motsvarande ordningsnummer.

T ex är 
ord("A") = 65 
ord("B") = 66 
ord("C") = 67 
Då kan vi räkna om strängen "ABC" till talet 656667, genom 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 hash(key) i Python men den använder 32 i stället för 100. För en binär dator är det nämligen mycket enklare att multiplicera med 32 än med 100. Här är en förenklad variant:

def hash2(s):             # Beräknar hashkoden för en sträng enligt
    result = 0            # s[0]*32^[n-1] + s[1]*32^[n-2] + ... + s[n-1]
    for c in s:                    
        result = result*32 + ord(c) 
    return result

Om nyckeln är ett datum eller personnummer behöver vi inte konvertera till tal.

  • Man kan "vika" talet genom att dela upp det i lika stora delar som sedan summeras, t ex 20+17+09+11 = 57,
  • Eller kvadrera det:20170911² = 406865650569921 och plocka ut de mittersta siffrorna: 650.

En hashfunktion bör ha god spridning - vi vill inte att många nycklar ska ge samma hashvärde. Med programmet barchart.py Download barchart.py med tillhörande datafil slumpnamn30.txt Download slumpnamn30.txt kan du experimentera med fördelningen för olika hashfunktioner.

Modulo

I kursen använder vi modulo för att få hashfunktionens tal att passa in i vektorn.

Exempel: Datum kan hashas in i hashtabellen med 20170911 % size

Krockhantering

En idé är att lägga alla namn som hashar till ett visst index som en länkad krocklista. Om man har femtio procents luft i sin hashtabell blir krocklistorna i regel mycket korta. Krocklistorna behandlas enklast som stackar, och hashtabellen innehåller då bara topp-pekarna till stackarna.

Linjär probning

En annan metod är att vid krock lägga noden på första lediga plats. Är det tomt där, tittar man på nästa, osv. Detta kallas linjär probning. En fördel med denna metod är att man slipper alla pekare. En stor nackdel är att om det börjat klumpa ihop sej någonstans har klumpen en benägenhet att växa. Detta kallas för klustring.

Här finns en animation (Länkar till en externa sida.)Länkar till en externa sida.

Kvadratisk probning

I stället för att leta lediga platser som ligger tätt ihop kan man därför göra större hopp. Hopplängden bör då variera. Ett sätt är att "hoppa fram" i jämna kvadrater, så kallad kvadratisk probning. Om hashfunktionen gav värdet h tittar man i ordning på platserna: h+1, h+4, h+9, ... . Överstiger värdena hashtabellens storlek använder man resten vid heltalsdivision precis som vid beräkningen av h. Om tabellstorleken är ett primtal. och tabellen är som mest halvfull, så riskerar man inte att fastna i en evig hopprunda.

Dubbelhashning

Ytterligare ett sätt att lösa krockproblemet är dubbelhashning. I denna variant räknas nästa värde fram med en annan hashfunktion som tar som indata den första hashfunktionens värde. För att hitta efterföljande platser låter man den andra hashfunktionen få sitt förra värde som indata.

Både kvadratisk probning och dubbelhashning ger goda prestanda om hashtabellen har femtio procent luft. En nackdel med båda metoderna är att man inte enkelt kan ta bort noder utan att förstöra hela systemet.

En fördel med probning är att de kan vara med cache-effektiva, man får färre cache-missar. Datorarkitektur som cache ingår inte i kursen men är ett debatterat ämne för hur hashtabeller ska implementeras och kan vara bra att känna till.