Hashtabellen Teil 1: Erst einmal ein statisches `unordered_map` für C89 ohne Elemententfernung

Habe mich heute spontan dazu entschlossen, einen Leitfaden zu Hashtabellen (Streuwerttabellen) zu schreiben.
Wenn es gut ankommt, dann schreibe ich Teil 2.

INHALT

1. Was sind Hashtabellen? (Array + Hash-Funktion)
2. (Statische) Implementation mit std::unordered_map von C++ als Vorbild

Fangen wir an.

1. Was sind Hashtabellen? (Array + Hash-Funktion)

Man greift auf Array-Elemente mit einem Zahlen-Index zu.

char fruits[3][32] = {"apple", "kiwi", "orange"};
printf("%.32s\n", fruits[2]); /* orange */

Jetzt möchte man aber keine Zahlen für die Indexierung, sondern Werte wie "Apfel".

printf("%.32s\n", fruits["Apfel"]); /* apple */

Also statt fruits[0] möchte man fruits["Apfel"].
Den neuen Index "Apfel" nennt man dann Schlüssel.
Das Array-Element "apple" nennt man dann Wert.

fruits["Apfel"] ist nicht möglich in C.
Es sei denn, wir weisen für jeden Schlüssel einen Zahlenwert zu und schreiben uns eine Funktion, die den Array-Zugriffsoperator[] nachahmt.

Um Schlüssel auf Zahlenwerte abzubilden, können wir beispielsweise diese Funktion hier benutzen:

size_t hasher(void* key) {
  assert(key != NULL);
  return 712572UL; /* some random number*/
}

Hier weisen wir für jeden Schlüssel einfach den Wert 712572 zu.
Wir könnten genauso gut 0 oder 1 oder 42 nehmen.
Diese Funktion, die Schlüssel auf Zahlen (Array-Indexwerte) abbildet, nennt man Hash-Funktion.
Davon gibt es mehrere.

Normalerweise möchte man für jeden Schlüssel einen guten Streuwert, erzielen.
Also zum Beispiel pseudozufällige Zahlen, die nach einem bestimmten deterministischen Verfahren, bestimmt werden.

Idealerweise möchte man sogar eine eindeutige Zuweisung von Schlüssel auf einen Indexwert haben.
Das geht aber nicht, wenn man bedenkt, dass die Indexwerte wie hier endlich sind, also von 0 bis maximal 2 gehen.

Wenn man ein unendlich großes Array hat, dann könnte man so eine eindeutige Zuordnung von Schlüssel und Indexwert erzielen.
Wir möchten es aber zunächst einfach halten.
(Auch wenn diese Funktion nicht gut geeignet ist, gute Streuwerte/Hashwerte zu erzeugen.)

Wegen der Länge 3 beim Array fruits, geht fruits[712572UL] nicht.
Das geht

fruits[712572UL % 3U]; /* evaluates to index 0, "apple" */

Damit nun fruits["Apfel"] möglich ist, schreiben wir als Beispiel

void* find(void* array, void* key) {
    size_t hashed_index = hasher2(key) % 3U; /* index 0 */
    return (unsigned char*)array + sizeof(char[32]) * hashed_index;
}

Nun haben wir unseren Array-Zugriffsoperator [] als find umgeschrieben.
Wir probieren

char key[32] = "Apfel";
printf("%.32s\n", *(char(*)[32])find(fruits, &key)); /* apple */

Wir bekommen "apple".

Was passiert, wenn wir mal das da machen?:

char key[32] = "Stefan Raab";
printf("%.32s\n", *(char(*)[32])find(fruits, &key)); /* apple */

Wir bekommen immer noch "apple".

Ist auch nicht weiter verwunderlich, da unser hasher immer nur konstant 712572 liefert und dann damit immer auf Divisionsrest 0 kommt.

Wir müssen also sicherstellen, dass dieser Schlüssel existiert, indem wir in einem Array vergleichen und suchen.
"Stefan Raab" existiert nicht.
Und ganz nebenbei, Schlüssel-Werte-Paare der Form: "Apfel" -> "apple" und "Apfel" -> "ringo" gehen auch nicht, da die Suche und der Vergleich damit nicht eindeutig möglich wäre.

Damit wir nun die einmalige Existenz eines Schlüssels sicherstellen und Vergleiche machen können, wollen wir dieses Array-Format bewerkstelligen

{|STATUS 1|SCHLUESSEL 1|WERT 1|, ..., |STATUS N|SCHLUESSEL N|WERT N|}

Also ein Array mit Elementen |STATUS|SCHLUESSEL|WERT|.
(Geht auch anders, aber das finde ich einfach genug.)
Solche Array-Elemente nennt man Eimer oder "Buckets".

Wir möchten wissen, ob ein Eimer voll ist oder nicht.
Wenn wir später uns ermöglichen Eimer aus dem Array zu löschen, dann möchten wir auch wissen, ob der Eimer von jemandem gelöscht wurde.

Hierzu ein Gedankenexperiment.

Wir nehmen an, dass den Indexwert 0 zugewiesen bekommt und den Indexwert 1.
Index 2 bleibt leer.

{|VOLL|🍏|"apple"|, |VOLL|🥝|"kiwi"|, LEER, -, "" }

Jetzt fügen wir den Eimer "VOLL", "🍊", "orange" hinzu, bekommt auch den Indexwert 1 wie .

Jetzt haben wir eine sogenannte Kollision, die wir gesondert behandeln müssen.
Hierzu machen wir uns es einfach und bringen die Orange auf den nächsten freien Index.
In diesem Fall also Index 2.

{|VOLL|🍏|"apple"|, |VOLL|🥝|"kiwi"|, VOLL, "🍊", "orange" }

Wenn wir jetzt nach suchen möchten, erzeugen wir uns zunächst den Hashwert mit unserer Hash-Funktion.

Hashfunktion(🍊) -> 1

Also schauen wir jetzt bei Index 1 im Array nach und wir sehen, dass er voll mit ist.

Da wir abgemacht haben, dass wir bei einer Kollision es auf den nächsten freien Platz bringen, schauen wir einfach bei Arrayindex 2 weiter.

Volltreffer, wir kommen auf

Suche(🍊) -> "orange"

Jetzt möchten wir nochmal nach suchen und wir nehmen diesmal an, dass als gelöscht markiert ist vor dem Hinzufügen von .

{|VOLL|🍏|"apple"|, |GELOESCHT|🥝|"kiwi"|, VOLL, "🍊", "orange" }

Wenn wir das nicht gesondert markiert hätten mit GELOESCHT und stattdessen einfach LEER verwendet hätten, dann wäre die Suche Suche(🍊) -> "orange" nicht erfolgreich.

Wenn ein Eimer LEER ist, dann nehmen wir an, dass es zu keinen Kollisionen davor kam.
Das bedeutet, dass wir dann annehmen können, dass der Schlüssel nicht existiert und die Suche danach einfach beenden.

Somit bleibt die Suchkette erhalten und wird nicht unterbrochen.
Natürlich könnten wir auch das ganze Array einfach absuchen und keine Markierungen machen, ob da etwas war oder nicht.
Aber dann brauchen wir Hashtabellen nicht und können gleich Arrays verwenden.
Wir brauchen ein "Signal", dass uns "sagt":

"Hey, es kam mal hier an der Stelle (zum Beispiel Index 1, wie bei ) zu einer Kollision, guck, dass Du weiter schaust beim nächsten Eimer.
Falls Du bei der Suche auf ein LEER kommst, kannst Du die 'Vermisstenanzeige' von aufgeben und die Suche beenden."

Angemerkt sei noch, dass bei einem LEER der Eimer |GELOESCHT|🥝|"kiwi"| mit "Stefan Raab" befüllt werden könnte.

{|VOLL|🍏|"apple"|, |VOLL|"Stefan Raab"|"TV Total"|, VOLL, "🍊", "orange" }

(Die Frage ist, will man, dass "Stefan Raab" da existiert als Schlüssel?!?)

Die Suchkette bleibt damit trotzdem erhalten.
Wenn Du magst, kannst Du das ja nochmal durchgehen mit Hashfunktion(🍊) -> 1 und Suche(🍊) -> "orange".

Hashtabellen haben also 3 grundlegende Operationen:

Einfuegen("🍊")
Loeschen(🥝)
Suche(🍊) -> "orange"

Das, was an einer Hashtabelle besonders ist, ist die Eigenschaft (bei einer guten Hashwertfunktion), dass die Suche im Array nahezu sofort erfolgt (im Idealfall).
Also ein Array, das mit einer Hash-Funktion "aufgemotzt" wurde, um die Suche im Array zu beschleunigen.

Wir halten also fest:

Ein Array, gekoppelt mit einer Hash-Funktion, nennt man eine Hashtabelle.
Eine Hashtabelle kann man als Array aus Eimern der Form |STATUS|SCHLUESSEL|WERT| implementieren.
Um die Suchkette der Hashtabelle nicht zu unterbrechen, verwenden wir bei den Statusmarkierungen neben LEER und VOLL auch GELOESCHT.
Eine Hashtabelle hat 3 Grundoperationen: Suchen, Loeschen und Einfuegen.

2. (Statische) Implementation mit std::unordered_map von C++ als Vorbild

"Backzutaten" für unsere unordered_map Implementierung:

Suchoperation unordered_map_find
Einfügeoperation unordered_map_insert
Löschoperation unordered_map_erase (beim nächsten Teil, jetzt nicht)
Ein struct unordered_map mit geeigneten Zustandsvariablen ("Mitgliedsvariablen").
Weitere Funktionen wie unordered_map_begin, unordered_map_end etc.
"Private" bzw. gekapselte Hilfsfunktionen wie bucket_at und bucket_insert_at, um die Arbeit bei der Implementierung zu erleichtern.

Wir orientieren uns bei der Benennung unserer Hashtabellen-Funktionen an std::unordered_map von C++.

Dazu käme beispielsweise so eine Anwender-Schnittstelle infrage:

typedef struct doz_unordered_map doz_unordered_map;

struct doz_unordered_map {
    unsigned char* data;
    size_t key_size;
    size_t mapped_size;
    size_t flag_size;
    size_t value_size; /* (key_type, mapped_type) */
    size_t bucket_size;
    size_t (*hasher)(void const* key);
    unsigned int (*key_equal)(void const* key_1, void const* key_2,
                              size_t key_size);
    size_t size; /* number of elements in the container */
    size_t capacity;
};

doz_unordered_map* doz_unordered_map_new(
    size_t key_size, size_t mapped_size, size_t (*hasher)(void const* key),
    unsigned int (*key_equal)(void const* key_1, void const* key_2,
                              size_t key_size));
void doz_unordered_map_delete(doz_unordered_map* self);
void* doz_unordered_map_begin(doz_unordered_map* self);
void* doz_unordered_map_end(doz_unordered_map* self);
void* doz_unordered_map_next(doz_unordered_map* self, void* iterator);
size_t doz_unordered_map_bucket_size(doz_unordered_map* self);
void* doz_unordered_map_get_first(doz_unordered_map* self, void* iterator);
void* doz_unordered_map_get_second(doz_unordered_map* self, void* iterator);
void* doz_unordered_map_find(doz_unordered_map* self, void* key);
void* doz_unordered_map_insert(doz_unordered_map* self, void* key, void* value);

Wir schauen uns zunächst einmal die Struktur an.

struct doz_unordered_map {
    unsigned char* data;
    size_t key_size;
    size_t mapped_size;
    size_t flag_size;
    size_t value_size; /* (key_type, mapped_type) */
    size_t bucket_size;
    size_t (*hasher)(void const* key);
    unsigned int (*key_equal)(void const* key_1, void const* key_2,
                              size_t key_size);
    size_t size; /* number of elements in the container */
    size_t capacity;
};

data soll auf unser heapallokiertes Array zeigen.
key_size ist die Grösse des Schlüsseldatentyps in Bytes.
mapped_size ist die Grösse des Wertes (key_size -> mapped_size).
flag_size ist die Grösse des Statuswertes (also VOLL, LEER, GELOESCHT).
value_size ist key_size + mapped_size (war halt bei C++ auch so, siehe Referenzpunkt 1).
bucket_size ist flag_size + value_size.
hasher ist ein Funktionszeiger für eine Hashfunktion.
Den Funktionszeiger key_equal brauchen wir um damit Schlüssel zu vergleichen.
size ist die Anzahl der eingefügten Elemente.
capacity ist die Länge des dynamich allokierten Arrays

Unser Array-Format soll dan so aussehen:

{|FLAG 1|KEY 1|VALUE 1|, ... , |FLAG N|KEY N|VALUE N|}

bzw.

|unsigned char|K|V|

K (key_size), V (mapped_size) sind dabei nicht von uns bestimmte Typen.

Flag soll dann 1 Byte betragen.

Der Typ `char` ist nicht immer 1 Byte, aber meistens ist das so.

Was wir hier machen wollen, ist erst einmal das unordered_map-Objekt erzeugen (doz_unordered_map_new) und befreien (doz_unordered_map_delete).

doz_unordered_map* doz_unordered_map_new(
    size_t key_size, size_t mapped_size, size_t (*hasher)(void const* key),
    unsigned int (*key_equal)(void const* key_1, void const* key_2,
                              size_t key_size)) {
    size_t const flag_size = sizeof(unsigned char);
    size_t const value_size = key_size + mapped_size;
    size_t const bucket_size = flag_size + value_size;
    size_t const initial_capacity = 11U; /* should be some prime number */
    doz_unordered_map* map =
        (doz_unordered_map*)malloc(sizeof(doz_unordered_map));
    map->data = (unsigned char*)calloc(initial_capacity, bucket_size);
    map->key_size = key_size;
    map->mapped_size = mapped_size;
    map->flag_size = flag_size;
    map->value_size = value_size;
    map->bucket_size = bucket_size;
    map->hasher = hasher;
    map->key_equal = key_equal;
    map->size = 0U;
    map->capacity = initial_capacity;
    return map;
}

Wir setzen die Strukturobjektvariablen und allokieren uns genug Speicher für das Objekt selbst und für das Array von Eimern ("Buckets").

void doz_unordered_map_delete(doz_unordered_map* self) {
    free(self->data);
    self->data = NULL;
    free(self);
}

Man sollte evtl. auch nachgucken, ob da die Allokationen und Deallokationen gelaufen sind.
Ich mach das hier nicht, um es kurz zu halten.

Dann wollen wir noch Iterator-/Zeiger-Funktionen haben, die dazu da sind um auf die Hashtabelle zuzugreifen und zu iterieren zu können:

void* doz_unordered_map_begin(doz_unordered_map* self) {
    assert(map_is_valid(self) == 1U);
    return self->data;
}

void* doz_unordered_map_end(doz_unordered_map* self) {
    assert(map_is_valid(self) == 1U);
    return self->data + self->bucket_size * self->capacity;
}

void* doz_unordered_map_next(doz_unordered_map* self, void* iterator) {
    return (unsigned char*)iterator + self->bucket_size;
}

size_t doz_unordered_map_bucket_size(doz_unordered_map* self) {
    return self->bucket_size;
}

void* doz_unordered_map_get_first(doz_unordered_map* self, void* iterator) {
    return (unsigned char*)iterator + self->flag_size;
}

void* doz_unordered_map_get_second(doz_unordered_map* self, void* iterator) {
    return (unsigned char*)iterator + self->flag_size + self->key_size;
}

Bevor wir uns anschauen, ob die Funktionen doz_unordered_map_new und doz_unordered_map_delete funktionieren, definieren wir uns eine Vergleichsfunktion und eine Hashfunktion.

static size_t default_hasher(void const* key) {
    return 0U;
}

static unsigned int default_key_equal(void const* key_1, void const* key_2,
                                      size_t key_size) {
    return memcmp(key_1, key_2, key_size) == 0;
}

default_hasher ist unsere provisorische Hashfunktion, die immer konstant 0 liefert.
(Ist gut bei der Fehlersuche.)
default_key_equal, macht Bytevergleiche der Schlüssel.

`default_key_equal` ist für C-Strukturobjekte nicht geeignet, da es Bytevergleiche sind.
Strukturen in C bekommen in der Regel Zusatzbytes zur "Aufpolsterung" ("Padding").
Dient wohl zur Optimierung und Ausrichtung des Objektspeichers.

Wir wollen nun char[32] also Char-Arrays oder Strings der Grösse 32 in der Hashtabelle.
Unser Schlüsseldatentyp und Wertedatentyp (mapped_type) ist somit 32 Byte.
Dazu kommen noch die Vergleichsfunktion und noch die (provisorische) Hashfunktion.

    doz_unordered_map* my_map = doz_unordered_map_new(
        sizeof(char[32]), sizeof(char[32]), default_hasher, default_key_equal);

   doz_unordered_map_delete(my_map);

Klappt.
Nun weiter mit den Iteratoren.
Wir iterieren mal die leere Hashtabelle durch.

        void* it = NULL;
        size_t counter = 0U;
        for (it = doz_unordered_map_begin(my_map);
             it != doz_unordered_map_end(my_map);
             it = doz_unordered_map_next(my_map, it)) {
            printf("[%02lu]: (%.32s -> %.32s)\n", counter,
                   *(char(*)[32])doz_unordered_map_get_first(my_map, it),
                   *(char(*)[32])doz_unordered_map_get_second(my_map, it));
            ++counter;
        }

Klappt auch!

So jetzt wird es ernst, wir fangen an mit doz_unordered_map_find.

Als Hilfsfunktion bei der Implementierung dient uns

static void* bucket_at(doz_unordered_map* map, size_t i) {
    return (unsigned char*)map->data + map->bucket_size * i;
}

Wir verwenden diese Statusbytes bzw. Statuswerte (VOLL, GELOESCHT, LEER) zur Markierung der Eimer:

#define DOZ_UNORDERED_MAP_FLAG_EMPTY 0U
#define DOZ_UNORDERED_MAP_FLAG_FULL 1U
#define DOZ_UNORDERED_MAP_FLAG_REMOVED 2U

Und wir kommen auf

void* doz_unordered_map_find(doz_unordered_map* self, void* key) {
    size_t hashed_index = 0U;
    void* iterator = NULL;
    assert(map_is_valid(self) == 1U);
    assert(key != NULL);

    hashed_index = self->hasher(key) % self->capacity;

    iterator = bucket_at(self, hashed_index);
    {
        size_t i = 0U;
        unsigned int search = 1U;

        for (i = 0U; (i < self->capacity) && (search == 1U); ++i) {
            if (iterator == doz_unordered_map_end(self)) {
                iterator = doz_unordered_map_begin(self);
            }

            switch (*(unsigned char*)iterator) {
                case DOZ_UNORDERED_MAP_FLAG_EMPTY:
                    if (i == (self->capacity - 1U)) {
                        search = 0U; /* Our search is over here. */
                        iterator = doz_unordered_map_end(self);
                    }
                    break;
                case DOZ_UNORDERED_MAP_FLAG_FULL:
                    if (self->key_equal(
                            doz_unordered_map_get_first(self, iterator), key,
                            self->key_size)) {
                        search = 0U; /* Found it, let's stop here. */
                    }
                    break;
                case DOZ_UNORDERED_MAP_FLAG_REMOVED:
                    break;
                default:
                    break;
            }

            if (search == 1U) {
                iterator = doz_unordered_map_next(self, iterator);
            }
        }
    }

    return iterator;
}

Falls der Schlüssel nicht gefunden wurde, liefern wir einen Zeiger auf 1 Eimer nach dem Letzten Eimer (doz_unordered_map_end).
Da das auch so bei C++ Konvention ist.
Wir iterieren genau self->capacity (also 11) mal durch und gucken bei jeder Iteration, ob wir an der Grenze (doz_unordered_map_end) sind oder nicht.
Falls wir an der Grenze sind, dann fangen wir von Index 0 aus an (doz_unordered_map_begin).
Wenn der Eimer voll ist, soll reingeschaut werden, ob es auch der Schlüssel ist den wir suchen.
Falls nicht, soll weitergemacht werden mit der Suche.
Also auch, wenn wir ein DOZ_UNORDERED_MAP_FLAG_REMOVED-Statuswert haben, soll weitergemacht werden.
Falls der Schlüssel gefunden wird, beenden wir die Suche und liefern den Eimer als Iterator/Zeiger zurück.
Wenn wir einen leeren Eimer vorfinden, wird die Suche beendet.
Das war's.

Bei doz_unordered_map_insert brauchen wir die Hilfsfunktion

static void* bucket_insert_at(doz_unordered_map* map, size_t i,
                              unsigned char const* flag, void const* key,
                              void const* value) {
    void* iterator = bucket_at(map, i);
    memcpy(iterator, flag, map->flag_size);
    memcpy(doz_unordered_map_get_first(map, iterator), key, map->key_size);
    memcpy(doz_unordered_map_get_second(map, iterator), value,
           map->mapped_size);
    return iterator;
}

void* doz_unordered_map_insert(doz_unordered_map* self, void* key,
                               void* value) {
    size_t hashed_index = 0U;
    void* iterator = NULL;

    if (doz_unordered_map_find(self, key) != doz_unordered_map_end(self)) {
        return doz_unordered_map_end(self);
    }

    hashed_index = self->hasher(key) % self->capacity;

    iterator = bucket_at(self, hashed_index);
    {
        size_t i = 0U;
        unsigned int search = 1U;
        unsigned char flag = 0U;

        /* Find an empty spot (empty or removed) and insert the bucket there. */
        for (i = 0U; (i < self->capacity) && (search == 1U); ++i) {
            if (iterator == doz_unordered_map_end(self)) {
                iterator = doz_unordered_map_begin(self);
            }
            switch (*(unsigned char*)iterator) {
                case DOZ_UNORDERED_MAP_FLAG_EMPTY:
                case DOZ_UNORDERED_MAP_FLAG_REMOVED:
                    search = 0U; /* Our search is over here. */
                    flag = DOZ_UNORDERED_MAP_FLAG_FULL;
                    iterator = bucket_insert_at(
                        self, (hashed_index + i) % self->capacity, &flag, key,
                        value);
                    ++self->size;
                    break;
                case DOZ_UNORDERED_MAP_FLAG_FULL:
                    break;
                default:
                    break;
            }

            if (search == 1U) {
                iterator = doz_unordered_map_next(self, iterator);
            }
        }
    }

    return iterator;
}

Wir holen uns erst mal den Eimer indem wir den Schlüssel in die Hashfunktion übergeben und davor auch sicherstellen, dass der Schlüssel noch nicht existiert.
Dann schauen wir wie bei der Suche mit doz_unordered_map_find nach einem freien Platz.
Ein Platz gilt als "frei", wenn

DOZ_UNORDERED_MAP_FLAG_EMPTY
DOZ_UNORDERED_MAP_FLAG_REMOVED

gilt.

Wenn der Eimer voll ist, suchen wir weiter, bis wir die Kapazität (11 Iterationen) gesprengt haben.

In Ordnung, schauen wir das Ganze mal in Aktion an:

    static char fruits_de[][32] = {"Apfel",    "Pfirsich",     "Birne",
                                   "Erdbeere", "Wassermelone", "Weintraube",
                                   "Banane",   "Quitte",       "Kirsche",
                                   "Orange",   "Kiwi",         "Ananas"};
    static char fruits_en[][32] = {
        "apple",  "peach",  "pear",   "strawberry", "watermelon", "grape",
        "banana", "quince", "cherry", "orange",     "kiwi",       "pineapple"};

Das da oben wollen wir in die Hashtabelle reinbekommen.

    {
        size_t i = 0U;

        for (i = 0U; i < sizeof(fruits_de) / sizeof(*fruits_de); ++i) {
            doz_unordered_map_insert(my_map, fruits_de[i], fruits_en[i]);
        }
    }

Drin!

[00]: (Apfel -> apple)
[01]: (Pfirsich -> peach)
[02]: (Birne -> pear)
[03]: (Erdbeere -> strawberry)
[04]: (Wassermelone -> watermelon)
[05]: (Weintraube -> grape)
[06]: (Banane -> banana)
[07]: (Quitte -> quince)
[08]: (Kirsche -> cherry)
[09]: (Orange -> orange)
[10]: (Kiwi -> kiwi)

Geschafft!
Das war es zu den Hashtabellen.
Bitte verwende eine gescheite Hashfunktion und auch eine passende Vergleichsfunktion.

Viel Spass!