---
title: "Tables de hachage"
date: "2022-01-19"
patat:
  eval:
    tai:
      command: fish
      fragment: false
      replace: true
    ccc:
      command: fish
      fragment: false
      replace: true
  images:
    backend: auto
---

# 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.
$$

# Préambule

\small

* On considère pas le cas du chaînage en cas de collisions.
* L'insertion est construite avec une forme du type

    ```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;
    ```
\normalsize

* Gestion de l'état d'une case *explicite*

    ```C
    typedef enum {EMPTY, OCCUPIED, DELETED} state;
    ```

# L'insertion

## Pseudocode?

. . .

```C
insert(table, key, value) {
    index = hash de la clé;
    index = 
        si "index" est déjà "occupé"
        et la clé correspondante n'est pas "key"
        alors gérer la collision;

    changer l'état de la case "index" à "occupé";
    changer la valeur de la case "index" à "value";
}
```

# La suppression

## Pseudocode?

. . .

```C
value_t remove(table, key) {
    index = hash de la clé;
    tant que l'état de la case n'est pas "vide"
        si "index" est "occupé" et la clé est "key" 
            changer l'état de la case à "supprimé"
        sinon
            index = rehash
}
```

# La recherche

## Pseudocode?

. . .

```C
bool search(table, key, value) {
    index = hash de la clé;
    tant que l'état de la case n'est pas "vide"
        si "index" est "occupé" et la clé est "key" 
            retourner vrai
        sinon
            index = rehash
}
```

# Écrivons le code!

* Mais avant:
    * Quelles sont les structures de données dont nous avons besoin?
    * Y a-t-il des fonctions auxiliaires à écrire?
    * Écrire les signatures des fonctions.

. . .

## Structures de données

\footnotesize

. . .

```C
typedef enum {empty, deleted, occupied};
typedef ... key_t;
typedef ... value_t;
typedef struct _cell_t {
    key_t key; 
    value_t value;
    state_t state;
} cell_t;
typedef struct _hm {
    cell_t *table;
    int capacity;
    int size;
} hm;
```

# Écrivons le code!

## Fonctions auxiliaires

. . .

```C
static int hash(key_t key);
static int rehash(int index, key_t key);
static int find_index(hm h, key_t key);
```

##  Signature de l'API 

```C
void hm_init(hm *h, int capacity);
void hm_destroy(hm *h);
bool hm_set(hm *h, key_t key, value_t *value);
bool hm_get(hm h, key_t key, value_t *value);
bool hm_remove(hm *h, key_t key, value_t *value);
bool hm_search(hm h, key_t key);
void hm_print(hm h);
```

# Live code session! 

0. Offered to you by ProtonVPN[^1]!

. . .

1. Like the video.
2. Subscribe to the channel.
3. Use our one time voucher for ProtonVPN: `PAULISAWESOME`.
4. Consider donating on our patreon.

[^1]: The fastest way to connect to BBB!
