Hash Table — O(1) Average-case Lookup

နားလည်ထားရမယ့် အချက်

Lesson content တစ်ခုကို slug နဲ့ ရှာချင်တယ်ဆိုကြပါစို့ — naive အကြံအိုက်တစ်ခုက (slug, content) tuple list တစ်ခုကို linear scan လုပ်ပြီး slug ကိုက်တဲ့ entry ရှာတာဖြစ်တယ်၊ list ရဲ့ ဆုံးပိုင်းက entry ကို ရှာရင်တောင် O(n) ကြာနိုင်တယ်။ Hash table ကတော့ ဒီကို ဆန်းသစ်ပုံဖြင့် ဖြေရှင်းတယ် — key (slug) ကို hash function တစ်ခုနဲ့ integer index တစ်ခုဖြစ်အောင် compute လုပ်ပြီး၊ ဒီ index ကို underlying array ရဲ့ 'bucket' အဖြစ် တိုက်ရိုက်သုံးတယ်၊ ဒါကြောင့် lookup က index ကို O(1) မှာ compute လုပ်နိုင်ပြီး bucket ကို တိုက်ရိုက် ထိရောက်ရောက် သွားရောက်ကြည့်နိုင်တယ်။ Key နှစ်ခုက hash function ကနေ index တူတူထွက်လာနိုင်တယ် — ဒါကို collision လို့ခေါ်တယ်၊ ရိုးရှင်းတဲ့ resolution strategy တစ်ခုက chaining ဖြစ်တယ် — bucket တစ်ခုစီမှာ single value မဟုတ်ဘဲ (linked) list တစ်ခု သိမ်းထားပြီး collision ဖြစ်တဲ့ key တွေအားလုံးကို အဲဒီ list ထဲ ထည့်ထားတယ်။ Collision အရေအတွက် နည်းနေသေးရင် average case O(1) ရနေတယ်၊ ဒါပေမယ့် hash function ညံ့ရင် (ဒါမှမဟုတ် adversarial input ရှိရင်) bucket တစ်ခုထဲကို key အများကြီး ကျရောက်နိုင်လို့ worst case O(n) အထိ degrade ဖြစ်နိုင်တယ်။ Python ရဲ့ `dict` နဲ့ `set` က production-quality hash table implementation တွေဖြစ်တယ်။

လက်တွေ့ scenario နဲ့ ချိတ်ကြည့်မယ်

Tutorial Platform ရဲ့ slug-to-content lookup ဟာ hash table ရဲ့ classic use case ပဲဖြစ်တယ် — course တစ်ခုမှာ lesson ရာနဲ့ချီရှိနေရင်တောင် `lessons_by_slug[slug]` လို dict lookup က O(1) ဆက်ဖြစ်နေတယ်၊ URL router က slug ကို content ဖြစ်အောင် instant ပြောင်းပေးနိုင်တာ ဒီနောက်ကွယ်က hash table ကြောင့်ဖြစ်တယ်။

• Hash function က key ကို bucket index ဖြစ်အောင် compute လုပ်ပေးလို့ O(1) average-case lookup ဖြစ်တယ်
• Key နှစ်ခု index တူထွက်တာ collision ဖြစ်ပြီး chaining က resolution strategy တစ်ခု
• Python ရဲ့ dict/set က hash table ကို base ခံထားလို့ average O(1) ဖြစ်ပေမယ့် worst case O(n) ဖြစ်နိုင်တယ်

အတူတူ စမ်းရေးကြည့်မယ်

lessons = [
    ("linked-lists", "Linked Lists content..."),
    ("stacks", "Stacks content..."),
    ("queues", "Queues content..."),
    ("hash-tables", "Hash Tables content..."),
]

# Naive approach: linear scan through a list of tuples - O(n) worst case
def find_naive(slug):
    for s, content in lessons:
        if s == slug:
            return content
    return None

# Hash table approach: dict hashes the slug straight to a bucket - O(1) average
lesson_map = dict(lessons)

def find_hashed(slug):
    return lesson_map.get(slug)

print(find_naive("hash-tables"))
print(find_hashed("hash-tables"))

နှစ်ခုစလုံး 'Hash Tables content...' ဆိုတဲ့ string တူတူပြန်ပေးပေမယ့်၊ `find_naive` က list ကို scan လုပ်ပြီး၊ `find_hashed` က hash index ကို တိုက်ရိုက်ထိသွားတာ ကွာခြားချက်ရှိတယ်။

Wikipedia — Hash table — Data Structures & Algorithms