cours_14.md

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

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

\footnotesize

```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

  typedef enum {EMPTY, OCCUPIED, DELETED} state;

L'insertion

Pseudocode?

. . .

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?

. . .

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?

. . .

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

. . .

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

. . .

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

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. 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! ↩