HASH
TABLES

Une hash table (table de hachage) est une structure de données qui stocke des paires clé → valeur et permet d'accéder à n'importe quelle valeur en O(1) — temps constant, peu importe la taille de la table. Elle utilise une fonction de hachage pour convertir une clé (string, int...) en un index de tableau.

/* ── 1. Le nœud (une paire clé/valeur) ─────────────────────── */
typedef struct hash_node_s
{
    char              *key;    /* la clé   — une string */
    char              *value;  /* la valeur — une string */
    struct hash_node_s *next;   /* chaînage en cas de collision */
} hash_node_t;

/* ── 2. La table elle-même ──────────────────────────────────── */
typedef struct hash_table_s
{
    unsigned long int  size;   /* nombre de cases dans le tableau */
    hash_node_t      **array;  /* tableau de pointeurs vers des nœuds */
} hash_table_t;

Visualisation de la structure en mémoire :

  hash_table_t
  ┌──────────┬──────────────────────────────────────────┐
  │ size = 8 │ array (pointeur vers tableau de ptr)     │
  └──────────┴──────────────────────────────────────────┘
                │
                ▼
  array[0] → NULL
  array[1] → NULL
  array[2] → [key:"age"  | val:"25"  | next:NULL]
  array[3] → [key:"name" | val:"Alice"| next:NULL]
  array[4] → NULL
  array[5] → [key:"city" | val:"Paris"| next:NULL]
  array[6] → NULL
  array[7] → NULL

La méthode utilisée à Holberton — chaque case du tableau contient une linked list de nœuds. En cas de collision, on ajoute en tête de liste.

void hash_table_print(const hash_table_t *ht)
{
    hash_node_t       *node;
    unsigned long int  i;

    if (!ht)
        return;
    printf("{");
    i = 0;
    while (i < ht->size)
    {
        node = ht->array[i];
        while (node != NULL)
        {
            printf("'%s': '%s', ", node->key, node->value);
            node = node->next;
        }
        i++;
    }
    printf("}\n");
}

#include <stdio.h>
#include <stdlib.h>
#include "hash_tables.h"

int main(void)
{
    hash_table_t *ht;
    char         *val;

    ht = hash_table_create(1024);  /* créer une table de 1024 cases */
    if (!ht)
        return (1);

    hash_table_set(ht, "name",  "Alice");
    hash_table_set(ht, "age",   "25");
    hash_table_set(ht, "city",  "Paris");
    hash_table_set(ht, "name",  "Bob");    /* mise à jour */

    val = hash_table_get(ht, "name");
    printf("name = %s\n", val);    /* → "Bob" */

    val = hash_table_get(ht, "city");
    printf("city = %s\n", val);    /* → "Paris" */

    val = hash_table_get(ht, "unknown");
    printf("unknown = %p\n", (void*)val); /* → NULL */

    hash_table_print(ht);
    hash_table_delete(ht);
    return (0);
}

/*
 *  LES 2 STRUCTURES
 *  ─────────────────────────────────────────────────────────
 *  hash_node_t  → { char *key, char *value, node_t *next }
 *  hash_table_t → { unsigned long int size, node_t **array }
 *
 *  LE FLUX
 *  ─────────────────────────────────────────────────────────
 *  SET : key → hash_djb2(key) % size → idx → insert en tête
 *  GET : key → hash_djb2(key) % size → idx → strcmp dans liste
 *
 *  LA FONCTION DJB2
 *  ─────────────────────────────────────────────────────────
 *  hash = 5381
 *  while (c = *str++)
 *      hash = hash * 33 + c   (ou (hash << 5) + hash + c)
 *
 *  LES COLLISIONS
 *  ─────────────────────────────────────────────────────────
 *  Gérées par chaining (linked list par case)
 *  Insertion toujours EN TÊTE → O(1)
 *
 *  COMPLEXITÉ
 *  ─────────────────────────────────────────────────────────
 *  set / get / delete    → O(1) moyen, O(n) pire cas
 *  print / delete_table  → O(n + m)  toujours
 *
 *  RÈGLES D'OR
 *  ─────────────────────────────────────────────────────────
 *  1. strdup() pour key et value — jamais stocker les ptr originaux
 *  2. Toujours hash % size — jamais utiliser le hash brut comme index
 *  3. strcmp() pour comparer les clés — jamais == sur char*
 *  4. Initialiser array à NULL — jamais laisser du garbage
 *  5. free(key) → free(value) → free(node) → free(array) → free(ht)
 *  6. Insertion en tête — O(1) garanti
 */