---
title: "Listes triées, listes doublement chaînées, et tables de hachage"
date: "2024-01-09"
---

# Rappel

\Huge Listes triées

# Rappel: liste triées (1/3)

## Qu'est-ce qu'une liste triée?

. . .

* une liste,
* dont les éléments sont insérés dans l'ordre.

## Structure de donnée?

. . .

```C
typedef struct _element { // chaque élément
    int data;
    struct _element *next;
} element;
typedef element* sorted_list; // la liste
```

# Rappel: liste triées (2/3)

## Fonctionnalités?

. . .

```C
// insertion de val
sorted_list sorted_list_push(sorted_list list, int val);
// la liste est-elle vide?
bool is_empty(sorted_list list); // list == NULL
// extraction de val (il disparaît)
sorted_list sorted_list_extract(sorted_list list, int val); 
 // rechercher un élément et le retourner
element* sorted_list_search(sorted_list list, int val);
```

# Rappel: liste triées (3/3)

## L'insertion: 3 cas

1. La liste est vide.

. . .

2. L'insertion se fait "avant" le premier élément.

. . .

3. L'insertion se fait après la tête de la liste.

. . .

# L'extraction

## Trois cas

1. L'élément à extraire n'est **pas** le premier élément de la liste

. . .

![Extraction d'un élément qui n'est pas le premier.](figs/sorted_list_extract_any.svg){width=70%}

. . .

\scriptsize

```C
sorted_list sorted_list_extract(sorted_list list, int val) {
    element *prec = *crt = list; // needed to glue elements together
    while (NULL != crt && val > crt->data) {
	   prec = crt;
	   crt = crt->next;
	}
    if (NULL != crt && prec != crt && crt->data == val) { // glue things together
        prec->next = crt->next;
        free(crt);
    }
    return list;
}
```


# L'extraction

2. L'élément à extraire est le premier élément de la liste

. . .

![Extraction d'un élément qui est le premier.](figs/sorted_list_extract_first.svg){width=70%}

. . .

\footnotesize

```C
sorted_list sorted_list_extract(sorted_list list, int val) {
    element *prec = *crt = list; // needed to glue elements together
    while (NULL != crt && val > crt->data) {
	   prec = crt;
	   crt = crt->next;
	}
    // glue things together
    if (NULL != crt && crt->data == val && prec == crt) {
        list = list->next;
        free(crt);
    }
    return list;
}
```

# L'extraction

3. L'élément à extraire n'est **pas** dans la liste.
    * La liste est vide.
    * La valeur est plus grande que le dernier élément de la liste.
    * La valeur est plus petite que la valeur de `crt`.

. . .

On retourne la liste inchangée.

. . .

\footnotesize

```C
sorted_list sorted_list_extract(sorted_list list, int val) {
    element *prec = *crt = list; // needed to glue elements together
    while (NULL != crt && val > crt->data) {
	   prec = crt;
	   crt = crt->next;
	}
    if (NULL == crt || crt->data != val) { // val not present
        return list;
    }
}
```

# La recherche



```C
element* sorted_list_search(sorted_list list, int val);
```

* Retourne `NULL` si la valeur n'est pas présente (ou la liste vide).
* Retourne un pointeur vers l'élément si la valeur est présente.

. . .

```C
element* sorted_list_search(sorted_list list, int val) {
    // search for element smaller than val
    element* pos = sorted_list_position(list, val); 
    if (NULL == pos && val == list->data) {
        return list; // first element contains val
    } else if (NULL != pos && NULL != pos->next 
        && val == pos->next->data) 
    {
        return pos->next; // non-first element contains val
    } else {
        return NULL; // well... val's not here
    }
}
```

# La recherche

## La fonction `sorted_list_position`

```C
element* sorted_list_position(sorted_list list, int val);
```

![Trois exemples de retour de la fonction `sorted_list_position()`.](figs/sorted_list_position.svg)

# La recherche

## Exercice: implémenter

```C
element* sorted_list_position(sorted_list list, int val);
```

. . .

```C
element* sorted_list_position(sorted_list list, int val) {
    element* pos = list;
    if (sorted_list_is_empty(list) || val <= list->data) {
        pos = NULL;
    } else {
        while (NULL != pos->next && val > pos->next->data) {
            pos = pos->next;
        }
    }
    return pos;
}
```

# Complexité de la liste chaînée triée

## L'insertion?

. . .

$$
\mathcal{O}(N).
$$

## L'extraction?

. . .

$$
\mathcal{O}(N).
$$

## La recherche?

. . .

$$
\mathcal{O}(N).
$$


# Liste doublement chaînée

## Application: navigateur ou éditeur de texte

* Avec une liste chaînée:
    * Comment implémenter les fonctions `back` et `forward` d'un navigateur?
    * Comment implémenter les fonctions `undo` et `redo` d'un éditeur de texte?

. . .

Pas possible.

## Solution?

. . .

* Garder un pointeur supplémentaire sur l'élément précédent et pas seulement le
  suivant.

. . .

* Cette structure de donnée est la **liste doublement chaînée** ou **doubly
  linked list**.

# Liste doublement chaînée

\Huge Liste doublement chaînée

# Liste doublement chaînée

## Exercices

* Partir du dessin suivant et par **groupe de 5**

![Un schéma de liste doublement chaînée d'entiers.](figs/doubly_linked_list.svg)

1. Écrire les structures de données pour représenter la liste doublement
   chaînée dont le type sera `dll` (pour
   `doubly_linked_list`)

# Liste doublement chaînée

2. Écrire les fonctionnalités de création et consultation

```C 
// crée la liste doublement chaînée
dll dll_create();
// retourne la valeur à la position actuelle dans la liste
int dll_value(dll list);
// la liste est-elle vide?
bool dll_is_empty(dll list);
// Est-ce que pos est le 1er élément?
bool dll_is_head(dll list);
// Est-ce que pos est le dernier élément?
bool dll_is_tail(dll list);
// data est-elle dans la liste?
bool dll_is_present(dll list, int data);
// affiche la liste
void dll_print(dll list);
```

# Liste doublement chaînée

3. Écrire les fonctionnalités de manipulation 

```C 
// déplace pos au début de la liste
dll dll_move_to_head(dll list);
// déplace pos à la position suivante dans la liste
dll dll_next(dll list);
// déplace pos à la position précédente dans la liste
dll dll_prev(dll list);
```

# Liste doublement chaînée

4. Écrire les fonctionnalités d'insertion

```C
// insertion de data dans l'élément après pos
dll dll_insert_after(dll list, int data);
// insertion de data en tête de liste
dll dll_push(dll list, int data);
```

5. Écrire les fonctionnalités d'extraction

```C
// extraction de la valeur se trouvant dans l'élément pos
// l'élément pos est libéré
int dll_extract(dll *list);
// extrait la donnée en tête de liste
int dll_pop(dll *list);
// vide la liste
void dll_destroy(dll *list);
```

# Les tables de hachage

\Huge Les tables de hachage

# Tableau vs Table

## Tableau

* Chaque élément (ou valeur) est lié à un indice (la case du tableau).

```C 
annuaire tab[2] = {
    "+41 22 123 45 67", "+41 22 234 56 78", ...
};
tab[1] == "+41 22 123 45 67";
```

## Table

* Chaque élément (ou valeur) est lié à une clé.

```C 
annuaire tab = {
//  Clé   ,    Valeur
    "Paul",    "+41 22 123 45 67",
    "Orestis", "+41 22 234 56 78",
};
tab["Paul"]    == "+41 22 123 45 67";
tab["Orestis"] == "+41 22 234 56 78";
```

# Table

## Définition

Structure de données abstraite où chaque *valeur* (ou élément) est associée à une *clé* (ou
argument).

On parle de paires *clé-valeur* (*key-value pairs*).

## Donnez des exemples de telles paires

. . .

* Annuaire (nom-téléphone),
* Catalogue (objet-prix),
* Table de valeur fonctions (nombre-nombre),
* Index (nombre-page)
* ...

# Table

## Opérations principales sur les tables

* Insertion d'élément (`insert(clé, valeur)`{.C}), insère la paire `clé-valeur`
* Consultation (`get(clé)`{.C}), retourne la `valeur` correspondant à `clé`
* Suppression (`remove(clé)`{.C}), supprime la paire `clé-valeur`

## Structure de données / implémentation

Efficacité dépend de différents paramètres:

* taille (nombre de clé-valeurs maximal),
* fréquence d'utilisation (insertion, consultation, suppression),
* données triées/non-triées,
* ...

# Consultation séquentielle (`sequential_get`)

## Séquentielle

* table représentée par un (petit) tableau ou liste chaînée,
* types: `key_t` et `value_t` quelconques, et `key_value_t`

    ```C
    typedef struct {
        key_t key;
        value_t value;
    } key_value_t;
    ```
* on recherche l'existence de la clé séquentiellement dans le tableau, on
  retourne la valeur.

# Consultation séquentielle (`sequential_get`)

## Implémentation? Une idée?

. . .

```C
bool sequential_get(int n, key_value_t table[n], key_t key, 
    value_t *value) 
{
    int pos = n - 1;
    while (pos >= 0) {
        if (key ==  table[pos].key) {
            *value = table[pos].value;
            return true;
        }
        pos--;
    }
    return false;
}
```

. . .

## Inconvénient?

# Consultation séquentielle (`sequential_get`)

## Exercice: implémenter la même fonction avec une liste chaînée

Poster le résultat sur matrix.

# Consultation dichotomique (`binary_get`)

## Dichotomique

* table représentée par un (petit) tableau trié par les clés,
* types: `key_t` et `value_t` quelconques, et `key_value_t`
* on recherche l'existence de la clé par dichotomie dans le tableau, on
  retourne la valeur,
* les clés possèdent la notion d'ordre (`<, >, =` sont définis).

# Consultation dichotomique (`binary_get`)

\footnotesize

## Implémentation? Une idée?

. . .

```C
bool binary_get1(int n, value_key_t table[n], key_t key, value_t *value) {
    int top = n - 1, bottom = 0;
    while (top > bottom) { 
        int middle = (top + bottom) / 2;
        if (key > table[middle].key) {
            bottom  = middle+1;
        } else {
            top = middle;
        }
    }
    if (key == table[top].key) {
        *value = table[top].value;
        return true;
    } else {
        return false;
    }
} 
```

# Consultation dichotomique (`binary_get`)

\footnotesize

## Autre implémentation

```C
bool binary_get2(int n, key_value_t table[n], key_t key, value_t *value) {
    int top = n - 1, bottom = 0;
    while (true) { 
        int middle = (top + bottom) / 2;
        if (key > table[middle].key) {
            bottom  = middle + 1;
        } else if (key < table[middle].key) {
            top = middle;
        } else {
            *value = table[middle].value;
            return true;
        }
        if (top < bottom) {
             break;
        }
    }
    return false;
}
```

## Quelle est la différence avec le code précédent?

# Transformation de clé (hashing)

## Problématique: Numéro AVS (13 chiffres)

* Format: 106.3123.8492.13

    ```
    Numéro AVS    | Nom
    0000000000000 | -------
    ...           | ...
    1063123849213 | Paul
    ...           | ...
    3066713878328 | Orestis
    ...           | ...
    9999999999999 | -------
    ```

## Quelle est la clé? Quelle est la valeur?

. . .

* Clé: Numéro AVS, Valeur: Nom.

## Nombre de clés? Nombre de citoyens? Rapport?

. . .

* $10^{13}$ clés, $10^7$ citoyens, $10^{-5}$ ($10^{-3}\%$ de la table est
  occupée) $\Rightarrow$ *inefficace*.
* Pire: $10^{13}$ entrées ne rentre pas dans la mémoire d'un
  ordinateur.

# Transformation de clé (hashing)

## Problématique 2: Identificateurs d'un programme

* Format: 8 caractères (simplification)

    ```
    Identificateur | Adresse
    aaaaaaaa       | -------
    ...            | ...
    resultat       | 3aeff
    compteur       | 4fedc
    ...            | ...
    zzzzzzzz       | -------
    ```

## Quelle est la clé? Quelle est la valeur?

. . .

* Clé: Identificateur, Valeur: Adresse.

## Nombre de clés? Nombre d'identificateur d'un programme? Rapport?

. . .

* $26^{8}\sim 2\cdot 10^{11}$ clés, $2000$ identificateurs, $10^{-8}$ ($10^{-6}\%$ de la table est
  occupée) $\Rightarrow$ *un peu inefficace*.

# Fonctions de transformation de clé (hash functions)

* La table est représentée avec un tableau.
* La taille du tableau est beaucoup plus petit que le nombre de clés.
* On produit un indice du tableau à partir d'une clé:
$$
h(key) = n,\quad n\in\mathbb{N}.
$$
En français: on transforme `key` en nombre entier qui sera l'indice dans le
tableau correspondant à `key`.

## La fonction de hash

* La taille du domaine des clés est beaucoup plus grand que le domaine des
  indices.
* Plusieurs indices peuvent correspondre à la **même clé**:
    * Il faut traiter les **collisions**.
* L'ensemble des indices doit être plus petit ou égal à la taille de la table.

## Une bonne fonction de hash

* Distribue uniformément les clés sur l'ensemble des indices.

# Fonctions de transformation de clés: exemples

## Méthode par troncature

\begin{align*}
&h: [0,9999]\rightarrow [0,9]\\
&h(key)=\mbox{troisième chiffre du nombre.}
\end{align*}

```
Key  | Index
0003 | 0
1123 | 2 \
1234 | 3  |-> collision.
1224 | 2 / 
1264 | 6 
```

## Quelle est la taille de la table?

. . .

C'est bien dix oui.

# Fonctions de transformation de clés: exemples

## Méthode par découpage

Taille de l'index: 3 chiffres.

```
key = 321 991 24 ->  321
                     991
                    + 24
                    ----
                    1336 -> index = 336
```

## Devinez l'algorithme?

. . .

On part de la gauche:

1. On découpe la clé en tranche de longueur égale à celle de l'index.
2. On somme les nombres obtenus.
3. On tronque à la longueur de l'index.

# Fonctions de transformation de clés: exemples

## Méthode multiplicative

Taille de l'index: 2 chiffres.

```
key = 5486 -> key^2 = 30096196 -> index = 96
```

On prend le carré de la clé et on garde les chiffres du milieu du résultat.

# Fonctions de transformation de clés: exemples

## Méthode par division modulo

Taille de l'index: `N` chiffres.

```
h(key) = key % N.
```

## Quelle doit être la taille de la table?

. . .

Oui comme vous le pensiez au moins `N`.

# Traitement des collisions

## La collision

```
key1 != key2, h(key1) == h(key2)
```

## Traitement (une idée?)

. . .

* La première clé occupe la place prévue dans le tableau.
* La deuxième (troisième, etc.) est placée ailleurs de façon **déterministe**.

Dans ce qui suit la taille de la table est `table_size`.

# La méthode séquentielle

\footnotesize

## Comment ça marche?

* Quand l'index est déjà occupé on regarde sur la position suivante, jusqu'à en
  trouver une libre.

```C
index = h(key);
while (table[index].state == OCCUPIED && table[index].key != key) {
   index = (index + 1) % table_size; // attention à pas dépasser
}
table[index].key = key;
table[index].state = OCCUPIED;
```

## Problème?

. . .

* Regroupement d'éléments (clustering).

# Méthode linéaire

\footnotesize

## Comment ça marche?

* Comme la méthode séquentielle mais on "saute" de `k`.

```C
index = h(key);
while (table[index].state == OCCUPIED && table[index].key != key) {
   index = (index + k) % table_size; // attention à pas dépasser
}
table[index].key = key;
table[index].state = OCCUPIED;
```

## Quelle valeur de `k` éviter?

. . .

* Une valeur où  `table_size` est multiple de `k`.

Cette méthode répartit mieux les regroupements au travers de la table.

# Méthode du double hashing

\footnotesize

## Comment ça marche?

* Comme la méthode linéaire, mais `k = h2(key)` (variable).

```C
index = h(key);
while (table[index].state == OCCUPIED && table[index].key != key) {
   index = (index + h2(k)) % table_size; // attention à pas dépasser
}
table[index].key = key;
table[index].state = OCCUPIED;
```

## Quelle propriété doit avoir `h2`?

## Exemple

```C
h2(key) = (table_size - 2) - key % (table_size -2)
```

# Méthode pseudo-aléatoire

\footnotesize

## Comment ça marche?

* Comme la méthode linéaire mais on génère `k` pseudo-aléatoirement.

    ```C
    index = h(key);
    while (table[index].state == OCCUPIED && table[index].key != key) {
        index = (index + random_number) % table_size;
    }
    table[index].key = key;
    table[index].state = OCCUPIED;
    ```

## Comment s'assurer qu'on va bien retrouver la bonne clé?

. . .

* Le germe (seed) de la séquence pseudo-aléatoire doit être le même.
* Le germe à choisir est l'index retourné par `h(key)`.

    ```C
    srand(h(key));
    while {
        random_number = rand();
    }
    ```

# Méthode quadratique

* La fonction des indices de collision est de degré 2.
* Soit $J_0=h(key)$, les indices de collision se construisent comme:

    ```C 
    J_i = J_0 + i^2 % table_size, i > 0,
    J_0 = 100, J_1 = 101, J_2 = 104, J_3 = 109, ...
    ```

## Problème possible?

. . .

* Calculer le carré peut-être "lent".
* En fait on peut ruser un peu.

# Méthode quadratique

\footnotesize

```C 
J_i = J_0 + i^2 % table_size, i > 0,
J_0 = 100
          \
           d_0 = 1 
          /        \
J_1 = 101           Delta = 2
          \        /
           d_1 = 3
          /        \
J_2 = 104           Delta = 2
          \        /
           d_2 = 5
          /        \
J_3 = 109           Delta = 2
          \        /
           d_3 = 7
          /        
J_4 = 116
--------------------------------------
J_{i+1} = J_i + d_i,
d_{i+1} = d_i + Delta, d_0 = 1, i > 0.
```

# Méthode de chaînage

## Comment ça marche?

* Chaque index de la table contient un pointeur vers une liste chaînée
  contenant les paires clés-valeurs.

## Un petit dessin

```











```

# Méthode de chaînage

## Exemple

On hash avec la fonction `h(key) = key % 11` (`key` est le numéro de la lettre
de l'alphabet)

```
 U  | N | E | X | E | M | P | L | E | D | E | T | A | B | L | E
 10 | 3 | 5 | 2 | 5 | 2 | 5 | 1 | 5 | 4 | 5 | 9 | 1 | 2 | 1 | 5
```

## Comment on représente ça? (à vous)

. . .

![La méthode de chaînage](figs/fig_hash.png){width=80%}

# Méthode de chaînage

Avantages:

* Si les clés sont grandes l'économie de place est importante (les places vides
  sont `NULL`).
* La gestion des collisions est conceptuellement simple.
* Pas de problème de regroupement (clustering).

# Exercice 1

* Construire une table à partir de la liste de clés suivante:
    ```
    R, E, C, O, U, P, A, N, T
    ```

* On suppose que la table est initialement vide, de taille $n = 13$.
* Utiliser la fonction $h1(k)= k \mod 13$ où k est la $k$-ème lettre de l'alphabet et un traitement séquentiel des collisions.

# Exercice 2

* Reprendre l'exercice 1 et utiliser la technique de double hachage pour traiter
  les collisions avec

\begin{align*}
h_1(k)&=k\mod 13,\\
h_2(k)&=1+(k\mod 11).
\end{align*}
* La fonction de hachage est donc $h(k)=(h(k)+h_2(k)) \% 13$ en cas de
  collision.


# Exercice 3

* Stocker les numéros de téléphones internes d'une entreprise suivants dans un
tableau de 10 positions.
* Les numéros sont compris entre 100 et 299.
* Soit $N$ le numéro de téléphone, la fonction de hachage est
$$
h(N)=N\mod 10.
$$
* La fonction de gestion des collisions est
$$
C_1(N,i)=(h(N)+3\cdot i)\mod 10.
$$
* Placer 145, 167, 110, 175, 210, 215 (mettre son état à occupé).
* Supprimer 175 (rechercher 175, et mettre son état à supprimé).
* Rechercher 35.
* Les cases ni supprimées, ni occupées sont vides.
* Expliquer se qui se passe si on utilise?
$$
C_1(N,i)=(h(N)+5\cdot i)\mod 10.
$$

