On this page
บทเรียน: Hash Table
👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ
โครงสร้างที่ค้นหา/นับ/จับคู่ได้เร็วเฉลี่ย O(1) — กุญแจของโจทย์สัมภาษณ์จำนวนมาก
Hash table (dict ใน Python, HashMap ใน Java) เก็บข้อมูลเป็นคู่ key → value และค้นหาด้วย key ได้เร็วเฉลี่ย O(1) เมื่อเจอคำว่า "นับ", "หาตัวซ้ำ", "เคยเห็นไหม", หรือ "หาคู่ที่รวมได้ค่าเป้าหมาย" มักใช้ hash table
ตัวอย่าง: Two Sum
หาคู่ตัวเลขที่บวกกันได้ target — ใช้ hash table เก็บค่าที่เคยเห็น ลดจาก O(n²) เหลือ O(n)
python
def two_sum(nums, target):
seen = {} # value -> index
for i, n in enumerate(nums):
need = target - n
if need in seen:
return [seen[need], i]
seen[n] = i
return []
print(two_sum([2, 7, 11, 15], 9)) # [0, 1]การนับความถี่
python
from collections import Counter
count = Counter("banana")
print(count) # {'a': 3, 'n': 2, 'b': 1}
print(count['a']) # 3ข้อควรระวัง
key ต้องเป็นชนิดที่ hash ได้ (string, number, tuple) — list หรือ dict เป็น key ไม่ได้ และอย่าลืมว่า O(1) เป็นค่าเฉลี่ย กรณีแย่สุดอาจเป็น O(n)