ตารางแฮช

ตารางแฮช (Hash table, Hash map) เป็นโครงสร้างข้อมูลในรูปแบบตาราง ซึ่งอาจใช้แถวลำดับในการทำ ใช้ในการเก็บข้อมูลจำนวนมาก เพื่อสะดวกต่อการเก็บและค้นหา โดยการผ่านฟังก์ชันแฮช
== ลักษณะของตารางแฮช ==
ตารางแฮชมักใช้แถวลำดับหรือMapขนาดใหญ่เพื่อใช้ในการจัดการเก็บข้อมูลจำนวนมาก โดยมีลักษณะการเก็บแบบดัชนีได้ (Indexing) วิธีการเก็บนั้นจะนำข้อมูลที่จะนำมาเก็บผ่านฟังก์ชันฟังก์ชันหนึ่ง(เราจะเรียกข้อมูลที่ผ่านฟังก์ชันนั้นว่า key) ซึ่งเรียกว่าฟังก์ชันแฮชจะได้เลขซึ่งจำเพาะกับข้อมูลนั้น กล่าวคือ ข้อมูลแต่ละตัวเมื่อผ่านฟังก์ชันแฮชแล้ว จะได้เลขที่แตกต่างกัน แล้วจึงนำข้อมูลไปเก็บไว้ในตาราง แถวลำดับ หรือ Map ที่กำหนดไว้
ตามรูปเป็นการเก็บหมายเลขโทรศัพท์ โดยใช้ชื่อผู้ใช้โทรศัพท์เป็น key ก็สามารถทำได้โดยการสร้างฟังก์ชันแฮชของชื่อผู้ใช้โทรศัพท์ เราก็จะได้ว่าหมายเลขโทรศัพท์นี้ควรเก็บในช่องใด เมื่อจะค้นหาหมายเลขโทรศัพท์ของผู้ใช้โทรศัพท์คนใด ก็นำชื่อผู้ใช้โทรศัพท์ผ่านฟังก์ชันแฮช ก็จะรู้ว่าหมายเลขโทรศัพท์ของเขาผู้นั้นอยู่ในช่องใดได้ทันที ฟังก์ชันแฮชก็เปรียบเทียบได้กับ สารบัญหรือดรรชนีของหนังสือนั่นเอง
== จุดเด่นของตารางแฮช ==
ตารางแฮชเน้นการค้นหาและเพิ่มลดสมาชิกอย่างรวดเร็ว จนเป็นเวลาคงที่ O(1) แต่ข้อมูลเหล่านั้นจะต้องไม่มีลำดับและไม่ซ้ำกันเท่านั้น
== บริการที่มักจะมี ==
คืนข้อมูลที่คู่กับ key ที่กำหนด
เพิ่มข้อมูลลงในตารางแฮชให้สอดคล้องกับ key ที่กำหนด
ลดข้อมูลที่คู่ key ที่กำหนดในตารางแฮช
== ความเร็วที่ใช้ในการทำงาน ==
การทำงานของตารางแฮชเน้นการเข้าถึงข้อมูลอย่างรวดเร็วเป็นเวลาคงที่ 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: \lambda)ให้มีค่าเท่ากับจำนวนข้อมูล(N)หารด้วยขนาดของตาราง(tablesize)
\lambda=\frac{N}{tablesize}
ซึ่งในวิธี SeparateChaining จะสามารถประมาณได้ว่าเป็นความยาวเฉลี่ยของรายการในแต่ละช่อง
สำหรับวิธี OpenAddressing นั้นต้องมีค่าสัดส่วนบรรจุน้อยกว่าหนึ่งอยู่เสมอ ในทางปฏิบัติสำหรับ OpenAddressing เรามักให้ค่าสัดส่วนบรรจุให้น้อยกว่า 0.5 เพื่อกันการชนกันมาก 
เมื่อมีข้อมูลมากขึ้นแต่จำนวนตารางเท่าเดิม ค่าสัดส่วนบรรจุก็จะมากขึ้นเรื่อยๆ วิธีการแก้คือจะสร้างตารางแฮชที่ใหญ่กว่าเดิมและย้ายข้อมูลทั้งหมดไปแฮชใหม่ๆ เรามักเรียกขั้นตอนนี้ว่า รีแฮช (rehash)
== ดูเพิ่ม ==
ฟังก์ชันแฮช
โครงสร้างข้อมูล
โครงสร้างข้อมูล
ขั้นตอนวิธีการค้นหา
การแฮช