Systemnahe Programmierung in C: Hashtabellen

Hashtabellen	werden zu effizienten Implementierung von Mengen und Tabellen verwendet. Voraussetzung ist eine Hashfuntion auf dem Element- oder Schlüssel-Datentyp.
	Eine Hashfunktion ist eine Abbildung des Elementbereiches auf ein Intervall der natürlichen Zahlen [0 .. max-1].
Idee	Die Suche nach einem Element wird durch einen indizierten Zugriff in ein Feld realisiert. Wenn dieses alleine zum Ziel führen würde, hätte man eine Suche, die in O(1) laufen würde, also nicht mehr von der Größe der zu durchsuchenden Menge abhängen würde.
	Dieses Ziel kann nicht vollständig erreicht werden. Dazu wäre eine injektive Hashfunktion Voraussetzung. Solche Funktionen existieren im Allgemeinen nicht, da der Elementbereich üblicherweise unbeschränkt viele Elemente enthält.
	Aber es gibt sehr effizente Implementierungen, die für einen großen Bereich von Anwendungen diese Laufzeit fast erreichen.
Effizienz	Die Qualität der Implementierung hängt stark von der Wahl der Hashfunktion ab. Die Hashfunktion sollte alle Werte des Elementbereichs gleichmäßig auf das Intervall abbilden. Ähnliche Elemente sollten möglichst nicht auf den gleichen Wert abgebildet werden.

1. Implementierung	ist eine sehr rudimentäre Implementierung.
	Sie verwendet ein Feld fester Länge. Elemente, deren Hashwert gleich dem eines schon eingetragenen Wertes ist, werden in die erste freie Stelle hinter dem Hashindex eingetragen.
	Dieses funktioniert nur dann, wenn die Anzahl der zu speichernden Elemente kleiner als die Länge des Intervalls ist.
	Sie funktioniert effizient nur dann, wenn die Anzahl signifikant kleiner ist, z.B. max 70% der Größe der Tabelle beträgt.
	Das Löschen von Elementen ist nicht effizient zu realisieren.

2.Implementierung	ist eine allgemein einsetzbare Realisierung.
	Sie besitzt nicht die oben beschriebenen Nachteile. Es wird mit dynamischer Anpassung der Tabellenlänge gearbeitet, um ein Gleichgewicht zwischen Speicherplatzausnutzung und Laufzeit zu erreichen.
	Die einzelnen Tabelleneinträge sind verkettete Listen. Bei Verwendung einer guten Hashfunktion bleiben diese Listen aber sehr kurz (0 <= length <= 2).

Eine Schnittstelle für die Elemente: Element.h

#ifndef ELEMENT_H__
#define ELEMENT_H__ 1
typedef char *Element;
extern int compare(Element e1,
                   Element e2);
extern unsigned int hash(Element e);
#endif

Eine Implementierung für die Elemente: Element.c

#include "Element.h"
#include <string.h>
int
compare(Element e1, Element e2)
{
  int cmp = strcmp(e1, e2);
  return (cmp >= 0) - (0 >= cmp);
}
/* hash function as used in Java for Strings */
unsigned int
hash(Element e)
{
  unsigned int res = 0;
  while (*e != 0)
    {
      res = 31 * res + *e;
      ++e;
    }
  return res;
}

Die Schnittstelle für die beschränkt einsetzbare Hashtabelle: Hashtable0.h

#ifndef HASHTABLE0_H__
#define HASHTABLE0_H__
/*--------------------*/
#include "Element.h"
typedef struct Entry *Set;
struct Entry
{
  int used;
  Element info;
};
/*--------------------*/
extern Set mkEmptySet(void);
extern int isInSet(Element e, Set s);
extern Set insertElem(Element e, Set s);
/* not implemented:
   extern Set removeElem(Element e, Set s);
*/
extern int invSetAsHashtable(Set s);
/*--------------------*/
#endif

Die Implementierung für die beschränkt einsetzbare Hashtabelle: Hashtable0.c

#include "Hashtable0.h"
#include <stdlib.h>
#include <stdio.h>
#define eqElement(e1,e2) (compare((e1),(e2)) == 0)
/* constant hashtable size */
/* not very flexible */
#define size 1024
/* counting modulo size */
/* call these macros only with simple variables */
#define incr(i) i = (i == size - 1) ? 0 : i + 1
#define decr(i) i = ((i == 0) ? size : i) - 1
/*--------------------*/
Set
mkEmpty(void)
{
  Set res = malloc(size * sizeof(*res));
  if (!res)
    {
      perror
        ("mkEmptySet: malloc failed");
      exit(1);
    }
  {
    unsigned int i;
    for (i = 0; i < size; ++i)
      res[i].used = 0;
  }
  return res;
}
/*--------------------*/
int
isInSet(Element e, Set s)
{
  unsigned int i = hash(e) % size;
  while (s[i].used
         && !eqElement(s[i].info, e))
    {
      incr(i);
    }
  return s[i].used;
}
/*--------------------*/
Set
insertElem(Element e, Set s)
{
  unsigned int i = hash(e) % size;
  while (s[i].used
         && !eqElement(s[i].info, e))
    {
      incr(i);
    }
  if (!s[i].used)
    {
      s[i].used = 1;
      s[i].info = e;
    }
  return s;
}
/*--------------------*/
int
invSetAsHashtable(Set s)
{
  unsigned int i;
  for (i = 0; i < size; ++i)
    {
      if (s[i].used)
        {
          unsigned int ix =
            hash(s[i].info) % size;
          /* all entries in hashtable
             in the intervall [ix..i]
             must be filled, otherwise the hash does not
             fit to the position
           */
          unsigned int j = i;
          while (j != ix)
            {
              decr(j);
              if (!s[j].used)
                return 0;
            }
        }
    }
  return 1;
}

Die Schnittstelle für die allgemein einsetzbare Hashtabelle: Hashtable.h

#ifndef HASHTABLE_H__
#define HASHTABLE_H__
/*--------------------*/
#include "Element.h"
typedef struct Node *List;
struct Node
{
  Element info;
  List next;
};
typedef struct hashtable *Set;
struct hashtable
{
  unsigned int size;
  unsigned int card;
  List *table;
};
/*--------------------*/
extern Set mkEmptySet(void);
extern int isEmptySet(Set s);
extern int isInSet(Element e, Set s);
extern Set insertElem(Element e, Set s);
extern Set removeElem(Element e, Set s);
extern unsigned int card(Set s);
extern int invSetAsHashtable(Set s);
/*--------------------*/
#endif

Die Implementierung für die allgemein einsetzbare Hashtabelle: Hashtable.c

#include "Hashtable.h"
#include <stdlib.h>
#include <stdio.h>
/*--------------------*/
/* auxiliary list functions */
#define eqElement(e1,e2) (compare((e1),(e2)) == 0)
#define mkEmptyList() ((List)0)
#define isEmptyList(l) ((l) == (List)0)
static int
isInList(Element e, List l)
{
  while (!isEmptyList(l))
    {
      if (eqElement(e, l->info))
        return 1;
      l = l->next;
    }
  return 0;
}
/*--------------------*/
static List
cons(Element e, List l)
{
  /* the only call of malloc for List values */
  List res = malloc(sizeof(*l));
  if (!res)
    {
      perror("cons: malloc failed");
      exit(1);
    }
  res->info = e;
  res->next = l;
  return res;
}
/*--------------------*/
static List
removeElem1(Element e, List l)
{
  if (isEmptyList(l))
    return l;
  if (eqElement(e, l->info))
    {
      List l1 = l->next;
      free(l);
      return l1;
    }
  l->next = removeElem1(e, l->next);
  return l;
}
/*--------------------*/
/* hash table creation */
/* size for new empty hashtable */
#define initialSize 16
Set
mkEmpty(void)
{
  Set res = malloc(sizeof(*res));
  List *table =
    malloc(initialSize *
           sizeof(*table));
  if (!res || !table)
    {
      perror
        ("mkEmptySet: malloc failed");
      exit(1);
    }
  res->size = initialSize;
  res->card = 0;
  res->table = table;
  {
    unsigned int i;
    for (i = 0; i < res->size; ++i)
      table[i] = mkEmptyList();
  }
  return res;
}
/*--------------------*/
Set
resizeHashtable(Set s,
                unsigned int newsize)
{
  unsigned int size = s->size;
  List *newtable =
    malloc(newsize * sizeof(*newtable));
  List *oldtable = s->table;
  unsigned int i;
  /* initialize new table */
  for (i = 0; i < newsize; ++i)
    newtable[i] = mkEmptyList();
  /* move entries from old table into new table */
  for (i = 0; i < size; ++i)
    {
      List l = oldtable[i];
      while (!isEmptyList(l))
        {
          List l1 = l;
          unsigned int i2 =
            hash(l->info) % newsize;
          l = l->next;
          l1->next = newtable[i2];
          newtable[i2] = l1;
        }
    }
  free(oldtable);
  s->size = newsize;
  s->table = newtable;
  return s;
}
/*--------------------*/
/* if card > 1.0 * size, the table size is doubled */
/* this factor and the expansion factor can be tuned */
Set
checkTableOverflow(Set s)
{
  /* don't use floating point arithmetic for this check */
  if (s->card > s->size)
    return resizeHashtable(s,
                           2 * s->size);
  return s;
}
/*--------------------*/
/* if card < 0.25 * size, the table size is divided by 2 */
/* this factor and the shrinking factor can be tuned */
Set
checkTableUnderflow(Set s)
{
  if (s->size > initialSize
      && 4 * s->card < s->size)
    return
      resizeHashtable(s, s->size / 2);
  return s;
}
/*--------------------*/
int
isInSet(Element e, Set s)
{
  unsigned int i = hash(e) % s->size;
  return isInList(e, s->table[i]);
}
/*--------------------*/
Set
insertElem(Element e, Set s)
{
  unsigned int i = hash(e) % s->size;
  List l = s->table[i];
  if (!isInList(e, l))
    {
      s->table[i] = cons(e, l);
      ++(s->card);
      s = checkTableOverflow(s);
    }
  return s;
}
Set
removeElem(Element e, Set s)
{
  unsigned int i = hash(e) % s->size;
  List l = s->table[i];
  if (isInList(e, l))
    {
      s->table[i] = removeElem1(e, l);
      --(s->card);
      s = checkTableUnderflow(s);
    }
  return s;
}
/*--------------------*/
static int
checkHashes(Set s)
{
  unsigned int i;
  for (i = 0; i < s->size; ++i)
    {
      List l = s->table[i];
      while (!isEmptyList(l))
        {
          if (hash(l->info) % s->size !=
              i)
            return 0;
          l = l->next;
        }
    }
  return 1;
}
static int
checkCard(Set s)
{
  unsigned int i;
  unsigned int res = 0;
  for (i = 0; i < s->size; ++i)
    {
      List l = s->table[i];
      while (!isEmptyList(l))
        {
          ++res;
          l = l->next;
        }
    }
  return res == s->card;
}
static int
checkTableLevel(s)
{
  /* check whether size and
     card fit the space constraints */
  return 1;
}
int
invSetAsHashtable(Set s)
{
  return
    checkHashes(s)
    &&
    checkCard(s)
    &&
    checkTableLevel(s);
}

Hashtabellen