p4

  • Inlämningsdatum 31 mar 2021 av 23.59
  • Poäng 1
  • Lämnar in en filuppladdning
  • Filtyper c, h och txt

p4

1 Hashtabell i C

Implementera en hashtabell i C som kan lagra strängar. Den givna koden använder C99 syntax för kommentarer och för att slippa varningar så kan du kompilera med flaggan -std=C99 Den senaste C-standarden är från 2018 men den är inte så vanlig än så länge. Många värden är hårdkodade i den givna koden, ringa in och notera vad som är hårdkodat.

1.1 Modifiera dubbellänkade listan

Du behöver modifiera den dubbellänkad listan i P3 och använda den för krockhantering.

Ändra så att key är en char *

struct nod {
    char key[512];
    char value[512];
    struct nod * next;
    struct nod * prev;
};
typedef struct nod Nod;

Ändra implementationen av search och printnod då key är av typen char *. Använd strcmp i search.

Testa din kod med några enkla tester.

1.2 Hashfunktionen tilpro_hash

Hashfunktionen tilpro_hash är given nedan. Koden använder en global variabel för hashstorlek. Storleken ska anges som en två-potens.


//const int HASHVEKSIZE = 1         // 2 upphöjt till 0, hashtabellen beter sig som en länkad lista.
//const int HASHVEKSIZE = 4         // 2 upphöjt till 2, överskådlig storlek för test av kod t.ex.

//const int HASHVEKSIZE = 65536     // 2 upphöjt till 16
//const int HASHVEKSIZE = 131072    // 2 upphöjt till 17
//const int HASHVEKSIZE = 262144    // 2 upphöjt till 18 
//const int HASHVEKSIZE = 524288    // 2 upphöjt till 19 
const int HASHVEKSIZE = 1048576;    // 2 upphöjt till 20, ungefär 1 miljon
//const int HASHVEKSIZE = 2097152   // 2 upphöjt till 21
//const int HASHVEKSIZE = 4194304   // 2 upphöjt till 22

uint32_t tilpro_hash(const char * s) {
  uint32_t hash = 0;
  size_t i = 0;
  while (s[i] != '\0') {
    hash += s[i++];
    hash += hash << 10;
    hash ^= hash >> 6;
  }
  hash += hash << 3;
  hash ^= hash >> 11;
  hash += hash << 13;

  hash = hash & ( HASHVEKSIZE - 1 );
  return hash;
}

På sista raden AND Links to an external site.-as alla bitar större än hashstorleken med noll och sätts till noll. Det är viktigt att du förstår denna rad för  att förstå varför storleken ska sättas till en 2-potens.

hash = hash & ( HASHVEKSIZE - 1 );

Exempel:

hash 01001110111011011011110111111010
HASHVEKSIZE - 1 00000000000011111111111111111111
bitand ger 00000000000011011011110111111010

Du behöver inte kunna redogöra för detaljerna i den övriga hashfunktionskoden men för den intresserade görs följande bitoperationer.

<< skiftar bitar åt vänster, lägger på nollor d.v.s multiplicerar med 2 ett antal gånger
>> skiftar bitar åt höger, tar bort de lägsta bitarna d.v.s. heltalsdividierar med 2 ett antal gånger
^= XOR Links to an external site. med sig själv och högerledet

Du kan skapa din hashtabell genom att deklarera en array av dubbellänkade listnoder.

Nod ** myhashvek = malloc(sizeof(Nod *) * HASHVEKSIZE);

Observera att du behöver den globala variabeln HASHVEKSIZE och kan behöva deklarera den som extern.

extern const int HASHVEKSIZE;

1.3 Hashtabellens gränssnitt

Gränssnittet till hashtabellen är put, get, init. Du får utöka med mer funktionalitet om du vill.

  • void put(Nod ** hashtable, char * key, char * value)

    put tar hashtabellen och två strängar key och value som parametrar. put räknar ut hashindex för key med tilpro_hash och söker där i den dubbellänkade listan efter key. Om ingen sådan Nod påträffas läggs en ny Nod med key och value in i listan om däremot en Nod med key påträffas ska value ändras (använd strcpy)

  • char * get(Nod ** hashtable, char * key)

    get tar hashtabellen och en sträng key som parametrar och returnerar NULL om key inte finns annars returneras värdet associerat med key. get räknar ut hashindex för key med tilpro_hash och söker där i den dubbellänkade listan efter key.

  • void init(Nod ** hashtable)

    init itererar genom hashtabellen och sätter alla index till NULL. Det går att lösa med en for-loop som går från 0 till HASHVEKSIZE men det finns även en funktion memset som kan användas.

1.4 Headerfil hashfunc.h

Headerfilen för den dubbellänkade listan kan se ut så här:

#ifndef tproHASHFUNC_H
#define tproHASHFUNC_H

#include <stdint.h>
#include "lista.h"    // en headerfil för en modifierad dubbellänkad lista p3

uint32_t tilpro_hash(const char * s) ;

void put(Nod ** hashtable, char * key, char * value); 
char * get(Nod ** hashtable, char * key); 

void init(Nod ** vek);

#endif

1.5 Implementationsfil hashfunc.c

Skriv koden för hashfunktionerna put, get, init i en C-fil som inkluderar header-filen.

#include "hashfunc.h"
#include <stdint.h>
#include <string.h>
#include <stdlib.h>

const int HASHVEKSIZE = 1048576;    // 2 upphöjt till 20 ungefär 1 miljon
//const int HASHVEKSIZE = 2097152     // 2 upphöjt till 21
//const int HASHVEKSIZE = 4194304     // 2 upphöjt till 22

uint32_t tilpro_hash(const char * s) {
  uint32_t hash = 0;
  //...
}

void put(Nod ** hashtable, char * key, char * value) {
  // TODO
}

char * get(Nod ** hashtable, char * key) {
  // TODO
}

void init(Nod ** vek) {
  // TODO
}

1.6 Testprogram main.c

Skriv ett litet testprogram för att testa din hashtabell. Ändra tillfälligt i tilpro_hash så att funktionen alltid returnerar 17 för för att testa om din krockhantering fungerar.

#include "hashfunc.h"
// ...

extern const int HASHVEKSIZE;
// ...

int main() {
  Nod ** myhashvek = malloc(sizeof(Nod *) * HASHVEKSIZE);
  init(myhashvek);

  put(myhashvek, "Adam", "123321");
  char * s = get(myhashvek, "Adam");
  printf("Adam -> value = %s expecting Adam\n", s);

  // ...
}

1.7 Hasha många artister

Ladda ner filen sang-artist-data.txt från lab d4 och hasha värden från den. Vissa rader väldigt långa t.ex. 420 tecken på rad 379894

ARBHXC11187FB5C13B	Cherokee;Brian McKnight;Myron McKinley;Andrew Gooche;Cedric Anderson;Angelo Earl;Suzie Katayama;Murray Adler;Marlo De Leon;Bruce Dukov;Armen Garabedian;Karen Jones;Ezra Kliger;Katia Popov;Barbara Porter;Eve Sprecher;Ed Stein;John Wittenberg;Ken Yerke;Endre Granat;Anatoly Rosinski;Denyse Buffom;Matt Funes;Janet Lakatos;Cynthia Morrow;Larry Corbett;Steve Richards;Dan Smith	Steppin' Stone	271.98649	0

Nedan är ett program som läser in artister från sang-artist-data.txt till en artistarray av artist-structar. Modifiera programmet och testa att lagra många nyckel/värde-par i din hashvektor.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct artist {
  char artistid[20];
  char artistname[400];
  char songtitle[300];
  double length;
  int year;
};

typedef struct artist Artist;


//  Läser artister från filename och lägger dem i artistarray
//  returnerar antalet inlästa artister
int readartists(char * filename, Artist * artistarray) {
  char linebuffer[425];

  FILE * fil = fopen(filename, "r");

  int currentartist = 0;

  while (fgets (linebuffer, 425, fil) != NULL) {

    Artist * artist = artistarray + currentartist;

    int i = 0;
    int j = 0;
    // kolumner är TAB-separerade 
    while (linebuffer[i] != '\t')             
      i++;

    strncpy(artist -> artistid, linebuffer, j);

    i += 1;
    j = i;
    while (linebuffer[i] != '\t') 
      i++;

    strncpy(artist -> artistname, linebuffer + j, i - j);

    i += 1;
    j = i;
    while (linebuffer[i] != '\t') 
      i++;

    strncpy(artist -> songtitle, linebuffer + j, i - j);

    i += 1;
    // atof - array to float
    artist -> length = atof(linebuffer + i);  

    while (linebuffer[i] != '\t') 
      i++;

    i += 1;
    // atoi - array to integer 
    artist -> year = atoi(linebuffer + i);    

    currentartist += 1;
  }

  fclose(fil);
  return currentartist;
}

int main() {
  Artist * artister = malloc(sizeof(Artist) * 1000000);

  // calloc är ett alternativ till malloc som initierar vektorn till noll.
  // Avlägsnar också varningarna i valgrind för, Conditional jump or move depends on uninitialised value(s)
  //   Artist * artister = calloc(1000000, sizeof(Artist));

  int antalartister = readartists("sang-artist-data.txt", artister);

  int i = 0;
  for (i = 0; i < antalartister; i += 1) {
    printf("artist: %s\n  songtitle: %s\n  length: %f\n",
       artister[i].artistname, artister[i].songtitle, artister[i].length);
  }

  free(artister);
  return 0;
}

1.8 Lägg upp dina filer på KTH:s github.

Öppna länken till KTH:s github i din webbläsare. Det finns ett repository där du ska lägga upp din kod. Addressen är:

https://gits-15.sys.kth.se/tilpro2021/ANVNAMN-labbar

där du ska byta ut ANVNAMN mot ditt KTH-login.

Har du gjort rätt finns flera underkataloger, tryck på underkatalogen p4 och ladda sedan upp filer genom att trycka på knappen/upload files/

Ladda upp dina c- och h-filer.

Det går att ladda upp via terminalen men det förutsätter att man lagt upp en publik SSH-nyckel på KTH:s github så att github kan autentisera dig.

2 Redovisning

Vid redovisning ska du kunna:

  • rita vad som händer när man stoppar in eller söker i din hashtabell,
  • visa vad som är hårdkodat i koden,
  • visa hur koden testats (glöm inte minnesläckor).

 

1617227999 03/31/2021 11:59pm