20.4 unordered_map และ unordered_set

set กับ map เรียงข้อมูลให้ตลอดเวลา จึงตอบได้ว่าค่าน้อยสุดคืออะไร หรือค่าแรกที่ ≥ x คืออะไร แต่ถ้าโจทย์ถามแค่ว่ามีไหม หรือนับว่ากี่ครั้ง การเรียงไว้ก็เป็นงานที่เปล่าประโยชน์ C++ มีอีกคู่หนึ่งที่ไม่เรียง คือ unordered_set กับ unordered_map ใช้คำสั่งชุดเดียวกัน แต่ข้างในเป็นตารางแฮช (hash table) ซึ่งแต่ละคำสั่งใช้เวลาเฉลี่ย O(1) หน้านี้ดูว่าเร็วขึ้นจริงแค่ไหน และกรณีไหนที่มันช้าลงจนแพ้ map แบบไม่เห็นฝุ่น

ตารางแฮชทำงานยังไง

นึกถึงอาเรย์นับในหน้า 5.3 ที่ใช้ค่าเป็นหมายเลขช่องตรงๆ เร็วมากแต่ต้องมีช่องเท่ากับช่วงของค่า ตารางแฮชแก้ด้วยการมีช่องจำนวนพอประมาณ เรียกว่า bucket แล้วแปลงค่าเป็นหมายเลขช่องด้วยการ mod กับจำนวนช่อง ถ้ามี 7 ช่อง ค่า 40 ไปอยู่ช่อง 40 % 7 = 5 ค่าที่ตกช่องเดียวกันต่อกันเป็นรายการในช่องนั้น เหมือน linked list ในบทที่ 14

หาค่า 22 ก็คำนวณ 22 % 7 = 1 แล้วไล่ดูเฉพาะช่อง 1 ซึ่งมีแค่สองตัว ไม่ต้องดูช่องอื่นเลย ตารางแฮชของ C++ คอยเพิ่มจำนวนช่องให้มากกว่าจำนวนค่าเสมอ พอค่าเพิ่มจนแน่นก็ขยายตารางแล้วย้ายทุกค่าไปช่องใหม่ ถ้าค่ากระจายตัวดี แต่ละช่องมีของแค่หนึ่งสองตัว ทุกคำสั่งจึงใช้เวลาเฉลี่ย O(1) ค่าที่ไม่ใช่ตัวเลขเช่นข้อความ จะถูกแปลงเป็นตัวเลขด้วยฟังก์ชันแฮชก่อน แล้วค่อย mod

ใช้งานเหมือน set และ map

เปลี่ยนชื่อชนิดอย่างเดียว คำสั่ง insert count find erase size และวงเล็บเหลี่ยมของ map ใช้ได้เหมือนเดิมทุกอย่าง รวมถึงกับดักวงเล็บเหลี่ยมสร้างคีย์ในหน้า 20.3 ด้วย สิ่งที่หายไปคือทุกอย่างที่อาศัยลำดับ

• ไม่มี lower_bound upper_bound
• begin() ไม่ใช่ค่าน้อยสุด และไม่มี rbegin()
• วนด้วย for แล้วได้ลำดับที่เดาไม่ได้ ไม่ใช่จากน้อยไปมาก และไม่ใช่ตามลำดับที่ใส่

ตัวอย่างการใช้งานจริงอยู่ในหัวข้อจับคู่ผลรวมข้างล่าง

เร็วกว่า map แค่ไหน

นับความถี่ของตัวเลขสุ่ม 0 ถึง 10⁹ ด้วย map<int, int> เทียบกับ unordered_map<int, int> โค้ดเหมือนโปรแกรม calls ในหน้า 20.3 ต่างกันแค่ชื่อชนิด จับเวลาเฉพาะช่วงนับ

map<int, int> tree_count;
for (int x : values) {
    tree_count[x]++;
}
unordered_map<int, int> hash_count;
for (int x : values) {
    hash_count[x]++;
}

วัดบนโน้ตบุ๊ก ASUS Vivobook S 14 ซีพียู AMD Ryzen AI 9 HX 370 แรม 32 GB ระบบ Windows 11 คอมไพล์ด้วย GCC 14.2 ของ Code::Blocks ตัวเลขเป็นวินาที แต่ละช่องคือค่ากลางของการรันสามครั้ง

เร็วกว่าจริงแต่ไม่ได้ต่างกันเป็นสิบเท่าอย่างที่ O(1) กับ O(log N) ชวนให้คิด เพราะการคำนวณ mod การจองหน่วยความจำให้ของแต่ละตัว และการขยายตารางกินเวลาไม่น้อย ในโจทย์ส่วนใหญ่ map ก็ทันสบายอยู่แล้ว unordered_map ช่วยได้ตอนที่เวลาเฉียดขอบจริงๆ

กรณีแย่ที่สุด

O(1) เป็นแค่ค่าเฉลี่ยเมื่อค่ากระจายไปหลายช่อง ถ้าค่าส่วนใหญ่ตกช่องเดียวกัน ช่องนั้นจะยาวเป็นหมื่น ทุกคำสั่งต้องไล่ทั้งรายการ กลายเป็น O(N) ต่อครั้ง ตารางแฮชของ GCC แปลง int เป็นหมายเลขช่องด้วยการ mod กับจำนวนช่องตรงๆ และจำนวนช่องเป็นจำนวนเฉพาะชุดที่รู้กันล่วงหน้า เช่น ตอนเก็บค่าไว้ราวหนึ่งหมื่นถึงสองหมื่นค่า ตารางมี 20753 ช่อง ถ้าทุกค่าเป็นพหุคูณของ 20753 ทุกค่าจะตกช่อง 0 หมด

ลองนับความถี่ของตัวเลขสองแสนตัว ที่สุ่มมาจากพหุคูณของ 20753 สองหมื่นแบบ ทุกค่ายังไม่เกิน 10⁹ ตามขอบเขตโจทย์ทั่วไป

วัดบนเครื่องเดิม ช่องแบบ -O2 เป็นค่ากลางของการรันสามครั้ง ช่องแบบ Code::Blocks ของแถวที่สองรันครั้งเดียว

map ไม่สนว่าค่าหน้าตาเป็นอย่างไร ยังเป็น O(log N) เสมอ ส่วน unordered_map ช้าลงหลายร้อยเท่า ข้อมูลแบบนี้ไม่เกิดขึ้นเองตามธรรมชาติ แต่คนออกโจทย์ตั้งใจสร้างได้ การแข่งที่เปิดให้ผู้เข้าแข่งขันส่งชุดทดสอบมาโจมตีโปรแกรมของคนอื่นได้ เช่น Codeforces มีคนทำแบบนี้จริงเป็นประจำ ส่วนการสอบที่ชุดทดสอบเตรียมไว้ล่วงหน้าเจอน้อยกว่ามาก แต่ก็ไม่มีอะไรรับประกัน ตารางแฮชกันได้ด้วยการเขียนฟังก์ชันแฮชเอง ซึ่งเกินขอบเขตของบทนี้

ตัวอย่าง จับคู่ผลรวมเท่ากับ K

น้องได้บัตรของขวัญมูลค่า K บาท ร้านมีสินค้า N ชิ้นเรียงบนชั้น อยากซื้อของสองชิ้นที่ราคารวมเท่ากับ K พอดี ให้บอกตำแหน่งของสองชิ้นนั้น ถ้ามีหลายคู่ ตอบคู่ไหนก็ได้ ถ้าไม่มีให้พิมพ์ no pair

ไล่ชิ้นที่ j จากซ้ายไปขวา ชิ้นที่ j ราคา p ต้องการคู่ราคา K - p ถ้าราคานั้นเคยเจอในชิ้นก่อนหน้าก็จบ จึงต้องจดไว้ว่าราคาที่เคยเจออยู่ตำแหน่งไหน งานแบบนี้คือ map ที่ไม่ต้องเรียง

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long target;
    cin >> n >> target;
    unordered_map<long long, int> position;
    for (int j = 1; j <= n; j++) {
        long long price;
        cin >> price;
        auto it = position.find(target - price); // (1)!
        if (it != position.end()) {
            cout << it->second << ' ' << j << '\n';
            return 0;
        }
        position[price] = j; // (2)!
    }
    cout << "no pair\n";
    return 0;
}

1. ใช้ find ไม่ใช่วงเล็บเหลี่ยม เพราะแค่ถาม ไม่อยากสร้างคีย์ราคาที่ไม่มีอยู่จริงทิ้งไว้
2. จดราคานี้หลังจากถามแล้ว ถ้าจดก่อน ของราคา K/2 ชิ้นเดียวจะจับคู่กับตัวเอง ถ้าราคาซ้ำ ตำแหน่งจะถูกเขียนทับด้วยชิ้นหลัง ซึ่งไม่ผิดเพราะโจทย์ขอคู่ไหนก็ได้

6 1000
350 720 500 280 650 500

2 4

ชิ้นที่ 4 ราคา 280 ต้องการ 720 ซึ่งอยู่ชิ้นที่ 2 คู่ 350 กับ 650 และคู่ 500 กับ 500 ก็ใช้ได้ แต่ชิ้นที่ 4 เจอคู่ก่อน ถ้ามีของราคา 450 แค่ชิ้นเดียวกับ K = 900 โปรแกรมจะตอบ no pair ถูกต้อง เพราะ 450 ถูกจดหลังจากถามไปแล้ว

ถ้าราคาถึง 10⁹ K อาจถึง 2 × 10⁹ ซึ่งเฉียดขอบของ int มาก โปรแกรมนี้จึงเก็บทั้ง K และราคาเป็น long long จะได้ไม่ต้องคิดว่าบวกลบกันแล้วล้นหรือเปล่า

เทียบสี่วิธีกับราคาสุ่ม 1 ถึง 10⁹ N ชิ้น K = 10⁹ และนับทุกคู่ให้ครบแทนการหยุดที่คู่แรก ทุกวิธีจะได้ทำงานเต็มที่

• สองลูป ลองทุกคู่ i < j ตรงๆ O(N²)
• sort แล้วค้นหา เรียงราคา แล้วแต่ละชิ้นใช้ lower_bound กับ upper_bound ในหน้า 19.2 นับว่าราคา K - p มีกี่ชิ้นถัดไปทางขวา O(N log N)
• map แบบโปรแกรม gift แต่เก็บจำนวนชิ้นของแต่ละราคา O(N log N)
• unordered_map เหมือนข้อก่อน เฉลี่ย O(N)

วัดบนโน้ตบุ๊ก ASUS Vivobook S 14 ซีพียู AMD Ryzen AI 9 HX 370 แรม 32 GB ระบบ Windows 11 คอมไพล์ด้วย GCC 14.2 ของ Code::Blocks แบบ -O2 ตัวเลขเป็นวินาที แต่ละช่องคือค่ากลางของการรันสามครั้ง

คอมไพล์แบบ Code::Blocks สองลูปใช้ 13.2 วินาทีที่ N = 10⁵ และ 60.6 วินาทีที่ N = 2 × 10⁵ อีกสามวิธีไม่ถึง 0.2 วินาที

สามวิธีหลังทันสบาย และน่าสังเกตว่า sort แล้วค้นหาเร็วพอๆ กับตารางแฮช เพราะอาเรย์ที่เรียงแล้วอ่านต่อเนื่องในหน่วยความจำ ถ้าข้อมูลมาครบตั้งแต่ต้น วิธีเรียงก็เป็นคำตอบที่ดีมาก map กับ unordered_map ได้เปรียบเมื่อข้อมูลไหลเข้ามาเรื่อยๆ และต้องตอบทันทีว่ามีคู่แล้วหรือยัง

เลือกใช้อะไรดี

ลองทำให้พัง

แบบที่ 1 เรียก lower_bound ของ unordered_set

unordered_set<int> departures = {360, 395, 430, 480, 545, 610};
cout << *departures.lower_bound(400) << '\n';

bus.cpp:7:25: error: 'class std::unordered_set<int>' has no member named 'lower_bound'
    7 |     cout << *departures.lower_bound(400) << '\n';
      |                         ^~~~~~~~~~~

has no member named แปลว่าชนิดนี้ไม่มีคำสั่งชื่อนี้ ตารางแฮชไม่รู้ว่าค่าไหนน้อยกว่าค่าไหน จึงตอบคำถามเรื่องลำดับไม่ได้ ถ้าต้องใช้ lower_bound ต้องกลับไปใช้ set

แบบที่ 2 คาดว่าวนแล้วจะได้ค่าเรียง

#include <bits/stdc++.h>
using namespace std;

int main()
{
    unordered_set<int> plates = {4521, 1088, 7310, 2950, 15, 999999};
    for (int plate : plates) {
        cout << plate << ' ';
    }
    cout << '\n';
    unordered_map<string, int> score = {{"nok", 82}, {"ploy", 91}, {"arm", 66}, {"beam", 74}};
    for (auto entry : score) {
        cout << entry.first << ' ' << entry.second << '\n';
    }
    return 0;
}

บนเครื่องที่เขียนเอกสารนี้ได้ผลแบบนี้ ทั้งแบบ Code::Blocks และแบบ -O2

999999 15 2950 7310 1088 4521
beam 74
arm 66
ploy 91
nok 82

ไม่เรียงจากน้อยไปมาก และไม่ตรงกับลำดับที่ใส่ด้วย ลำดับนี้ขึ้นกับจำนวนช่องและฟังก์ชันแฮชของ compiler แต่ละรุ่น เครื่อง grader อาจได้ลำดับอื่น ถ้าโจทย์ให้พิมพ์เรียง แต่ใช้แบบ unordered แล้วบังเอิญผ่านตัวอย่าง ก็อาจตกชุดทดสอบที่เหลือ

สรุป

• unordered_set กับ unordered_map ใช้คำสั่งเหมือน set กับ map แต่ไม่เรียง ไม่มี lower_bound และวนได้ลำดับที่เดาไม่ได้
• ข้างในเป็นตารางแฮช แต่ละคำสั่งเฉลี่ย O(1) แต่ถ้าค่าชนช่องเดียวกันมากๆ จะเป็น O(N)
• วัดจริงเร็วกว่า map ไม่กี่เท่า แต่กรณีแย่ที่สุดช้ากว่าหลายร้อยเท่า ใช้ map เป็นค่าเริ่มต้น
• จับคู่ผลรวมเท่ากับ K ไล่ไปทีละตัวแล้วถามว่าเคยเห็น K - x ไหม ถามก่อนแล้วค่อยจด
• ข้อมูลมาครบตั้งแต่ต้น sort แล้วค้นหาก็เร็วพอๆ กัน