ตารางแฮช

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

 ลักษณะของตารางแฮช 
ตารางแฮชมักใช้แถวลำดับ หรือ 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)

 ดูเพิ่ม 
ฟังก์ชันแฮช
โครงสร้างข้อมูล

หมวดหมู่:โครงสร้างข้อมูล
หมวดหมู่:ขั้นตอนวิธีการค้นหา
หมวดหมู่:การแฮช