แฮชเป็นโครงสร้างข้อมูลอีกแบบหนึ่งที่มีประสิทธิภาพมากๆในเรื่องเพิ่ม ลบ ค้นหา (ค่อนข้างจำกัดแต่ว่ามีประสิทธิภาพมากๆ) โดยเวลาคงที่เพียง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