Hash Table เจาะลึก

dict และ set ของ Python เบื้องหลังคือ hash table — โครงสร้างที่ค้นหา/เพิ่ม/ลบได้ O(1) โดยเฉลี่ย เข้าใจว่ามันทำงานยังไงและใช้แก้โจทย์ได้ คือหนึ่งในทักษะที่ทรงพลังที่สุด

hash table ทำงานยังไง

hash function แปลง key เป็นตัวเลข (hash) แล้วใช้เลขนั้นบอกตำแหน่งเก็บ (bucket) ทำให้กระโดดไปหาได้เลยไม่ต้องไล่ — จึง O(1) โดยเฉลี่ย

เมื่อ 2 key ได้ตำแหน่งเดียวกัน (collision) hash table จัดการด้วยการเก็บต่อกันในตำแหน่งนั้น กรณีแย่สุดจึงเป็น O(n) แต่ในทางปฏิบัติเกิดน้อยมาก

ใช้ hash แก้โจทย์: Two Sum

โจทย์คลาสสิก: หาคู่ที่บวกกันได้ target — แทน loop ซ้อน O(n²) ใช้ dict จำตัวที่เคยเจอ เหลือ O(n)

def two_sum(nums, target):
    seen = {}                      # value -> index
    for i, n in enumerate(nums):
        need = target - n
        if need in seen:           # เคยเจอตัวที่ต้องการ? (O(1))
            return (seen[need], i)
        seen[n] = i
    return None

print(two_sum([2, 7, 11, 15], 9))   # (0, 1)

นับความถี่ & group

from collections import Counter, defaultdict

# นับความถี่
print(Counter("banana"))      # Counter({'a':3,'n':2,'b':1})

# group anagram (คำที่สลับตัวอักษรกัน)
def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        key = "".join(sorted(w))   # anagram มี key เดียวกัน
        groups[key].append(w)
    return list(groups.values())

print(group_anagrams(["eat", "tea", "tan", "ate"]))
# [['eat','tea','ate'], ['tan']]

สรุปหัวข้อนี้

• hash table: hash(key) → ตำแหน่งเก็บ → ค้น/เพิ่ม/ลบ O(1) เฉลี่ย
• collision จัดการได้ แต่กรณีแย่สุด O(n) (เกิดน้อย)
• two-sum: ใช้ dict จำตัวที่เจอ ลด O(n²) → O(n)
• นับ → Counter, group → defaultdict; เจอ 'เคยเจอ/นับ/จับคู่' คิดถึง hash