unordered_set আর unordered_map: সোজা ঠিক bucket-এ চলে যাওয়া

Zara একটা online game-এর server চালায়, আর প্রতিটা নতুন player নিজের একটা username বেছে নেয়। সেকেন্ডে হাজার হাজার বার server-কে একটা প্রশ্নের উত্তর দিতে হয়: এই নামটা কি কেউ নিয়ে ফেলেছে? দশ লাখ নামের তালিকা একটা একটা করে দেখলে প্রতিটা প্রশ্নে লাগে দশ লাখ তুলনা। Module 8-এর set-এ লাগে কয়েক ডজন, আর নাম দিয়ে index করা array তো হতেই পারে না, কারণ নাম কোনো সংখ্যা না। কিন্তু নামটা নিজেই যদি বলে দিত, কোথায় খুঁজতে হবে?

একটা সংখ্যা, যেটা বলে দেয় কোথায় খুঁজতে হবে

একটা hash function একটা key-কে একটা পূর্ণসংখ্যায় বদলে দেয়, আর program চলার সময় একই key সবসময় একই সংখ্যা দেয়। C++-এ প্রতিটা সংখ্যার type আর string-এর জন্য এমন একটা তৈরিই আছে: std::hash। hash<int>() ছোট্ট একটা hashing object বানায়, আর (42) ওর হাতে key 42 তুলে দেয়।

#include <functional>
#include <iostream>
#include <string>
using namespace std;

int main() {
    cout << hash<int>()(42) << '\n';
    cout << hash<string>()("cat") << '\n';
    cout << hash<string>()("act") << '\n';
    for (int key : {12, 7, 20, 9, 31}) {
        cout << key << " % 5 = " << hash<int>()(key) % 5 << '\n';
    }
    return 0;
}

42
5726227304015210059
18297190751667054611
12 % 5 = 2
7 % 5 = 2
20 % 5 = 0
9 % 5 = 4
31 % 5 = 1

GCC 12-এ একটা int-এর hash হলো সংখ্যাটা নিজেই, তাই 42 দেয় 42। String-এর hash প্রতিটা byte মিশিয়ে বানানো, তাই cat আর act, একই তিনটা অক্ষর হয়েও, পায় একদম আলাদা সংখ্যা। এই সংখ্যাগুলো GCC 12-এর নিজের: C++ standard এদের একটাও বেঁধে দেয় না, আর অন্য library অন্য সংখ্যা print করতে পারে।

একটা hash container ভেতরে রাখে bucket-এর একটা array, আর প্রতিটা bucket হলো key-এর একটা ছোট্ট তালিকা। একটা key রাখার সময় container-টা key-এর hash-কে bucket-এর সংখ্যা দিয়ে ভাগ করে ভাগশেষ নেয়, program-এর শেষ লাইনগুলো যেমন করেছে, আর সেটাই key-এর bucket। পরে key-টা খুঁজতে গেলে আবার সেই একই bucket বের করে, আর খোঁজে শুধু ওই bucket-এ। এক bucket-এ দুইটা key, যেমন এখানে 12 আর 7, মানে একটা collision।

তাই খুঁজতে গিয়ে কখনো পুরো table ঘাঁটতে হয় না: একটা hash, একটা %, আর ছোট্ট একটা bucket-এ খোঁজা।

Table-টাকে ভরতে, collision হতে আর বড় হতে দেখো

unordered_set<int> s(5) পাঁচটা bucket-এর একটা table চায়। GCC 12 এটা নিয়ে কী করেছে, widget-টা একটা একটা call ধরে সেটাই আবার চালিয়ে দেখায়। প্রতিটা অবস্থা Compiler Explorer-এ একটা program নিজে print করেছে। খেয়াল করো, একটা bucket-এর ভেতরে ক্রমটা কেমন, আর ছয় নম্বর key এলে কী হয়।

Load factor হলো key-এর সংখ্যাকে bucket-এর সংখ্যা দিয়ে ভাগ করলে যা হয়। GCC 12 এটাকে 1 পর্যন্ত উঠতে দেয়, তাই পাঁচটা key পাঁচটা bucket ভরে ফেলতে পারে। ছয় নম্বর key এলে এটা 1 পেরিয়ে যেত, তাই table আগে বড় হয়ে 11টা bucket হলো, আর প্রতিটা key সরে গেল নিজের নতুন bucket-এ: এটাই rehash। GCC 12 বেছেছে 11, একটা prime সংখ্যা, যেটা আগের সংখ্যার অন্তত দ্বিগুণ; পুরো তালিকাটা দেখাবে lesson 05।

একটা bucket-এর ভেতরে নতুন key থাকে সবার আগে: 7 বসেছে 12-এর সামনে। find(31) bucket 9-এর তিনটা key-এর সাথে তুলনা করেছে, আর অন্য কোনো bucket ছোঁয়নি। find(5) একটা খালি bucket পেয়ে একটাও তুলনা না করেই থেমে গেছে। তাই একটা খোঁজায় খরচ হয় শুধু এক bucket-এর তুলনা, আর rehash প্রতিটা bucket-কে ছোট রাখে।

প্রথম দিনেই যে syntax লাগবে

#include <unordered_set>
#include <unordered_map>

unordered_set<T> s;               an empty set of keys of type T
unordered_set<T> s{a, b, c};      a set made from a list; repeats are dropped
s.insert(x);                      add x; nothing happens if x is already there
s.erase(x);                       remove x, if it is there
s.count(x)                        1 if x is there, 0 if not
s.find(x)                         an iterator to x, or s.end() if x is not there
s.size()    s.empty()             how many keys, and whether there are none
for (T x : s)                     every key once, in an order you cannot count on

unordered_map<K, V> m;            keys of type K, each with a value of type V
m[k] = v;                         store v under k; k is added if it is missing
m[k]                              the value under k; a missing k is added first
m.find(k)                         an iterator to the pair (k, value), or m.end()
for (auto& [k, v] : m)            every key with its value, in no fixed order

তাই call-গুলো set আর map-এর মতোই; বদলায় শুধু ক্রম আর খরচ।

insert, আর কোনো নির্দিষ্ট ক্রম ছাড়া হাঁটা

s.insert(x) x-কে ওর bucket-এ বসায়, আর একটা range-for প্রতিটা key-এর উপর দিয়ে একবার করে হাঁটে। Module 8-এর set হাঁটত সাজানো ক্রমে। এটা তা করে না।

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    unordered_set<int> s{5, 3, 9, 1, 7};
    s.insert(3);
    cout << "walk:";
    for (int x : s) {
        cout << ' ' << x;
    }
    cout << " (size " << s.size() << ")\n";
    return 0;
}

walk: 7 1 9 3 5 (size 5)

দ্বিতীয় 3 কিছুই বদলায়নি, তাই size রইল 5। হাঁটাটা সাজানো না, আবার তালিকার ক্রমেও না। এটা GCC 12-এর নিজের ক্রম, যেটা আসে bucket-গুলো থেকে, আর কোন key কখন এসেছে, তা থেকে।

Key-গুলো একই থাকলেও এই ক্রম বদলে যেতে পারে। এই program পাঁচটা key রাখে, তারপর আরও নয়টা যোগ করে আবার erase করে দেয়। বাড়তি key-গুলো table-টাকে বড় করে দেয়, আর পরের হাঁটাটা হয় অন্যরকম।

#include <iostream>
#include <unordered_set>
using namespace std;

void show(const unordered_set<int>& s) {
    cout << s.bucket_count() << " buckets:";
    for (int x : s) {
        cout << ' ' << x;
    }
    cout << '\n';
}

int main() {
    unordered_set<int> s;
    for (int x : {40, 7, 21, 3, 15}) {
        s.insert(x);
    }
    show(s);
    for (int x = 50; x < 59; x++) {
        s.insert(x);
    }
    for (int x = 50; x < 59; x++) {
        s.erase(x);
    }
    show(s);
    return 0;
}

13 buckets: 15 3 21 7 40
29 buckets: 40 7 3 15 21

একই পাঁচটা key, অথচ দুই রকম হাঁটা: table 13টা bucket থেকে বড় হয়ে 29টা হয়েছে, আর rehash ওকে নতুন করে সাজিয়েছে। নয়টা key erase করার পরেও table আর ছোট হয়নি। তাই hash container-এর হাঁটার ক্রমের উপর কোনো program-কে কখনো ভরসা করতে দিয়ো না: পরের rehash, বা অন্য একটা compiler, সেটা বদলে দিতে পারে।

আছে তো? count আর find

s.count(x) ফেরত দেয় 1, যদি x থাকে, আর 0, যদি না থাকে। s.find(x) ফেরত দেয় x-এর দিকে একটা iterator, আর x না থাকলে s.end()।

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    unordered_set<int> s{3, 9, 14, 27, 31};
    cout << s.count(14) << ' ' << s.count(5) << '\n';
    auto it = s.find(27);
    if (it != s.end()) {
        cout << "found " << *it << '\n';
    }
    if (s.find(5) == s.end()) {
        cout << "5 is not there\n";
    }
    return 0;
}

1 0
found 27
5 is not there

* দিয়ে পড়ার আগে find-এর উত্তর end()-এর সাথে মিলিয়ে নাও, কারণ *s.end() পড়া হলো undefined behaviour। তাই সোজা হ্যাঁ বা না জানতে count, আর জায়গাটাও লাগলে find।

key ধরে erase

s.erase(x) x থাকলে সেটা সরায়, না থাকলে কিছুই করে না।

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    unordered_set<int> s{3, 9, 14, 27, 31};
    s.erase(14);
    s.erase(5);
    cout << "size " << s.size() << ", 14 there: " << s.count(14) << '\n';
    return 0;
}

size 4, 14 there: 0

erase(14) 14-কে ওর bucket-এ পেয়ে খুলে নিল। erase(5) কিছুই পেল না, কিছুই করল না, কোনো error-ও দিল না। তাই নেই এমন key erase করা নিরাপদ।

unordered_map: প্রতিটা key-এর সাথে একটা value

একটা unordered_map প্রতিটা key-এর পাশে একটা value রাখে, যেমন দোকানের একটা জিনিসের নামের পাশে তার দাম। Key ঠিক করে কোন bucket, আর value চলে ওর সাথে সাথে। Value হতে পারে এমন যেকোনো কিছু, যেটা key-এর মনে রাখা দরকার: একটা দাম, একটা level, বা কোনো কিছু কতবার ঘটেছে, সেই সংখ্যা।

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> price;
    price["tea"] = 20;
    price["bun"] = 15;
    price["tea"] = 25;
    cout << "tea " << price["tea"] << ", size " << price.size() << '\n';

    auto it = price.find("bun");
    if (it != price.end()) {
        cout << it->first << " costs " << it->second << '\n';
    }
    cout << "cake " << price["cake"] << ", size " << price.size() << '\n';

    for (const auto& [item, cost] : price) {
        cout << item << ' ' << cost << '\n';
    }
    return 0;
}

tea 25, size 2
bun costs 15
cake 0, size 3
cake 0
bun 15
tea 25

price["tea"] = 25 20-কে বদলে দিল, কারণ প্রতিটা key থাকে একবারই। find("bun") pair-টার দিকে একটা iterator দিল, যার first-এ key আর second-এ value। price["cake"] পড়তেই cake যোগ হয়ে গেল 0 value নিয়ে, তাই size 2 থেকে হলো 3। শেষ loop প্রতিটা pair-এর নাম দেয় [item, cost], মানে একটা structured binding, আর loop pair-গুলোর উপর দিয়ে যায় GCC 12-এর ক্রমে।

তাই value রাখতে [], আর কিছু যোগ না করে শুধু জিজ্ঞেস করতে find।

একটা খোঁজার খরচ: গড়ে O(1), worst case-এ O(n)

একটা খোঁজা একটা hash আর একটা % বের করে, তারপর key-টাকে একটা bucket-এর key-গুলোর সাথে তুলনা করে। Load factor 1 পেরোনোর আগেই GCC 12 rehash করে ফেলে, তাই গড়ে একটা bucket-এ থাকে মোটামুটি একটা key। তাই table-এ যত key-ই থাকুক, একটা খোঁজায় তুলনা লাগে একটা কি দুইটা: গড়ে O(1)। Insert আর erase-এর খরচও তাই, সাথে মাঝে মাঝে একটা rehash, যেটা প্রতিটা key-কে একবার করে সরায়।

Worst case হলো সব key একই bucket-এ। তখন একটা খোঁজায় তুলনা লাগে n-টা key-এর সবগুলোর সাথে, O(n), সাধারণ একটা তালিকার মতো। এমন হতে হলে কাউকে hash জেনে-বুঝে key বাছতে হয়, আর lesson 04 এমন key বানিয়ে দেখাবে। Module 8-এর set-এ দশ লাখ key-তে লাগে মোটামুটি 20 থেকে 40 ধাপ, key যেমনই হোক। কিন্তু সেটা কখনো একটা-দুইটায় নামে না।

তাই hash container ক্রম আর একটা পাকা worst case ছেড়ে দেয়, আর বদলে একটা খোঁজা শুধু ছোট্ট একটা bucket ঘাঁটে।

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    unordered_set<int> s;
    for (int x : {42, 7, 19, 7, 3}) {
        s.insert(x);
    }
    cout << s.size() << " different values:";
    for (int x : s) {
        cout << ' ' << x;
    }
    cout << '\n';
    return 0;
}

4 different values: 19 7 3 42

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

int main() {
    unordered_set<string> taken{"zara", "kenji", "bob", "zara1"};
    for (string want : {"maria", "zara", "bob"}) {
        string name = want;
        int n = 1;
        while (taken.count(name) == 1) {
            name = want + to_string(n);
            n++;
        }
        taken.insert(name);
        cout << want << " gets " << name << '\n';
    }
    cout << taken.size() << " names taken\n";
    return 0;
}

maria gets maria
zara gets zara2
bob gets bob1
7 names taken

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> level{{"zara", 4}, {"kenji", 2}, {"amara", 7}};
    for (string who : {"kenji", "zara", "kenji"}) {
        level[who]++;
    }
    for (string who : {"bob", "kenji"}) {
        auto it = level.find(who);
        if (it == level.end()) {
            cout << who << " has not played yet\n";
        } else {
            cout << who << " is on level " << it->second << '\n';
        }
    }
    for (const auto& [name, lv] : level) {
        cout << name << ": level " << lv << '\n';
    }
    return 0;
}

bob has not played yet
kenji is on level 4
amara: level 7
kenji: level 4
zara: level 5

#include <iostream>
using namespace std;

int main() {
    unordered_set<int> s{3, 1, 2};
    cout << s.size() << '\n';
    return 0;
}

unordered_set<string> names{"maria", "bob", "zara", "amara"};
for (const string& name : names) {
    cout << name << '\n';
}

unordered_set<int> s{10, 20, 30};
cout << s[0] << '\n';

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    unordered_set<int> s{5, 3, 9, 1, 7};
    cout << "walk:";
    for (int x : s) {
        cout << ' ' << x;
    }
    cout << '\n';
    return 0;
}

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 0;
    cin >> n;
    unordered_set<string> banned;   // every banned word
    for (int i = 0; i < n; i++) {
        string word;
        cin >> word;
        // Add word to banned.
    }

    int m = 0;
    cin >> m;
    for (int i = 0; i < m; i++) {
        string word;
        cin >> word;
        // Print word, or *** if it is banned. Put one space between two
        // words, and end the line after the last one.
    }
    return 0;
}

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    unordered_map<string, int> total;   // each player's points so far
    for (int i = 0; i < n; i++) {
        string name;
        int points;
        cin >> name >> points;
        // Add points to name's total.
    }

    // Walk total and keep the winner: more points wins, and a tie goes to
    // the name that comes first in alphabetical order. Print the winner's
    // name and total.

    return 0;
}

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    int n;
    cin >> n;
    unordered_set<int> seen;   // every number the game has reached so far

    // Play the game from n: each step replaces the number by the sum of the
    // squares of its digits. Print how many steps it takes to reach 1, or
    // loops if the game never gets there.

    return 0;
}

এরপর lesson 02 চারটা hash container-এর প্রতিটা operation একটা একটা করে দেখাবে, প্রতিটার খরচসহ।