ตารางแฮชและพจนานุกรม — โครงสร้างที่ใช้บ่อยที่สุด

ตารางแฮช (hash table) คือโครงสร้างที่เปลี่ยนการค้นหาแบบไล่ทีละตัว O(n) ให้กลายเป็นการเข้าถึงโดยตรง O(1) โดยเฉลี่ย มันคือ “เครื่องยนต์” ที่ทำงานเงียบ ๆ อยู่เบื้องหลังซอฟต์แวร์เกือบทุกชิ้น ตั้งแต่ฐานข้อมูล แคช ไปจนถึงตัวแปร dict ที่คุณใช้ทุกวัน

แนวคิดหลัก

ตารางแฮชเก็บข้อมูลแบบ คู่กุญแจ–ค่า (key–value) เช่น "สมชาย" → 25 หัวใจของมันคือ ฟังก์ชันแฮช (hash function) ที่รับกุญแจเข้าไปแล้วคำนวณออกมาเป็น เลขดัชนีของช่อง (bucket index) ในอาเรย์เบื้องหลัง

ฟังก์ชันแฮชเปรียบเหมือนพนักงานจัดเอกสาร: ยื่นชื่อให้ แล้วมันบอกได้ทันทีว่าเอกสารอยู่ลิ้นชักไหน โดยไม่ต้องเปิดดูทุกลิ้นชัก

ขั้นตอนการเก็บค่า (set) และดึงค่า (get):

1. คำนวณ index = hash(key) % ขนาดอาเรย์
2. ไปที่ช่องตำแหน่งนั้นทันที แล้วเก็บหรืออ่านค่า

เพราะการกระโดดไปยังช่องที่คำนวณได้นั้นใช้เวลาคงที่ การ get และ set จึงเป็น O(1) โดยเฉลี่ย ไม่ขึ้นกับว่ามีข้อมูลกี่ล้านตัว

กายวิภาคของฟังก์ชันแฮช

ฟังก์ชันแฮชที่ดีต้องมีคุณสมบัติสามข้อ:

1. กำหนดผลแน่นอน (deterministic) — กุญแจเดิมต้องได้แฮชเดิมเสมอ (ในการรันโปรแกรมครั้งเดียวกัน)
2. คำนวณเร็ว — ควรเป็น O(1) เทียบกับขนาดกุญแจ ไม่งั้นก็เสียประเด็นทั้งหมดไป
3. กระจายสม่ำเสมอ (uniform) — ต้องกระจายกุญแจไปทั่วทุกช่องอย่างเท่า ๆ กัน ไม่ให้ช่องใดช่องหนึ่งรับภาระมากเกินไป

ฟังก์ชันแฮชที่ แย่ ก็ยัง “ทำงานได้” (คืนค่าจำนวนเต็มออกมาเสมอ) แต่มันจะทำให้กุญแจกระจุกตัวอยู่ด้วยกัน และเงียบ ๆ เปลี่ยนตารางที่ควรเป็น O(1) ให้กลายเป็นลิงก์ลิสต์ที่เป็น O(n) นี่คือเหตุผลที่ภาษาโปรแกรมระดับโปรดักชันไม่ปล่อยให้คุณเขียนฟังก์ชันแฮชสตริงของตัวเองตามใจชอบ — hash() ของ Python สำหรับสตริงใช้ SipHash ซึ่งเป็นฟังก์ชันผสมที่ออกแบบด้วยแนวคิดเชิงรหัสลับ เพื่อป้องกันการกระจุกตัวแบบนี้โดยเฉพาะ

hash(key) % table_size จะดีได้แค่ไหนก็ขึ้นอยู่กับ hash() เท่านั้น การหารเอาเศษ (modulo) เป็นส่วนที่ง่าย แต่การออกแบบ hash() ที่ดีคือส่วนที่ยาก

ตัวอย่างไล่ทีละขั้นที่ 1 — ไล่จากแฮชไปยังช่องด้วยมือ

เพื่อให้เห็นการชนกันเกิดขึ้นจริง ลองใช้ฟังก์ชันแฮชของเล่นที่ อ่อนแอ โดยตั้งใจ เพื่อให้เลขคำนวณง่าย: h(s) = ผลรวมของ ord(c) สำหรับทุกตัวอักษร c ใน s ขนาดตาราง = 8

กุญแจ	ผลรวมรหัสตัวอักษร	% 8	ช่อง
"cat"	312	0	0
"dog"	314	2	2
"bird"	417	1	1
"fish"	426	2	2 ← ชนกับ "dog"
"lion"	434	2	2 ← ชนกับ "dog", "fish"

ตารางผลลัพธ์ (แบบต่อโซ่):

ช่อง 0: [ ("cat", ...) ]
ช่อง 1: [ ("bird", ...) ]
ช่อง 2: [ ("dog", ...) ] -> [ ("fish", ...) ] -> [ ("lion", ...) ]
ช่อง 3..7: [ ]

สังเกตว่าช่อง 2 ตอนนี้มี 3 รายการ — การค้นหา "lion" ต้องไล่ผ่าน "dog" และ "fish" ก่อน นี่คือต้นทุนของฟังก์ชันแฮชที่อ่อนแอ: การรวมค่าตัวอักษรแบบบวกล้วน ๆ ไม่สนใจลำดับหรือตำแหน่งของตัวอักษรเลย จึงทำให้หลายคำที่ต่างกันตกไปอยู่ในผลรวมที่ใกล้เคียงกัน ฟังก์ชันแฮชจริง (SipHash, MurmurHash, FNV) จะผสมบิตด้วยการคูณและการเลื่อนบิต (shift) เพื่อป้องกันการกระจุกตัวแบบนี้โดยเฉพาะ บทเรียนคือ: อย่าคิดค้นฟังก์ชันแฮชเองสำหรับโค้ดโปรดักชัน — ใช้ตัวที่ภาษาให้มาแทน

การแก้ปัญหาการชนกัน: การต่อโซ่ vs. open addressing

ฟังก์ชันแฮชย่อกุญแจจำนวนมหาศาลให้เหลือดัชนีจำนวนจำกัด ดังนั้นการชนกันจึงเกิดขึ้นแน่นอนทางคณิตศาสตร์เมื่อมีกุญแจมากพอ (นี่คือหลักคณิตศาสตร์เดียวกับ “ปัญหาวันเกิด” — การชนกันจะเกิดเร็วกว่าที่สัญชาตญาณคาดไว้มาก) มีสองวิธีมาตรฐานในการรับมือกับมัน

การต่อโซ่ (chaining) — แต่ละช่องเก็บลิสต์เล็ก ๆ (หรือลิงก์ลิสต์) ของคู่ที่ตกลงมาที่นั่น เมื่อค้นหาก็ไล่ดูเฉพาะในลิสต์สั้น ๆ ของช่องนั้น นี่คือสิ่งที่ตัวอย่างไล่ทีละขั้นที่ 1 ข้างต้นแสดงให้เห็น

Open addressing — ไม่มีลิสต์เลย ถ้าช่องถูกจองไปแล้ว ก็ สำรวจ (probe) ไปข้างหน้า (ตามกฎที่กำหนดไว้) เพื่อหาช่องว่างถัดไป แล้วเก็บค่าไว้ที่นั่นแทน

ตัวอย่างไล่ทีละขั้นที่ 2 — open addressing แบบ linear probing

ขนาดตาราง = 8, ฟังก์ชันแฮชคือฟังก์ชันเอกลักษณ์ (h(k) = k), กฎการสำรวจ: “ถ้าช่องถูกจอง ให้ลองช่องถัดไป” (linear probing) แทรกค่า 3, 11, 19, 8 ตามลำดับ:

แทรก	h(k) % 8	ช่องที่ลอง	ผลลัพธ์
3	3	3 (ว่าง)	วางที่ตำแหน่ง 3
11	3	3 (ถูกจองโดย 3) → สำรวจช่อง 4 (ว่าง)	วางที่ตำแหน่ง 4
19	3	3 (ถูกจอง) → 4 (ถูกจอง) → สำรวจช่อง 5 (ว่าง)	วางที่ตำแหน่ง 5
8	0	0 (ว่าง)	วางที่ตำแหน่ง 0

อาเรย์สุดท้าย: [8, _, _, 3, 11, 19, _, _]

การค้นหา 19 ต้องทำการสำรวจแบบเดิมซ้ำ (3 → 4 → 5) เพื่อเจอมัน — นี่คือต้นทุนที่ open addressing ต้องจ่ายจากการไม่มีลิสต์

	การต่อโซ่	Open addressing
หน่วยความจำเพิ่มต่อช่อง	ต้นทุนลิสต์/พอยน์เตอร์เล็กน้อย	ไม่มี — ใช้อาเรย์เดิมซ้ำ
load factor เกิน 1.0 ได้ไหม	ได้	ไม่ได้ ต้องอยู่ที่ < 1.0 เสมอ
ความเป็นมิตรกับแคช	แย่กว่า (โครงสร้างลิงก์กระจายในหน่วยความจำ)	ดีกว่า (อาเรย์ต่อเนื่อง เป็นมิตรกับแคช)
การลบ	ตรงไปตรงมา (ลบออกจากลิสต์)	ยุ่งยาก — ต้องใช้เครื่องหมาย “tombstone” แทนที่จะเป็นช่องว่างจริง ๆ
กรณีเลวร้ายสุด	O(n) เพื่อไล่โซ่ที่ยาวเส้นเดียว	O(n) เพื่อสำรวจทั้งตาราง

dict และ set ของ CPython จริง ๆ ใช้ open addressing ภายใน (ด้วยลำดับการสำรวจแบบสุ่มเทียม ไม่ใช่ linear probing ธรรมดา) — นี่เป็นส่วนหนึ่งที่ทำให้ dict ของ Python เป็นมิตรกับแคชและเร็วมากในทางปฏิบัติ

Load factor และการขยายขนาด (rehashing)

Load factor α = จำนวนข้อมูล ÷ จำนวนช่อง คือตัวเลขตัวเดียวที่บอกได้ว่าตารางแฮชของคุณตอนนี้เร็วแค่ไหน

• load factor ต่ำ (เช่น 0.25) → ช่องส่วนใหญ่ว่าง โซ่แทบทุกเส้นยาว 0 หรือ 1 → เร็ว แต่เปลืองหน่วยความจำ
• load factor สูง (เช่น เข้าใกล้ 1.0 หรือเกินกว่านั้น) → โซ่ยาวขึ้น → การค้นหาเสื่อมลงไปทาง O(n)

การ implement ส่วนใหญ่จะสั่ง ขยายขนาด (resize) เมื่อ α ข้ามเกณฑ์ที่กำหนด (มักอยู่ที่ 0.66–0.75): จัดสรรอาเรย์ใหม่ที่ใหญ่กว่า (โดยทั่วไปคือเพิ่มเป็นสองเท่า) แล้ว คำนวณตำแหน่งใหม่ (rehash) ให้กับทุกกุญแจที่มีอยู่ ในอาเรย์ใหม่ เพราะ index = hash(key) % ขนาดใหม่ จะให้ผลต่างออกไปเมื่อขนาดเปลี่ยน

การขยายขนาดเองก็เป็น O(n) — แต่มันเกิดขึ้นไม่บ่อย (แค่ทุก ๆ ครั้งที่ขนาดเพิ่มเป็นสองเท่า) ดังนั้นต้นทุนของมัน เมื่อกระจาย (“amortized”) ไปตลอดการแทรกทั้งหมดที่นำไปสู่มัน จะเพิ่มเพียง O(1) โดยเฉลี่ยต่อการแทรกหนึ่งครั้ง นี่คือกลเม็ดการวิเคราะห์แบบ amortized เดียวกับที่ใช้อธิบายการขยายขนาดของอาเรย์พลวัต (list)

ตัวอย่างไล่ทีละขั้นที่ 3 — การขยายขนาดในการทำงานจริง

ขนาดตาราง = 4, ฟังก์ชันแฮชแบบเอกลักษณ์, แทรก 1, 2, 3, 4:

แทรก	h(k) % 4	ช่อง
1	1	1
2	2	2
3	3	3
4	0	0

จนถึงตอนนี้ยังดี — 4 ข้อมูล 4 ช่อง α = 1.0 ยังไม่มีการชนกัน แต่เราอยู่ในโซนอันตรายแล้ว ลองแทรก 5:

5 % 4 = 1 → ชนกับกุญแจ 1

α ตอนนี้คือ 5/4 = 1.25 เกินเกณฑ์ขยายขนาดแล้ว → ตารางขยายเป็นขนาด 8 และคำนวณตำแหน่งใหม่ให้ทุกกุญแจ:

กุญแจ	h(k) % 8	ช่องใหม่
1	1	1
2	2	2
3	3	3
4	4	4
5	5	5

ตอนนี้ทั้งห้ากุญแจตกไปอยู่คนละช่องกันหมด — การชนกันหายไป และ α ลดลงเหลือ 5/8 = 0.625 นี่คือเหตุผลที่การขยายขนาด “คืนสภาพ” ประสิทธิภาพ O(1) ได้: มันไม่ใช่เวทมนตร์ แต่เป็นการให้พื้นที่ฟังก์ชันแฮชกระจายกุญแจได้มากขึ้นตรง ๆ

ข้อสังเกต: การขยายขนาดจะช่วยได้ ก็ต่อเมื่อฟังก์ชันแฮชผสมบิตได้ดีตั้งแต่แรก ย้อนกลับไปดูตัวอย่างไล่ทีละขั้นที่ 1 — ฟังก์ชันแฮชแบบ “รวมค่าตัวอักษร” ที่อ่อนแอ มักจะทำให้กุญแจ ชุดเดิม กระจุกตัวอยู่ด้วยกันไม่ว่าตารางจะใหญ่แค่ไหน เพราะผลรวมพื้นฐานยังใกล้เคียงกันไม่ว่า modulus จะเป็นเท่าไร การขยายขนาดแก้ปัญหาความหนาแน่น ไม่ใช่ฟังก์ชันแฮชที่แย่

ทำไม O(1) ถึงเป็นค่าเฉลี่ย ไม่ใช่กรณีเลวร้ายสุด

ข้อกล่าวอ้าง O(1) ตั้งอยู่บนสมมติฐานที่ CLRS เรียกว่า simple uniform hashing — ทุกกุญแจมีโอกาสเท่ากันที่จะถูกแฮชไปยังช่องใดช่องหนึ่ง โดยไม่ขึ้นกับกุญแจอื่น ภายใต้สมมติฐานนี้ เมื่อคุม load factor α ให้คงที่ (ด้วยการขยายขนาด) จำนวนกุญแจที่ คาดหวัง ว่าต้องตรวจต่อการค้นหาหนึ่งครั้งคือ O(1 + α) = O(1)

แต่นั่นคือ ค่าเฉลี่ยจากอินพุตแบบสุ่ม ไม่ใช่การรับประกันสำหรับอินพุตทุกแบบที่เป็นไปได้:

• กรณีเลวร้ายสุดคือ O(n) เสมอ ถ้าทุกกุญแจบังเอิญแฮชไปลงช่องเดียวกันหมด คุณก็สร้างลิงก์ลิสต์ราคาแพงขึ้นมาโดยไม่รู้ตัว สิ่งนี้ไม่มีทางตัดทิ้งได้โดยสิ้นเชิงในทางทฤษฎี — ทำได้แค่ทำให้ แทบเป็นไปไม่ได้ในทางปฏิบัติ ด้วยฟังก์ชันแฮชที่ดี
• ผู้ประสงค์ร้ายทำลายสมมติฐานนี้ได้ ถ้าผู้โจมตีรู้ (หรือเดาได้) ฟังก์ชันแฮชของคุณ พวกเขาสามารถสร้างกุญแจอินพุตที่ชนกันโดยตั้งใจทั้งหมด — เรียกว่า การโจมตีแบบ hash flooding การป้อนกุญแจแบบนี้เข้าตารางแฮชที่ไม่ระวังจะเปลี่ยนตัวจัดการคำขอที่ควรเป็น O(n) ให้กลายเป็นการโจมตีปฏิเสธการให้บริการ (denial-of-service) แบบ O(n²) นี่คือช่องโหว่ที่เกิดขึ้นจริงในประวัติศาสตร์ (หลายภาษาโปรแกรม รวมถึง PHP, Java และ Python รุ่นแรก ๆ ได้รับการแพตช์ราวปี 2011–2012 หลังมีการเผยแพร่เรื่องนี้) — นี่คือเหตุผลที่ Python สุ่มค่าการแฮชสตริงในแต่ละโปรเซสโดยค่าเริ่มต้น (PYTHONHASHSEED) เพื่อให้สตริงเดียวกันแฮชต่างกันในแต่ละครั้งที่รัน และผู้โจมตีไม่สามารถคำนวณกุญแจที่ชนกันไว้ล่วงหน้าได้

“ค่าเฉลี่ย O(1)” คือข้อความที่พูดถึงอินพุต ทั่วไป ภายใต้ฟังก์ชันแฮช ที่ดี — ไม่ใช่กฎฟิสิกส์ตายตัว การตัดสินว่ามันเป็นจริงหรือไม่ต้องตรวจสอบทั้งสองเงื่อนไข

เมื่อการแฮชเสื่อมลงเป็น O(n)

ให้สังเกตรูปแบบความล้มเหลวเหล่านี้:

1. ฟังก์ชันแฮชอ่อนแอหรือมีอคติ — ทำให้กุญแจกระจุกตัวไม่ว่าตารางจะใหญ่แค่ไหน (ตัวอย่างไล่ทีละขั้นที่ 1)
2. ปล่อยให้ load factor โตแบบไม่มีการควบคุม — การ implement (หรือของที่คุณเขียนเอง) ที่ไม่เคยขยายขนาดจะเห็นโซ่ยาวขึ้นเป็นเส้นตรงตาม n
3. กุญแจที่ถูกควบคุมโดยผู้โจมตี — hash flooding ตามที่อธิบายไว้ข้างต้น
4. สัญญา __eq__/__hash__ ที่ผิดพลาดบนอ็อบเจ็กต์ที่กำหนดเอง — Python กำหนดว่าถ้า a == b แล้ว hash(a) == hash(b) ต้องเป็นจริงด้วย ถ้าคุณ override __eq__ บนคลาสหนึ่งแต่ลืม __hash__ อ็อบเจ็กต์ที่ดูเหมือนเท่ากันอาจตกไปอยู่คนละช่อง (หรือ Python จะทำให้คลาสนั้น unhashable ไปเลย ซึ่งจริง ๆ แล้วเป็นความล้มเหลวที่ ปลอดภัยกว่า)
5. กุญแจที่เปลี่ยนแปลงได้ (mutable) — นี่คือเหตุผลที่ Python ไม่ยอมให้ใช้ list เป็นกุญแจของ dict หรือสมาชิกของ set: ถ้าคุณเปลี่ยนค่ามันหลังจากแทรกไปแล้ว แฮชของมันจะเปลี่ยนไป และตารางจะมองหามันผิดช่องตลอดไป มีแต่ชนิดที่ ไม่เปลี่ยนแปลง (immutable) เท่านั้น (str, int, tuple ของสมาชิกที่ไม่เปลี่ยนแปลง, frozenset) ที่ hashable โดยค่าเริ่มต้น

ตัวอย่างไล่ทีละขั้นที่ 4 — กรณีเลวร้ายสุดจากผู้ประสงค์ร้าย

สมมติ (เชิงสมมติฐาน) ว่าเซอร์วิสหนึ่งแฮช request ID ที่เข้ามาด้วยฟังก์ชันที่บกพร่อง h(k) = len(k) % 8 — มันดูแค่ ความยาว ของสตริง ไม่สนใจเนื้อหาเลย ผู้โจมตีส่ง ID "aaaaaaaa", "bbbbbbbb", "cccccccc", … — ทั้งหมดยาว 8 ตัวอักษร — และทุกตัวตกไปช่องเดียวกันหมด:

ช่อง 0 (len % 8 == 0): [aaaaaaaa] -> [bbbbbbbb] -> [cccccccc] -> ... (n ตัว โซ่เดียวยาวมาก)

ทุกการค้นหาต้องไล่ทั้งโซ่: O(n) ต่อคำขอหนึ่งครั้ง เซิร์ฟเวอร์ที่คาดหวังการจัดการคำขอแบบ O(1) ถูกผลักดันไปเป็น O(n) ต่อคำขอ รวมเป็น O(n²) สำหรับ n คำขอ — นี่คือลักษณะที่แท้จริงของการโจมตีปฏิเสธการให้บริการแบบ hash flooding ทางแก้ไม่เคยเป็น “เพิ่มช่องให้มากขึ้น” — แต่เป็น “ใช้ฟังก์ชันแฮชที่ผสม เนื้อหา ของกุญแจจริง ๆ ไม่ใช่คุณสมบัติที่แปลงมาจากมัน”

ใน Python

ใน Python ทั้ง dict, set, Counter, และ defaultdict ล้วนถูกสร้างจากตารางแฮชตัวเดียวกันเบื้องหลัง

# dict — คู่กุญแจ–ค่า
ages = {}
ages["สมชาย"] = 25        # set: O(1) โดยเฉลี่ย
ages["สมหญิง"] = 30
print(ages["สมชาย"])      # get: O(1) โดยเฉลี่ย -> 25
print("สมชาย" in ages)    # ตรวจสมาชิก: O(1) -> True

# set — ตรวจการเป็นสมาชิกอย่างรวดเร็ว
seen = set()
seen.add("a")
seen.add("b")
print("a" in seen)        # O(1) -> True
print("z" in seen)        # O(1) -> False

เทียบกับ list ที่การตรวจ x in my_list ต้องไล่ทีละตัวเป็น O(n) — set จึงเร็วกว่ามากเมื่อข้อมูลเยอะ

collections.Counter (คลาสลูกของ dict) นับสิ่งต่าง ๆ ได้โดยไม่ต้องเขียนตรรกะเก็บตัวนับเอง:

from collections import Counter

counts = Counter(["a", "b", "a", "c", "a", "b"])
print(counts)                  # Counter({'a': 3, 'b': 2, 'c': 1})
print(counts.most_common(1))   # [('a', 3)]

collections.defaultdict ตัดขั้นตอน “เช็คก่อนว่ากุญแจมีอยู่ไหม” ออกไป ซึ่งเป็นจุดที่มือใหม่มักแอบเผลอสร้าง O(n) การไล่ list หรือ KeyError กลับมาโดยไม่รู้ตัว:

from collections import defaultdict

groups = defaultdict(list)          # กุญแจที่ไม่มี -> เริ่มต้นเป็น []
groups["ผลไม้"].append("แอปเปิล")     # ไม่มี KeyError ไม่ต้องเช็ค init เอง
groups["ผลไม้"].append("กล้วย")
groups["ผัก"].append("แครอท")
print(dict(groups))
# {'ผลไม้': ['แอปเปิล', 'กล้วย'], 'ผัก': ['แครอท']}

ข้อสังเกตเชิงปฏิบัติที่ควรรู้ไว้:

• ตั้งแต่ Python 3.7 เป็นต้นมา dict รักษา ลำดับการแทรก (insertion order) ไว้เป็นการรับประกันของภาษา (ผลพลอยได้จาก implementation ของ dict แบบกระชับ) — แต่นี่ไม่เหมือนกับการ เรียงลำดับ (sorted) และไม่ได้เปลี่ยนความซับซ้อน O(1) โดยเฉลี่ยแต่อย่างใด
• มีแต่อ็อบเจ็กต์ที่ hashable (ซึ่งก็คือไม่เปลี่ยนแปลงได้อย่างมีประสิทธิผล) เท่านั้นที่เป็นกุญแจของ dict หรือสมาชิกของ set ได้: str, int, float, tuple (ของสมาชิกที่ hashable), frozenset ส่วน list และ dict ถูกออกแบบให้ unhashable — ด้วยเหตุผลเรื่องความเปลี่ยนแปลงได้จากหัวข้อ “เมื่อการแฮชเสื่อมลง” ข้างต้น
• คลาสที่กำหนดเองเป็น hashable โดยค่าเริ่มต้น (แฮชตาม identity) แต่ถ้าคุณกำหนด __eq__ เอง คุณต้องกำหนด __hash__ ที่สอดคล้องกันด้วย ไม่งั้น Python จะทำให้คลาสนั้น unhashable เพื่อป้องกันไม่ให้คุณทำลายสัญญาของ dict/set โดยไม่รู้ตัว

ชัยชนะ O(n²) → O(n)

ลองนับว่าในรายการตัวเลขมีตัวซ้ำกี่ตัว (หาตัวซ้ำ) วิธีตรงไปตรงมาคือเทียบทุกคู่ — ช้ามาก

# วิธีไร้เดียงสา: ลูปซ้อนลูป -> O(n^2)
def has_duplicate_slow(nums):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False

ถ้า nums มี 1,000,000 ตัว วิธีนี้ต้องเทียบประมาณ 5 แสนล้านครั้ง — ช้าเกินใช้งานจริง

# วิธีใช้ตารางแฮช: เดินรอบเดียว -> O(n)
def has_duplicate_fast(nums):
    seen = set()
    for x in nums:
        if x in seen:        # ตรวจสมาชิก O(1)
            return True
        seen.add(x)          # เพิ่ม O(1)
    return False

# นับความถี่ด้วย dict / Counter
from collections import Counter
counts = Counter(nums)       # O(n) เดินรอบเดียว

ความต่างอยู่ตรงไหน? วิธีแรกถามว่า “ตัวนี้ซ้ำกับตัวไหนบ้าง” แล้วต้องไล่ดูทุกตัว วิธีที่สองเปลี่ยนคำถามเป็น “ตัวนี้เคยเห็นแล้วหรือยัง” ซึ่ง set ตอบได้ใน O(1) เราจึงแลก “หน่วยความจำเพิ่มเล็กน้อย” กับ “ความเร็วที่เพิ่มมหาศาล” การเปลี่ยนกรอบคำถามแบบ “แฮชแทนการไล่หา” นี้คือวิธีที่พบบ่อยที่สุดวิธีเดียวที่ทำให้โซลูชันไร้เดียงสาแบบ O(n²) กลายเป็น O(n) — ให้สังเกตทุกครั้งที่เห็นลูปซ้อนอยู่ในลูปเพียงเพื่อตรวจสมาชิกหรือหาค่าที่ตรงกัน

ความซับซ้อน

การดำเนินการ	เฉลี่ย	กรณีเลวร้ายสุด
get (ดึงค่า)	O(1)	O(n)
set (เก็บค่า)	O(1)	O(n)
delete (ลบ)	O(1)	O(n)
contains (ตรวจสมาชิก)	O(1)	O(n)

กรณีเลวร้ายสุดเกิดเมื่อกุญแจชนกันหมดในช่องเดียว ซึ่งแทบไม่เกิดถ้าฟังก์ชันแฮชดีและคุม load factor ไว้ ดังนั้นในทางปฏิบัติเราถือว่าเป็น O(1) แต่อย่างที่ตัวอย่างไล่ทีละขั้นที่ 4 แสดงให้เห็น “แทบไม่เกิด” นั้นตั้งอยู่บนสมมติฐานว่าฟังก์ชันแฮชไม่บกพร่องและอินพุตไม่ได้ถูกออกแบบมาเพื่อโจมตี

โจทย์จากโลกจริง

การนับความถี่ของคำในเอกสารขนาดใหญ่ เช่น หาว่าคำใดปรากฏบ่อยที่สุดในหนังสือ 500 หน้า

เราจำลองด้วย dict ที่ใช้ “คำ” เป็นกุญแจ และ “จำนวนครั้ง” เป็นค่า:

from collections import Counter

def top_words(text, k=10):
    words = text.lower().split()
    counts = Counter(words)        # O(n) เดินทุกคำรอบเดียว
    return counts.most_common(k)

ทำไมใช้ dict? เพราะเราต้องอัปเดตจำนวนของคำเดิมซ้ำ ๆ จำนวนมาก ถ้าใช้ list แล้วค้นหาว่า “คำนี้เคยนับหรือยัง” จะเป็น O(n) ต่อคำ รวมเป็น O(n²) แต่ dict ทำให้แต่ละการอัปเดตเป็น O(1) รวมทั้งงานเป็น O(n) — เร็วพอที่จะประมวลผลเอกสารหลายล้านคำได้ในพริบตา

แบบฝึกหัด

1. Two Sum — ให้ลิสต์ nums และค่าเป้าหมาย target จงหาดัชนีของเลขสองตัวที่บวกกันได้ target (ใช้ตารางแฮชให้เป็น O(n))

เฉลย

def two_sum(nums, target):
    seen = {}                       # ค่า -> ดัชนี
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:            # O(1)
            return [seen[need], i]
        seen[x] = i
    return None
# two_sum([2, 7, 11, 15], 9) -> [0, 1]

แทนการเทียบทุกคู่ O(n²) เราจำตัวที่ผ่านมาแล้วไว้ใน dict แล้วถามว่า “ต้องการอีกตัวคือ target - x เคยเห็นไหม” ใน O(1)

2. ตัวอักษรแรกที่ไม่ซ้ำ (First Non-Repeating Character) — ให้สตริง จงคืนตัวอักษรตัวแรกที่ปรากฏเพียงครั้งเดียว

เฉลย

from collections import Counter

def first_unique(s):
    counts = Counter(s)             # O(n)
    for ch in s:                    # O(n)
        if counts[ch] == 1:
            return ch
    return None
# first_unique("aabbcdd") -> "c"

นับความถี่ทุกตัวก่อนด้วย dict แล้วเดินตามลำดับเดิมเพื่อหาตัวแรกที่ความถี่เป็น 1 รวมเป็น O(n)

3. จัดกลุ่มแอนนาแกรม (Group Anagrams) — ให้ลิสต์คำ จงจัดกลุ่มคำที่เป็นแอนนาแกรมของกันและกัน เช่น ["eat","tea","tan","ate","nat"]

เฉลย

from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        key = "".join(sorted(w))    # คำที่เป็นแอนนาแกรมจะมีกุญแจเหมือนกัน
        groups[key].append(w)
    return list(groups.values())
# -> [["eat","tea","ate"], ["tan","nat"]]

ใช้ “ตัวอักษรที่เรียงแล้ว” เป็นกุญแจของ dict คำที่เป็นแอนนาแกรมจะตกลงช่องเดียวกันโดยอัตโนมัติ

4. หาตัวที่หายไป — ลิสต์ควรมีเลข 1..n แต่ขาดไปหนึ่งตัว จงหาตัวที่หาย โดยใช้ set ให้เป็น O(n)

เฉลย

def find_missing(nums, n):
    present = set(nums)             # O(n)
    for i in range(1, n + 1):
        if i not in present:        # O(1)
            return i
    return None

5. ทายช่อง (Predict the Bucket) — ใช้ฟังก์ชันแฮชของเล่นจากตัวอย่างไล่ทีละขั้นที่ 1 (h(s) = ผลรวมของ ord(c) ของทุกตัวอักษร) กับตารางขนาด 8 คำว่า "ant" จะตกลงช่องไหน? มันจะชนกับกุญแจที่มีอยู่แล้วในตารางนั้นไหม (cat, dog, bird, fish, lion)?

เฉลย

s = "ant"
total = ord("a") + ord("n") + ord("t")   # 97 + 110 + 116 = 323
bucket = total % 8                        # 323 % 8 = 3

"ant" แฮชไปยังช่อง 3 ซึ่งว่างอยู่ในตารางเดิม — ครั้งนี้ไม่มีการชนกัน (ลองดู "tan" ด้วย: ตัวอักษรเดียวกัน ผลรวมเดียวกัน ช่องเดียวกับ "ant" — เป็นเครื่องเตือนใจว่าฟังก์ชันแฮชของเล่นนี้ไม่สนใจ ลำดับ ตัวอักษรเลย ซึ่งจะเป็นสัญญาณอันตรายสำหรับฟังก์ชันแฮชจริง)

6. จับผิดบัค (Spot the Bug) — เพื่อนร่วมทีมเขียนโค้ดนี้เพื่อกำจัดรายการ user ID ที่ซ้ำกันในสตรีมข้อมูล โดยรักษาลำดับเดิมไว้:

def dedupe(ids):
    result = []
    for uid in ids:
        if uid not in result:      # บัคอยู่ตรงนี้
            result.append(uid)
    return result

โค้ดนี้ให้ผลลัพธ์ถูกต้อง แต่มีอะไรผิดพลาด และคุณจะแก้อย่างไรโดยยังรักษาลำดับไว้?

เฉลย

uid not in result ตรวจสมาชิกใน list ซึ่งเป็น O(n) — ทำให้ทั้งฟังก์ชันกลายเป็น O(n²) แก้โดยติดตามการเป็นสมาชิกด้วย set คู่ไปกับ list ที่รักษาลำดับ:

def dedupe(ids):
    result = []
    seen = set()
    for uid in ids:
        if uid not in seen:      # O(1)
            seen.add(uid)        # O(1)
            result.append(uid)
    return result

ตอนนี้การตรวจสมาชิกเป็น O(1) และทั้งฟังก์ชันเป็น O(n) (ใน Python 3.7+ dict.fromkeys(ids) เป็นวิธีที่สั้นกว่าในการกำจัดค่าซ้ำโดยรักษาลำดับ เพราะ dict รักษาลำดับการแทรกไว้)

7. เลือกโครงสร้างที่ถูกต้อง (Pick the Right Structure) — คุณกำลังสร้างเว็บครอว์เลอร์ที่ต้องไม่เข้าเว็บ URL เดิมซ้ำสองครั้ง และไม่สนใจลำดับที่เข้าเยี่ยมชม URL เลย ควรใช้โครงสร้างไหน: list, set, หรือ dict? แล้วถ้าต้อง จำเพิ่มด้วย ว่าแต่ละ URL คืน HTTP status code อะไรกลับมาล่ะ?

เฉลย

สำหรับ “ไม่เข้าซ้ำสองครั้ง” โดยไม่สนใจลำดับ: ใช้ set ของ URL ที่เยี่ยมชมแล้ว — ตรวจสมาชิกที่ O(1) ก่อนครอว์ลิงก์ใหม่แต่ละอัน เทียบกับ O(n) ถ้าใช้ list

ถ้าต้องเก็บ status code ต่อ URL ด้วย ให้อัปเกรดเป็น dict ({url: status_code}) — มันให้ทั้งการตรวจสมาชิกแบบ O(1) (url in visited_dict) และ ที่เก็บค่าที่เกี่ยวข้อง โดยไม่ต้องใช้สองโครงสร้างแยกกัน

8. Load Factor และการขยายขนาด — ตารางแฮชที่มี 16 ช่อง ตอนนี้มีข้อมูล 11 รายการ และ implementation ของมันจะขยายขนาด (เพิ่มจำนวนช่องเป็นสองเท่า) เมื่อ load factor จะเกิน 0.75 ถ้าคุณแทรกอีก 2 รายการ มันจะขยายขนาดไหม? load factor ทันทีหลังขยายขนาด (ถ้ามี) คือเท่าไร?

เฉลย

load factor ปัจจุบัน: 11 / 16 = 0.6875 หลังแทรกอีกหนึ่งรายการ: 12 / 16 = 0.75 — พอดีที่เกณฑ์ หลังแทรกรายการที่สอง (13 รายการ ยังคง 16 ช่องก่อนขยาย 13 / 16 = 0.8125) แน่นอนว่าข้าม 0.75 ไปแล้ว จึงเกิดการขยายขนาดเป็น 32 ช่อง: load factor ใหม่ = 13 / 32 = 0.40625

วิพากษ์โค้ดจากปัญญาประดิษฐ์

คุณขอให้ AI เขียนฟังก์ชันหา “อีเมลที่ซ้ำ” ในรายชื่อผู้ใช้ AI ตอบกลับมาดังนี้:

def find_duplicate_emails(users):
    duplicates = []
    for i in range(len(users)):
        for j in range(i + 1, len(users)):
            if users[i]["email"] == users[j]["email"]:
                if users[i]["email"] not in duplicates:
                    duplicates.append(users[i]["email"])
    return duplicates

ลองตัดสิน: โค้ดนี้ให้ผลถูกต้อง แต่มันมีลูปซ้อนลูปเป็น O(n²) และยังมี not in duplicates (ซึ่งบน list ก็เป็น O(n) อีก) ถ้ามีผู้ใช้ 1 ล้านคนจะช้าจนใช้ไม่ได้ จงเขียนใหม่ด้วย set ให้เป็น O(n)

เฉลย

def find_duplicate_emails(users):
    seen = set()
    duplicates = set()
    for u in users:
        email = u["email"]
        if email in seen:          # O(1)
            duplicates.add(email)  # O(1)
        else:
            seen.add(email)
    return list(duplicates)

เดินรอบเดียว O(n) ใช้ seen จำอีเมลที่เคยพบ และ duplicates เก็บตัวที่พบซ้ำ ทุกการตรวจและเพิ่มเป็น O(1) — เปลี่ยน O(n²) ให้เป็น O(n)

🎮 เกมเดฟ: Spatial Hash สำหรับการตรวจจับการชนกัน

ตารางแฮชคือวิธีที่เอนจินเกมจริงหลีกเลี่ยงการเช็คสไปรต์ทุกตัวกับสไปรต์ทุกตัวเพื่อหาการชนกัน แทนที่จะแฮชสตริงหรือตัวเลข คุณแฮช ตำแหน่ง: จัดสไปรต์เข้าช่องตามเซลล์กริดที่มันอยู่ ทำให้การตรวจการชนกันต้องดูแค่สไปรต์ไม่กี่ตัวที่อยู่เซลล์เดียวกัน (หรือเซลล์ข้างเคียง) กลเม็ด “แฮชกุญแจตรงไปยังช่องของมัน” แบบเดียวกันนี้ยังอยู่เบื้องหลังการค้นหาเอนทิตีด้วย id (entities[entity_id]) และการค้นหาชนิดไทล์ (tile_types[tile_id]) — ไม่มีเอนจินไหนอยากไล่สแกนลิสต์แค่เพื่อตอบว่า “อะไรอยู่ที่ id นี้”

ตัวอย่างไล่ทีละขั้น — จากการตรวจชนแบบ O(n²) สู่ spatial hash

from collections import defaultdict

CELL_SIZE = 64  # ประมาณความกว้างของสไปรต์หนึ่งตัว

class SpatialHash:
    """จัดสไปรต์เข้าช่องตามเซลล์กริด เพื่อให้ 'มีอะไรอยู่ใกล้ ๆ' ถามได้ถูก"""
    def __init__(self, cell_size: int = CELL_SIZE):
        self.cell_size = cell_size
        self.buckets = defaultdict(list)      # (cx, cy) -> [สไปรต์]

    def _cell(self, x, y):
        return (int(x // self.cell_size), int(y // self.cell_size))

    def insert(self, sprite):
        self.buckets[self._cell(sprite.x, sprite.y)].append(sprite)

    def nearby(self, sprite):
        cx, cy = self._cell(sprite.x, sprite.y)
        found = []
        for dx in (-1, 0, 1):
            for dy in (-1, 0, 1):
                found.extend(self.buckets.get((cx + dx, cy + dy), []))
        return found

# วิธีไร้เดียงสา: เช็คสไปรต์ทุกตัวกับทุกตัว -> O(n^2)
def collisions_naive(sprites):
    pairs = []
    for i in range(len(sprites)):
        for j in range(i + 1, len(sprites)):
            if sprites[i].overlaps(sprites[j]):
                pairs.append((sprites[i], sprites[j]))
    return pairs

# Spatial hash: เช็คเฉพาะสไปรต์ที่อยู่เซลล์เดียวกัน (หรือข้างเคียง) -> ~O(n)
def collisions_hashed(sprites, cell_size=CELL_SIZE):
    grid = SpatialHash(cell_size)
    for s in sprites:
        grid.insert(s)
    pairs = []
    for s in sprites:
        for other in grid.nearby(s):
            if other is not s and s.overlaps(other):
                pairs.append((s, other))
    return pairs

ถ้ามีสไปรต์ 500 ตัวบนหน้าจอ collisions_naive จะรันการเช็คซ้อนทับประมาณ 125,000 ครั้งในทุก ๆ เฟรม ส่วน collisions_hashed จะจัดสไปรต์ทั้ง 500 ตัวเข้าช่องก่อน (O(n)) แล้วแต่ละสไปรต์เช็คแค่สไปรต์ในบริเวณเซลล์ข้างเคียง 3×3 ของตัวเอง — ถ้าสไปรต์กระจายตัวพอสมควร นั่นคือจำนวนการเช็คที่น้อยและเกือบคงที่ต่อสไปรต์หนึ่งตัว ทำให้ทั้งรอบเป็น ~O(n) นี่คือแนวคิด hash(key) % table_size เดียวกับที่เจอไปแล้วในบทเรียนนี้ ต่างกันแค่ key ตอนนี้คือตำแหน่ง ไม่ใช่สตริง

รูป: ตำแหน่งของสไปรต์ถูกแฮชไปยังเซลล์ของกริด และช่องของเซลล์นั้นเก็บเฉพาะสไปรต์ที่อยู่ใกล้กัน — ไม่ต้องไล่สแกนทั้งโลกเกม

กลเม็ด “แฮชแล้วเข้าช่อง” แบบเดียวกันนี้ยังโผล่มาอีกสองที่ในเอนจินทั่วไป คราวนี้แฮช id ธรรมดาแทนตำแหน่ง:

entities = {}                        # entity_id -> อ็อบเจ็กต์ Entity
entities[42] = Entity("goblin")
entities[42].hp -= 10                # O(1) -- ไม่ต้องไล่ลิสต์เอนทิตี

TILE_TYPES = {0: "grass", 1: "wall", 2: "water", 3: "lava"}
def tile_at(grid, tx, ty):
    return TILE_TYPES[grid[ty][tx]]  # ค้นหาด้วย dict O(1) ไม่ใช่การไล่หาทีละตัว

ทั้งสองอย่างเป็น dict ธรรมดา แต่ผลตอบแทนเหมือนกับ spatial hash ข้างบนทุกประการ: id หรือรหัสไทล์แฮชตรงไปยังช่องของมันเลย แทนที่จะบังคับให้ไล่สแกนทีละตัวผ่านเอนทิตีหรือชนิดไทล์ทุกตัวในเกม ลองเล่น <algo-hash size="8"> ด้านล่างด้วยกุญแจของคุณเอง แล้วดูว่าแต่ละตัวตกไปช่องไหน

แบบฝึกหัด

G1. แฮชตำแหน่ง — สไปรต์ตัวหนึ่งอยู่ที่ (150, 230) ถ้าใช้ CELL_SIZE = 64 มันแฮชไปยังเซลล์ (ช่อง) ไหน?

เฉลย

cx = 150 // 64   # 2
cy = 230 // 64   # 3
# cell = (2, 3)

G2. การชนกันในช่องเดียว — สไปรต์ห้าตัวอยู่ที่ (10,10), (95,20), (150,150), (205,190), (300,300) ถ้าใช้ cell_size = 100 ช่องไหนมีสไปรต์มากกว่าหนึ่งตัว และสไปรต์คู่ไหนที่กลายเป็นตัวเก็งสำหรับการเช็คซ้อนทับจริง?

เฉลย

(10,10)   -> (0,0)
(95,20)   -> (0,0)   # ช่องเดียวกับ (10,10)
(150,150) -> (1,1)
(205,190) -> (2,1)
(300,300) -> (3,3)

ช่อง (0,0) มีสไปรต์สองตัว — (10,10) กับ (95,20) — จึงมีแค่คู่นี้ที่ต้องเช็คซ้อนทับจริง ๆ ส่วนสไปรต์ตัวอื่นอยู่คนเดียวในช่องของตัวเอง จึงข้ามการเช็คไปได้เลย

G3. การเลือกขนาดเซลล์ — สไปรต์ของคุณทุกตัวมีขนาด 32×32 พิกเซล เพื่อนร่วมทีมคนหนึ่งเสนอ CELL_SIZE = 8 อีกคนเสนอ CELL_SIZE = 2000 แต่ละแบบผิดพลาดตรงไหน แล้วคุณจะเลือกขนาดเท่าไร?

เฉลย

CELL_SIZE = 8 เล็กกว่าสไปรต์มาก: สไปรต์ขนาด 32×32 ตัวเดียวจะครอบคลุมประมาณ 4×4 = 16 เซลล์ คุณจึงต้องแทรก (หรือเช็ค) มันในหลายช่องแค่เพื่อรู้ว่ามันอยู่ตรงไหน — กลายเป็นภาระบัญชีที่เพิ่มขึ้นโดยไม่ได้อะไร ส่วน CELL_SIZE = 2000 ใหญ่กว่าพื้นที่เล่นทั้งหมดที่สไปรต์จะชนกันได้จริง แทบทุกสไปรต์จะตกไปช่องเดียวกัน แล้ว nearby() ก็เสื่อมกลับไปเป็นการไล่สแกนเกือบทั้งหมด — รูปแบบความล้มเหลวเดียวกันกับฟังก์ชันแฮชแย่ ๆ ที่ทำให้กุญแจกระจุกตัว กฎง่าย ๆ คือเลือกขนาดเซลล์ให้ใกล้เคียง (หรือเป็นทวีคูณเล็ก ๆ ของ) ขนาดสไปรต์ที่ใหญ่ที่สุด เพื่อให้แต่ละสไปรต์แตะแค่ 1–4 เซลล์ และแต่ละช่องมีสไปรต์แค่หยิบมือเดียว

G4. จับผิดบัค — nearby() ของเพื่อนร่วมทีมเช็คแค่เซลล์ของสไปรต์เอง:

def nearby(self, sprite):
    return self.buckets.get(self._cell(sprite.x, sprite.y), [])

สไปรต์สองตัวซ้อนทับกันชัดเจนบนหน้าจอ แต่ฟังก์ชันนี้ไม่เคยรายงานว่าเป็นเพื่อนบ้านกันเลย ผิดตรงไหน แล้วเวอร์ชัน 3×3 ข้างบนแก้อย่างไร?

เฉลย

สไปรต์ที่อยู่ใกล้ขอบเซลล์ของมันสามารถซ้อนทับกับสไปรต์ที่แฮชไปยังเซลล์ ข้างเคียง ได้ — กริดเป็นการแบ่งพื้นที่ตามอำเภอใจ ไม่ใช่ขอบเขตที่โลกเกมยึดถือจริง การเช็คแค่ self._cell(...) จึงพลาดทุกการชนที่คร่อมเส้นแบ่งเซลล์ ทางแก้คือเช็คเซลล์ข้างเคียงเต็ม 3×3 (dx, dy ใน {-1,0,1}) แบบที่ SpatialHash.nearby() ข้างบนทำ เพื่อให้สไปรต์ถูกเทียบกับทุกอย่างในเซลล์ของตัวเอง และ แปดเซลล์ที่ล้อมรอบมัน

โจทย์ท้าทาย

โจทย์ท้าทาย ๑ — ค้นหาเพื่อนบ้านที่ใกล้ที่สุด (Nearest-neighbour query) ให้ SpatialHash และจุดค้นหาหนึ่งจุด (เช่น “ไอเทมที่ใกล้ผู้เล่นที่สุดอยู่ตรงไหน?”) จงหาสไปรต์ที่ใกล้ที่สุด โดย ไม่ ไล่สแกนสไปรต์ทุกตัวในเกม

แนวทาง

เริ่มที่เซลล์ของจุดค้นหาเองแล้วเช็คสิ่งที่อยู่ในนั้น ถ้าว่างเปล่า (หรือต้องการการรับประกันความถูกต้อง) ให้ขยายออกไปทีละวง: เช็คบริเวณ 3×3 ก่อน แล้ว 5×5 แล้ว 7×7 หยุดทันทีที่เจอตัวเก็งตัวหนึ่ง และ ได้ขยายไปอีกหนึ่งวงเกินกว่าตัวนั้นแล้ว (เพราะสไปรต์ที่ใกล้กว่าอาจแอบอยู่คนละฝั่งเส้นแบ่งเซลล์ในวงถัดไป) ติดตามตัวเก็งที่ดีที่สุด (ใกล้ที่สุด) ที่เจอไว้ และขยายต่อเฉพาะตอนที่ยังมีโอกาสทางคณิตศาสตร์ที่จะเจอตัวที่ใกล้กว่า เมื่อเทียบกับระยะของวงนั้น ๆ วิธีนี้เปลี่ยนการค้นหาเพื่อนบ้านที่ใกล้ที่สุดจาก O(n) ให้เหลือประมาณ O(1) เมื่อสไปรต์กระจายตัวสม่ำเสมอ แลกกับภาระบัญชีกรณีขอบเขตเล็กน้อย

โจทย์ท้าทาย ๒ — Hash Flooding จากสไปรต์ที่กระจุกตัว เวทมนตร์ในบอสไฟท์ดึงมอนสเตอร์ 300 ตัวเข้ามารวมกันในไทล์เดียวขนาด 64×64 ช่องนั้นตอนนี้มี 300 รายการ และทุกการเรียก nearby() ใกล้ไทล์นั้นก็กลับไปมีต้นทุน O(n) อีกครั้ง — รูปแบบความล้มเหลวเดียวกันกับการป้อนอินพุตที่ผู้ประสงค์ร้ายออกแบบมาให้ชนกันกับฟังก์ชันแฮชแย่ ๆ เพียงแต่คราวนี้ “ผู้ประสงค์ร้าย” คือดีไซน์เกมของคุณเอง

แนวทาง

ทางแก้ไม่เคยเป็น “เพิ่มช่องให้มากขึ้นทั่วทั้งกริด” (นั่นคือสัญชาตญาณเรื่องการขยายขนาดจากก่อนหน้านี้ในบทเรียน และมันไม่ช่วยเมื่อ ภาระ กระจุกตัวอยู่จุดเดียว) แต่ให้ตรวจจับช่องที่มีความยาวเกินเกณฑ์ที่กำหนดแล้วจัดการเป็นกรณีพิเศษ — ไม่ว่าจะแบ่งเซลล์ร้อนนั้นเป็นกริดย่อยที่ละเอียดขึ้นตามความต้องการ (spatial hash ตัวจิ๋วซ้อนอยู่ในช่องที่แน่น คล้ายแนวคิด quadtree) หรือส่งสไปรต์ในช่องที่แน่นเกินไปผ่านเส้นทางตรวจชนแบบ “ฝูงชน” ที่ถูกกว่า (เช่น มองกลุ่มก้อนนั้นเป็นวงกลมวงเดียวรอบจุดศูนย์กลางแทนการเช็คทีละคู่) บทเรียนทั่วไปนี้ยกมาจากตารางแฮชธรรมดาได้ตรง ๆ: ฟังก์ชันแฮชที่สม่ำเสมอตั้งอยู่บนสมมติฐานว่ากุญแจกระจายตัวสม่ำเสมอ และอินพุตที่กระจุกตัว — ไม่ว่าจะมาจากเจตนาร้ายหรือแค่บอสอารีน่ายอดนิยม — ต้องมีแผนที่มากกว่าแค่ “ทำให้ตาราง (หรือกริด) ใหญ่ขึ้น” เสมอ

เจาะลึกเพิ่มเติม

• MIT 6.006 — Introduction to Algorithms, บทเรียน “Hashing with Chaining” และ “Table Doubling, Karp-Rabin” (เผยแพร่ฟรีบน MIT OpenCourseWare)
• Stanford CS161 — Design and Analysis of Algorithms, หัวข้อ Hashing และ Universal Hashing
• CLRS — Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein), บทที่ 11 “Hash Tables” — การอธิบายเชิงทฤษฎีอย่างเป็นทางการของ simple uniform hashing การวิเคราะห์การต่อโซ่ และ universal hashing ที่หัวข้อ “เฉลี่ย vs. เลวร้ายสุด” ของบทเรียนนี้ต่อยอดมาจาก
• Sedgewick & Wayne — Algorithms, 4th ed., หัวข้อ 3.4 “Hash Tables” — implementation ที่สะอาดของทั้ง separate chaining และ linear probing พร้อมการอธิบายเรื่องการขยายขนาดอาเรย์ควบคู่กับตารางแฮชที่ดีเป็นพิเศษ
• Weiss — Data Structures and Algorithm Analysis บทเรื่องการแฮช — เปรียบเทียบกลยุทธ์แก้การชนกัน (chaining, linear/quadratic probing, double hashing) เคียงข้างกันอย่างชัดเจน พร้อมการอนุมานความซับซ้อนแบบละเอียด
• Skiena — The Algorithm Design Manual, 3rd ed. — บทเรื่อง “Dictionaries” ที่เล่าเกร็ดประสบการณ์จริง ดีสำหรับสัญชาตญาณ “เมื่อไรควรใช้อะไร” และเรื่องเล่าจริงเกี่ยวกับความล้มเหลวของตารางแฮชในทางปฏิบัติ (รวมถึงปัญหาแบบ hash flooding)
• เอกสารของ Python และซอร์สโค้ด CPython — บันทึกการ implement dict (objects/dictobject.c) และบทความ “The Mighty Dictionary” ที่อธิบาย open addressing ที่ Python ใช้จริง