Cara menggunakan algoritma carian hash dalam C++

Cara menggunakan algoritma carian cincang dalam C++

Algoritma carian cincang ialah teknologi carian dan storan yang cekap indeks panjang tetap melalui fungsi cincang, dan kemudian menggunakan indeks ini untuk mencari dalam struktur data. Dalam C++, kita boleh melaksanakan algoritma carian hash dengan menggunakan bekas cincang dan fungsi cincang dalam perpustakaan standard. Artikel ini akan memperkenalkan cara menggunakan algoritma carian hash dalam C++ dan memberikan contoh kod khusus.

1. Memperkenalkan fail pengepala dan ruang nama
   Pertama sekali, sebelum menggunakan algoritma carian cincang dalam C++, anda perlu memperkenalkan fail pengepala dan ruang nama yang sepadan.

#include <unordered_set>  // 哈希集合的头文件
#include <unordered_map>  // 哈希映射的头文件

using namespace std;

2. Gunakan Set Cincang
   Set cincang (set_tidak tersusun) ialah bekas yang tidak dipesan dan tidak boleh diulang. Kita boleh menggunakan koleksi cincang untuk mencapai carian pantas dan penyahduplikasian.

Pertama, kami mencipta koleksi cincang dan menambah elemen padanya.

unordered_set<int> hashSet;
hashSet.insert(1);
hashSet.insert(2);
hashSet.insert(3);

Seterusnya, kita boleh menggunakan fungsi count() untuk menentukan sama ada unsur wujud dalam set cincangan.

bool exist = hashSet.count(2);

Kami juga boleh menggunakan fungsi erase() untuk memadamkan elemen dalam koleksi.

hashSet.erase(2);

3. Gunakan Peta Cincang
   Peta cincang (unordered_map) ialah bekas pasangan nilai kunci. Kita boleh menggunakan peta cincang untuk mencari dan menentukan dengan cepat sama ada nilai utama wujud.

Pertama, kami mencipta peta cincang dan menambah pasangan nilai kunci padanya.

unordered_map<string, int> hashMap;
hashMap["apple"] = 3;
hashMap["banana"] = 5;
hashMap["orange"] = 2;

Kita boleh menggunakan fungsi find() untuk mencari nilai dalam peta cincang dan menentukan sama ada pasangan nilai kunci wujud.

auto iter = hashMap.find("apple");
if (iter != hashMap.end()) {
    int value = iter->second;
    cout << "apple的值为：" << value << endl;
} else {
    cout << "未找到相关键值对" << endl;
}

Kami juga boleh menggunakan fungsi erase() untuk memadamkan pasangan nilai kunci dalam peta cincang.

hashMap.erase("banana");

4. Fungsi Cincang Tersuai
   Dalam perpustakaan standard C++, fungsi cincang lalai boleh memenuhi kebanyakan keperluan. Tetapi dalam senario tertentu, kita mungkin perlu menyesuaikan fungsi cincang.

Kami boleh menyesuaikan fungsi cincang dengan melebihkan templat std::cincang.

// 自定义哈希函数
struct MyHash {
    size_t operator()(const string& str) const {
        size_t result = 0;
        for (char c : str) {
            result = result * 31 + c;
        }
        return result;
    }
};

unordered_map<string, int, MyHash> hashMap;

Dalam kod di atas, kami membebankan fungsi operator() dalam struktur MyHash untuk menukar rentetan kepada nilai cincang.

5. Mengoptimumkan kecekapan algoritma carian cincang
   Untuk mengoptimumkan lagi kecekapan algoritma carian cincang, kami boleh melaraskan kapasiti bekas cincang atau menetapkan yang sesuai faktor beban.

// 调整哈希容器的容量
hashMap.resize(100);

// 设置负载因子为0.5
hashMap.max_load_factor(0.5);

Di atas ialah pengenalan kepada cara menggunakan algoritma carian cincang dalam C++ dan beberapa teknik pengoptimuman saya harap ia dapat membantu anda. Dalam aplikasi praktikal, algoritma carian hash ialah teknologi carian dan penyimpanan yang cekap yang boleh meningkatkan kecekapan pelaksanaan program dengan banyak. Jika anda berminat dengan algoritma carian hash, anda mungkin ingin membuat penyelidikan dan latihan lanjut untuk mengembangkan pengetahuan dan kemahiran anda.

Atas ialah kandungan terperinci Cara menggunakan algoritma carian hash dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!