Topik pengaturcaraan ini adalah sesuatu yang saya temui di kolej semester ini, dan saya tidak fikir saya akan menemui topik ini jika bukan kerana dia. Saya dapati ia menarik, jadi saya cuba membuat tutorial tentang apa yang saya faham, sudah tentu ia tidak akan lengkap, hanya meliputi perkara yang saya rasa paling menarik. Dalam artikel ini, kami akan meneroka pelaksanaan jadual cincang dalam PHP untuk menyimpan dan menyusun data pemain bola sepak, menyusunnya mengikut bilangan gol.

Apakah Jadual Hash?

Jadual cincang ialah struktur data yang membolehkan maklumat diperoleh dengan cekap. Ia digunakan secara meluas dalam pelbagai bidang pengaturcaraan, daripada pangkalan data kepada cache, kerana prestasi masa purata yang berterusan dalam kebanyakan operasi carian dan sisipan. Dan rangka kerja yang menggunakan fungsi cincang untuk memetakan kunci kepada kedudukan dalam tatasusunan. Apabila kami ingin menyimpan nilai, kami menggunakan fungsi cincang untuk mengira kedudukan di mana ia harus dimasukkan. Apabila kami perlu mendapatkan semula nilai ini, kami menggunakan fungsi cincang yang sama untuk mencari kedudukannya dengan cepat.

Perkara yang perlu diberi perhatian dalam Jadual Hash

• Perlanggaran: Apabila dua kekunci berbeza menghasilkan indeks cincang yang sama, perlanggaran berlaku. Pelaksanaan kami menggunakan tinjauan linear untuk mencari kedudukan tersedia seterusnya dalam tatasusunan jika perlanggaran berlaku.
• Prestasi Carian: Agar carian menjadi cekap, adalah penting bahawa fungsi cincang mengagihkan data secara sama rata. Dalam pelaksanaan ini, kami menggunakan pemalar emas sebagai asas fungsi cincang, kaedah yang diketahui dapat membantu penyerakan seragam.

Perlaksanaan

1. Kelas Pemain

Kelas Pemain mewakili setiap pemain, menyimpan nama dan bilangan gol mereka.

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

Kelas HashTable ialah struktur data utama, bertanggungjawab untuk menyimpan pemain. Ia mentakrifkan kaedah untuk memasukkan pemain dan untuk mengembalikan 10 penjaring terbanyak.

Pembina dan Fungsi Hash

Pembina memulakan tatasusunan yang menyimpan data, manakala kaedah cincang mengira indeks menggunakan pemalar emas. Saya memilih kaedah pendaraban, kerana ia mengelakkan kebimbangan tentang kuasa dua dalam saiz jadual. Memandangkan saiz jadual adalah berdasarkan jumlah data dalam fail CSV, pilihan ini membantu memastikan pengedaran kunci yang lebih sekata, walaupun tanpa kawalan tepat ke atas saiz jadual.

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

Sisipan dengan Pengendalian Perlanggaran

Kaedah put memasukkan objek Pemain ke dalam jadual. Jika indeks yang dijana sudah diduduki, kami menggunakan tinjauan linear sehingga kami menemui kedudukan kosong.

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

Mengeluarkan 10 Penjaring Terbanyak

Kaedah top10Gunners mengisih jadual mengikut bilangan gol dan mengembalikan 10 penjaring terbanyak.

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

Menguji Jadual Hash

Berikut ialah contoh cara menambah pemain ke meja dan mendapatkan 10 penjaring terbanyak:

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

Pertimbangan Akhir

Pelaksanaan ini menunjukkan cara membuat jadual cincang ringkas dengan pengendalian perlanggaran dan cara menyimpan objek (seperti pemain) dalam jadual cincang. Berikut ialah beberapa perkara untuk refleksi dan penambahbaikan:

• Resolusi Perlanggaran: Terdapat kaedah resolusi perlanggaran lain seperti kuadratik probing dan rantaian berasingan yang boleh diterokai untuk meningkatkan prestasi.
• Mengubah saiz: Untuk mengelakkan jadual penuh, kami boleh melaksanakan mekanisme mengubah saiz yang dinamik.
• Fungsi Cincang Alternatif: Menguji fungsi cincang yang berbeza boleh meningkatkan kejimatan dan mengurangkan perlanggaran.

Ikuti pautan kod

Atas ialah kandungan terperinci Melaksanakan Jadual Hash dalam PHP untuk Menyimpan Data Penjaring Terbanyak Brasileir?o. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!