Was ist eine Hash-Tabelle und wie erstellt man sie in C? [closed]

Ich habe ein paar Fragen zu einer Datenstruktur namens Hash-Tabelle (auch bekannt als assoziatives Array) und wie sie in C implementiert wird.

Wie erstellt man eine Hash-Tabelle in C? Was ist eine Hashtabelle und wie implementiert man sie? Warum sollte ich eine Hash-Tabelle anstelle eines Arrays verwenden wollen?

HINWEIS: Ich weiß, dass dies eine wirklich umfassende Frage ist, die eine umfassende Antwort erfordert, aber ich habe sie gestellt, weil mich einige Leute gefragt haben, was das alles sei. Also habe ich es hier eingefügt, um es vollständig zu erklären und anderen zu helfen.

Voraussetzungen

Für diese Antwort gehe ich davon aus, dass Sie wissen, wie man Zeiger und Strukturen verwendet, und ein grundlegendes Verständnis der C-Sprache haben.

Auch wenn Sie es nicht wissen. Wenn es um die Geschwindigkeit von Algorithmen und Datenstrukturen geht, sollten Sie die Begriffe kennen:

O() = (es wird “Big-oh” ausgesprochen) Big-oh oder O() bezieht sich auf die “Worst-Case-Szenario”-Laufzeit. In ähnlicher Weise ist es in der Mathematik die große O-Notation und beschreibt das Begrenzungsverhalten einer Funktion. Wenn etwas O (1) ist, ist das konstante Zeit “wirklich gut”. Wenn etwas O(n) ist, bedeutet das, wenn die Liste eine Million lang ist. Es wird im schlimmsten Fall eine Million Mal laufen. O() wird im Allgemeinen verwendet, um zu bestimmen, wie schnell etwas läuft, denn so schnell läuft es im schlimmsten Fall.

Ω = (griechischer Buchstabe Omega) bezieht sich auf das beste Szenario. Es wird nicht so oft verwendet wie O(), also werde ich nicht zu sehr ins Detail gehen. Aber wissen Sie nur, dass wenn etwas Ω (1) ist, es im besten Fall nur einmal dauert.

Θ = (griechischer Buchstabe Theta) ist insofern einzigartig, als es nur verwendet wird, wenn die O()- und Ω()-Laufzeit gleich sind. So wie im Fall des rekursiven Sortieralgorithmus Zusammenführen, sortieren. Die Laufzeit beträgt Θ(n(log(n))). Das heißt, es ist O(n(log(n))) und es ist Ω(n(log(n))).

Was ist eine Hash-Tabelle?

Eine Hash-Tabelle oder ein assoziatives Array ist eine beliebte Datenstruktur, die beim Programmieren verwendet wird. Eine Hash-Tabelle ist nur eine verknüpfte Liste (ich werde später darauf eingehen, was eine verknüpfte Liste ist) mit einer Hash-Funktion. Eine Hash-Funktion nimmt im Grunde nur Dinge und legt sie in verschiedene “Körbe”. Jeder “Korb” ist nur eine weitere verknüpfte Liste oder etwas anderes, je nachdem, wie Sie es implementieren. Ich werde mehr Details zu Hash-Tabellen erklären, wenn ich Ihnen zeige, wie man eine implementiert.

Warum sollte ich eine Hash-Tabelle anstelle eines Arrays verwenden wollen?

Ein Array ist sehr einfach zu verwenden und einfach zu erstellen, hat aber auch seine Nachteile. Nehmen wir für dieses Beispiel an, wir haben ein Programm, in dem wir alle seine Benutzer in einem Array halten möchten.

Das ist ziemlich einfach. Sagen wir einfach, wir planen, dass dieses Programm nicht mehr als 100 Benutzer hat, und füllen dieses Array mit unseren Benutzern

char* users[100];

// iterate over every user and "store" their name
for (int i = 0; i < userCount; i++)
{
    users[i] = "New username here";
}

Das funktioniert also alles bestens und auch noch richtig schnell. Das ist O(1) genau dort. Wir können auf jeden Benutzer in konstanter Zeit zugreifen.

Aber nehmen wir nun an, dass unser Programm richtig beliebt wird. Es hat jetzt über 80 Benutzer. Uh-oh! Wir erhöhen besser die Größe dieses Arrays, sonst bekommen wir einen Pufferüberlauf.

Wie machen wir das? Nun, wir müssen ein neues Array erstellen, das größer ist, und den Inhalt des alten Arrays in das neue Array kopieren.

Das ist sehr kostspielig und das wollen wir nicht. Wir wollen klug denken und nicht etwas verwenden, das eine feste Größe hat. Nun, wir wissen bereits, wie wir Zeiger zu unserem Vorteil nutzen können, und wir können Informationen in a bündeln struct wenn wir wollten.

Wir könnten also eine erstellen struct um den Benutzernamen zu speichern und ihn dann (über einen Zeiger) auf einen neuen zeigen zu lassen struct. Voila! Wir haben jetzt eine Datenstruktur, die erweiterbar ist. Es ist eine Liste gebündelter Informationen, die durch Zeiger miteinander verknüpft sind. Also der Name verkettete Liste.

Verknüpfte Listen

Lassen Sie uns also diese verknüpfte Liste erstellen. Zuerst brauchen wir eine struct

typedef struct node
{
    char* name;
    struct node* next;
}
node;

Okay, also haben wir eine Zeichenfolge name und a… Moment mal… Ich habe noch nie von einem Datentyp namens a gehört struct node. Nun, zu unserer Bequemlichkeit I typedef ein neuer “Datentyp” genannt node das ist auch unser struct genannt node.

Nun, da wir unseren Knoten für unsere Liste haben, was brauchen wir als nächstes? Nun, wir müssen eine “Root” zu unserer Liste erstellen, damit wir das können traverse es (ich werde erklären, was ich damit meine traverse später). Lassen Sie uns also eine Wurzel zuweisen. (erinnere dich daran node Datentyp I typdefed früher)

node* first = NULL;

Jetzt, wo wir unseren Root haben, müssen wir nur noch eine Funktion erstellen, um neue Benutzernamen in unsere Liste einzufügen.

/*
 * inserts a name called buffer into
 * our linked list
 */
void insert(char* buffer)
{     
    // try to instantiate node for number
    node* newptr = malloc(sizeof(node));
    if (newptr == NULL)
    {
        return;
    }

    // make a new ponter
    newptr->name = buffer;
    newptr->next = NULL;

    // check for empty list
    if (first == NULL)
    {
        first = newptr;
    }
    // check for insertion at tail
    else
    {
        // keep track of the previous spot in list
        node* predptr = first;

        // because we don't know how long this list is
        // we must induce a forever loop until we find the end
        while (true)
        {
            // check if it is the end of the list
            if (predptr->next == NULL)
            {
                // add new node to end of list
                predptr->next = newptr;

                // break out of forever loop
                break;
            }

            // update pointer
            predptr = predptr->next;
        }
    }         
}

Hier bitteschön. Wir haben eine einfache verknüpfte Liste und jetzt können wir so viele Benutzer hinzufügen, wie wir wollen, und müssen uns keine Sorgen machen, dass uns der Platz ausgeht. Aber das hat auch Nachteile. Das große Problem dabei ist, dass jeder Knoten oder „Benutzer“ in unserer Liste „anonym“ ist. Wir wissen nicht, wo sie sind oder wie viele Benutzer wir damit haben. (Natürlich gibt es Möglichkeiten, dies viel besser zu machen – ich möchte nur eine sehr einfache verknüpfte Liste zeigen.) Wir müssen die gesamte Liste durchlaufen, um einen Benutzer hinzuzufügen, da wir nicht direkt auf das Ende zugreifen können.

Es ist, als wären wir in einem riesigen Sandsturm und du kannst nichts sehen und wir müssen zu unserer Scheune. Wir können nicht sehen, wo unsere Scheune ist, aber wir haben eine Lösung. Da stehen Leute bei uns (unsere nodes) und alle halten zwei Seile (unsere Pointer). Jede Person besitzt nur ein Seil, aber dieses Seil wird am anderen Ende von jemand anderem gehalten. Genau wie unsere struct, dient das Seil als Hinweis darauf, wo sie sich befinden. Wie kommen wir zu unserer Scheune? (in diesem Beispiel ist die Scheune die letzte “Person” in der Liste). Nun, wir haben keine Ahnung, wie groß unsere Gruppe von Leuten ist oder wohin sie gehen. Tatsächlich sehen wir nur einen Zaunpfahl, an dem ein Seil befestigt ist. (Unsere Wurzel!) Dieser Zaunpfosten wird sich nie ändern, also können wir den Pfosten greifen und weitergehen, bis wir unsere erste Person sehen. Diese Person hält zwei Seile (den Zeiger des Pfostens und ihren Zeiger).

Also fahren wir weiter am Seil entlang, bis wir eine neue Person erreichen und uns an ihrem Seil festhalten. Irgendwann kommen wir ans Ende und finden unsere Scheune!

Das ist also eine verkettete Liste in Kürze. Seine Vorteile sind, dass es beliebig erweitert werden kann, aber seine Laufzeit hängt davon ab, wie groß die Liste ist, nämlich O(n). Wenn es also 1 Million Benutzer gibt, müsste es 1 Million Mal ausgeführt werden, um einen neuen Namen einzufügen! Wow, das scheint wirklich verschwenderisch zu sein, nur einen Namen einzufügen.

Zum Glück sind wir schlau und können eine bessere Lösung schaffen. Warum haben wir nicht, anstatt nur eine verkettete Liste zu haben, ein paar verkettete Listen. Eine Reihe von verknüpften Listen, wenn Sie so wollen. Warum erstellen wir nicht ein Array der Größe 26. So können wir für jeden Buchstaben des Alphabets eine eindeutige verknüpfte Liste haben. Jetzt statt einer Laufzeit von n. Wir können vernünftigerweise sagen, dass unsere neue Laufzeit n/26 sein wird. Nun, das macht überhaupt keinen großen Unterschied, wenn Sie eine Liste haben, die 1 Million groß ist. Aber wir werden es für dieses Beispiel einfach halten.

Wir haben also ein Array von verknüpften Listen, aber wie werden wir unsere Benutzer in das Array einsortieren? Nun… warum machen wir nicht eine Funktion, die entscheidet, welcher Benutzer wohin gehen soll. Diese Funktion “hasht” die Benutzer, wenn Sie so wollen, in ein Array oder eine “Tabelle”. Lassen Sie uns also diese “gehashte” verknüpfte Liste erstellen. Daher die Namens-Hash-Tabelle

Hash-tabelle

Wie ich gerade sagte, wird unsere Hash-Tabelle ein Array von verknüpften Listen sein und anhand des ersten Buchstabens ihres Benutzernamens gehasht werden. A geht auf Position 0, B zu 1 und so weiter.

Das struct für diese Hash-Tabelle ist die gleiche wie die Struktur für unsere vorherige verknüpfte Liste

typedef struct node
{
    char* name;
    struct node* next;
}
node;

Jetzt brauchen wir genau wie unsere verknüpfte Liste eine Wurzel für unsere Hash-Tabelle

node* first[26] = {NULL};

Die Wurzel ist ein Array in der Größe des Alphabets und alle Positionen darin werden initialisiert NULL. (Denken Sie daran: Das letzte Element in einer verketteten Liste muss immer auf zeigen NULL sonst würden wir nicht wissen, dass es das Ende war)

Lassen Sie uns eine Hauptfunktion erstellen. Es braucht einen Benutzernamen, den wir hashen und dann einfügen.

int main(char* name)
{
    // hash the name into a spot
    int hashedValue = hash(name);

    // insert the name in table with hashed value
    insert(hashedValue, name);
}

Hier ist also unsere Hash-Funktion. Es ist ziemlich einfach. Alles, was wir tun wollen, ist, uns den ersten Buchstaben des Wortes anzusehen und einen Wert von 0 bis 25 anzugeben, je nachdem, um welchen Buchstaben es sich handelt

/*
 * takes a string and hashes it into the correct bucket
 */
int hash(const char* buffer)
{
    // assign a number to the first char of buffer from 0-25
    return tolower(buffer[0]) - 'a';
}

Jetzt müssen wir also nur noch unsere Einfügefunktion erstellen. Es wird genauso aussehen wie unsere Einfügefunktion zuvor, außer dass wir es jedes Mal, wenn wir auf unseren Stamm verweisen, als Array referenzieren.

/*
 * takes a string and inserts it into a linked list at a part of the hash table
 */
void insert(int key, const char* buffer)
{
    // try to instantiate node to insert word
    node* newptr = malloc(sizeof(node));
    if (newptr == NULL)
    {
        return;
    }

    // make a new pointer
    strcpy(newptr->name, buffer);
    newptr->next = NULL;

    // check for empty list
    if (first[key] == NULL)
    {
       first[key] = newptr;
    }
    // check for insertion at tail
    else
    {
        node* predptr = first[key];
        while (true)
        {
            // insert at tail
            if (predptr->next == NULL)
            {
                predptr->next = newptr;
                break;
            }

            // update pointer
            predptr = predptr->next;
        }
    }
}

Das sind also die Grundlagen einer Hash-Tabelle. Es ist ziemlich einfach, wenn Sie wissen, wie man Zeiger und Strukturen verwendet. Ich weiß, das war ein ziemlich einfaches Beispiel für eine Hash-Tabelle mit nur einer Einfügefunktion, aber Sie können es viel besser machen und mit Ihrer Hash-Funktion kreativer werden. Sie können das Array auch beliebig groß machen oder sogar ein mehrdimensionales Array verwenden.