ตารางแฮช

ตารางแฮช (hash table) เป็นโครงสร้างข้อมูลที่ใช้ฟังก์ชันแฮช (hash function) เพื่อแปลงคีย์ (key) เป็นตำแหน่งในอาร์เรย์ (array) ซึ่งรองรับการแทรก (insertion) การลบ (deletion) และการค้นหา (lookup) โดยมีประสิทธิภาพเชิงเวลาคงที่โดยเฉลี่ย เมื่อมีการจัดการการชนกัน (collision) ได้ดี

Definition

ตารางแฮชเป็นโครงสร้างข้อมูลที่จัดเก็บคู่คีย์-ค่า (key-value pairs) ในอาร์เรย์ โดยใช้ฟังก์ชันแฮชในการคำนวณดัชนีสำหรับแต่ละคีย์เพื่อเข้าถึงอาร์เรย์ พร้อมด้วยกลไกการแก้ไขการชนกันเพื่อจัดการกับคีย์ที่แตกต่างกันแต่ถูกแฮชไปยังดัชนีเดียวกัน

Scope

หัวข้อนี้ครอบคลุมพจนานุกรมที่ใช้การแฮช (hashing-based dictionaries): ฟังก์ชันแฮชและคุณสมบัติที่พึงประสงค์ กลยุทธ์การแก้ไขการชนกัน (separate chaining และ open addressing) แฟกเตอร์โหลด (load factor) และการปรับขนาด (resizing) กรอบการทำงานของการแฮชแบบสากล (universal hashing) และการแฮชแบบสมบูรณ์ (perfect hashing) ที่ให้การรับประกันที่พิสูจน์ได้ และโครงสร้างเชิงความน่าจะเป็นที่เกี่ยวข้อง เช่น บลูมฟิลเตอร์ (Bloom filters) หัวข้อนี้ไม่รวมโครงสร้างพจนานุกรมแบบเรียงลำดับ ซึ่งครอบคลุมภายใต้ต้นไม้ค้นหา (search trees)

Core questions

• อะไรทำให้ฟังก์ชันแฮชดี และจะเลือกฟังก์ชันแฮชอย่างไรให้กระจายคีย์ได้อย่างสม่ำเสมอ?
• การชนกันได้รับการแก้ไขอย่างไรโดยการเชื่อมโยง (chaining) หรือการเปิดแอดเดรส (open addressing) และส่งผลต่อต้นทุนอย่างไร?
• แฟกเตอร์โหลดควบคุมเวลาการทำงานที่คาดหวังและกระตุ้นการปรับขนาดอย่างไร?
• การแฮชแบบสากลและการแฮชแบบสมบูรณ์ให้การรับประกันประสิทธิภาพที่พิสูจน์ได้จริงได้อย่างไร?
• เมื่อใดที่โครงสร้างเชิงความน่าจะเป็นที่มีประสิทธิภาพด้านพื้นที่ เช่น บลูมฟิลเตอร์ เหมาะสมกว่าตารางที่แม่นยำ?

Key concepts

• ฟังก์ชันแฮช
• การเชื่อมโยงแยก
• การเปิดแอดเดรส
• แฟกเตอร์โหลด
• การแฮชซ้ำและการปรับขนาด
• การแฮชแบบสากล
• การแฮชแบบสมบูรณ์
• บลูมฟิลเตอร์

Key theories

การแฮชแบบสากล

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

การแก้ไขการชนกันและแฟกเตอร์โหลด

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

Clinical relevance

ตารางแฮชเป็นหนึ่งในโครงสร้างข้อมูลที่ใช้บ่อยที่สุดในการคำนวณ: ใช้ในการสร้างพจนานุกรมและเซตในไลบรารีมาตรฐาน เป็นพื้นฐานของการทำดัชนีฐานข้อมูลและแคชในหน่วยความจำ รองรับตารางสัญลักษณ์ในคอมไพเลอร์ และเป็นรากฐานของการกำจัดข้อมูลซ้ำซ้อน (deduplication) และการทดสอบการเป็นสมาชิก (membership tests) บลูมฟิลเตอร์ช่วยปรับขนาดการสอบถามการเป็นสมาชิกในฐานข้อมูลและเครือข่ายที่การจัดเก็บข้อมูลที่แม่นยำไม่สามารถทำได้จริง

History

การแฮชมีต้นกำเนิดในช่วงทศวรรษ 1950 โดยมีผลงานที่เชื่อว่าเป็นของ Hans Peter Luhn ที่ IBM Burton Bloom ได้นำเสนอ Bloom filter ที่มีประสิทธิภาพด้านพื้นที่ในปี 1970 Carter และ Wegman ได้กำหนดรูปแบบการแฮชแบบสากล (universal hashing) และต่อมาเป็นการแฮชแบบสากลอย่างเข้มข้น (strongly universal hashing) ในช่วงปลายทศวรรษ 1970 และต้นทศวรรษ 1980 ซึ่งเป็นการวางรากฐานทางทฤษฎีที่เข้มงวดให้กับการแฮช

Key figures

• Hans Peter Luhn
• J. Lawrence Carter
• Mark Wegman
• Burton H. Bloom

Seminal works

• bloom1970
• carter1981
• cormen2009

Frequently asked questions

ทำไมการดำเนินการของตารางแฮชจึงถูกอธิบายว่าเป็น O(1) โดยเฉลี่ย แทนที่จะเป็น O(1) ที่รับประกัน?

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

บลูมฟิลเตอร์คืออะไร และแตกต่างจากตารางแฮชอย่างไร?

บลูมฟิลเตอร์เป็นโครงสร้างเชิงความน่าจะเป็นขนาดกะทัดรัดที่ใช้ทดสอบการเป็นสมาชิกของเซตโดยใช้ฟังก์ชันแฮชหลายฟังก์ชันบนอาร์เรย์บิต อาจให้ผลบวกปลอม (false positives) แต่ไม่เคยให้ผลลบปลอม (false negatives) และไม่จัดเก็บคีย์ใดๆ โดยแลกความแม่นยำกับการประหยัดพื้นที่จำนวนมากเมื่อเทียบกับตารางแฮช