สมัครเรียนโทร. 085-350-7540 , 084-88-00-255 , ntprintf@gmail.com
แฮชเป็นโครงสร้างข้อมูลอีกแบบหนึ่งที่มีประสิทธิภาพมากๆในเรื่องเพิ่ม ลบ ค้นหา (ค่อนข้างจำกัดแต่ว่ามีประสิทธิภาพมากๆ) โดยเวลาคงที่เพียงO(1) เท่านั้น โดยการทำงานของแฮชจะแตกต่างจากโครงสร้างข้อมูลแบบอื่นๆคือ โครงสร้างข้อมูลแบบอื่นๆจะเก็บข้อมูลเป็นระเบียบเรียบร้อยด้วยตำแหน่งที่กำหนดเอาไว้ เช่นฮีปก็สามารถหาโหนดพ่อลูกกันได้เพราะตำแหน่งเรียงจากซ้ายไปขวาอย่างตายตัว แต่แฮชใช้วิธีการเอาข้อมูลมาผ่านกระบวนการหนึ่งๆจนได้ตำแหน่งข้อมูลออกมาก็จะเอาไปเก็บไว้ในตำแหน่งนั้น
ตารางแฮช(Hash table) คีย์(Key) ดัชนี(Index)
ตารางแฮชเป็นที่เก็บข้อมูลขนาดจำนวนมากๆ อาจใช้อาร์เรย์ก็ได้สร้างอาร์เรย์ที่มันใหญ่ๆหน่อยหรืออาจใช้แมพ(map) ไปเลยก็ได้ โดยการจะเอาข้อมูลเข้ามาในนี้ได้จะใช้คีย์(อาจจะเป็น เลขที่สมาชิก รหัสสินค้า รหัสบัตรประชาชน อะไรก็ได้แต่ต้องไม่ซ้ำกัน) เป็นสิ่งแทนข้อมูลสำหรับการค้นหา เอาคีย์ไปผ่านสิ่งที่เรียกว่า แฮชฟังก์ชัน(Hash Function)(ซึ่งเป็นกระบวนการทำอะไรกับเลขนั้นๆก็ได้ เช่นหาร) จะได้เป็นเลขๆหนึ่งออกมาเลขนี้จะถือเป็นดัชนีที่เป้นตำแหน่งที่จะเอาคีย์ไปใส่ในตารางแฮช
รูป 8-1
เช่น อยากเก็บข้อมูลค้นไข้ในโรงพยาบาล ถ้ากลัวว่าเก็บชื่อแล้วข้อมูลจะซ้ำกันเสียเวลาหา ก็เก็บเป็นเลขประจำตัวประชาชนซึ่งไม่ซ้ำกันแน่ๆ เอาไปผ่านแฮชฟังก์ชันออกได้เลขหนึ่งก็เอาเลขนั้นไปเก็บในตารางแฮช
รูป8-2
จากรูปให้รหัสสมาชิกเป็น key Hash เอาไปผ่าน Function ได้เลขหนึ่งออกมาเป็น address เอาคีย์ไปใส่ในตารางแฮชตาม address ที่ได้ พอเอาคีย์ไปทำการค้นหาก็จะได้ชื่อของสมาชิกนั้นๆออกมา เป็นต้น
ปัญหาการชนกัน
เนื่องจากการเก็บข้อมูลด้วยแฮชต้องผ่านแฮชฟังก์ชั่นเพื่อหาดัชนี แต่บางครั้งก็อาจเกิดเหตุการณ์ที่แม้จะมีช่องว่างมากมายแต่คีย์ที่ผ่านแฮชฟังก์ชันกลับได้ดัชนีเดียวกัน แต่ช่องหมายเลขเดียวกันไม่สามารถเก็บข้อมูลสองตัวพร้อมกัน หรือก็คือเกิดข้อมูลชนกัน มีวิธีแก้แยกได้เป็น 2 วิธีดังนี้
Separate Chain Hashing
เป็นการสร้างโซ่ด้วยการเอา list เข้ามาช่วย ในการเก็บข้อมูล คือเมื่อมีตารางแฮช ตารางนั้นจะไม่ได้มีแค่ช่องเดียวแต่จะมีช่องย่อยที่เป็นยาวต่อๆกันออกไป เมื่อตัวใดที่ต้องเก็บในตารางแฮชตำแหน่งเดียวกัน ก็จะถูกเก็บไว้ใน list นี้ต่อไปเรื่อยๆ
รูป 8-3
จะเห็นได้ว่าตารางแฮชหน้าตาเปลี่ยนไปจากที่ช่องที่ 0 จะเก็บได้แค่ข้อมูลเดียว ก็สามารถเก็บได้หลายตัวเพราะมีช่องย่อยๆที่เกิดจาก list เข้ามาช่วยเป็นส่วนต่อ
Open Addressing
อีกวิธีการหนึ่งคือ Open Addressing แปลตรงตัวว่า เปิดที่อยู่(ใหม่) หรือก็คือการหาช่องใหม่ให้นั่นเอง ถ้าข้อมูลที่เข้าเกิดการชนกันขึ้นมาก็ต้องให้หาช่องใหม่ไปลงแทนการสร้างลิสต์ช่องเดิม ซึ่งการคำนวณหาช่องใหม่มี 3 วิธี
- Double Hashing
เป็นการเปลี่ยนช่องโดยการเอาฟังก์ชันแฮชอีกอันมาช่วยหาช่องใหม่ ทำให้การกระจายตัวของข้อมูลในตารางแฮชสม่ำเสมอ
- Linear Probe
เป็นการเปลี่ยนช่องแบบคงที่ ทำให้ข้อมูลอยู่ใกล้ๆกัน
- Quadratic Probe
- เป็นการคำนวณหาช่องใหม่ โดยส่วนใหญ่จะใช้ฟังก์ชันยกกำลังสอง ข้อมูลก็จะอยู่ใกล้ๆกันถ้าเกิดการชนอีก
ตัวอย่างการสร้างแฮชแบบ Separate Chain Hashing
รูป 8-4
บรรทัดที่ 9 : สร้างคลาส Hash
บรรทัดที่ 11 : สร้างตัวแปร size สำหรับเป็นขนาด
บรรทัดที่ 12 : สร้างตัวแปร capacity สำหรับใช้ใน hashFunction
บรรทัดที่ 13 : สร้าง data เป็นข้อมูลแบบ LinkedList
บรรทัดที่ 15 : สร้างคอนสตรัคเตอร์ของ Hash
บรรทัดที่ 17 : กำหนดให้ size เริ่มต้นจาก 0
บรรทัดที่ 18 : กำหนดให้ capacity เป็น 13 เป็นเลขเฉพาะจะดีเพื่อลดโอกาสชน
บรรทัดที่ 19:
รูป 8-5
บรรทัดที่ 22 : สร้าง hashFunction สำหรับเอาคีย์มาหาดัชนี
บรรทัดที่ 24: ให้ตัวแปร t เรียกเมท็อด hashCode ซึ่งเป็นเมท็อดสำหรับคืนค่าตำแหน่ง เอามาmod ด้วย capacity
บรรทัดที่ 27 : สร้างเมท็อด add
บรรทัดที่ 29 : เอาข้อมูลที่เข้ามาไปผ่าน hashFunction
บรรทัดที่ 30-32 : ถ้าตำแหน่งที่ได้ไม่มีให้สร้างโหนดใน LinkedList เข้ามาเก็บ
บรรทัดที่ 34: ถ้ามีตำแหน่งนั้นอยู่ลปแวก็เพิ่มข้อมูลลงไปเลยด้วยเมท็อด addFirst ที่มีอยู่แล้วใน LinkedList
รูป 8-6
บรรทัดที่ 38 : สร้างเมท็อด isContainสำหรับตรวจว่ามีข้อมูลซ้ำกันหรือไม่
บรรทัดที่ 40:เอาข้อมูลที่เข้ามาไปผ่าน hashFunction
บรรทัดที่ 41-43: ถ้าไม่มีข้อมูลตำแหน่งนั้น คืนว่า null
บรรทัดที่ 45: มีข้อมูลคืนค่า true
Tag ที่น่าสนใจ: hash data_structure hash_table key index separate_chain_hashing open_addressing double_hashing linear_probe quadratic_probe hash_function collision linked_list hash_code
หากมีข้อผิดพลาด/ต้องการพูดคุยเพิ่มเติมเกี่ยวกับบทความนี้ กรุณาแจ้งที่ http://m.me/Expert.Programming.Tutor
085-350-7540 (DTAC)
084-88-00-255 (AIS)
026-111-618
หรือทาง EMAIL: NTPRINTF@GMAIL.COM
Copyright (c) 2013 expert-programming-tutor.com. All rights reserved. | 085-350-7540 | 084-88-00-255 | ntprintf@gmail.com