Hash Table เป็นโครงสร้างข้อมูลที่เก็บข้อมูลแบบ associative manner ใน hash table ข้อมูลจะถูกเก็บในรูปแบบ array โดยแต่ละค่าข้อมูลจะมี index value ที่ไม่ซ้ำกัน การเข้าถึงข้อมูลจะเร็วมากถ้าเรารู้ index ของข้อมูลที่ต้องการ
ดังนั้น Hash Table จึงกลายเป็นโครงสร้างข้อมูลที่การ insert และ search เร็วมาก ไม่ว่าข้อมูลจะมีขนาดเท่าใด Hash Table ใช้ array เป็นสื่อเก็บข้อมูล และใช้ hash technique สร้าง index สำหรับ insert หรือ locate element
Hashing
Hashing เป็นเทคนิคแปลงช่วงของคีย์ (key values) ให้เป็นช่วงของ index ใน array เราจะใช้ modulo operator เพื่อแปลงช่วงคีย์ ตัวอย่าง hash table ขนาด 20 และ items ต่อไปนี้จะถูกเก็บ (รูปแบบ key, value):
ที่นี่เรามี hash function ที่รับคีย์และสร้าง index สำหรับตาราง index เหล่านี้บอกเราว่าค่าเก็บอยู่ที่ไหน ตอนที่เราต้องการค้นหาค่าที่เกี่ยวข้องกับคีย์ เราเพียงแค่รัน hash function บนคีย์อีกครั้งและได้ค่าในเวลาใกล้เคียง constant time
Hash functions ยากมากในการออกแบบ มาดูตัวอย่าง:
สมมติเรามี hash function ดังนี้:
ตัวอย่าง
function modBy11(key) {
return key % 11;
}
และเราเริ่มรันฟังก์ชันนี้บนคู่คีย์-ค่าที่ต้องการเก็บ เช่น:
- (15, 20) - Hash code: 4
- (25, 39) - Hash code: 3
- (8, 55) - Hash code: 8
- (26, 84) - Hash code: 4
ที่นี่เราเห็นว่ามี collision เกิดขึ้น คือ ถ้าเราเก็บ 15 ก่อน แล้วเจอคีย์ 26 ด้วย hash function นี้ มันจะพยายามใส่ entry ในช่องเดียวกัน เรียกว่า collision และเราต้องมี collision handling mechanism มีอัลกอริธมที่ชัดเจนหลายตัว เช่น:
- Linear Probing: ค้นหาช่องว่างถัดไปใน array โดยดูช่องต่อไปจนกว่าจะเจอช่องว่าง ในตัวอย่าง ช่อง 4 ถูกใช้แล้ว เราสามารถใส่ในช่อง 5 ได้
- Separate Chaining: แต่ละตำแหน่งใน hash table จะเชื่อมกับ list เมื่อเกิด collision ให้ append คู่คีย์-ค่าที่ปลาย list นี้ อาจทำให้ search ใช้เวลานานขึ้นถ้า chain ยาวเกินไป
ตอนนี้เราเข้าใจ Hash Table และ collision resolution แล้ว มาสร้าง HashTable class กัน
เมธอดที่เราจะนำไปใช้
เราจะนำเมธอดเหล่านี้ไปใช้:
- put(key, value): เพิ่มคู่คีย์-ค่าใหม่ใน hash table
- get(key): ดึงค่าที่เกี่ยวข้องกับคีย์
- remove(key): ลบคู่คีย์-ค่าออกจากตาราง
- forEach(): วนลูปผ่านคู่คีย์-ค่าทั้งหมด
- static join(): เมธอด static รวม 2 hash tables ใหม่
