Beispiel: Implementation einer Hash-Tabelle

// Beispiel zur Veranschaulichung einer Hash-Funktion
// (c) 05/97 Gottfried Rudorfer

#include <iostream.h>
#include <new.h>
extern "C" 
{
  // for exit() 
#include <stdlib.h>
  // for strcpy() and strlen()
#include <string.h>  
} 

// forward reference
class Table;

class Element
{
public:
  friend class Table; 
  Element(char *key, char *value);
  ~Element();
private:
  char *key;
  char *value;
  Element *next;
};

class Table 
{
public:
  Table(unsigned int s, unsigned int m);
  ~Table();
  void Put(char *key, char *value);
  void Print();
  void Delete(char *key);
  char *Get(char *key);
private:
  unsigned int Hash(char *key);
  unsigned int hash_mult, hash_size;
  //array of pointers to Element
  Element **hash_table;
};

// Konstruktor mit zwei Argumenten
Element::Element(char *new_key, char *new_value)
{
  // +1 für das terminierende '\0' !!
  key = new char [strlen(new_key)+1];
  value = new char [strlen(new_value)+1];
  
  strcpy(key, new_key);
  strcpy(value, new_value);
  next = NULL;
}

// Destruktor für obigen Konstruktor
Element::~Element()
{
  // lösche zuerst das nächste Listenelement,
  // soferne es vorhanden ist.
  delete key;
  delete value;
}

// Konstruktor mit zwei Argumenten
Table::Table(unsigned int s, unsigned int m)
{
  hash_size = s;
  hash_mult = m;
  // Array von Pointern auf Instanzen der Klasse Element
  // Die Instanzen werden hier nicht erzeugt.
  hash_table = new Element* [hash_size];
  for(unsigned int i=0; i<hash_size; i++)
    hash_table[i] = NULL;
}

// Destruktor für obigen Konstruktor
Table::~Table()
{
  Element *e, *n; //n ist die Adresse zum nächsten Element
  // lösche zuerst die linked lists
  for(unsigned int i=0; i<hash_size; i++) {
    e=hash_table[i];
    while(e != NULL) {
      n=e->next;
      delete e;
      e=n;
    }
  }
  
  
  // lösche die Hash-Tabelle
  // [] bei delete ist notwendig, wenn ein benutzerdefinierter
  // Typ an der Adresse gespeichert ist.
  delete [] hash_table;
}

unsigned int Table::Hash(char *p)
{
  unsigned long hash_val = 0;
  
  for(; *p; p++)
    hash_val = hash_val * hash_mult + *p;
  hash_val %= hash_size;
  return hash_val;
}

void Table::Put(char *new_key, char *new_value)
{
  unsigned int hash_val = Hash(new_key);
  Element *p, *e = hash_table[hash_val];
  if (e == NULL)
    {
      // new list
      hash_table[hash_val] = \
        new Element(new_key, new_value);
    }
  else
    {
      while(e != NULL)
        {
          if (!strcmp(new_key, e->key))
            {
              // key found, replace value
              delete e->value;
              e->value = new char [strlen(new_value)+1];
              strcpy(e->value, new_value);
              return;
            }
          else
            {
              p = e;
              e = e->next;
            }
        }
      // new element at the end of list
      p->next = new Element(new_key, new_value);
    }
}

char *Table::Get(char *existing_key)
{
  int hash_val = Hash(existing_key);
  Element *e = hash_table[hash_val];

  while(e != NULL)
    {
      if (!strcmp(existing_key, e->key))
        return(e->value); 
      else
        e = e->next;
    }
  // Der Key wurde nicht in der Hash-Tabelle gefunden.
  return NULL;
}

void Table::Delete(char *existing_key)
{
  int hash_val = Hash(existing_key);
  Element *e = hash_table[hash_val];
  Element *p=NULL;

  while(e != NULL)
    {
      if (!strcmp(existing_key, e->key))
        {
          if (p == NULL)
            {
              // first element
              if (e->next == NULL)
                {
                  // list contains only one element
                  hash_table[hash_val] = NULL;
                }
              else
                {
                  // second element ist now first
                  hash_table[hash_val] = e->next;
                }
            }
          else
            {
              // other elements (not first)
              if (e->next == NULL)
                {
                  // last element
                  p->next = NULL;
                }
              else
                {
                  // element in the middle of list
                  p->next = e->next;
                }
            }
          delete e;
          return;
        }
      p = e;
      e = e->next;
    }
  cout << "Element not found!" << endl;
}

void Table::Print()
{
  Element *e;
  unsigned int j;

  for (unsigned int i = 0; i < hash_size; i++)
    {
      cout << i << ":";
      e = hash_table[i];
      j = 0;
      while(1)
        {
          cout << " listelem " << j;
          if (e == NULL)
            {
              cout << ": NULL ";
              break;
            }
          else
            {
              cout << ": key: " << e->key \
                   << " value: " << e->value;
              j++;
              e = e->next;
            }
	
        }
      cout << endl;
    }
}

void NoSpace()
{
  cerr << "New Failed" << endl;
  exit(1);
}

main()
{
  // Rufe die Funktion NoSpace() auf
  // wenn new keinen freien Speicher 
  // belegen kann
  set_new_handler(NoSpace);
  unsigned int size;

  Table *hash = NULL;
  char key_buffer[128], value_buffer[128];
  char c, *result;



  cout << "** Hashing Example **" <<endl;

  while(1)
    {
      cout << "0) Hash-Tabelle erzeugen;" << endl;
      cout << "1) enter new key and value;" << endl;
      cout << "2) display value behind key;" << endl;
      cout << "3) display hash-table;" << endl;
      cout << "4) delete entry;" << endl;
      cout << "5) Hash-Tabelle zerstören;" <<endl;
      cout << "9) end program;" << endl;
      cin >>c;
      switch(c)
        {
          case '0':
            cout << "enter size of Hash-Table ";
            cin >> size;
            if (size == 0) {
              cerr << "Kann eine Hash-Tabelle der Größe 0 nicht anlegen" << endl;
              break;
            }
            hash = new Table(size, 65559);

            break;
          case '1':
            if (hash == NULL) {
              cerr << "Es existiert noch keine Hash-Tabelle" << endl;
              break;
            }
            cout << "enter key ";
            cin >> key_buffer;
            cout << "enter value ";
            cin >> value_buffer;
            hash->Put(key_buffer, value_buffer);
            break;
          case '2':
            if (hash == NULL) {
              cerr << "Es existiert noch keine Hash-Tabelle" << endl;
              break;
            }
            cout << "enter key ";
            cin >> key_buffer;
            result = hash->Get(key_buffer);
            if (NULL == result)
              {
                cout << "key " << key_buffer << " ";
                cout << "does not exist" << endl;
              }      
            else
              {
                cout << "value for " << key_buffer;
                cout << " is " << result <<endl;
              }
            break;
          case '3':
            if (hash == NULL) {
              cerr << "Es existiert noch keine Hash-Tabelle" << endl;
              break;
            }

            hash->Print();
            break;
          case '4':
            if (hash == NULL) {
              cerr << "Es existiert noch keine Hash-Tabelle" << endl;
              break;
            }

            cout << "enter key ";
            cin >> key_buffer;
            hash->Delete(key_buffer);
            break;
          case '5':
            delete hash;
            hash=NULL;
            break;

          case '9':
            exit(0);
          default:
            cout << "unknown command!" << endl;    
        }
    }
}