0Pricing
C++ Academy · Pelajaran

Fungsi Hash Kustom

Hash tipe Anda sendiri

Fungsi Hash Kustom adalah pelajaran C++ Academy gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar C++ Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus C++ Academy mencakup 4 pelajaran total.

Mengapa Menggunakan Hash Khusus?

Kontainer tidak terurut memerlukan cara untuk melakukan hash pada kuncinya. Tipe bawaan dan std::string sudah memiliki hash, tetapi tipe buatan Anda sendiri belum. Anda harus menyediakannya.

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

int main() {
    std::unordered_set<std::string> s{"hi"};
    std::cout << s.count("hi") << '\n';
    return 0;
}

Templat std::hash

std::hash adalah funktor yang memetakan nilai ke size_t. Anda memanggilnya seperti fungsi.

#include <iostream>
#include <functional>
#include <string>

int main() {
    std::hash<std::string> h;
    std::cout << "hash exists and returns a size_t\n";
    std::size_t v = h("hello");
    std::cout << (v != 0 ? "non-zero hash" : "zero") << '\n';
    return 0;
}

Struct untuk Hash

Misalkan kita memiliki Point dengan dua int. Untuk menyimpannya dalam unordered_set, kita memerlukan kesamaan dan hash.

#include <iostream>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

int main() {
    Point a{1, 2}, b{1, 2};
    std::cout << std::boolalpha << (a == b) << '\n';
    return 0;
}

Menulis Funktor Hash

Funktor hash adalah struct dengan operator() yang mengembalikan size_t. Gabungkan hash bidang, sering kali menggunakan XOR dan pergeseran.

#include <iostream>
#include <functional>

struct Point { int x, y; };

struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

int main() {
    PointHash h;
    std::cout << "hashed: " << (h({3, 4}) != 0 ? "ok" : "zero") << '\n';
    return 0;
}

Menggunakan Funktor Hash

Teruskan funktor hash sebagai argumen templat kedua dari kontainer tidak terurut.

#include <iostream>
#include <unordered_set>
#include <functional>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

int main() {
    std::unordered_set<Point, PointHash> pts;
    pts.insert({1, 2});
    pts.insert({1, 2});
    std::cout << pts.size() << '\n';
    return 0;
}

Kesamaan Juga Diperlukan

Dua kunci berada dalam bucket yang sama jika hash keduanya bertabrakan. Kontainer kemudian menggunakan operator== untuk membedakan keduanya, sehingga kesamaan wajib disediakan.

#include <iostream>
#include <unordered_set>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x * 31 + p.y);
    }
};

int main() {
    std::unordered_set<Point, PointHash> s{{1, 1}, {2, 2}};
    std::cout << s.count({1, 1}) << '\n';
    return 0;
}

Melakukan Hash pada Kunci Map

Hash khusus yang sama memungkinkan struct menjadi kunci dalam unordered_map.

#include <iostream>
#include <unordered_map>
#include <functional>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

int main() {
    std::unordered_map<Point, std::string, PointHash> m;
    m[{0, 0}] = "origin";
    std::cout << m[{0, 0}] << '\n';
    return 0;
}

Menggabungkan Banyak Bidang

Helper umum menggabungkan hash satu bidang demi satu bidang menggunakan pola pengalian dan penambahan yang mirip dengan boost::hash_combine.

#include <iostream>
#include <functional>

std::size_t combine(std::size_t seed, std::size_t v) {
    return seed ^ (v + 0x9e3779b9 + (seed << 6) + (seed >> 2));
}

int main() {
    std::size_t h = 0;
    h = combine(h, std::hash<int>()(10));
    h = combine(h, std::hash<int>()(20));
    std::cout << (h != 0 ? "combined ok" : "zero") << '\n';
    return 0;
}

Distribusi Hash yang Baik

Hash buruk yang mengembalikan nilai konstan menempatkan semuanya dalam satu bucket, sehingga kinerjanya menurun menjadi O(n). Campurkan bit dari semua bidang dengan baik.

#include <iostream>
#include <functional>

struct Bad { std::size_t operator()(int) const { return 0; } };
struct Good { std::size_t operator()(int x) const { return std::hash<int>()(x); } };

int main() {
    std::cout << Bad()(5) << ' ' << (Good()(5) != 0 ? "varies" : "0") << '\n';
    return 0;
}

Membuat Spesialisasi std::hash

Alternatifnya, buat spesialisasi std::hash untuk tipe Anda agar dapat digunakan tanpa meneruskan funktor secara eksplisit.

#include <iostream>
#include <unordered_set>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

namespace std {
    template <> struct hash<Point> {
        std::size_t operator()(const Point& p) const {
            return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
        }
    };
}

int main() {
    std::unordered_set<Point> s{{1, 2}};
    std::cout << s.count({1, 2}) << '\n';
    return 0;
}

Lambda sebagai Hash

Dalam C++20, Anda bahkan dapat menggunakan lambda tanpa status sebagai hash dengan meneruskan tipenya.

#include <iostream>
#include <unordered_set>

int main() {
    auto h = [](int x) { return std::hash<int>()(x * 2654435761u); };
    std::unordered_set<int, decltype(h)> s(8, h);
    s.insert(42);
    std::cout << s.count(42) << '\n';
    return 0;
}

Pemeriksaan Singkat

Uji pemahaman Anda tentang hashing khusus.

Ringkasan

Anda telah belajar melakukan hash pada tipe buatan sendiri:

  • sediakan funktor hash (atau buat spesialisasi std::hash) yang mengembalikan size_t
  • sediakan juga operator== agar kunci yang bertabrakan dapat dibedakan
  • gabungkan hash bidang dengan baik untuk menghasilkan distribusi yang baik

Selanjutnya, Anda akan mempelajari bucket dan performa faktor muatan.

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Fungsi Hash Kustom” gratis?

Ya — teks lengkap “Fungsi Hash Kustom” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus C++ Academy, upgrade ke CoddyKit PRO. Kursus C++ Academy mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Fungsi Hash Kustom”?

Hash tipe Anda sendiri Kamu berlatih C++ Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai C++ Academy?

Tidak diperlukan pengalaman sebelumnya. C++ Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.

Berapa lama pelajaran “Fungsi Hash Kustom” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran C++ Academy ini?

Ya. Setiap pelajaran C++ Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

  1. std::unordered_map
  2. unordered_set
  3. Fungsi Hash Kustom
  4. Pertimbangan Performa
← Kembali ke C++ Academy