Hashing

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

#define NAAMLENGTH 10

typedef struct {
  char naam[NAAMLENGTH];
} Key;

typedef struct {
  int nummer;
} Waarde;

void printKeyWaarde(Key k, Waarde w) { printf("%s %d", k.naam, w.nummer); }

unsigned int hash(Key k) {
  // gebaseerd op http://www.cse.yorku.ca/~oz/hash.html
  unsigned char* s = k.naam;
  unsigned int hash = 5381; // priemgetal
  while (*s) {
    hash = ((hash << 5) + hash) + *s++; /* hash * 33 + karakter */
  }
  return hash;
}

int equals(Key k1, Key k2) { return strcmp(k1.naam, k2.naam) == 0; }

typedef struct elem {
  Key key;
  Waarde waarde;
  struct elem* volgende;
} Element;

Element* createEl(Key k, Waarde w) {
  Element* el = malloc(sizeof(Element));
  el->key = k;
  el->waarde = w;
  el->volgende = NULL;
  return el;
}

void destroyEl(Element* el) {
  if (el != NULL) {
    destroyEl(el->volgende);
    free(el);
  }
}

typedef struct {
  int lengte;
  int gevuld;
  Element** elementen;
} HashTabel;

HashTabel create() {
  HashTabel t = {0, 0, NULL};
  return t;
}

void destroy(HashTabel* t) {
  if (t->lengte > 0) {
    assert(t->elementen != NULL);
    for (int i = 0; i < t->lengte; ++i) {
      destroyEl(t->elementen[i]);
    }
    free(t->elementen);
    t->elementen = NULL;
    t->lengte = 0;
    t->gevuld = 0;
  }
}

void print(HashTabel* t) {
  printf("lengte %d gevuld %d\n", t->lengte, t->gevuld);
  for (int i = 0; i < t->lengte; ++i) {
    printf("index %3d", i);
    Element* el = t->elementen[i];
    while (el != NULL) {
      printf(" | ");
      printKeyWaarde(el->key, el->waarde);
      el = el->volgende;
    }
    printf("\n");
  }
}

Element* vind(HashTabel* t, Key k) {
  if (t->lengte == 0) {
    return NULL;
  }
  int index = hash(k) % t->lengte;
  Element* el = t->elementen[index];
  while (el != NULL) {
    if (equals(el->key, k)) {
      return el;
    }
    el = el->volgende;
  }
  return NULL;
}

void groei(HashTabel* t);

void voegToe(HashTabel* t, Key k, Waarde w) {
  if (t->lengte == 0) {
    groei(t);
  }
  int index = hash(k) % t->lengte;
  Element* el = t->elementen[index];
  if (el == NULL) {
    t->elementen[index] = createEl(k, w);
  } else if (equals(el->key, k)) {
    return; // zit al in tabel
  } else {
    while (el->volgende != NULL) {
      el = el->volgende;
      if (equals(el->key, k)) {
        return; // zit al in tabel
      }
    }
    el->volgende = createEl(k, w);
  }
  t->gevuld += 1;
  if (t->lengte <= t->gevuld) {
    groei(t);
  }
}

void groei(HashTabel* t) {
  HashTabel nieuw = create();
  nieuw.lengte = 2 * t->lengte + 1; // 0,1,3,7,15, enz.
  nieuw.elementen = malloc(sizeof(Element*) * nieuw.lengte);
  for (int i = 0; i < nieuw.lengte; ++i) {
    nieuw.elementen[i] = NULL;
  }
  for (int i = 0; i < t->lengte; ++i) {
    Element* el = t->elementen[i];
    while (el != NULL) {
      voegToe(&nieuw, el->key, el->waarde);
      el = el->volgende;
    }
  }
  destroy(t);
  t->lengte = nieuw.lengte;
  t->gevuld = nieuw.gevuld;
  t->elementen = nieuw.elementen;
}

int verwijder(HashTabel* t, Key k) {
  if (t->lengte == 0) {
    return 0;
  }
  int index = hash(k) % t->lengte;
  Element* el = t->elementen[index];
  if (el == NULL) {
    return 0;
  }
  if (equals(el->key, k)) {
    Element* tmp = el->volgende;
    free(el);
    t->elementen[index] = tmp;
    return 1;
  }
  while (el->volgende != NULL) {
    if (equals(el->volgende->key, k)) {
      Element* tmp = el->volgende->volgende;
      free(el->volgende);
      el->volgende = tmp;
      t->gevuld -= 1;
      return 1;
    }
    el = el->volgende;
  }
  return 0;
}

void main() {
  HashTabel t = create();
  for (char i = 'a'; i < 'a' + 6; ++i) {
    Waarde w = {i % 5};
    Key k = {""};
    for (int j = 0; j < NAAMLENGTH - 1; ++j) {
      k.naam[j] = i + ((i+2*j) % 5); // gekozen om veel collisions te hebben
    }
    k.naam[NAAMLENGTH - 1] = '\0';
    voegToe(&t, k, w);
    print(&t);
  }
  Key k = {"gdfcegdfc"};
  verwijder(&t, k);
  print(&t);
  destroy(&t);
}