在 PHP 中实现哈希表来存储巴西得分王数据

这个编程主题是我这学期在大学里遇到的，如果不是她，我想我不会遇到这个主题。我发现它很有趣，所以我尝试根据我所理解的内容制作一个教程，当然它不会完整，只是涵盖我认为最有趣的点。在本文中，我们将探索 PHP 中的哈希表实现，用于存储和组织足球运动员数据，并按进球数对其进行排序。

什么是哈希表？

哈希表是允许有效检索信息的数据结构。由于它们在大多数搜索和插入操作中具有恒定的平均时间性能，因此广泛应用于从数据库到缓存的各个编程领域。以及一个使用哈希函数将键映射到数组中的位置的框架。当我们想要存储一个值时，我们使用哈希函数来计算它应该插入的位置。当我们需要检索这个值时，我们应用相同的哈希函数来快速找到它的位置。

哈希表的注意点

• 冲突：当两个不同的键生成相同的哈希索引时，就会发生冲突。如果发生碰撞，我们的实现使用线性轮询来查找数组中的下一个可用位置。
• 搜索性能：为了使搜索高效，哈希函数均匀分布数据非常重要。在此实现中，我们使用黄金常数作为哈希函数的基础，这是一种已知有助于均匀散射的方法。

执行

1. 玩家等级

Player 类代表每个球员，存储他们的姓名和进球数。

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类是主要的数据结构，负责存储玩家。它定义了输入玩家和返回前 10 名得分手的方法。

哈希构造函数和函数

构造函数初始化存储数据的数组，而哈希方法则使用黄金常量计算索引。我选择了乘法方法，因为它避免了对表大小中 2 的幂的担忧。由于表大小基于 CSV 文件中的数据量，因此即使无法精确控制表大小，此选择也有助于确保键的分布更加均匀。

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

带有碰撞处理的插入

put 方法将 Player 对象插入表中。如果生成的索引已被占用，我们将应用线性轮询，直到找到空位置。

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

提取得分最高的 10 名球员

top10Gunners 方法按进球数对表格进行排序，并返回前 10 名得分手。

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

测试哈希表

以下是如何将玩家添加到表中并获取前 10 名得分手的示例：

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

最后的考虑因素

此实现演示了如何创建具有碰撞处理功能的简单哈希表以及如何在哈希表中存储对象（例如玩家）。以下是一些反思和改进的点：

• 碰撞解决：还有其他碰撞解决方法，例如二次探测和单独链接，可以探索以提高性能。
• 调整大小：为了避免表满，我们可以实现动态调整大小机制。
• 替代哈希函数：测试不同的哈希函数可以提高稀疏性并减少冲突。

关注代码链接

以上是在 PHP 中实现哈希表来存储巴西得分王数据的详细内容。更多信息请关注PHP中文网其他相关文章！