Jadual cincang dan jadual cincang dalam C++

Jadual cincang dan jadual cincang dalam C++

Jadual cincang dan jadual cincang ialah struktur data yang sangat biasa dalam sains komputer. kenapa? Kerana jadual cincang dan jadual cincang boleh mencari elemen tertentu dengan cepat dalam masa yang tetap. Dalam banyak aplikasi, perbezaan prestasi ini adalah ketara.

Jadi, apakah perbezaan antara jadual hash dan jadual hash? Dalam C++, perbezaan antara kedua-duanya adalah sangat halus, dan mereka secara amnya boleh dianggap sebagai konsep yang sama. Dalam artikel ini, kami akan memperkenalkan jadual cincang dan jadual cincang secara terperinci.

Jadual cincang

Jadual cincang ialah struktur data berdasarkan fungsi cincang. Ia menyokong operasi pemasukan dan carian masa berterusan. Elemen data jadual cincang disusun mengikut hasil fungsi cincang. Untuk kunci yang berbeza, hasil yang dikembalikan oleh fungsi cincang adalah unik, iaitu setiap nilai kunci sepadan dengan nilai cincang.

Untuk menggunakan jadual cincang dalam C++, gunakan kelas unordered_map dalam perpustakaan standard. Selepas memasukkan fail pengepala ff4294d2f1027f38dcfc6e591d43822a, kita boleh mentakrifkan objek unordered_map dan kemudian mengendalikannya menggunakan fungsi ahlinya. Contohnya:

#include <unordered_map>
#include <string>
#include <iostream>

int main()
{
    std::unordered_map<std::string, int> grades;

    // 添加键值对
    grades["John"] = 90;
    grades["Sara"] = 85;
    grades["Bob"] = 95;

    // 查找键对应的值
    std::cout << "John's grade is " << grades["John"] << std::endl;

    return 0;
}

Dalam contoh di atas, kami menggunakan unordered_map2afa4d3f8bd3b313b9a5d1f92444599b gred objek untuk melaksanakan fungsi pertanyaan gred pelajar. Melalui gred["John"], kita boleh mencari gred John dengan mudah dan hasil keluarannya ialah 90.

Jadual Hash

Jadual cincang ialah struktur data yang memetakan kunci ke lokasi berdasarkan fungsi cincang. Ia membolehkan operasi seperti sisipan dan carian dilakukan dalam masa yang tetap. Idea teras jadual cincang dan jadual cincang adalah sama, cuma perbezaannya ialah jadual cincang juga perlu mengendalikan konflik.

Konflik yang dipanggil bermakna dua nilai utama berbeza dicincang ke kedudukan yang sama oleh fungsi cincang. Pada masa ini, anda perlu menggunakan kaedah penyelesaian konflik fungsi cincang, seperti pencincangan terbuka atau pencincangan senarai terpaut. Dalam pencincangan terbuka, kaedah alamat terbuka adalah menggunakan slot lain, ia dipanggil slot terbuka, hitung nilai cincang kunci untuk memasukkan kunci dalam slot lain jadual cincang, jika slot sudah diduduki, cuba slot A lain . Dalam pencincangan senarai terpaut, senarai terpaut dilaksanakan dalam slot jadual cincang.

Untuk menggunakan jadual cincang dalam C++, anda perlu menggunakan kelas unordered_map atau unordered_set dalam perpustakaan standard. Apabila menggunakan kedua-dua kelas ini, kami juga perlu menyediakan fungsi cincangan lalai ialah templat kelas std::cincang, yang boleh memetakan sebarang pembolehubah jenis boleh cincang kepada nilai integer yang unik. Contohnya:

#include <unordered_set>
#include <string>
#include <iostream>

struct Person
{
    std::string name;
    int age;
};

bool operator==(const Person& lhs, const Person& rhs)
{
    return lhs.name == rhs.name && lhs.age == rhs.age;
}

// 哈希函数
struct PersonHash
{
    std::size_t operator()(const Person& p) const
    {
        std::size_t h1 = std::hash<std::string>()(p.name);
        std::size_t h2 = std::hash<int>()(p.age);
        return h1 ^ (h2 << 1);
    }
};

int main()
{
    std::unordered_set<Person, PersonHash> people = {
        {"John", 30},
        {"Sara", 25},
        {"Bob", 45},
    };

    // 添加元素
    people.insert({"Mary", 38});

    // 查找元素
    Person p = {"John", 30};
    if (people.find(p) != people.end()) {
        std::cout << p.name << " is found" << std::endl;
    }

    return 0;
}

Dalam contoh di atas, kami menggunakan unordered_set20bfbb0b621c690185512e65beed2107 untuk mengekalkan sekumpulan maklumat orang, dengan Person ialah jenis struktur yang mengandungi dua medan: nama dan umur. Perlu diingatkan bahawa kami juga menyediakan fungsi cincang tersuai PersonHash Memandangkan jenis Orang bukan jenis boleh cincang, kami perlu menyediakan fungsi cincang untuknya.

Ringkasan

Jadual cincang dan jadual cincang adalah struktur data yang sangat praktikal dalam C++ Dalam pembangunan sebenar, ia sering digunakan untuk mengekalkan set dan indeks kata kunci. Apabila menggunakannya, anda perlu memberi perhatian kepada pilihan fungsi hash dan cara menangani konflik.

Atas ialah kandungan terperinci Jadual cincang dan jadual cincang dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!