Les tables de hachage : l'arme secrète qui rend votre code 1000 fois plus rapide

Qu'est-ce qu'une table de hachage et pourquoi en a-t-on besoin ?

Une table de hachage (table de hachage ou carte de hachage) est une structure de données qui stocke des paires clé-valeur et fournit un accès très rapide aux données. En moyenne, les opérations de recherche, d'insertion et de suppression sont effectuées en O(1) — temps constant. Cela signifie que, indépendamment du fait que 10 ou 10 millions d'éléments soient stockés dans la table, l'accès à l'un d'entre eux prendra à peu près le même temps.

Un exemple simple de la vie :

const userAges = {
    "Alexey": 28,
    "Maria": 25,
    "Dmitry": 32
};

console.log(userAges["Maria"]); // 25 - accès instantané !

Dans la plupart des langages de programmation modernes, les tables de hachage sont intégrées : dict en Python, Map en JavaScript, HashMap en Java, map en Go.

Comment fonctionne une table de hachage

Sous le capot, une table de hachage est un tableau ordinaire. La magie se produit grâce à fonctions de hachage, qui convertit la clé (chaîne, nombre ou objet) en un index de tableau.

Processus de travail :

1. Hachage de la clé: La clé (par exemple, « Alexey ») est passée à travers une fonction de hachage qui renvoie un nombre (par exemple, 42)

2. Calcul de l'indice: Le résultat du hachage est converti en un index de tableau à l'aide de l'opération de reste de division : index = hash % array.length

3. Enregistrement de la valeur: La valeur est enregistrée dans la cellule du tableau avec cet index

"Alexey" → hash("Alexey") → 1892374 → 1892374 % 10 → index 4 Array : [_, _, _, _, {key : "Alexey", value : 28}, _, _, _, _, _]

Fonctions de hachage : le cœur du système

Une bonne fonction de hachage doit avoir plusieurs propriétés :

• Déterminisme - la même clé donne toujours le même hachage

• Uniformité — les hachages doivent être répartis uniformément sur toute la plage de valeurs

• Rapidité - le calcul du hachage doit être rapide

• Minimisation des collisions — des clés différentes doivent donner des hachages différents

Exemple de fonction de hachage simple pour les chaînes :

function simpleHash(str, tableSize) {
    let hash = 0;
    for (let i = 0; i < str.length; i++) {
        hash = (hash + str.charCodeAt(i) * (i + 1)) % tableSize;
    }
    return hash;
}

console.log(simpleHash("Alexey", 100)); // par exemple, 67
console.log(simpleHash("Maria", 100));   // par exemple, 23

Dans les systèmes réels, des fonctions plus complexes sont utilisées, telles que MurmurHash, CityHash ou des fonctions cryptographiques telles que SHA-256 (pour des cas particuliers).

Conflits : lorsque deux clés veulent la même place

Collision se produit lorsque deux clés différentes obtiennent le même index après le hachage. C'est un problème inévitable, car le nombre de clés possibles est généralement supérieur à la taille du tableau.

« Alexey » → index 4 « Dmitry » → index 4 ← Collision !

Méthode de chaînage (Chaining)

La façon la plus populaire de résoudre les conflits. Chaque cellule du tableau ne contient pas une seule valeur, mais une liste (chaîne) de toutes les valeurs avec le même index.

class HashTable {
    constructor(size = 50) {
        this.table = new Array(size);
        this.size = size;
    }

    _hash(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash = (hash + key.charCodeAt(i) * (i + 1)) % this.size;
        }
        return hash;
    }

    set(key, value) {
        const index = this._hash(key);
        
        if (!this.table[index]) {
            this.table[index] = [];
        }
        
        // Vérifiez si une telle clé existe déjà
        for (let item of this.table[index]) {
            if (item[0] === key) {
                item[1] = value; // Mise à jour de la valeur
                return;
            }
        }
        
        // Ajout d'une nouvelle paire clé-valeur
        this.table[index].push([key, value]);
    }

    get(key) {
        const index = this._hash(key);
        const bucket = this.table[index];
        
        if (!bucket) return undefined;
        
        for (let item of bucket) {
            if (item[0] === key) {
                return item[1];
            }
        }
        
        return undefined;
    }

    remove(key) {
        const index = this._hash(key);
        const bucket = this.table[index];
        
        if (!bucket) return false;
        
        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] === key) {
                bucket.splice(i, 1);
                return true;
            }
        }
        
        return false;
    }
}

// Utilisation
const users = new HashTable();
users.set("Alexey", { age: 28, city: "Moscow" });
users.set("Maria", { age: 25, city: "St. Petersburg" });
users.set("Dmitry", { age: 32, city: "Novosibirsk" });

console.log(users.get("Maria")); // { age: 25, city: "Saint-Pétersbourg" }users.remove("Alexey");
console.log(users.get("Alexey")); // undefined

Adressage ouvert (Open Addressing)

Au lieu de créer des chaînes, en cas de collision, nous recherchons une autre cellule libre dans le tableau selon un certain algorithme :

Perforation linéaire — on vérifie les cellules suivantes d'affilée : index, index+1, index+2...

class HashTableOpenAddressing {
    constructor(size = 50) {
        this.table = new Array(size);
        this.size = size;
        this.count = 0;
    }

    _hash(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash = (hash + key.charCodeAt(i) * (i + 1)) % this.size;
        }
        return hash;
    }

    set(key, value) {
        if (this.count / this.size > 0.7) {
            this._resize(); // Augmenter la taille lors du remplissage > 70 %
        }

        let index = this._hash(key);
        let i = 0;

        while (this.table[index] !== undefined && this.table[index].key !== key) {
            i++;
            index = (this._hash(key) + i) % this.size; // Perforation linéaire
        }

        if (this.table[index] === undefined) {
            this.count++;
        }

        this.table[index] = { key, value };
    }

    get(key) {
        let index = this._hash(key);
        let i = 0;

        while (this.table[index] !== undefined) {
            if (this.table[index].key === key) {
                return this.table[index].value;
            }
            i++;
            index = (this._hash(key) + i) % this.size;
        }

        return undefined;
    }

    _resize() {
        const oldTable = this.table;
        this.size *= 2;
        this.table = new Array(this.size);
        this.count = 0;

        for (let item of oldTable) {
            if (item !== undefined) {
                this.set(item.key, item.value);
            }
        }
    }
}

Échantillonnage quadratique — on vérifie : index, index+1², index+2², index+3²...

Double hachage - on utilise la deuxième fonction de hachage pour calculer l'étape.

Performance et complexité

Load Factor (coefficient de remplissage) = nombre d'éléments / taille du tableau

Lorsque le facteur de charge est > 0,7, il est généralement effectué rehashing - création d'un nouveau tableau de plus grande taille et déplacement de tous les éléments.

Cas d'utilisation réels

1. Mise en cache des résultats

class Cache {
    constructor() {
        this.cache = new Map();
    }

    async fetchUser(userId) {
        // Vérification du cache
        if (this.cache.has(userId)) {
            console.log('Received from cache');
            return this.cache.get(userId);
        }

        // Chargement des données
        const user = await api.getUser(userId);
        
        // Enregistrer dans le cache
        this.cache.set(userId, user);
        
        return user;
    }
}

2. Calcul de la fréquence des éléments

function countWords(text) {
    const wordCount = new Map();
    const words = text.toLowerCase().split(/\s+/);

    for (let word of words) {
        wordCount.set(word, (wordCount.get(word) || 0) + 1);
    }

    return wordCount;
}

const text = "JavaScript is a programming language JavaScript is popular";
console.log(countWords(text));
// Map { 'javascript' => 2, 'ce' => 1, 'langue' => 1, ... }... }

3. Recherche de doublons

function hasDuplicates(arr) {
    const seen = new Set();
    
    for (let item of arr) {
        if (seen.has(item)) {
            return true;
        }
        seen.add(item);
    }
    
    return false;
}

console.log(hasDuplicates([1, 2, 3, 4, 5])); // false
console.log(hasDuplicates([1, 2, 3, 2, 5])); // true

4. Indexation dans les bases de données

Les bases de données utilisent des index de hachage pour rechercher rapidement des enregistrements par clé :

-- В PostgreSQL
CREATE INDEX users_email_hash ON users USING HASH (email);

-- Теперь поиск по email молниеносный
SELECT * FROM users WHERE email = 'alex@example.com';

5. Identifiants utilisateur uniques

class Session {
    constructor() {
        this.sessions = new Map();
    }

    createSession(userId) {
        const sessionId = this.generateSessionId();
        this.sessions.set(sessionId, {
            userId,
            createdAt: Date.now(),
            data: {}
        });
        return sessionId;
    }

    getSession(sessionId) {
        return this.sessions.get(sessionId);
    }

    destroySession(sessionId) {
        this.sessions.delete(sessionId);
    }

    generateSessionId() {
        return Math.random().toString(36).substring(2);
    }
}

6. Routage dans les frameworks web

class Router {
    constructor() {
        this.routes = new Map();
    }

    addRoute(path, handler) {
        this.routes.set(path, handler);
    }

    handleRequest(path) {
        const handler = this.routes.get(path);
        
        if (handler) {
            return handler();
        }
        
        return 'Not Found';
    }
}

const router = new Router();
router.addRoute('/home', () => 'Home Page');
router.addRoute('/about', () => 'About Page');

console.log(router.handleRequest('/home')); // Home Page - O(1)!

7. Anagrammes et regroupement de lignes

function groupAnagrams(words) {
    const groups = new Map();

    for (let word of words) {
        // Trier les lettres comme une clé
        const key = word.split('').sort().join('');
        
        if (!groups.has(key)) {
            groups.set(key, []);
        }
        
        groups.get(key).push(word);
    }

    return Array.from(groups.values());
}

console.log(groupAnagrams(['eat', 'tea', 'tan', 'ate', 'nat', 'bat']));
// [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

Map vs Object en JavaScript : que choisir ?

JavaScript propose deux façons de travailler avec les tables de hachage :

Object:

const obj = {};
obj.name = "Alexey";
obj['age'] = 28;

Map:

const map = new Map();
map.set('name', 'Alexey');
map.set('age', 28);

Quand utiliser Map :

• Les clés ne sont pas des chaînes (objets, nombres, fonctions)

• Une itération est nécessaire dans l'ordre d'addition

• Ajouts/suppressions fréquents d'éléments

• Vous devez connaître le nombre exact d'éléments (map.size)

Quand utiliser Object :

• Les clés sont toujours des lignes

• Besoin de JSON.stringify/parse

• Structure de configuration simple

Conseils pratiques

1. Choisissez la bonne taille initiale

// Si vous savez qu'il y aura ~1000 éléments
const map = new Map(); // Par défaut, petite taille
// vs
const users = new HashTable(2000); // Éviter le rehashing

2. Soyez prudent avec les objets tels que les clés

const map = new Map();
const key1 = { id: 1 };
const key2 = { id: 1 };

map.set(key1, 'value1');
console.log(map.get(key2)); // non défini! Différents objets

3. Nettoyez les données inutilisées

// Utilisez WeakMap pour le nettoyage automatique
const cache = new WeakMap();
let user = { name: 'Alexey' };

cache.set(user, 'some data');
user = null; // Les données seront automatiquement supprimées de WeakMap

Conclusion

Les tables de hachage sont une structure de données fondamentale qui est utilisée partout : des bases de données aux frameworks Web, des compilateurs aux moteurs de recherche. Comprendre leur conception, la résolution des conflits et les performances fait de vous un développeur plus efficace.

Dans Codique Nous analysons non seulement les tables de hachage, mais aussi des dizaines d'autres sujets importants pour les développeurs : des bases aux techniques avancées. Nos cours comprennent des exercices pratiques et des études de cas réels de l'industrie.

Rejoignez notre chaîne Telegram — vous trouverez ici une communauté amicale de développeurs, des ressources utiles chaque semaine, des analyses de tâches intéressantes et des réponses à vos questions.

Grandissons ensemble ! 🚀