ตารางแฮช — การทำงานของแฮชและการจัดการการชนกัน

ตารางแฮชเก็บคู่คีย์-ค่าโดยใช้การแฮชเพื่อแปลงแต่ละคีย์ให้เป็นดัชนีของอาร์เรย์ วิธีนี้ทำให้ตารางกระโดดไปใกล้ตำแหน่งที่ถูกต้องได้เลย แทนที่จะต้องไล่ดูข้อมูลที่เก็บไว้ทีละรายการ

นั่นจึงเป็นเหตุผลว่าทำไมตารางแฮชมักมีเวลาใกล้เคียง $O(1)$ สำหรับการค้นหา การแทรก และการลบบนกรณีเฉลี่ย แต่มีเงื่อนไขสำคัญคือ ฟังก์ชันแฮชต้องกระจายคีย์ได้ดีพอสมควร และตารางต้องมีกฎสำหรับจัดการการชนกันด้วย

ตารางแฮชทำอะไร

ตารางแฮชเก็บคู่คีย์-ค่า เช่น "name" -> "Ada" หรือ 42 -> "blue" โดยมีส่วนหลักอยู่ 2 ส่วน:

• อาร์เรย์ของช่องหรือบักเก็ต
• ฟังก์ชันแฮชที่แมปแต่ละคีย์ไปยังหนึ่งในช่องเหล่านั้น

ถ้าอาร์เรย์มี $m$ ช่อง คุณอาจมองว่าฟังก์ชันแฮชสร้างดัชนีตั้งแต่ $0$ ถึง $m-1$

สำหรับตัวอย่างจำนวนเต็มขนาดเล็ก กฎอาจเป็น

$$h(k) = k \bmod 8$$

ดังนั้นคีย์ $10$ จะไปที่ช่อง $2$ เพราะ $10 \bmod 8 = 2$

ฟังก์ชันแฮชจริงมักถูกออกแบบอย่างระมัดระวังกว่านี้ โดยเฉพาะสำหรับสตริงและชุดข้อมูลขนาดใหญ่ แต่แนวคิดหลักยังเหมือนเดิม คือคำนวณดัชนีอย่างรวดเร็ว แล้วตรวจสอบรายการที่เก็บอยู่ตรงนั้น

ทำไมการชนกันของแฮชจึงหลีกเลี่ยงไม่ได้

การชนกันเกิดขึ้นเมื่อคีย์ที่ต่างกันสองตัวถูกแมปไปยังช่องเดียวกัน

นี่เป็นเรื่องปกติ เพราะโดยทั่วไปตารางมีจำนวนช่องน้อยกว่าจำนวนคีย์ที่เป็นไปได้ทั้งหมด เมื่อใช้

$$h(k) = k \bmod 8$$

คีย์ $10$, $18$ และ $26$ จะถูกแมปไปที่ช่อง $2$ ทั้งหมด ดังนั้นแม้ฟังก์ชันจะทำงานตรงตามที่กำหนด ตารางก็ยังต้องแก้ปัญหาความขัดแย้งนี้อยู่ดี

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

ตัวอย่างทีละขั้น: หนึ่งตาราง หนึ่งการชนกัน

สมมติว่าตารางมี $8$ ช่อง และใช้

$$h(k) = k \bmod 8$$

แทรกคีย์ $10$, $18$ และ $7$

ก่อนอื่น $10$ ไปที่ช่อง $2$ เพราะ $10 \bmod 8 = 2$

ถัดมา $18$ ก็แฮชไปที่ช่อง $2$ เช่นกัน จึงเกิดการชนกัน

จากนั้น $7$ ไปที่ช่อง $7$ ดังนั้นการแทรกครั้งนี้จึงไม่ชนกับใคร

รูปแบบที่สำคัญจะเหมือนเดิมเสมอ:

1. แฮชคีย์
2. ไปยังช่องที่ได้จากการแฮช
3. ถ้ามีคีย์อื่นอยู่ตรงนั้นแล้ว ให้ใช้กฎจัดการการชนกัน

เมื่อเข้าใจรูปแบบนี้แล้ว กลยุทธ์หลักสองแบบในการจัดการการชนกันก็จะเข้าใจได้ง่ายขึ้น

Chaining กับ Open Addressing

Chaining เก็บบักเก็ตไว้ในแต่ละช่อง

ในแบบ chaining แต่ละช่องจะเก็บชุดข้อมูลขนาดเล็กหลายรายการ แทนที่จะเก็บได้เพียงรายการเดียว

ถ้า $10$ และ $18$ ต่างก็แฮชไปที่ช่อง $2$ บักเก็ต $2$ อาจเก็บ

• $(10, \text{value}_1)$
• $(18, \text{value}_2)$

ถ้าต้องการหาคีย์ $18$ ตารางก็จะกระโดดไปที่บักเก็ต $2$ แล้วเปรียบเทียบเฉพาะรายการในบักเก็ตนั้น

chaining เข้าใจได้ไม่ยากในเชิงแนวคิด และการลบมักทำได้ง่ายกว่าแบบ open addressing แต่ข้อแลกเปลี่ยนคือ ถ้าบักเก็ตยาวมาก การทำงานก็จะช้าลง

Open addressing อยู่ภายในอาร์เรย์ทั้งหมด

ในแบบ open addressing แต่ละช่องของอาร์เรย์เก็บข้อมูลได้มากที่สุดหนึ่งรายการเท่านั้น ถ้าช่องหลักเต็ม ตารางจะลองตรวจช่องอื่นตามกฎที่กำหนดไว้

กฎที่พบบ่อยอย่างหนึ่งคือ linear probing: ถ้าช่อง $2$ ถูกใช้งานอยู่แล้ว ก็ลอง $3$ จากนั้น $4$ แล้ว $5$ และวนกลับต้นอาร์เรย์หากจำเป็น

วิธีนี้ไม่ต้องมีลิสต์บักเก็ตแยกต่างหาก แต่ช่องที่ถูกเติมใกล้กันอาจสะสมจนกลายเป็นกลุ่มก้อน อีกประเด็นหนึ่งคือ การค้นหาและการลบต้องใช้กฎการ probing แบบเดียวกับที่ใช้ตอนแทรกข้อมูล

เมื่อใดที่การบอกว่า $O(1)$ ถือว่าสมเหตุสมผล

ตารางแฮชมักถูกอธิบายว่ามีการค้นหา การแทรก และการลบเป็น $O(1)$ โดยเฉลี่ย แต่ข้อความแบบกรณีเฉลี่ยนี้ขึ้นอยู่กับเงื่อนไขบางอย่าง:

• ฟังก์ชันแฮชกระจายคีย์ได้ดีพอสมควร
• load factor ถูกควบคุมให้อยู่ในระดับเหมาะสม
• กลยุทธ์จัดการการชนกันถูกนำไปใช้อย่างถูกต้อง

load factor คืออัตราส่วน

$$\text{load factor} = \frac{\text{number of stored entries}}{\text{number of slots}}$$

ถ้าตารางเต็มเกินไป การชนกันจะเกิดบ่อยขึ้น และประสิทธิภาพก็จะแย่ลง นั่นจึงเป็นเหตุผลว่าทำไมหลาย implementation จึงขยายขนาดอาร์เรย์เมื่อข้อมูลเริ่มแน่น

อย่างไรก็ตาม ประสิทธิภาพในกรณีเลวร้ายที่สุดก็ยังอาจลดลงเข้าใกล้ $O(n)$ ได้ ถ้ามีคีย์จำนวนมากไปกองอยู่ในบริเวณเดียวกัน

ข้อผิดพลาดที่พบบ่อยเกี่ยวกับตารางแฮช

คิดว่าการชนกันแปลว่าฟังก์ชันแฮชล้มเหลว

ไม่ใช่ การชนกันเป็นสิ่งที่คาดไว้ได้ คำถามจริงคือ ตารางจัดการกับมันได้มีประสิทธิภาพหรือไม่

มองว่า $O(1)$ เป็นจริงเสมอโดยไม่มีเงื่อนไข

$O(1)$ มักเป็นคำอธิบายสำหรับกรณีเฉลี่ย ไม่ใช่คำสัญญาสำหรับทุกอินพุตและทุกช่วงเวลา

สับสนระหว่างการแฮชในที่นี้กับการเข้ารหัส

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

ลืมเปรียบเทียบคีย์จริง

คีย์สองตัวอาจให้ผลแฮชเหมือนกันได้ หลังจากไปถึงบักเก็ตหรือจุด probing ที่ถูกต้องแล้ว ตารางก็ยังต้องตรวจสอบว่าคีย์ตรงกันจริงหรือไม่

ตารางแฮชถูกใช้เมื่อใด

ตารางแฮชถูกใช้ทุกครั้งที่การค้นหาด้วยคีย์อย่างรวดเร็วเป็นเรื่องสำคัญ ตัวอย่างที่พบบ่อยได้แก่ dictionary, symbol table, cache, indexing และการนับความถี่ของข้อมูล

มันเหมาะมากเมื่อการค้นหาแบบตรงตัวด้วยคีย์สำคัญกว่าการเก็บข้อมูลให้เรียงลำดับ ถ้าคุณต้องการการไล่ดูข้อมูลตามลำดับ การค้นหาเป็นช่วง หรือหาค่าที่ใกล้ที่สุด โครงสร้างข้อมูลแบบอื่นอาจเหมาะกว่า

ลองทำตัวอย่างการชนกันที่คล้ายกัน

ใช้อาร์เรย์ขนาดเล็กที่มี $8$ ช่อง และใช้ $h(k)=k \bmod 8$ แทรกคีย์สักสองสามตัว เช่น $3$, $11$, $19$ และ $27$ จากนั้นจัดการการชนกันหนึ่งครั้งด้วย chaining และอีกครั้งด้วย linear probing

แบบฝึกหัดเดียวนี้ช่วยให้เห็นแนวคิดหลักได้ชัดเจนอย่างรวดเร็ว: การชนกันเป็นสิ่งที่หลีกเลี่ยงไม่ได้ และกฎจัดการการชนกันจะเปลี่ยนพฤติกรรมของตาราง ถ้าคุณอยากต่อยอด ลองเปลี่ยนขนาดตารางแล้วดูว่ารูปแบบการชนกันเปลี่ยนไปอย่างไร