www.mucker^.at

Hashing ist eine Möglichkeit zur Implementierung von so genannten DICTIONARIES, dies sind Datentypen zur Darstellung von Mengen, welche die Operationen INSERT, DELETE und MEMBER zu Verfügung stellen.

Die Grundidee des "Hashverfahrens" ist, aus dem Wert eines zu speichernden Mengenelementes seine Adresse im Speicher zu berechnen. Den Speicher der Mengenelemente bezeichnen wir als "Behälter" oder auch "Buckets" und nummeriert ihn zum Beispiel mit B(0) bis B(m-1). Der Wertebereich W der Mengenelemente kann beliebig groß sein, im Normalfall ist die Mächtigkeit von W sehr viel größer als m.

Mathematisch betrachtet ist eine so genannte "Hashfunktion" eine totale Abbildung

hash: W -> {0, ..., m-1}

W könnte zum Beispiel die Menge aller Zeichenketten mit einer Länge kleiner 20 sein.

Ein Beispiel: Wir wollen die sieben Wochentage auf 10 Buckets verteilen. Als Hashfunktion verwenden wir die Summe der ASCII-Werte der ersten drei Zeichen eines Wochentages modulo 10, wenn also ord('a') = 97, ord('b') = 98 ist, dann ist zum Beispiel

hash('Montag') = (ord('M') + ord('o') + ord ('n')) mod 10 = 1.

Mit dem folgenden kleinen Perl-Script ...

#!/usr/bin/perl

use strict; use warnings;

my @wochentag = (
    'Montag',
    'Dienstag',
    'Mittwoch',
    'Donnerstag',
    'Freitag',
    'Samstag',
    'Sonntag',
);

my $MAXBUCKET = 9;
my @bucket;

# initialisiere Buckets
foreach (0..$MAXBUCKET) {$bucket[$_] = '';}

foreach (@wochentag) {
    # Wochentag einfuegen, bei Kollision
    # anhaengen
    $bucket[&hash($_)] .= " $_";
}

foreach (0 .. $#bucket) {
    print "bucket[$_] = $bucket[$_]\n";
}

sub hash {
    my $string = $_[0];
    my $hash = 0;
    foreach (0..2) {$hash += ord(substr($string,$_));}
    return $hash % ($MAXBUCKET+1);
}

... erhalten wir als Ergebnis:

  bucket[0] = 
  bucket[1] =  Montag Mittwoch Donnerstag Samstag
  bucket[2] = 
  bucket[3] = 
  bucket[4] =  Dienstag
  bucket[5] = 
  bucket[6] =  Freitag
  bucket[7] =  Sonntag
  bucket[8] = 
  bucket[9] = 

Wir sehen also, dass mit unserer Hashfunktion nur eine sehr schlechte Verteilung auf unsere 10 "Buckets" erreicht wird. Es kommt zu Kollisionen (Bucket 1).



Die Hashverfahren unterscheiden sich in der Behandlung dieser Kollisionen. Beim so genannten "Offenen Hashing" nimmt man an, das jeder Bucket beliebig viele Schlüssel aufnehmen kann (Wie in unserem ersten Beispiel). Beim "Geschlossenen Hashing" kann jeder Behälter nur eine geringe Anzahl von Schlüsseln aufnehmen, im Normalfall einen.

Wenn man nun beim Einfügen auf einen bereits belegten Behälter stößt, muss man den nächsten unbelegten suchen. Dieses Verfahren nennt man "Rehashing" oder auch "Offene Adressierung".

Die einfachste Art ist im folgenden Script gezeigt: Man betrachtet sukzessive die auf den berechneten Behälter folgenden, bis man auf einen freien gelangt.

#!/usr/bin/perl

use strict; use warnings;

my @wochentag = (
    'Montag',
    'Dienstag',
    'Mittwoch',
    'Donnerstag',
    'Freitag',
    'Samstag',
    'Sonntag',
);

my $MAXBUCKET = 9;
my @bucket;

# initialisiere Buckets
foreach (0..$MAXBUCKET) {$bucket[$_] = '';}

foreach (@wochentag) {

   # Naechster Bucket
   my $next = &hash($_);
 
   # Solange kein freier Bucket, versuche
   # den naechsten
   while ($bucket[$next] ne '') {
       $next = ($next + 1) % ($MAXBUCKET + 1)
   }
   $bucket[$next] = " $_";
}

foreach (0 .. $#bucket) {
    print "bucket[$_] = $bucket[$_]\n";
}

sub hash {
    my $string = $_[0];
    my $hash = 0;
    foreach (0..2) {$hash += ord(substr($string,$_));}
    return $hash % ($MAXBUCKET+1);
}

Damit erhalten wir die Ausgabe

bucket[0] =  Donnerstag
bucket[1] =  Samstag
bucket[2] = 
bucket[3] = 
bucket[4] =  Dienstag
bucket[5] =  Freitag
bucket[6] =  Sonntag
bucket[7] = 
bucket[8] =  Montag
bucket[9] =  Mittwoch

Dies sieht bereits besser aus.

[FORTSETZUNG FOLGT]