ตารางแฮช
ตารางแฮช (อังกฤษ: Hash table, Hash map) เป็นโครงสร้างข้อมูลในรูปแบบตาราง ซึ่งอาจใช้แถวลำดับในการทำ ใช้ในการเก็บข้อมูลจำนวนมาก เพื่อสะดวกต่อการเก็บและค้นหา โดยการผ่านฟังก์ชันแฮช
| ตารางแฮช | |||||
|---|---|---|---|---|---|
การใช้งานตารางแฮชผ่านฟังก์ชันแฮช | |||||
| ความสำคัญของลำดับ | ไม่มีความสำคัญ | ||||
| การซ้ำกันของสมาชิก | ไม่อนุญาตให้ซ้ำได้ | ||||
| เวลาที่ใช้ค้นหาตามดัชนี | - | ||||
| เวลาที่ใช้ค้นหาตามค่า | O (1) | ||||
| เวลาที่ใช้ในการเข้าถึง | O (1) | ||||
| การทำให้ว่าง | - | ||||
| เวลาที่ใช้ทำให้ว่าง | - | ||||
| โครงสร้างต้นแบบ | ตาราง | ||||
| ความซับซ้อนในการคำนวณแบบสัญกรณ์โอใหญ่ | |||||
| |||||
ลักษณะของตารางแฮช
ตารางแฮชมักใช้แถวลำดับหรือMapขนาดใหญ่เพื่อใช้ในการจัดการเก็บข้อมูลจำนวนมาก โดยมีลักษณะการเก็บแบบดัชนีได้ (Indexing) วิธีการเก็บนั้นจะนำข้อมูลที่จะนำมาเก็บผ่านฟังก์ชันฟังก์ชันหนึ่ง(เราจะเรียกข้อมูลที่ผ่านฟังก์ชันนั้นว่า key) ซึ่งเรียกว่าฟังก์ชันแฮชจะได้เลขซึ่งจำเพาะกับข้อมูลนั้น กล่าวคือ ข้อมูลแต่ละตัวเมื่อผ่านฟังก์ชันแฮชแล้ว จะได้เลขที่แตกต่างกัน แล้วจึงนำข้อมูลไปเก็บไว้ในตาราง แถวลำดับ หรือ Map ที่กำหนดไว้
ตามรูปเป็นการเก็บหมายเลขโทรศัพท์ โดยใช้ชื่อผู้ใช้โทรศัพท์เป็น key ก็สามารถทำได้โดยการสร้างฟังก์ชันแฮชของชื่อผู้ใช้โทรศัพท์ เราก็จะได้ว่าหมายเลขโทรศัพท์นี้ควรเก็บในช่องใด เมื่อจะค้นหาหมายเลขโทรศัพท์ของผู้ใช้โทรศัพท์คนใด ก็นำชื่อผู้ใช้โทรศัพท์ผ่านฟังก์ชันแฮช ก็จะรู้ว่าหมายเลขโทรศัพท์ของเขาผู้นั้นอยู่ในช่องใดได้ทันที ฟังก์ชันแฮชก็เปรียบเทียบได้กับ สารบัญหรือดรรชนีของหนังสือนั่นเอง
จุดเด่นของตารางแฮช
ตารางแฮชเน้นการค้นหาและเพิ่มลดสมาชิกอย่างรวดเร็ว จนเป็นเวลาคงที่ O(1) แต่ข้อมูลเหล่านั้นจะต้องไม่มีลำดับและไม่ซ้ำกันเท่านั้น
บริการที่มักจะมี
- คืนข้อมูลที่คู่กับ key ที่กำหนด
- เพิ่มข้อมูลลงในตารางแฮชให้สอดคล้องกับ key ที่กำหนด
- ลดข้อมูลที่คู่ key ที่กำหนดในตารางแฮช
ความเร็วที่ใช้ในการทำงาน
การทำงานของตารางแฮชเน้นการเข้าถึงข้อมูลอย่างรวดเร็วเป็นเวลาคงที่ O(1) ในกรณีเฉลี่ย (ใช้กับข้อมูลสุ่ม และมีการออกแบบโครงสร้างข้อมูลอย่างถูกต้อง)
| การทำงาน | เวลา |
|---|---|
| การหาตามคีย์ (ฟังก์ชันแฮช) | O(1) |
| การเข้าถึงสมาชิก | โดยเฉลี่ย O(1) |
การแก้ปัญหาการชนกัน
การชนกัน (collision) เกิดจากการที่สมาชิกมากกว่าสองตัวเกิดมีผลของฟังก์ชันแฮชตรงกัน ทำให้เกิดการเก็บที่เดียวกัน หรือเมื่อคำนวณผลจากฟังก์ชันแฮชแล้วอาจมีค่ามากกว่าขนาดของ ตารางแฮชทำให้ต้องวนกลับมาใส่แล้วเจอตัวที่เดิมเคยมีอยู่แล้ว วิธีการแก้ปํญหาที่นิยมมีสองวิธีคือ วิธี SperateChaining และ OpenAddressing
วิธี Separate Chaining
Separate Chaining คือการใช้รายการหรือแถวลำดับขยายขนาดได้แทนการเก็บ สมาชิกโดยตรง ตารางแฮชแต่ละช่องก็จะกลายเก็บข้อมูลในลักษณะเป็นรายการ เมื่อตัวใดที่ต้องเก็บในตารางแฮชตำแหน่งเดียวกัน ก็จะถูกเก็บไว้ในรายการนี้ต่อไปเรื่อยๆ (คล้ายๆพจนานุกรม เมื่อเปิดสารบัญแล้วเจอว่าตัวอักษรตัวแรกของคำที่เราจะหาอยู่ในหน้าใด ก็เปิดหน้านั้นแล้วต้องมานั่งไล่หาต่อในรายการของคำที่มีตัวอักษรตัวแรกเหมือนกับคำที่เราจะหาต่อไป)
วิธี Open Addressing
เมื่อการการชนเกิดขึ้นวิธีการของ Open Addressing คือการหาช่องในตารางแฮชใหม่โดยกระโดดไปจากที่เดิมเป็นฟังก์ชันหนึ่ง จนกว่าจะหาช่องว่างเจอจึงจะใส่ค่าลงไป ฟังก์ชันที่มักจะใช้กระโดดมีสามแบบคือ การตรวจเชิงเส้น (Linear Probing), การตรวจกำลังสอง (Quadatic Probing) และการแฮชสองชั้น (Double Hashing)
การตรวจเชิงเส้น
การตรวจเชิงเส้นจะทำให้กระโดดไปจากจุดเดิมเป็นระยะคงที่ การกระโดดเช่นนี้จะทำให้เกิดข้อมูลอยู่ ติดๆกันเป็นกลุ่มขนาดใหญ่แต่มีจำนวนกลุ่มน้อยๆ ทำให้ผลที่เข้ามาถ้ามีการชนกันบริเวณนี้ จะต้องเสียเวลากระโดดไปเพื่อพ้นจากช่วงนี้ และทำให้กลุ่มนี้ใหญ่ขึ้นไปเรื่อยๆอีก เราเรียกการเกาะกลุ่มเป็นจำนวนกลุ่มน้อยๆแต่กลุ่มขนาดใหญ่ๆ เนื่องจากการตรวจเชิงเส้นว่า การเกาะกลุ่มปฐมภูมิ (Primary Clustering)
การตรวจกำลังสอง
การตรวจกำลังสองมักคำนวณว่าจะทำให้กระโดดไปจากจุดเดิมเป็นระยะหนึ่ง ซึ่งเป็นฟังก์ชันตรรกยะ (มักเป็นฟังก์ชันยกกำลังสอง) การกระโดดเช่นนี้จะทำให้เกิดข้อมูลอยู่ ติดๆกันเป็นกลุ่มขนาดเล็กแต่มีจำนวนกลุ่มหลายกลุ่ม เพราะการกระโดดจะเป็นการกระโดดข้ามไปไม่ติดกัน แต่ถึงอย่างไรก็ตามถ้าแฮชชนกัน ก็จะไปเจอกลุ่มเล็กๆกลุ่มเดิมอยู่ดี และจะไม่เจอช่องว่างบางช่องว่างได้ เราเรียกการเกาะกลุ่มขนาดเล็กๆเป็นจำนวนมาก เนื่องจากการตรวจกำลังสองว่า การเกาะกลุ่มทุติยภูมิ (Secondary Clustering)
การแฮชสองชั้น
การแฮชสองชั้นจะใช้ฟังก์ชันการกระโดดเป็นฟังก์ชันแฮชอีกฟังก์ชันหนึ่ง (มักเอาฟังก์ชันแฮชฟังก์ชันเดิมมาช่วยคิด) จึงทำให้การกระโดดกระจายค่อนข้างสม่ำเสมอและไม่เกาะกลุ่มกัน
ความหนาแน่นของข้อมูล และการ Rehash
ถึงแม้ว่าการอนุญาตให้ชนกันทำให้เราสามารถใช้ตารางขนาดเล็กได้ แต่การให้เกิดการชนกันจนรายการยาวเกินไปหรือหนาแน่นเกินไป จะทำให้การเข้าถึงข้อมูลต้องเสียเวลาค้นหาในรายการมากกว่า จึงทำให้ผิดจุดประสงค์ความเป็นตารางแฮชที่ต้องการเข้าถึงข้อมูลอย่างรวดเร็วได้
เราจึงนิยามค่าสัดส่วนบรรจุ(load factor: )ให้มีค่าเท่ากับจำนวนข้อมูล(N)หารด้วยขนาดของตาราง(tablesize)
ซึ่งในวิธี SeparateChaining จะสามารถประมาณได้ว่าเป็นความยาวเฉลี่ยของรายการในแต่ละช่อง สำหรับวิธี OpenAddressing นั้นต้องมีค่าสัดส่วนบรรจุน้อยกว่าหนึ่งอยู่เสมอ ในทางปฏิบัติสำหรับ OpenAddressing เรามักให้ค่าสัดส่วนบรรจุให้น้อยกว่า 0.5 เพื่อกันการชนกันมาก[ต้องการอ้างอิง]
เมื่อมีข้อมูลมากขึ้นแต่จำนวนตารางเท่าเดิม ค่าสัดส่วนบรรจุก็จะมากขึ้นเรื่อยๆ วิธีการแก้คือจะสร้างตารางแฮชที่ใหญ่กว่าเดิมและย้ายข้อมูลทั้งหมดไปแฮชใหม่ๆ เรามักเรียกขั้นตอนนี้ว่า รีแฮช (rehash)