Esse tópico de programação foi algo que encontrei na faculdade neste semestre, e acho que não teria entrado em contato com esse assunto se não fosse por ela. Achei interessante, por isso tentei fazer um tutorial sobre o que entendi, claro que não será completo, apenas abordando os pontos que achei mais interessantes. Neste artigo, vamos explorar uma implementação de tabela hash em PHP para armazenar e organizar os dados de jogadores de futebol, ordenando-os pelo número de gols.
O que é uma Tabela Hash?
As tabelas hash são estruturas de dados que permitem a recuperação de informações com eficiência. Elas são amplamente utilizadas em várias áreas da programação, desde bancos de dados até caches, devido ao seu desempenho de tempo constante médio na maioria das operações de busca e inserção. E uma estrutura que usa uma função de hash para mapear chaves a posições em uma array. Quando queremos armazenar um valor, usamos a função de hash para calcular a posição na qual ele deve ser inserido. Quando precisamos recuperar esse valor, aplicamos a mesma função de hash para encontrar sua posição rapidamente.
Pontos para prestar atenção na Tabela Hash
- Colisões: Quando duas chaves diferentes geram o mesmo índice de hash, ocorre uma colisão. Nossa implementação usa sondagem linear para encontrar a próxima posição disponível no array caso uma colisão ocorra.
- Desempenho de Pesquisa: Para que a busca seja eficiente, é importante que a função de hash distribua uniformemente os dados. Nesta implementação, usamos a constante áurea como base da função de hash, um método conhecido por ajudar na dispersão uniforme.
Implementação
1. Classe Jogador
A classe Jogador representa cada jogador, armazenando seu nome e o número de gols.
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
A classe HashTable é a estrutura de dados principal, responsável por armazenar os jogadores. Ela define métodos para inserir jogadores e para retornar os 10 maiores artilheiros.
Construtor e Função de Hash
O construtor inicializa o array que armazena os dados, enquanto o método hash calcula o índice utilizando a constante áurea. Optei pelo método da multiplicação, pois ele evita preocupações com potências de dois no tamanho da tabela. Como o tamanho da tabela é baseado na quantidade de dados do arquivo CSV, essa escolha ajuda a garantir uma distribuição mais uniforme das chaves, mesmo sem um controle exato sobre o tamanho da tabela.
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);
}
Inserção com Tratamento de Colisões
O método put insere um objeto Jogador na tabela. Caso o índice gerado já esteja ocupado, aplicamos sondagem linear até encontrar uma posição vazia.
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.");
}
Extraindo os Top 10 Artilheiros
O método top10Artilheiros ordena a tabela por número de gols e retorna os 10 maiores artilheiros.
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;
}
}
Testando a Tabela Hash
Aqui está um exemplo de como adicionar jogadores à tabela e obter os 10 maiores artilheiros:
$arquivo = 'artilheiros.csv';
/*
Esse dados foram retirados do site da espn
https://www.espn.com.br/futebol/estatisticas/_/liga/bra.1
*/
$jogadores = [];
if (($handle = fopen($arquivo, 'r')) !== false) {
$header = fgetcsv($handle, 1000, ","); // Lê o cabeçalho
while (($linha = fgetcsv($handle, 1000, ",")) !== false) {
$jogadores[] = array_combine($header, $linha);
}
fclose($handle);
}
$tabela = new HashTable(count($jogadores));
foreach ($jogadores as $j) {
$jogador = new Jogador();
$jogador->setNome($j['Nome']);
$jogador->setGols((int) $j['G']);
$tabela->put($jogador->getGols(), $jogador);
}
var_dump($tabela->top10Artilheiros());
Considerações Finais
Esta implementação demonstra como criar uma tabela hash simples com tratamento de colisões e como armazenar objetos (como jogadores) em uma tabela hash. Aqui estão alguns pontos para reflexão e melhorias:
- Resolução de Colisões: Existem outros métodos de resolução de colisões, como sondagem quadrática e encadeamento separado, que podem ser explorados para melhorar o desempenho.
- Redimensionamento: Para evitar uma tabela cheia, podemos implementar um mecanismo de redimensionamento dinâmico.
- Funções de Hash Alternativas: Testar diferentes funções de hash pode melhorar a dispersão e reduzir colisões.
Top comments (0)