Hash Table เป็นโครงสร้างข้อมูลที่จัดเก็บข้อมูลในลักษณะที่เชื่อมโยงกัน ในตารางแฮช ข้อมูลจะถูกจัดเก็บในรูปแบบอาร์เรย์ โดยที่ค่าข้อมูลแต่ละค่ามีค่าดัชนีเฉพาะของตัวเอง การเข้าถึงข้อมูลจะเร็วมากหากเราทราบดัชนีของข้อมูลที่ต้องการ
ดังนั้นจึงกลายเป็นโครงสร้างข้อมูลที่การแทรกและการค้นหาทำได้เร็วมากโดยไม่คำนึงถึงขนาดของข้อมูล ตารางแฮชใช้อาร์เรย์เป็นสื่อเก็บข้อมูลและใช้เทคนิคแฮชเพื่อสร้างดัชนีที่จะแทรกองค์ประกอบหรือจะตั้งอยู่
การแฮช
การแฮชเป็นเทคนิคในการแปลงช่วงของค่าคีย์เป็นช่วงของดัชนีของอาร์เรย์ เราจะใช้ตัวดำเนินการโมดูโลเพื่อรับช่วงของค่าคีย์ ลองพิจารณาตัวอย่างตารางแฮชขนาด 20 และรายการต่อไปนี้จะถูกเก็บไว้ รายการอยู่ในรูปแบบ (คีย์, ค่า)
ที่นี่ เรามีฟังก์ชันแฮชที่รับคีย์และสร้างดัชนีสำหรับตาราง ดัชนีเหล่านี้ทำให้เราทราบว่าค่าถูกเก็บไว้ที่ใด ตอนนี้เมื่อใดก็ตามที่เราต้องการค้นหาค่าที่เกี่ยวข้องกับคีย์ เราเพียงแค่เรียกใช้ฟังก์ชันแฮชบนคีย์อีกครั้ง และรับค่าในเวลาเกือบคงที่
ฟังก์ชั่นแฮชนั้นค่อนข้างยากในการออกแบบ มาดูตัวอย่างกัน −
สมมติว่าเรามีฟังก์ชันแฮชต่อไปนี้ -
ตัวอย่าง
function modBy11(key) {
return key % 11;
} และเราเริ่มทำงานกับคู่คีย์-ค่าที่เราต้องการจัดเก็บ เช่น −
- (15, 20) - รหัสแฮช:4
- (25, 39) - รหัสแฮช:3
- (8, 55) - รหัสแฮช:8
- (26, 84) - รหัสแฮช:4
ที่นี่เราเห็นว่าเรามีการชนกัน กล่าวคือ ถ้าเราเก็บ 15 ไว้ก่อนแล้วพบคีย์ 26 ด้วยฟังก์ชันแฮชนี้ จะพยายามแก้ไขรายการนี้ในรูเดียวกัน นี้เรียกว่าการชนกัน และเพื่อจัดการกับสถานการณ์ดังกล่าว เราจำเป็นต้องกำหนดกลไกจัดการการชนกัน มีอัลกอริธึมการแก้ปัญหาการชนกันที่เรียบง่ายที่กำหนดไว้อย่างดี ตัวอย่างเช่น −
- การตรวจสอบเชิงเส้น:ในอัลกอริธึมนี้ เราสามารถค้นหาตำแหน่งว่างถัดไปในอาร์เรย์โดยดูในเซลล์ถัดไปจนกว่าเราจะพบเซลล์ว่าง ในตัวอย่างของเรา เนื่องจากถ่ายหลุมที่ 4 เราจึงเติมลงใน 5 ได้
- Separate Chaining:ในการใช้งานนี้:เราเชื่อมโยงแต่ละตำแหน่งในตารางแฮชกับรายการ เมื่อใดก็ตามที่เราเกิดการชนกัน เราจะผนวกคู่คีย์-ค่าต่อท้ายรายการนี้ ซึ่งอาจนำไปสู่เวลาการค้นหาที่นานขึ้นหากโซ่ยาวขึ้นเรื่อยๆ
ตอนนี้เราเข้าใจวิธีการทำงานของตารางแฮชแล้วและเราจะใช้วิธีการแก้ปัญหาการชนกันได้อย่างไร มาลองใช้คลาส HashTable กัน
วิธีการที่เราจะนำไปใช้
เราจะนำวิธีการเหล่านี้ไปปฏิบัติในการใช้งานของเรา -
- put(key, value):เพิ่มคู่คีย์-ค่าใหม่ในตารางแฮช
- get(key):รับค่าที่เกี่ยวข้องกับคีย์
- remove(key):ลบคู่คีย์-ค่าออกจากตาราง
- forEach():อนุญาตการวนซ้ำคู่คีย์-ค่าทั้งหมด
- static join():วิธีการแบบสแตติกในการรวมตารางแฮช 2 ตารางในตารางใหม่
