Implémentation d'une table de hachage en PHP pour stocker les données des meilleurs buteurs du Brésil

Ce sujet de programmation est quelque chose que j'ai découvert à l'université ce semestre, et je ne pense pas que j'aurais découvert ce sujet sans elle. Je l'ai trouvé intéressant, j'ai donc essayé de faire un tutoriel sur ce que j'ai compris, bien sûr il ne sera pas complet, reprenant juste les points que j'ai trouvés les plus intéressants. Dans cet article, nous explorerons une implémentation de table de hachage en PHP pour stocker et organiser les données des joueurs de football, en les classant par nombre de buts.

Qu'est-ce qu'une table de hachage ?

Les tables de hachage sont des structures de données qui permettent de récupérer efficacement les informations. Ils sont largement utilisés dans divers domaines de programmation, des bases de données aux caches, en raison de leurs performances en temps moyen constant dans la plupart des opérations de recherche et d'insertion. Et un framework qui utilise une fonction de hachage pour mapper les clés aux positions dans un tableau. Lorsque nous voulons stocker une valeur, nous utilisons la fonction de hachage pour calculer la position à laquelle elle doit être insérée. Lorsque nous avons besoin de récupérer cette valeur, nous appliquons la même fonction de hachage pour trouver rapidement sa position.

Points à prendre en compte dans la table de hachage

• Collision : Lorsque deux clés différentes génèrent le même index de hachage, une collision se produit. Notre implémentation utilise une interrogation linéaire pour trouver la prochaine position disponible dans le tableau en cas de collision.
• Performances de recherche : Pour que la recherche soit efficace, il est important que la fonction de hachage répartisse uniformément les données. Dans cette implémentation, nous utilisons la constante d'or comme base de la fonction de hachage, une méthode connue pour aider à la diffusion uniforme.

Mise en œuvre

1. Classe de joueur

La classe Player représente chaque joueur, en stockant son nom et son nombre de buts.

class Jogador
{
    private $nome = "";
    private $gols = 0;

    public function getNome()
    {
        return $this->nome;
    }

    public function setNome($nome)
    {
        $this->nome = $nome;
    }

    public function getGols()
    {
        return $this->gols;
    }

    public function setGols($gols)
    {
        if (is_numeric($gols) && $gols >= 0) {
            $this->gols = $gols;
        } else {
            throw new Exception("O número de gols deve ser um valor numérico e não negativo.");
        }
    }
}

2. Classe HashTable

La classe HashTable est la structure de données principale, responsable du stockage des joueurs. Il définit les modalités d'inscription des joueurs et de restitution des 10 meilleurs buteurs.

Constructeur et fonction de hachage

Le constructeur initialise le tableau qui stocke les données, tandis que la méthode de hachage calcule l'index en utilisant la constante d'or. J'ai opté pour la méthode de multiplication, car elle évite les soucis de puissances de deux dans la taille du tableau. Étant donné que la taille de la table est basée sur la quantité de données dans le fichier CSV, ce choix permet d'assurer une répartition plus uniforme des clés, même sans contrôle exact sur la taille de la table.

class Jogador
{
    private $nome = "";
    private $gols = 0;

    public function getNome()
    {
        return $this->nome;
    }

    public function setNome($nome)
    {
        $this->nome = $nome;
    }

    public function getGols()
    {
        return $this->gols;
    }

    public function setGols($gols)
    {
        if (is_numeric($gols) && $gols >= 0) {
            $this->gols = $gols;
        } else {
            throw new Exception("O número de gols deve ser um valor numérico e não negativo.");
        }
    }
}

Insertion avec gestion des collisions

La méthode put insère un objet Player dans la table. Si l'index généré est déjà occupé, nous appliquons une interrogation linéaire jusqu'à trouver une position vide.

class HashTable
{
    private $total_filme = 0;
    private $tabelaHas = [];

    public function __construct(int $max)
    {
        $this->total_filme = $max;
        $this->tabelaHas = array_fill(0, $max, null);
    }

    private function hash(int $numero_gols)
    {
        $a = 0.6180339887;
        $frac = $numero_gols * $a - floor($numero_gols * $a);
        return (int) ($this->total_filme * $frac);
    }

Extraire les 10 meilleurs buteurs

La méthode top10Gunners trie le tableau par nombre de buts et renvoie les 10 meilleurs buteurs.

    public function put(int $numero_gols, Jogador $jogador)
    {
        $posicao = $this->hash($numero_gols);

        for ($i = 0; $i < $this->total_filme; $i++) {
            $novaPosicao = ($posicao + $i) % $this->total_filme;

            if (is_null($this->tabelaHas[$novaPosicao])) {
                $this->tabelaHas[$novaPosicao] = $jogador;
                return;
            }
        }

        throw new Exception("Tabela hash está cheia. Não foi possível inserir.");
    }

Test de la table de hachage

Voici un exemple de la façon d'ajouter des joueurs au tableau et d'obtenir les 10 meilleurs buteurs :

    public function top10Artilheiros()
    {

        usort($this->tabelaHas, function ($a, $b) {

            if ($a->getGols() == $b->getGols()) {
                return 0;
            }

            return ($a->getGols() > $b->getGols()) ? -1 : 1;
        });

        $artilheiros = $this->tabelaHas;

        return array_slice($artilheiros, 0, 10);
    }

    public function getTabelaH()
    {
        return $this->tabelaHas;
    }
}

Considérations finales

Cette implémentation montre comment créer une table de hachage simple avec gestion des collisions et comment stocker des objets (tels que des joueurs) dans une table de hachage. Voici quelques points de réflexion et d'améliorations :

• Résolution des collisions : Il existe d'autres méthodes de résolution des collisions, telles que le sondage quadratique et le chaînage séparé, qui peuvent être explorées pour améliorer les performances.
• Redimensionnement : Pour éviter un tableau plein, nous pouvons implémenter un mécanisme de redimensionnement dynamique.
• Fonctions de hachage alternatives : tester différentes fonctions de hachage peut améliorer la parcimonie et réduire les collisions.

Suivez le lien du code

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!