Sets and HashMaps (set နဲ့ HashMap များ)

B4.1.5 (HL): Construct and apply sets as an ADT: unordered, unique elements; union, intersection, difference; check membership, add, remove, subset/superset. B4.1.6 (HL): Explain the core principles of ADTs: hash tables (hashing functions, collision resolution, load factors); mechanics of sets; HashMap/HashSet in Java.
မြန်မာလို: set (အစဉ် မရှိဘဲ မထပ်တဲ့ element တွေကို စုထားတဲ့ ဒေတာအစု) ကို ADT (abstract data type: operation တွေနဲ့ သတ်မှတ်တဲ့ ဒေတာ အမျိုးအစား) တစ်ခုအဖြစ် ကိုယ်တိုင် တည်ဆောက်ပြီး အသုံးချနိုင်ရပါမယ်: အစဉ် မရှိတာ၊ element တွေ မထပ်တာ၊ union (set နှစ်ခုလုံးက element အားလုံး)၊ intersection (set နှစ်ခုလုံးမှာ ပါတဲ့ element တွေ)၊ difference (set တစ်ခုမှာ ပါပြီး နောက်တစ်ခုမှာ မပါတဲ့ element တွေ)၊ element ပါမပါ စစ်ခြင်း၊ ထည့်ခြင်း၊ ဖယ်ခြင်း၊ subset/superset (set တစ်ခုက နောက်တစ်ခုရဲ့ အစိတ်အပိုင်း ဟုတ်မဟုတ်)။ ADT တွေရဲ့ အဓိက သဘောတရားတွေကို ရှင်းပြနိုင်ရပါမယ်: hash table (key-value တွေကို အမြန် ရှာနိုင်အောင် သိမ်းတဲ့ structure) တွေ (hashing function (key ကို bucket index အဖြစ် ပြောင်းတဲ့ function)၊ collision resolution (key နှစ်ခု index တူသွားရင် ဖြေရှင်းပုံ)၊ load factor (hash table ဘယ်လောက် ပြည့်နေလဲ ဆိုတာ))၊ set တွေ အလုပ်လုပ်ပုံ၊ Java ရဲ့ HashMap (Java ရဲ့ key-value hash table) နဲ့ HashSet (မထပ်တဲ့ element တွေ သိမ်းတဲ့ Java collection)။

ဒီစာမျက်နှာက HL အတွက်ပဲ ဖြစ်ပါတယ်။ SL (Standard Level) နဲ့ HL (Higher Level) ဆိုတာ IB Computer Science (နိုင်ငံတကာ ကျောင်းတွေမှာ သင်တဲ့ ကွန်ပျူတာသိပ္ပံ သင်ရိုး) သင်တန်းရဲ့ အဆင့်နှစ်ဆင့်ဖြစ်ပြီး HL အပိုင်းတွေက ပိုနက်နက်ရှိုင်းရှိုင်း လေ့လာရတဲ့ အပိုင်းတွေပါ။

အဓိက အယူအဆများ

အခုထိ တည်ဆောက်ခဲ့တဲ့ data structure (ဒေတာ သိမ်းဆည်းပုံ) တွေမှာ တန်ဖိုး တစ်ခုကို ရှာဖို့ traversal (node ဒါမှမဟုတ် element တိုင်းကို အစဉ်တကျ သွားကြည့်ခြင်း) လုပ်ရပါတယ်: linked list (node တွေ ချိတ်ဆက်ထားတဲ့ list) တွေမှာ O(n) လိုပြီး ဘယ်ညာ ညီမျှနေတဲ့ (balanced) BST (binary search tree: ဘယ်ဘက် ငယ်၊ ညာဘက် ကြီးတဲ့ binary tree) တွေမှာတောင် O(log n) လိုပါတယ်။ Hash-based structure (key ကို index အဖြစ် ပြောင်းပြီး သိမ်းတဲ့ structure) တွေကတော့ လုံးဝ မတူတဲ့ နည်းကို သုံးပါတယ်: သိမ်းမယ့် နေရာကို တန်ဖိုးကနေ တိုက်ရိုက် တွက်ထုတ်လို့ lookup (တန်ဖိုးကို ရှာယူခြင်း) က average case (ပျမ်းမျှ အခြေအနေ) မှာ O(1) ဖြစ်ပါတယ်။

Sets (မထပ်တဲ့ element တွေကို စုထားတဲ့ ဒေတာအစု)

Set ဆိုတာ unique (တစ်ခုနဲ့ တစ်ခု မထပ်တဲ့) element (အစုထဲက အချက်) တွေကို အစဉ် မသတ်မှတ်ဘဲ စုထားတဲ့ collection (ဒေတာအစု) ပါ။ ရှိပြီးသား element ကို ထပ်ထည့်ရင် ဘာမှ မပြောင်းပါဘူး။

Operation	Java `HashSet` method (သီးခြား အလုပ်တစ်ခု လုပ်ပေးတဲ့ code အပိုင်း)	ရှင်းလင်းချက်
Add	`add(element)`	Element ကို ထည့်တယ် (ရှိပြီးသားဆိုရင် လျစ်လျူရှုတယ်)
Remove	`remove(element)`	Element ကို ဖယ်ထုတ်တယ်
Contains	`contains(element)`	Element ပါမပါ (membership) စစ်တယ်: `true`/`false` ကို ပြန်ပေးတယ်
Size	`size()`	Element အရေအတွက်
Union	`addAll(otherSet)`	Set နှစ်ခုလုံးက element အားလုံး
Intersection	`retainAll(otherSet)`	Set နှစ်ခုလုံးမှာ ပါတဲ့ element တွေပဲ
Difference	`removeAll(otherSet)`	ဒီ set ထဲမှာ ပါပြီး တခြား set ထဲမှာ မပါတဲ့ element တွေ

retainAll နဲ့ removeAll က မူလ set ကို ပြောင်းလဲပစ်ပါတယ်။ မူလ set ကို ဆက်ထားဖို့ လိုရင် အရင် copy ကူးပါ: HashSet<String> result = new HashSet<>(setA); (Python ရဲ့ set operator (တန်ဖိုးတွေကို တွက်ချက်တဲ့ သင်္ကေတ) &၊ | နဲ့ - ကတော့ set အသစ် တစ်ခုကို ပြန်ပေးလို့ မူလ set တွေ မပြောင်းပါဘူး။)

HashMaps (Java ရဲ့ key-value hash table)

HashMap က key-value pair (key နဲ့ value တစ်တွဲ) တွေကို သိမ်းပါတယ်။ Key (value ကို ပြန်ရှာဖို့ သုံးတဲ့ တန်ဖိုး) တစ်ခုစီက value (key နဲ့ တွဲသိမ်းထားတဲ့ တန်ဖိုး) တစ်ခုတည်းနဲ့ အတိအကျ တွဲပါတယ်။ Key တွေ မထပ်ရပေမယ့် value တွေကတော့ ထပ်လို့ ရပါတယ်။

Operation	Java `HashMap` method	ရှင်းလင်းချက်
Put	`put(key, value)`	Key-value pair ကို ထည့်တယ် ဒါမှမဟုတ် ပြင်တယ်
Get	`get(key)`	Key တစ်ခုရဲ့ value ကို ယူတယ် (key မရှိရင် `null` (ဘာ object ကိုမှ မညွှန်းတဲ့ တန်ဖိုး) ကို ပြန်ပေးတယ်)
Contains key	`containsKey(key)`	Key ရှိမရှိ စစ်တယ်
Contains value	`containsValue(value)`	Value ရှိမရှိ စစ်တယ် (နှေးတယ်: O(n))
Remove	`remove(key)`	Key-value pair ကို ဖျက်တယ်
Size	`size()`	Key-value pair အရေအတွက်
Keys	`keySet()`	Key အားလုံးကို Set အဖြစ် ပြန်ပေးတယ်

Hashing အလုပ်လုပ်ပုံ

HashSet နဲ့ HashMap နှစ်ခုလုံးက အတွင်းမှာ hash table ကို သုံးပါတယ်။ အလုပ်လုပ်ပုံက:

Hash function က key ကို integer (ကိန်းပြည့်) တစ်ခု (hash code) အဖြစ် ပြောင်းပါတယ်
Hash code ကို bucket index (သိမ်းမယ့် အကွက်ရဲ့ နေရာအမှတ်) အဖြစ် ပြောင်းပါတယ် (များသောအားဖြင့် hashCode % tableSize)
Element ကို အဲဒီ bucket (hash table ထဲမှာ ဒေတာ သိမ်းတဲ့ အကွက်) ထဲမှာ သိမ်းပါတယ်

Bucket 10 ခု ပါတဲ့ table ထဲက နာမည် သုံးခုရဲ့ တကယ့် hashCode() တန်ဖိုးတွေပါ: “Alice” နဲ့ “Eve” နှစ်ခုလုံး bucket 8 ထဲ ရောက်ပါတယ်။ ဒါတွေက Java ရဲ့ တန်ဖိုးတွေပါ: Python ရဲ့ built-in hash() ကတော့ program run တိုင်း string တစ်ခုကို မတူတဲ့ တန်ဖိုး ပေးပါတယ်။

ပုံထဲက English စာတွေရဲ့ အဓိပ္ပာယ်: “% 10” က 10 နဲ့ စားလို့ ရတဲ့ အကြွင်း၊ “bucket 8 is already taken: a collision” က bucket 8 မှာ ရှိပြီးသား ဖြစ်နေလို့ collision ဖြစ်တယ် လို့ အဓိပ္ပာယ်ရပါတယ်။

Collision Resolution (key နှစ်ခု index တူသွားရင် ဖြေရှင်းပုံ)

မတူတဲ့ key နှစ်ခုကို hash လုပ်လိုက်တဲ့အခါ bucket တစ်ခုတည်း ရလာရင် collision (key နှစ်ခု bucket တစ်ခုတည်းကို ရောက်ခြင်း) ဖြစ်ပါတယ်။ အသုံးများတဲ့ နည်း နှစ်ခု ရှိပါတယ်:

နည်း	အလုပ်လုပ်ပုံ	Trade-off (တစ်ခု ရဖို့ တစ်ခု အလျှော့ပေးရတာ)
Chaining (bucket တစ်ခုစီမှာ list ချိတ်ပြီး သိမ်းခြင်း)	Bucket တစ်ခုစီမှာ entry (ထည့်ထားတဲ့ ဒေတာ တစ်ခု) တွေရဲ့ linked list တစ်ခုကို သိမ်းတယ်	ရိုးရှင်းတယ်၊ collision အများကြီးကို ကိုင်တွယ်နိုင်တယ်၊ ဒါပေမဲ့ memory (မှတ်ဉာဏ်) ပိုသုံးတယ်
Open addressing (နောက်ထပ် လွတ်နေတဲ့ bucket ကို ရှာပြီး သိမ်းခြင်း)	Bucket ပြည့်နေရင် နောက်ထပ် လွတ်နေတဲ့ bucket ကို probe လုပ် (တစ်ခုချင်း စစ်ရှာ) တယ်	Memory ပို မလိုဘူး၊ ဒါပေမဲ့ table ပြည့်လာလေ မြန်နှုန်း ကျလာလေ ဖြစ်တယ်

Collision တစ်ခုတည်းကို နည်း နှစ်မျိုးနဲ့ ဖြေရှင်းထားပုံပါ။ Chaining က နာမည် နှစ်ခုလုံးကို bucket 8 ရဲ့ linked list ထဲမှာ သိမ်းထားပြီး linear probing (နောက်က bucket တွေကို အစဉ်လိုက် စစ်ရှာခြင်း) က Eve ကို နောက်ထပ် လွတ်နေတဲ့ bucket 9 ကို ရွှေ့ပါတယ်။

ပုံထဲက English စာတွေရဲ့ အဓိပ္ပာယ်: “8 is taken, so try 9” က 8 မှာ ရှိပြီးသားမို့ 9 ကို စမ်းကြည့်တယ် လို့ အဓိပ္ပာယ်ရပါတယ်။ null (Python မှာ None) က list ရဲ့ အဆုံးကို ပြပါတယ်။

Java ရဲ့ HashMap က chaining ကို သုံးပါတယ် (bucket တစ်ခုစီမှာ linked list ထားပြီး chain တစ်ခု ရှည်လာရင် tree အဖြစ် ပြောင်းပါတယ်)။

Load Factor (hash table ဘယ်လောက် ပြည့်နေလဲ ဆိုတာ)

Load factor ဆိုတာ entry အရေအတွက်နဲ့ bucket အရေအတွက်ရဲ့ အချိုးပါ:

load factor = number of entries / number of buckets

Load factor က သတ်မှတ်ထားတဲ့ threshold (ကန့်သတ် တန်ဖိုး) ကို ကျော်သွားရင် (Java မှာ ပုံမှန် သတ်မှတ်ထားတဲ့ တန်ဖိုးက 0.75) table က resize လုပ်ပါတယ် (capacity (bucket အရေအတွက်) ကို နှစ်ဆ တိုးပြီး entry အားလုံးကို rehash (hash ပြန်တွက်ပြီး နေရာ ပြန်ချခြင်း) လုပ်ပါတယ်)။ Load factor မြင့်ရင် memory သက်သာပေမယ့် collision တွေ များလာပါတယ်။ Load factor နိမ့်ရင် memory ပိုကုန်ပေမယ့် operation တွေ မြန်နေပါတယ်။

ဘယ်အချိန်မှာ ဘာကို သုံးမလဲ

လိုအပ်ချက်	အသင့်တော်ဆုံး structure	အကြောင်းရင်း
မထပ်တဲ့ element တွေ၊ မြန်မြန် ရှာနိုင်ဖို့	`HashSet`	contains က O(1)၊ ထပ်နေတာတွေကို အလိုအလျောက် ဖယ်ပေးတယ်
Key နဲ့ value တွဲသိမ်းဖို့	`HashMap`	key နဲ့ get/put လုပ်တာ O(1)
Sorted (တန်ဖိုးအလိုက် အစဉ်တကျ စီပြီးသား) အစဉ် လိုရင်	`TreeSet` / BST	Hash table တွေက အစဉ်ကို မထိန်းထားပါဘူး
ဘယ်နှစ်ကြိမ် ပါလဲ ရေတွက်ဖို့	`HashMap<String, Integer>`	Item (အချက်) တစ်ခုစီကို သူ့ အရေအတွက်နဲ့ တွဲတယ်
နှစ်ခုလုံးမှာ ပါတဲ့ element တွေကို ရှာဖို့	`HashSet` နှစ်ခု + `retainAll`	Set intersection

အဆင့်ဆင့် ရှင်းပြထားတဲ့ ဥပမာများ

ဥပမာ 1: HashSet၊ မထပ်တဲ့ စကားလုံးများ

import java.util.HashSet;

public class UniqueWords {
    public static void main(String[] args) {
        String[] words = {"the", "cat", "sat", "on", "the", "mat", "the"};

        HashSet<String> unique = new HashSet<>();
        for (int i = 0; i < words.length; i++) {
            String w = words[i];
            unique.add(w);
        }
        // for-each version: for (String w : words) { unique.add(w); }

        System.out.println("Unique words: " + unique);
        System.out.println("Count: " + unique.size());
        System.out.println("Contains 'cat'? " + unique.contains("cat"));
        System.out.println("Contains 'dog'? " + unique.contains("dog"));
    }
}

words = ["the", "cat", "sat", "on", "the", "mat", "the"]

unique = set()    # set() makes an empty set -- {} would make an empty dict
for i in range(len(words)):
    w = words[i]
    unique.add(w)
# for-each version: for w in words:

# Python shows a set as {'on', 'cat', ...} rather than [on, cat, ...] -- order may vary either way
print("Unique words:", unique)
print("Count:", len(unique))
# Membership uses the in operator; Python prints True/False, Java prints true/false
print("Contains 'cat'?", "cat" in unique)
print("Contains 'dog'?", "dog" in unique)

Output (program က ထုတ်ပြတဲ့ ရလဒ်၊ element တွေရဲ့ အစဉ် ကွဲနိုင်ပါတယ်):

Unique words: [on, cat, the, mat, sat]
Count: 5
Contains 'cat'? true
Contains 'dog'? false

“the” ဆိုတဲ့ စကားလုံးက array (အရွယ်အစား ပုံသေ၊ အမျိုးအစားတူ ဒေတာစု) ထဲမှာ သုံးကြိမ် ပါပေမယ့် set ထဲမှာ တစ်ကြိမ်ပဲ ရှိပါတယ်။ Output ရဲ့ အစဉ်က ထည့်ခဲ့တဲ့ အစဉ် မဟုတ်ပါဘူး: HashSet မှာ အစဉ် မရှိလို့ element တွေ ဘယ်အစဉ်နဲ့မဆို ပေါ်လာနိုင်ပါတယ်။

ဥပမာ 2: Set Operation များ၊ ဈေးဝယ်စာရင်း

တစ်ယောက်ယောက်က ပန်ကိတ်မုန့် လုပ်ချင်ပါတယ်။ Set တစ်ခုမှာ ချက်နည်းအတွက် လိုတဲ့ ပါဝင်ပစ္စည်းတွေ ရှိပြီး နောက် set တစ်ခုမှာ မီးဖိုချောင်ထဲ ရှိပြီးသား ပစ္စည်းတွေ ရှိပါတယ်။ Set operation တစ်ခုစီက အဲဒီ set တွေနဲ့ ပတ်သက်တဲ့ မေးခွန်း တစ်ခုစီကို ဖြေပေးပါတယ်။

import java.util.HashSet;

public class ShoppingList {
    public static void main(String[] args) {
        HashSet<String> recipe = new HashSet<>();    // what the pancakes need
        recipe.add("flour");
        recipe.add("eggs");
        recipe.add("milk");
        recipe.add("butter");
        recipe.add("sugar");

        HashSet<String> pantry = new HashSet<>();    // what is already in the kitchen
        pantry.add("rice");
        pantry.add("eggs");
        pantry.add("sugar");
        pantry.add("salt");
        pantry.add("flour");

        // Intersection: ingredients already in the kitchen
        HashSet<String> inKitchen = new HashSet<>(recipe);
        inKitchen.retainAll(pantry);
        System.out.println("Already in the kitchen: " + inKitchen);

        // Difference: ingredients to buy
        HashSet<String> toBuy = new HashSet<>(recipe);
        toBuy.removeAll(pantry);
        System.out.println("To buy: " + toBuy);

        // Union: the pantry after shopping
        HashSet<String> restocked = new HashSet<>(pantry);
        restocked.addAll(recipe);
        System.out.println("Pantry after shopping: " + restocked);
    }
}

recipe = {"flour", "eggs", "milk", "butter", "sugar"}    # what the pancakes need
pantry = {"rice", "eggs", "sugar", "salt", "flour"}      # what is already in the kitchen

# The set operators return a NEW set, so no copy is needed (unlike Java's retainAll/removeAll/addAll)

# Intersection: ingredients already in the kitchen
in_kitchen = recipe & pantry
# Python shows a set as {'eggs', 'flour', ...} rather than [eggs, flour, ...]; the order may vary either way
print("Already in the kitchen:", in_kitchen)

# Difference: ingredients to buy
to_buy = recipe - pantry
print("To buy:", to_buy)

# Union: the pantry after shopping
restocked = pantry | recipe
print("Pantry after shopping:", restocked)

Output (element တွေရဲ့ အစဉ် ကွဲနိုင်ပါတယ်):

Already in the kitchen: [eggs, flour, sugar]
To buy: [butter, milk]
Pantry after shopping: [eggs, butter, salt, flour, milk, rice, sugar]

Difference က set နှစ်ခုရဲ့ အစဉ်ပေါ် မူတည်ပါတယ်။ recipe (ချက်နည်းအတွက် လိုတာ) ထဲက pantry (မီးဖိုချောင်ထဲ ရှိတာ) ကို နုတ်ရင် ဝယ်ရမယ့် စာရင်း ရပါတယ်။ pantry ထဲက recipe ကို နုတ်ရင်တော့ rice နဲ့ salt ကို ရပါမယ်၊ ဒါတွေက မီးဖိုချောင်ထဲ ရှိပေမယ့် ပန်ကိတ်မုန့် လုပ်ရာမှာ မသုံးတဲ့ ပစ္စည်းတွေပါ။

မူလ set ကို ဆက်ထားဖို့ လိုရင် retainAll၊ removeAll ဒါမှမဟုတ် addAll ကို မခေါ်ခင် set ကို အမြဲ copy ကူးပါ။ ဒီ method တွေက set ကို in place (မူလ set ထဲမှာပဲ) ပြောင်းလဲပါတယ်။

ဥပမာ 3: HashMap၊ အကြိမ်ရေ ရေတွက်ခြင်း

import java.util.HashMap;

public class FrequencyCounter {
    public static void main(String[] args) {
        String[] votes = {"Red", "Blue", "Red", "Green", "Blue", "Red", "Blue", "Blue"};

        HashMap<String, Integer> counts = new HashMap<>();
        for (int i = 0; i < votes.length; i++) {
            String vote = votes[i];
            if (counts.containsKey(vote)) {
                counts.put(vote, counts.get(vote) + 1);
            } else {
                counts.put(vote, 1);
            }
        }
        // for-each version: for (String vote : votes) { ... }

        System.out.println("Vote counts: " + counts);
        System.out.println("Red votes: " + counts.get("Red"));

        // Find the winner
        String winner = "";
        int maxVotes = 0;
        // keySet() has no index, so a for-each loop is the natural way to visit every key
        for (String key : counts.keySet()) {
            if (counts.get(key) > maxVotes) {
                maxVotes = counts.get(key);
                winner = key;
            }
        }
        System.out.println("Winner: " + winner + " with " + maxVotes + " votes");
    }
}

votes = ["Red", "Blue", "Red", "Green", "Blue", "Red", "Blue", "Blue"]

counts = {}    # an empty dict -- Python's HashMap
for i in range(len(votes)):
    vote = votes[i]
    if vote in counts:                     # in checks the KEYS, like containsKey
        counts[vote] = counts[vote] + 1    # counts[vote] reads/updates the value for that key
    else:
        counts[vote] = 1
# for-each version: for vote in votes:

# Python shows a dict as {'Red': 3, ...} rather than {Red=3, ...}
print("Vote counts:", counts)
print("Red votes:", counts["Red"])

# Find the winner
winner = ""
max_votes = 0
for key in counts:                         # looping over a dict visits its keys, like keySet()
    if counts[key] > max_votes:
        max_votes = counts[key]
        winner = key
print("Winner:", winner, "with", max_votes, "votes")

Output:

Vote counts: {Red=3, Blue=4, Green=1}
Red votes: 3
Winner: Blue with 4 votes

Frequency counter (အကြိမ်ရေ ရေတွက်တဲ့) ပုံစံက HashMap ကို အသုံးအများဆုံး နည်းတွေထဲက တစ်ခုပါ။ မထပ်တဲ့ item တစ်ခုစီက key ဖြစ်လာပြီး သူ့ အရေအတွက်က value ဖြစ်လာပါတယ်။

ဥပမာ 4: Hash Table အတွင်းမှာ အလုပ်လုပ်ပုံ

ရိုးရှင်းအောင် လုပ်ထားတဲ့ ဒီ hash table က key ရဲ့ စာလုံးတွေက သူ့ bucket ကို ဘယ်လို ဆုံးဖြတ်လဲ ပြပါတယ်။ Output မှာ မြင်ရတဲ့အတိုင်း collision တွေကို မကိုင်တွယ်သေးပါဘူး။

public class SimpleHashTable {
    private String[] table;
    private int size;

    public SimpleHashTable(int capacity) {
        table = new String[capacity];
        size = 0;
    }

    private int hash(String key) {
        int code = 0;
        for (int i = 0; i < key.length(); i++) {
            code = code + key.charAt(i);
        }
        return code % table.length;
    }

    public void put(String key) {
        int index = hash(key);
        System.out.println("'" + key + "' -> bucket " + index);
        table[index] = key;    // simplified: overwrites on collision
        size++;
    }

    public static void main(String[] args) {
        SimpleHashTable ht = new SimpleHashTable(7);
        ht.put("cat");
        ht.put("dog");
        ht.put("bat");
        ht.put("tac");          // anagram of "cat" -- same letter sum
    }
}

class SimpleHashTable():
    def __init__(self, capacity):
        self._table = [None] * capacity    # a fixed-size list of empty buckets
        self._size = 0                     # the leading underscore marks these as private (IB convention)

    def hash(self, key):
        code = 0
        for i in range(len(key)):
            code = code + ord(key[i])    # ord() gives the character code -- Java adds chars as numbers automatically
        return code % len(self._table)

    def put(self, key):
        index = self.hash(key)
        print("'" + key + "' -> bucket " + str(index))
        self._table[index] = key    # simplified: overwrites on collision
        self._size = self._size + 1

ht = SimpleHashTable(7)
ht.put("cat")
ht.put("dog")
ht.put("bat")
ht.put("tac")          # anagram of "cat" -- same letter sum

Output:

'cat' -> bucket 4
'dog' -> bucket 6
'bat' -> bucket 3
'tac' -> bucket 4

“cat” နဲ့ “tac” နှစ်ခုလုံး bucket 4 ကို hash ဖြစ်လို့ collision ဖြစ်ပါတယ်။ သူတို့မှာ စာလုံးတွေ အတူတူပဲ ပါလို့ (c+a+t = 312) စာလုံးတွေကို ပေါင်းတဲ့ hash က တန်ဖိုး အတူတူ ထုတ်ပေးပါတယ် (312 % 7 = 4)။ ရိုးရှင်းအောင် လုပ်ထားတဲ့ ဒီ version မှာ “tac” က “cat” ကို overwrite (ရှိပြီးသား content ကို ဖျက်ပြီး အသစ် ရေးခြင်း) လုပ်ပစ်ပါတယ်။ တကယ့် implementation (တကယ် အလုပ်လုပ်အောင် ရေးထားတဲ့ code) မှာဆိုရင် တန်ဖိုး နှစ်ခုလုံး သိမ်းထားနိုင်အောင် chaining (bucket တစ်ခုစီမှာ linked list) ကို သုံးပါလိမ့်မယ်။

Quick Check (အမြန် စစ်ဆေးမေးခွန်း)

Q1. "hello" ပါပြီးသား HashSet ပေါ်မှာ set.add("hello") ကို ခေါ်ရင် ဘာဖြစ်သလဲ။

Q2. HashMap ထဲမှာ key "age" က value 25 နဲ့ ရှိပြီးသား ဆိုရင် map.put("age", 30) ကို ခေါ်တဲ့အခါ ဘာဖြစ်သလဲ။

Q3. Hash table မှာ collision ဆိုတာ ဘာလဲ။

Q4. Hash table တစ်ခုမှာ entry 12 ခုနဲ့ bucket 16 ခု ရှိပါတယ်။ Load factor က ဘယ်လောက်လဲ။

Q5. setA.retainAll(setB) က ဘယ် set operation ကို လုပ်သလဲ။

Trace Exercise (code ကို တစ်ဆင့်ချင်း လိုက်ကြည့်ခြင်း)

ဒီ set နှစ်ခုပေါ်မှာ set operation တွေကို trace လုပ်ပါ (တစ်ဆင့်ချင်း လိုက်ပြီး မှတ်ပါ)။ နောက်ဆုံး row မှာ true (မှန်) ဒါမှမဟုတ် false (မှား) ကို English လို ရိုက်ထည့်ပါ:

setA = {1, 3, 5, 7, 9}
setB = {2, 3, 5, 8}

Operation	Java method	ရလဒ်
Union (A ∪ B)	`addAll`
Intersection (A ∩ B)	`retainAll`
Difference (A - B)	`removeAll`
B က A ရဲ့ subset လား။	`containsAll`

HashMap operation တွေကို တစ်ဆင့်ချင်း trace လုပ်ပါ။ အဖြေတွေကို Java က ပြတဲ့ ပုံစံအတိုင်း English လို ရိုက်ထည့်ပါ။

Operation	ပြီးနောက် map ရဲ့ အခြေအနေ	Return value (ပြန်ပေးတဲ့ တန်ဖိုး)
`put("A", 10)`	{A=10}
`put("B", 20)`		null
`put("A", 30)`
`get("B")`	{A=30, B=20}
`get("C")`	{A=30, B=20}

Code Completion (code ကွက်လပ် ဖြည့်ခြင်း)

HashMap ကို သုံးပြီး frequency counter ပုံစံကို ပြည့်စုံအောင် ဖြည့်ပါ။

Array ထဲမှာ စကားလုံး တစ်ခုစီ ဘယ်နှစ်ကြိမ် ပါလဲ ရေတွက်ပါ:

HashMap<String, Integer> counts = new HashMap<>();
for (int i = 0; i < words.length; i++) {
    String word = words[i];
    if (counts.(word)) {
        counts.put(word, counts.(word) + 1);
    } else {
        counts.put(word, );
    }
}

မူလ set ကို မပြောင်းအောင် copy တစ်ခုကို သုံးပြီး set intersection ကို ပြည့်စုံအောင် ဖြည့်ပါ။

Playlist (သီချင်းစာရင်း) တစ်ခုခုကိုမှ မပြောင်းဘဲ playlist နှစ်ခုလုံးမှာ ပါတဲ့ သီချင်းတွေကို ရှာပါ:

HashSet<String> onBoth = new (roadTrip);
onBoth.(workout);
System.out.println("On both: " + onBoth);

Spot the Error (အမှား ရှာခြင်း)

ဒီ code က intersection ရော မူလ set A ကိုပါ print ထုတ်ရမှာပါ၊ ဒါပေမဲ့ intersection လုပ်ပြီးနောက် set A က မှားနေပါတယ်:

1HashSet<String> setA = new HashSet<>(); 2setA.add("X"); setA.add("Y"); setA.add("Z"); 3HashSet<String> setB = new HashSet<>(); 4setB.add("Y"); setB.add("Z"); setB.add("W"); 5 6setA.retainAll(setB); 7System.out.println("Intersection: " + setA); 8System.out.println("Original A: " + setA); // expected {X, Y, Z}

Line 8 က comment “expected {X, Y, Z}” က {X, Y, Z} လို့ ထွက်ရမယ်လို့ ဆိုလိုပါတယ်။

မှန်ကန်တဲ့ ပြင်နည်းကို ရွေးပါ:

ဒီ frequency counter က compile မဖြစ်ပါဘူး:

1HashMap<String, Integer> map = new HashMap<>(); 2for (int i = 0; i < items.length; i++) { 3 String item = items[i]; 4 if (map.contains(item)) { 5 map.put(item, map.get(item) + 1); 6 } else { 7 map.put(item, 1); 8 } 9}

မှန်ကန်တဲ့ ပြင်နည်းကို ရွေးပါ:

Predict the Output (output ကို ကြိုခန့်မှန်းခြင်း)

ဒီ code က ဘာကို print ထုတ်သလဲ။

HashSet<String> fruits = new HashSet<>();
fruits.add("apple");
fruits.add("banana");
fruits.add("cherry");
fruits.add("apple");
fruits.remove("banana");
System.out.println(fruits.size());
System.out.println(fruits.contains("banana"));

Output ကို အတိအကျ ရိုက်ထည့်ပါ:

ဒီ code က ဘာကို print ထုတ်သလဲ။

HashMap<String, Integer> map = new HashMap<>();
map.put("X", 5);
map.put("Y", 10);
map.put("X", 15);
System.out.println(map.get("X"));
System.out.println(map.get("Z"));
System.out.println(map.size());

Output ကို အတိအကျ ရိုက်ထည့်ပါ:

Practice Exercises (လေ့ကျင့်ခန်းများ)

Core (အခြေခံ အဆင့်)

ထပ်နေတာတွေကို ဖယ်ပါ: Integer array {4, 2, 7, 2, 9, 4, 7, 1} ကို ပေးထားပါတယ်။ HashSet ကို သုံးပြီး ထပ်နေတာတွေကို ဖယ်ပါ။ မထပ်တဲ့ တန်ဖိုးတွေနဲ့ သူတို့ရဲ့ အရေအတွက်ကို print ထုတ်ပါ။ (ရရမယ့် အရေအတွက်: 5)
စကားလုံး အကြိမ်ရေ: စကားလုံးတွေကို String[] အဖြစ် သိမ်းထားတဲ့ စာကြောင်း တစ်ကြောင်းကို ပေးထားပါတယ်။ HashMap<String, Integer> ကို သုံးပြီး စကားလုံး တစ်ခုစီ ဘယ်နှစ်ကြိမ် ပါလဲ ရေတွက်ပါ။ စကားလုံး တစ်ခုစီနဲ့ သူ့ အရေအတွက်ကို print ထုတ်ပါ။
ကျောင်းသား ရှာခြင်း: ကျောင်းသား နာမည်တွေကို သူတို့ရဲ့ grade (အမှတ်) တွေနဲ့ တွဲပေးတဲ့ HashMap<String, Integer> တစ်ခု ဖန်တီးပါ။ ကျောင်းသား 5 ယောက် ထည့်ပြီး နာမည် တစ်ခုကို ရှာကာ “Found: [grade]” ဒါမှမဟုတ် “Not found” ကို print ထုတ်ပါ။

Extension (တိုးချဲ့ အဆင့်)

Set operation များ: Set နှစ်ခု ဖန်တီးပါ: classA = {"Alice", "Bob", "Carol", "Dave"} နဲ့ classB = {"Bob", "Dave", "Eve", "Frank"}။ ဒါတွေကို print ထုတ်ပါ: (a) အတန်း နှစ်ခုလုံးမှာ ရှိတဲ့ ကျောင်းသားတွေ (intersection)၊ (b) ကျောင်းသား အားလုံး (union)၊ (c) အတန်း A မှာပဲ ရှိတဲ့ ကျောင်းသားတွေ (difference)။ မူလ set တွေကို မပြောင်းအောင် ထိန်းထားပါ။
အများဆုံး ပါတဲ့ character: String (စာသား) တစ်ခုကို ပေးထားပါတယ်။ HashMap<Character, Integer> ကို သုံးပြီး character (စာလုံး ဒါမှမဟုတ် သင်္ကေတ) တစ်ခုစီ ဘယ်နှစ်ကြိမ် ပါလဲ ရေတွက်ပါ၊ ပြီးရင် အများဆုံး ပါတဲ့ character နဲ့ သူ့ အရေအတွက်ကို ရှာပြီး print ထုတ်ပါ။
Hash function ကို စမ်းသပ်ခြင်း: String တစ်ခုရဲ့ character တန်ဖိုးတွေကို ပေါင်းပြီး ရလဒ်ကို table size နဲ့ modulo (စားလို့ ရတဲ့ အကြွင်း) ယူကာ ပြန်ပေးတဲ့ ရိုးရှင်းတဲ့ hash function တစ်ခု ရေးပါ။ စကားလုံး 10 လုံးနဲ့ size 7 ရှိတဲ့ table ကို သုံးပြီး စမ်းပါ။ Collision ဘယ်နှစ်ခု ဖြစ်သလဲ။ Size 13 ရှိတဲ့ table နဲ့ စမ်းကြည့်ပါ။ Collision တွေ လျော့သွားသလား။

Challenge (စိန်ခေါ်မှု အဆင့်)

Two-sum ပြဿနာ: Integer array တစ်ခုနဲ့ target sum (ရချင်တဲ့ ပေါင်းလဒ်) ကို ပေးထားပါတယ်။ HashMap ကို သုံးပြီး ပေါင်းရင် target ရတဲ့ ဂဏန်း နှစ်ခုကို ရှာပါ။ ဂဏန်း တစ်ခုစီအတွက် target - number က map ထဲမှာ ရှိပြီးသားလား စစ်ပါ။ အဲဒီ ဂဏန်း အတွဲကို return (ရလဒ်အဖြစ် ပြန်ပေး) လုပ်ပါ။ HashMap နဲ့ဆိုရင် ဒါက O(n) ဖြစ်ပြီး nested loop (loop ထဲမှာ ထပ်ပါတဲ့ loop) တွေနဲ့ဆိုရင် O(n^2) ဖြစ်ပါတယ်။
ရိုးရှင်းတဲ့ spell checker (စာလုံးပေါင်း စစ်တဲ့ program): မှန်ကန်တဲ့ စကားလုံးတွေ ပါတဲ့ အဘိဓာန် တစ်ခုကို HashSet ထဲ ထည့်ပါ။ စာပိုဒ် တစ်ပိုဒ် (စကားလုံးတွေရဲ့ array) ကို ပေးထားရင် စကားလုံး တစ်ခုစီကို အဘိဓာန်နဲ့ တိုက်စစ်ပြီး စာလုံးပေါင်း မှားနေတဲ့ စကားလုံးတွေကို print ထုတ်ပါ။ တွက်ကြည့်ပါ: list (lookup တစ်ခါကို O(n)) သုံးရင်နဲ့ HashSet (lookup တစ်ခါကို O(1)) သုံးရင် ရှာရတဲ့ အလုပ် ဘယ်လောက် လိုမလဲ။

ဆက်စပ် ခေါင်းစဉ်များ

အရင် လေ့လာထားရမယ့် ခေါင်းစဉ်: What Are ADTs? (ADT ဆိုတာ ဘာလဲ): interface (class တစ်ခု implement လုပ်ရမယ့် method စာရင်း) နဲ့ implementation ကွာခြားချက် သဘောတရား
အရင် လေ့လာထားရမယ့် ခေါင်းစဉ်: OOP Fundamentals (object တွေကို အခြေခံပြီး program ရေးနည်းရဲ့ အခြေခံများ): class (object တွေ ဖန်တီးဖို့ ပုံစံခွက်)၊ object (class တစ်ခုကနေ ဖန်တီးထားတဲ့ instance) နဲ့ encapsulation (ဒေတာနဲ့ method ကို တစ်စုတည်း ထုပ်ပိုးခြင်း)
ဆက်စပ် ခေါင်းစဉ်: Binary Search Trees: မြန်မြန် ရှာနိုင်တဲ့ နောက်ထပ် structure တစ်ခုပါ၊ ဒါပေမဲ့ sorted အစဉ်ကို ထိန်းထားပါတယ် (O(1) အစား O(log n))
ဆက်စပ် ခေါင်းစဉ်: ArrayList (ကြီးလာ၊ သေးသွားနိုင်တဲ့ list): ကြီးလာ၊ သေးသွားနိုင်တဲ့ collection တွေပါ၊ ဒါပေမဲ့ element တွေ မထပ်ဖို့ အာမခံချက်လည်း မရှိ၊ O(1) lookup လည်း မရှိပါဘူး
နောက်ထပ် လေ့လာမယ့် ခေါင်းစဉ်: Choosing the Right Structure (သင့်တော်တဲ့ data structure ကို ရွေးချယ်ခြင်း): သင့်တော်တဲ့ tool ကို ရွေးနိုင်အောင် ADT အားလုံးကို နှိုင်းယှဉ်ခြင်း