Implementierung einer Hash-Tabelle in PHP zum Speichern der Daten der Top-Scorer von Brasilien

Dieses Programmierthema ist mir in diesem Semester im College begegnet, und ich glaube nicht, dass ich ohne sie auf dieses Thema gestoßen wäre. Ich fand es interessant, also habe ich versucht, ein Tutorial zu dem zu erstellen, was ich verstanden habe. Natürlich wird es nicht vollständig sein, sondern nur die Punkte abdecken, die ich am interessantesten fand. In diesem Artikel werden wir eine Hash-Tabellen-Implementierung in PHP untersuchen, um Fußballspielerdaten zu speichern und zu organisieren und sie nach der Anzahl der Tore zu ordnen.

Was ist eine Hash-Tabelle?

Hash-Tabellen sind Datenstrukturen, die das effiziente Abrufen von Informationen ermöglichen. Aufgrund ihrer konstanten durchschnittlichen Zeitleistung bei den meisten Such- und Einfügevorgängen werden sie häufig in verschiedenen Bereichen der Programmierung verwendet, von Datenbanken bis hin zu Caches. Und ein Framework, das eine Hash-Funktion verwendet, um Schlüssel Positionen in einem Array zuzuordnen. Wenn wir einen Wert speichern möchten, verwenden wir die Hash-Funktion, um die Position zu berechnen, an der er eingefügt werden soll. Wenn wir diesen Wert abrufen müssen, wenden wir dieselbe Hash-Funktion an, um seine Position schnell zu finden.

Zu beachtende Punkte in der Hash-Tabelle

• Kollisionen: Wenn zwei verschiedene Schlüssel denselben Hash-Index generieren, kommt es zu einer Kollision. Unsere Implementierung verwendet lineares Polling, um im Falle einer Kollision die nächste verfügbare Position im Array zu finden.
• Suchleistung: Damit die Suche effizient ist, ist es wichtig, dass die Hash-Funktion die Daten gleichmäßig verteilt. In dieser Implementierung verwenden wir die Goldene Konstante als Grundlage der Hash-Funktion, eine Methode, die bekanntermaßen bei der gleichmäßigen Streuung hilft.

Durchführung

1. Spielerklasse

Die Spielerklasse repräsentiert jeden Spieler und speichert seinen Namen und die Anzahl der Tore.

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. HashTable-Klasse

Die HashTable-Klasse ist die Hauptdatenstruktur, die für die Speicherung der Player verantwortlich ist. Es definiert Methoden für die Anmeldung von Spielern und für die Rückgabe der 10 besten Torschützen.

Hash-Konstruktor und Funktion

Der Konstruktor initialisiert das Array, das die Daten speichert, während die Hash-Methode den Index mithilfe der goldenen Konstante berechnet. Ich habe mich für die Multiplikationsmethode entschieden, da sie Bedenken hinsichtlich Zweierpotenzen in der Tabellengröße vermeidet. Da die Tabellengröße auf der Datenmenge in der CSV-Datei basiert, trägt diese Wahl dazu bei, eine gleichmäßigere Verteilung der Schlüssel sicherzustellen, auch ohne genaue Kontrolle über die Tabellengröße.

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.");
        }
    }
}

Einfügen mit Kollisionsbehandlung

Die Put-Methode fügt ein Player-Objekt in die Tabelle ein. Wenn der generierte Index bereits belegt ist, wenden wir eine lineare Abfrage an, bis wir eine leere Position finden.

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);
    }

Extrahieren der Top-10-Scorer

Die top10Gunners-Methode sortiert die Tabelle nach der Anzahl der Tore und gibt die 10 besten Torschützen zurück.

    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.");
    }

Testen der Hash-Tabelle

Hier ist ein Beispiel, wie man Spieler zur Tabelle hinzufügt und die 10 besten Torschützen erhält:

    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;
    }
}

Abschließende Überlegungen

Diese Implementierung zeigt, wie man eine einfache Hash-Tabelle mit Kollisionsbehandlung erstellt und wie man Objekte (z. B. Spieler) in einer Hash-Tabelle speichert. Hier sind einige Punkte zum Nachdenken und für Verbesserungen:

• Kollisionsauflösung: Es gibt andere Kollisionsauflösungsmethoden wie quadratische Sondierung und separate Verkettung, die zur Verbesserung der Leistung untersucht werden können.
• Größenänderung: Um eine vollständige Tabelle zu vermeiden, können wir einen dynamischen Größenänderungsmechanismus implementieren.
• Alternative Hash-Funktionen: Das Testen verschiedener Hash-Funktionen kann die Sparsity verbessern und Kollisionen reduzieren.

Code-Link folgen

Das obige ist der detaillierte Inhalt vonImplementierung einer Hash-Tabelle in PHP zum Speichern der Daten der Top-Scorer von Brasilien. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!