ตารางแฮช

จากวิกิพีเดีย สารานุกรมเสรี

ตารางแฮช
การใช้งานตารางแฮชผ่านฟังก์ชันแฮช
ความสำคัญของลำดับ	ไม่มีความสำคัญ
การซ้ำกันของสมาชิก	ไม่อนุญาตให้ซ้ำได้
เวลาที่ใช้ค้นหาตามดัชนี	-
เวลาที่ใช้ค้นหาตามค่า	O (1)
เวลาที่ใช้ในการเข้าถึง	O (1)
การทำให้ว่าง	-
เวลาที่ใช้ทำให้ว่าง	-
โครงสร้างต้นแบบ	ตาราง
โครงสร้างที่นำไปใช้

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

[แก้] ลักษณะของตารางแฮช

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

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

[แก้] จุดเด่นของตารางแฮช

ตารางแฮชเน้นการค้นหาและเพิ่มลดสมาชิกอย่างรวดเร็ว จนเป็นเวลาคงที่ O(1) แต่ข้อมูลเหล่านั้นจะต้องไม่มีลำดับและไม่ซ้ำกันเท่านั้น

[แก้] บริการที่มักจะมี

คืนข้อมูลที่คู่กับ key ที่กำหนด
เพิ่มข้อมูลลงในตารางแฮชให้สอดคล้องกับ key ที่กำหนด
ลดข้อมูลที่คู่ key ที่กำหนดในตารางแฮช

[แก้] ความเร็วที่ใช้ในการทำงาน

การทำงานของตารางแฮชเน้นการเข้าถึงข้อมูลอย่างรวดเร็วเป็นเวลาคงที่ O(1)

การทำงาน	เวลา
การหาตามคีย์(ฟังก์ชันแฮช)	O(1)
การเข้าถึงสมาชิก	O (1)

[แก้] การแก้ปัญหาการชนกัน

การชนกัน(collision) เกิดจากการที่สมาชิกมากกว่าสองตัวเกิดมีผลของฟังก์ชันแฮชตรงกัน ทำให้เกิดการเก็บที่เดียวกัน หรือเมื่อคำนวณผลจากฟังก์ชันแฮชแล้วอาจมีค่ามากกว่าขนาดของ ตารางแฮชทำให้ต้องวนกลับมาใส่แล้วเจอตัวที่เดิมเคยมีอยู่แล้ว วิธีการแก้ปํญหาที่นิยมมีสองวิธีคือ วิธี SperateChaining และ OpenAddressing

[แก้] วิธี SeperateChaining

การแก้ปัญหาการชนกันด้วย SeparateChaining

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

[แก้] วิธี OpenAddressing

การแก้ปัญหาการชนกันด้วย OpenAddressing

เมื่อการการชนเกิดขึ้นวิธีการของ OpenAddressing คือการหาช่องในตารางแฮชใหม่โดยกระโดดไปจากที่เดิมเป็นฟังก์ชันหนึ่ง จนกว่าจะหาช่องว่างเจอจึงจะใส่ค่าลงไป ฟังก์ชันที่มักจะใช้กระโดดมีสามแบบคือ การตรวจเชิงเส้น(Linear Probing),การตรวจกำลังสอง(Quadatic Probing) และ การแฮชสองชั้น(Double Hashing)

[แก้] การตรวจเชิงเส้น

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

[แก้] การตรวจกำลังสอง

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

[แก้] การแฮชสองชั้น

การแฮชสองชั้นจะใช้ฟังก์ชันการกระโดดเป็นฟังก์ชันแฮชอีกฟังก์ชันหนึ่ง (มักเอาฟังก์ชันแฮชฟังก์ชันเดิมมาช่วยคิด) จึงทำให้การกระโดดกระจายค่อนข้างสม่ำเสมอและไม่เกาะกลุ่มกัน

[แก้] ความหนาแน่นของข้อมูล และการ Rehash

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

เราจึงนิยามค่าสัดส่วนบรรจุ(load factor: $λ$ )ให้มีค่าเท่ากับจำนวนข้อมูล(N)หารด้วยขนาดของตาราง(tablesize)

$\lambda=\frac{N}{tablesize}$

ซึ่งในวิธีSeperateChaining จะสามารถประมาณได้ว่าเป็นความยาวเฉลี่ยของรายการในแต่ละช่อง สำหรับวิธีOpenAddressing นั้นต้องมีค่าสัดส่วนบรรจุน้อยกว่าหนึ่งอยู่เสมอ ในทางปฏิบัติสำหรับ OpenAddressing เรามักให้ค่าสัดส่วนบรรจุให้น้อยกว่า 0.5 เพื่อกันการชนกันมาก ^{[ต้องการแหล่งอ้างอิง]}

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

[แก้] ดูเพิ่ม