Menggunakan jadual hash untuk melaksanakan carian rentetan dalam C++

Jadual cincang ialah struktur data yang sangat biasa yang memetakan nilai utama ke dalam jadual bersaiz tetap, membolehkan operasi carian, sisipan dan pemadaman yang cekap. Dalam C++, kita boleh menggunakan unordered_map dalam STL (Perpustakaan Templat Standard) untuk melaksanakan jadual cincang.

Dalam aplikasi praktikal, selalunya perlu melakukan operasi carian pada rentetan. Sebagai contoh, cari bilangan kejadian kata kunci tertentu dalam teks atau cari semua baris yang mengandungi rentetan tertentu. Untuk melaksanakan tugas ini dengan cekap, carian rentetan boleh dilaksanakan menggunakan jadual cincang.

Dalam artikel ini, kami akan memperkenalkan kaedah khusus menggunakan jadual cincang untuk melaksanakan carian rentetan dalam C++. Kami akan menggunakan contoh mencari bilangan kali rentetan muncul dalam teks.

Pertama, kita perlu mentakrifkan fungsi untuk memetakan rentetan ke dalam jadual cincang. Kaedah biasa ialah menggunakan nilai cincang rentetan sebagai nilai utama, dengan itu memastikan rentetan yang berbeza dipetakan ke lokasi yang berbeza. Untuk membolehkan fungsi cincang mempunyai prestasi yang baik, ia perlu dikira dengan cepat dan kejadian konflik cincang harus diminimumkan.

Berikut ialah pelaksanaan fungsi cincang mudah yang menambahkan kod ASCII rentetan dan mengambil baki:

size_t hash_func(const std::string& str) {
    size_t hash_val = 0;
    for (char c : str) {
        hash_val += static_cast<size_t>(c);
    }
    return hash_val % MAP_SIZE;
}

Seterusnya, kita perlu memasukkan setiap perkataan dalam teks ke dalam jadual cincang. Kita boleh memasukkan teks ke dalam jadual cincang dengan membahagikannya kepada perkataan mengikut ruang dan memanggil fungsi cincang. Memandangkan kata kunci mungkin muncul beberapa kali, kami perlu merekodkan bilangan kali setiap kata kunci muncul. Kita boleh menggunakan unordered_map untuk mencapai fungsi ini Jika nilai kunci sudah wujud semasa sisipan, nilai akan ditambah:

std::unordered_map<std::string, size_t> word_map;
for (std::string word : words) {
    if (word_map.find(word) == word_map.end()) {
        word_map[word] = 1;
    } else {
        ++word_map[word];
    }
}

Akhirnya, kita boleh mendapatkan kejadiannya dalam teks dengan memanggil nilai yang sepadan dengan rentetan dalam jadual cincang. Bilangan kali:

size_t count = word_map["target_string"];

Kod lengkap adalah seperti berikut:

#include 
#include 
#include 
#include 

const size_t MAP_SIZE = 1024;

size_t hash_func(const std::string& str) {
    size_t hash_val = 0;
    for (char c : str) {
        hash_val += static_cast<size_t>(c);
    }
    return hash_val % MAP_SIZE;
}

int main() {
    std::vector words {"hello", "world", "hello", "c++", "hash", "world", "world"};
    std::unordered_map word_map;

    for (std::string word : words) {
        if (word_map.find(word) == word_map.end()) {
            word_map[word] = 1;
        } else {
            ++word_map[word];
        }
    }

    size_t count = word_map["world"];
    std::cout << "The word 'world' appears " << count << " times." << std::endl;

    return 0;
}

Dengan kod di atas, kita boleh menggunakan jadual cincang untuk mengira dengan cepat bilangan kali rentetan muncul dalam teks. Penggunaan jadual cincang boleh meningkatkan prestasi carian, yang lebih jelas untuk jumlah data yang besar. Ia juga mempunyai fleksibiliti dan kebolehskalaan yang hebat dalam aplikasi praktikal.

Atas ialah kandungan terperinci Menggunakan jadual hash untuk melaksanakan carian rentetan dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!