Discutez de la façon dont PHP résout les conflits de hachage

En programmation, la table de hachage est une structure de données très utile. Il peut rechercher et insérer des éléments en un temps O(1), mais la fonction de hachage peut provoquer des collisions de hachage, un problème qui se produit lorsque deux valeurs de clé différentes sont mappées sur le même index. Dans cet article, nous explorerons plusieurs façons de résoudre les problèmes de collision de hachage et comment les implémenter en PHP.

1. Méthode d'adresse en chaîne
   La méthode d'adresse en chaîne est l'une des méthodes les plus simples et les plus courantes pour résoudre les conflits de hachage. Dans la méthode d'adresse en chaîne, chaque emplacement de table de hachage pointe vers une liste chaînée, où chaque nœud contient une paire clé-valeur. Lorsqu'une collision de hachage se produit, un nouvel élément est ajouté à la liste chaînée à cette position. Lorsque vous recherchez un élément, il vous suffit de parcourir la liste chaînée pour trouver le nœud.

En PHP, nous pouvons utiliser des tableaux pour implémenter la méthode d'adresse en chaîne. Par exemple, voici une implémentation simple :

class Hashtable {
    private $table = array();
  
    public function put($key, $value) {
        $hash = $this->hashFunction($key);
        if (!isset($this->table[$hash])) {
            $this->table[$hash] = array();
        }
        foreach ($this->table[$hash] as &$v) {
            if ($v['key'] == $key) {
                $v['value'] = $value;
                return;
            }
        }
        $this->table[$hash][] = array('key' => $key, 'value' => $value);
    }
  
    public function get($key) {
        $hash = $this->hashFunction($key);
        if (isset($this->table[$hash])) {
            foreach ($this->table[$hash] as $v) {
                if ($v['key'] == $key) {
                    return $v['value'];
                }
            }
        }
        return null;
    }
  
    private function hashFunction($key) {
        return crc32($key); // 简单的哈希函数
    }
}

Dans cet exemple, nous définissons une classe de table de hachage Hashtable. Il utilise la fonction de hachage crc32 pour calculer la valeur de hachage de chaque clé et stocke les paires clé-valeur dans un tableau bidimensionnel. Lorsqu'un élément doit être trouvé ou inséré, nous calculons d'abord sa valeur de hachage, puis vérifions si l'emplacement où se trouve la valeur de hachage existe déjà. S'il n'existe pas, nous créons une nouvelle liste et ajoutons l'élément à la liste. Si la position existe déjà, nous parcourons la liste, trouvons l'élément correspondant à la clé et remplaçons la valeur. Cette implémentation est très simple, mais lorsque la taille de la table de hachage augmente, la longueur de la liste chaînée peut devenir très longue, affectant l'efficacité de la recherche.

2. Adressage ouvert
   L'adressage ouvert est une autre façon de résoudre les collisions de hachage. En adressage ouvert, lorsqu'une collision de hachage se produit, au lieu d'ajouter un nouvel élément à la liste chaînée, nous continuons à rechercher un emplacement libre en partant de la position d'origine et insérons l'élément dans la première position disponible. L'avantage de cette méthode est qu'elle ne nécessite pas de liste chaînée et peut réduire l'utilisation de la mémoire.

En PHP, nous pouvons utiliser des tableaux pour implémenter l'adressage ouvert. Par exemple, voici une implémentation simple :

class Hashtable {
    private $table = array();
  
    public function put($key, $value) {
        $i = $this->hashFunction($key);
        $j = $i;
        do {
            if (!isset($this->table[$j])) {
                $this->table[$j] = array('key' => $key, 'value' => $value);
                return;
            }
            if ($this->table[$j]['key'] == $key) {
                $this->table[$j]['value'] = $value;
                return;
            }
            $j = ($j + 1) % count($this->table);
        } while ($j != $i);
    }
  
    public function get($key) {
        $i = $this->hashFunction($key);
        $j = $i;
        do {
            if (isset($this->table[$j])) {
                if ($this->table[$j]['key'] == $key) {
                    return $this->table[$j]['value'];
                }
            } else {
                return null;
            }
            $j = ($j + 1) % count($this->table);
        } while ($j != $i);
        return null;
    }
  
    private function hashFunction($key) {
        return crc32($key); // 简单的哈希函数
    }
}

Dans cet exemple, nous définissons une autre classe de table de hachage Hashtable, qui utilise la fonction de hachage crc32 pour calculer la valeur de hachage de chaque clé et stocke les paires clé-valeur dans un format unidimensionnel. tableau. Lorsqu'un élément doit être trouvé ou inséré, nous calculons d'abord sa valeur de hachage et commençons à parcourir le tableau à partir de cette position. Si la position est vide, nous insérons le nouvel élément à cette position. Si la position est déjà occupée, nous continuerons à parcourir le tableau jusqu'à ce que nous trouvions une position libre ou traversions l'ensemble du tableau. Un inconvénient de cette implémentation est que lorsque la table de hachage augmente en taille, le stockage doit être réaffecté et les éléments existants copiés dans un nouveau tableau.

3. Double Hashing
   Le double hachage est une méthode qui utilise une fonction de hachage pour produire une série de valeurs de hachage afin de trouver une nouvelle position en cas de collision de hachage. En double hachage, nous utilisons deux fonctions de hachage différentes pour calculer la valeur de hachage de chaque clé et suivons la séquence de valeurs de hachage pour trouver une position vide. L'utilisation de plusieurs fonctions de hachage réduit le nombre de collisions de hachage et améliore l'efficacité de la recherche.

En PHP, nous pouvons utiliser des tableaux pour implémenter un double hachage. Par exemple, voici une implémentation simple :

class Hashtable {
    private $table = array();
  
    public function put($key, $value) {
        $i = $this->hashFunction1($key);
        $j = $this->hashFunction2($key);
        $k = $i;
        do {
            if (!isset($this->table[$k])) {
                $this->table[$k] = array('key' => $key, 'value' => $value);
                return;
            }
            if ($this->table[$k]['key'] == $key) {
                $this->table[$k]['value'] = $value;
                return;
            }
            $k = ($k + $j) % count($this->table);
        } while ($k != $i);
    }
  
    public function get($key) {
        $i = $this->hashFunction1($key);
        $j = $this->hashFunction2($key);
        $k = $i;
        do {
            if (isset($this->table[$k])) {
                if ($this->table[$k]['key'] == $key) {
                    return $this->table[$k]['value'];
                }
            } else {
                return null;
            }
            $k = ($k + $j) % count($this->table);
        } while ($k != $i);
        return null;
    }
  
    private function hashFunction1($key) {
        return crc32($key);
    }
  
    private function hashFunction2($key) {
        return ((int)(crc32($key) / count($this->table)) + 1) % count($this->table);
    }
}

Dans cet exemple, nous définissons une autre classe de table de hachage Hashtable, qui utilise deux fonctions de hachage pour calculer la valeur de hachage de chaque clé et combiner la paire clé-valeur stockée dans un tableau unidimensionnel . Lorsqu'un élément doit être trouvé ou inséré, nous calculons d'abord sa valeur de hachage et utilisons la première valeur de hachage comme position initiale et la deuxième valeur de hachage pour calculer la taille du pas de chaque recherche. Si la position est vide, nous insérons le nouvel élément à cette position. Si la position est déjà occupée, nous continuerons à parcourir le tableau jusqu'à ce que nous trouvions une position libre ou traversions l'ensemble du tableau. Un avantage de cette mise en œuvre est que l'utilisation de deux fonctions de hachage différentes peut réduire le nombre de collisions de hachage, l'utilisation de la seconde fonction de hachage pouvant réduire l'apparition de situations de « regroupement ».

Conclusion
Implémenter une table de hachage en PHP est un exercice amusant et utile. Lors de l'implémentation du code, nous avons vu trois méthodes couramment utilisées pour résoudre les conflits de hachage : la méthode d'adresse en chaîne, la méthode d'adressage ouverte et la méthode de double hachage. Chaque méthode a ses avantages et ses inconvénients, et nous devons choisir la méthode la mieux adaptée au scénario d'application actuel.

Enfin, il faut noter que bien que les tables de hachage soient très efficaces dans les opérations de recherche et d'insertion, lorsque le facteur de charge de la table de hachage est trop élevé, ses performances chuteront fortement. Par conséquent, nous devons vérifier le facteur de charge lors de l'insertion d'éléments et réallouer de la mémoire si nécessaire pour garantir un fonctionnement efficace de la table de hachage.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!