Implementing a Hash Table in PHP to Store Brasileirão Top Scorers Data

This programming topic was something I came across in college this semester, and I don't think I would have come across this topic if it weren't for her. I found it interesting, so I tried to make a tutorial on what I understood, of course it won't be complete, just covering the points that I found most interesting. In this article, we will explore a hash table implementation in PHP to store and organize football player data, ordering it by the number of goals.

What is a Hash Table?

Hash tables are data structures that allow information to be retrieved efficiently. They are widely used in various areas of programming, from databases to caches, due to their constant average time performance in most search and insert operations. And a framework that uses a hash function to map keys to positions in an array. When we want to store a value, we use the hash function to calculate the position at which it should be inserted. When we need to retrieve this value, we apply the same hash function to find its position quickly.

Points to pay attention to in the Hash Table

• Collisions: When two different keys generate the same hash index, a collision occurs. Our implementation uses linear polling to find the next available position in the array if a collision occurs.
• Search Performance: For the search to be efficient, it is important that the hash function evenly distributes the data. In this implementation, we use the golden constant as the basis of the hash function, a method known to help with uniform scattering.

Implementation

1. Player Class

The Player class represents each player, storing their name and number of goals.

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 Class

The HashTable class is the main data structure, responsible for storing the players. It defines methods for entering players and for returning the top 10 scorers.

Hash Constructor and Function

The constructor initializes the array that stores the data, while the hash method calculates the index using the golden constant. I opted for the multiplication method, as it avoids concerns about powers of two in the table size. Since the table size is based on the amount of data in the CSV file, this choice helps ensure a more even distribution of keys, even without exact control over the table size.

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 with Collision Handling

The put method inserts a Player object into the table. If the generated index is already occupied, we apply linear polling until we find an empty position.

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

Extracting the Top 10 Scorers

The top10Gunners method sorts the table by number of goals and returns the top 10 scorers.

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

Testing the Hash Table

Here is an example of how to add players to the table and get the top 10 scorers:

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

Final Considerations

This implementation demonstrates how to create a simple hash table with collision handling and how to store objects (such as players) in a hash table. Here are some points for reflection and improvements:

• Collision Resolution: There are other collision resolution methods such as quadratic probing and separate chaining that can be explored to improve performance.
• Resizing: To avoid a full table, we can implement a dynamic resizing mechanism.
• Alternative Hash Functions: Testing different hash functions can improve sparsity and reduce collisions.

Follow code link

The above is the detailed content of Implementing a Hash Table in PHP to Store Brasileirão Top Scorers Data. For more information, please follow other related articles on the PHP Chinese website!