Qu'est ce qu'une table de hachage et comment faire en C?

Conditions préalables

Pour cette réponse, je vais supposer que vous savez comment utiliser les pointeurs, les structures, et avoir une compréhension de base du langage C.

Aussi, si vous ne connaissez pas. Quand on parle de la vitesse d'algorithmes et structures de données, vous devez connaître les termes:

O() = (ça se prononce "Big o"), Grand-oh ou O() fait référence à la "pire-cas" scénario de l'exécution. De même, en mathématiques, il est grand O notation et décrit la limitation de comportement d'une fonction. Si somethings O(1) que la constante de temps "vraiment bon". Si somethings O(n) ce qui signifie que si la liste est un m de long. Il est, au pire, va courir d'un million de fois. O() est généralement utilisé pour déterminer la vitesse de quelque chose fonctionne, parce que c'est à quelle vitesse ça va fonctionner dans les pires cas.

Ω = (la lettre grecque Oméga) se réfère à son meilleur des cas. Il n'est pas utilisé que comme beaucoup comme O() donc je ne vais pas trop entrer dans les détails à ce sujet. Mais il faut savoir que si il y a des choses Ω(1), dans meilleur des cas, ça va prendre juste une fois.

Θ = (lettre grecque thêta) est unique en ce qu'il est utilisé uniquement lorsque les O() et Ω() d'exécution sont les mêmes. Ainsi, comme dans le cas de la récursif algorithme de tri fusion de tri. Il est temps d'exécution est en Θ(n(log(n))). Ce qui signifie qu'il est en O(n(log(n))) et c'est Ω(n(log(n))).

Qu'est ce qu'une table de Hachage?

Une table de hachage ou un tableau associatif est un populaire de la structure de données utilisée dans la programmation. Une table de hachage est juste une liste chaînée (je vais arriver à ce qu'une liste chaînée est plus tard) avec une fonction de hachage. Une fonction de hachage, fondamentalement, tout simplement, prend les choses et les met dans les différents "paniers". Chaque "panier" est juste une autre liste, ou quelque chose d'autre en fonction de comment la mettre en œuvre. Je vais vous expliquer plus de détails sur les tables de hachage quand je vous montre comment mettre en œuvre un.

Pourquoi voudrais-je utiliser une table de hachage plutôt qu'un tableau?

Un tableau est très facile à utiliser et simple à faire, mais il a aussi ses bas côtés. Pour cet exemple, disons que nous avons un programme et dans ce programme, nous voulons garder tous que c'est l'utilisateur dans un tableau.

C'est assez simple. Disons juste que nous plan sur ce programme, n'ayant pas plus de 100 utilisateurs et de remplir ce tableau avec nos utilisateurs

char* users[100];

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

De sorte que fonctionne super bien et vraiment rapide. C'est un O(1) à droite. On peut accéder à n'importe quel utilisateur en temps constant.

Mais nous allons maintenant supposer que notre programme est très populaire. Il a maintenant plus de 80 utilisateurs. Uh-Oh! Nous avons mieux augmenter la taille de ce tableau ou autre chose, nous allons obtenir un dépassement de la mémoire tampon.

Alors, comment faisons-nous cela? Eh bien, nous allons avoir à faire un nouveau tableau qui est plus grand et copiez le contenu de l'ancien tableau dans le tableau.

Qui est très coûteux et nous ne voulons pas le faire. Nous voulons penser intelligemment et de ne pas utiliser quelque chose qui a une taille fixe. Eh bien, nous savons déjà comment utiliser les pointeurs à notre avantage et nous pouvez regrouper des informations dans une structure si nous le voulions.

Donc, nous pourrions créer une structure pour stocker le nom d'utilisateur et point (via un pointeur) vers une nouvelle structure. Alto! Nous avons maintenant une structure de données qui est extensible. C'est une liste de livré des informations qui sont reliés par des pointeurs. Donc le nom de la liste liée.

Listes Liées

Permet donc de créer cette liste liée. Tout d'abord nous allons avoir besoin d'un struct

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

Bien, de sorte que nous avons une chaîne name et un... Attends... je n'ai jamais entendu parler d'un type de données appelé un struct node. Bien pour notre commodité, je typedef un nouveau "type de données" appelé un nœud qui se trouve être notre structure appelée nœud.

Alors, maintenant que nous avons notre nœud de notre liste à faire, maintenant, que faisons-nous besoin? Eh bien, nous avons besoin de créer une "racine" à notre liste. Donc, nous pouvons le traverser (je vais vous expliquer ce que je veux dire par traverser plus tard). Donc permet d'attribuer une racine. (rappelez-vous que les nœuds de données de type I définition de type plus tôt)

node* first = NULL;

Alors, maintenant que nous avons nos racines tout ce que nous devons faire est de faire une fonction pour insérer de nouveaux noms d'utilisateur dans notre liste.

/*
 * 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;
        }
    }         
}

Donc là vous allez. Nous avons une base de liste, et maintenant, nous pouvons continuer à ajouter des utilisateurs tout ce que nous voulons et nous n'avons pas à vous soucier de manquer d'espace. Mais cela vient avec bas côtés. Le gros problème avec cette approche est que chaque nœud ou "utilisateur" dans notre liste est "anonyme". Nous ne savons pas étaient-ils sont à combien d'utilisateurs que nous avons avec cette. (bien sûr, il ya des façons de rendre ce beaucoup mieux, mais je veux juste montrer d'une très simple liste chaînée), de Sorte que nous avons à parcourir toute la liste pour ajouter un utilisateur car nous ne pouvons pas accéder à la fin.

C'est comme nous sommes dans une énorme tempête de poussière et vous ne pouvez pas voir quoi que ce soit et nous avons besoin de faire notre grange. Nous ne pouvons pas voir où notre grange est mais nous avons une solution. Il y a des gens debout que l'on (nos nœuds) et ils sont tous la tenue de deux cordes (notre pointeurs). Chaque personne possède une corde, mais que la corde est tenue à l'autre extrémité par quelqu'un d'autre. Tout comme notre structure, la corde agit comme un pointeur à l'endroit où ils sont. Alors, comment pouvons-nous arriver à notre grange? (pour cet exemple, la grange est le dernier "personne" dans la liste). Eh bien, nous n'avons aucune idée de la taille de notre ligne de personnes sont ou d'où ils vont. En fait, tout ce que nous voyons est un poteau de clôture, avec une corde attachée à lui. (La racine de notre!) qui poteau de clôture ne changera jamais donc on peut se saisir de la poste et de commencer à se déplacer le long jusqu'à ce que nous voyons notre première personne. Cette personne est tenue de deux cordes (le poste de pointeur et de leurs pointeur).

Nous avons donc continuer à voyager le long de la corde jusqu'à ce que nous arrivons à une nouvelle personne et de saisir sur leur corde. Finalement, nous arrivons à la fin et de trouver notre grange!

C'est donc une liste liée dans une coquille de noix. Ses avantages sont qu'il peut étendre autant que vous voulez, mais il est temps d'exécution dépend de la taille de la liste. Il est temps d'exécution est O(n). Où si la liste était de 1 million de grande, elle aurait à courir 1 million de fois pour exécuter pour insérer un nouveau nom! Wow c'est vraiment juste gaspillage d'insérer 1 nom.

Heureusement, nous sommes intelligents et de créer une meilleure solution. Pourquoi n'avons-nous pas, au lieu d'avoir juste une liste liée, ont un peu les listes chaînées. Un tableau de listes liées, si vous voulez. Pourquoi ne pas faire un tableau de taille 26. Afin que nous puissions avoir une unique liste, pour chaque lettre de l'alphabet. Maintenant, au lieu d'une durée d'exécution de n. Nous pouvons raisonnablement dire que notre nouveau moment de l'exécution des n/26. Maintenant que ne fera pas beaucoup de différence si vous avez une liste de 1 million de gros. Mais nous allons garder les choses simples pour cet exemple.

Nous avons donc un tableau de listes liées mais comment allons-nous le tri de nos utilisateurs dans le tableau. Eh bien... pourquoi ne pas faire une fonction qui décide de l'utilisateur qui doit aller où. Cette fonction de "hachage" les utilisateurs si vous allez dans un tableau ou la "table". Créons donc ce "haché" liste liée. Ainsi, le nom de la table de hachage

Table De Hachage

Comme je viens de le dire, notre table de hachage sera un tableau de listes liées et sont hachés par la première lettre de leur nom d'utilisateur. Une volonté d'aller à la position 0, B 1, et ainsi de suite.

La structure pour le cette table de hachage sera la même que la structure de notre précédente liste liée

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

Maintenant, tout comme notre liste liée, nous avons besoin d'une racine pour notre table de hachage

node* first[26] = {NULL};

La racine sera un tableau de la taille de l'alphabet et tous les postes, il sera initialisé à NULL. (Rappelez-vous: le dernier élément dans une liste, a toujours pour point de NULL ou autre chose, nous ne savons pas, c'était la fin)

Permet de faire une fonction principale. Qui prend un nom d'utilisateur, nous allons hachage puis l'insérer.

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);
}

Voici donc notre fonction de hachage. C'est assez simple. Tout ce que nous voulons faire est de regarder la première lettre du mot et de donner une valeur de 0 - 25 basé sur ce que la lettre c'est

/*
 * 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';
}

Alors maintenant, tous nous avons besoin est de créer notre insérer une fonction. Il va ressembler notre insérer une fonction avant de l'exception chaque fois que nous faisons référence à nos racines, nous allons référencer comme un tableau.

/*
 * 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->word, 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;
        }
    }
}

Donc, c'est les bases d'une table de hachage. C'est assez simple si vous savez comment utiliser les pointeurs et structures. Je sais que c'est un exemple assez simple d'une table de hachage avec seulement une fonction d'insertion, mais vous pouvez faire beaucoup mieux et plus de créativité avec votre fonction de hachage. Vous pouvez également faire le tableau aussi grand que vous le voulez ou même utiliser un tableau multi-dimensionnel.