Skip to main content

hashing-and-hash-tables

การทำความเข้าใจเกี่ยวกับ Hashing และ Hash Tables​

Hashing และ Hash Tables เป็นเทคนิคที่ใช้ในการจัดเก็บข้อมูลเพื่อให้สามารถเข้าถึงได้อย่างมีประสิทธิภาพในเวลา O(1) ซึ่งเหมาะสำหรับการค้นหาหรือการจัดเก็บข้อมูลที่ต้องการการเข้าถึงอย่างรวดเร็ว

1. Hashing (การแฮช)​

Hashing คือกระบวนการที่ใช้ในการแปลงข้อมูลที่มีขนาดใหญ่ (เช่น ข้อความ หรือ อ็อบเจ็กต์) ให้กลายเป็นค่าตัวเลข (เรียกว่า hash code หรือ hash value) ที่มีขนาดเล็กและเหมาะสม ซึ่งสามารถใช้ในการระบุตำแหน่งที่เหมาะสมในโครงสร้างข้อมูล เช่น Hash Table.

วิธีการทำงานของ Hashing:​

  1. แปลงข้อมูลเป็นคีย์: ข้อมูลใดๆ (เช่น ชื่อผู้ใช้ หมายเลขประจำตัว) จะถูกแปลงเป็นตัวเลข (hash code) โดยใช้ ฟังก์ชันแฮช (hash function)
  2. การกำหนดตำแหน่งในการจัดเก็บ: ตัวเลขที่ได้จากฟังก์ชันแฮชจะถูกใช้เป็นดัชนีในการจัดเก็บข้อมูลในโครงสร้างข้อมูล
  3. การเข้าถึงข้อมูล: เมื่อเราต้องการเข้าถึงข้อมูลที่เก็บไว้ในโครงสร้างข้อมูล ก็จะใช้ค่าของคีย์เพื่อคำนวณตำแหน่งใน Hash Table และดึงข้อมูลออกมา

ฟังก์ชันแฮช (Hash Function):​

ฟังก์ชันแฮชจะรับข้อมูลเข้าและแปลงเป็นค่าผลลัพธ์ที่เป็นตัวเลข โดยจะต้องมีคุณสมบัติดังนี้:

  • ความเร็ว: ต้องสามารถคำนวณได้อย่างรวดเร็ว
  • การกระจายตัว: ค่าผลลัพธ์ต้องกระจายตัวได้ดีเพื่อหลีกเลี่ยงปัญหาการชนกันของคีย์ (Collisions)

ตัวอย่างฟังก์ชันแฮชที่ง่ายที่สุดคือการใช้การหารค่าตัวเลขโดยใช้ตัวหาร (modulus):

hash_value = key % table_size

ตัวอย่างเช่น หากมีค่า key = 15 และ table_size = 10, ผลลัพธ์ของการแฮชจะเป็น 15 % 10 = 5

2. Hash Tables (แฮชเทเบิล)​

Hash Table (หรือ Hash Map) เป็นโครงสร้างข้อมูลที่ใช้ Hashing ในการจัดเก็บข้อมูล โดยใช้ คีย์ เพื่อค้นหาหรือเข้าถึงข้อมูลที่เก็บไว้

โครงสร้างของ Hash Table:​

  • Buckets (หรือ Slots): ใช้สำหรับเก็บข้อมูล โดยแต่ละ bucket จะเก็บค่าที่สัมพันธ์กับคีย์
  • Hash Function: ใช้ในการคำนวณตำแหน่งของข้อมูลใน hash table โดยการแปลงคีย์เป็นค่า hash
  • Collision Handling: เมื่อมีการชนกัน (สองคีย์ได้ค่า hash เหมือนกัน) จะต้องมีวิธีจัดการการชนกัน เช่น การใช้ Chaining หรือ Open Addressing

วิธีการทำงานของ Hash Table:​

  1. การแทรกข้อมูล (Insert): คำนวณตำแหน่งของข้อมูลโดยใช้ฟังก์ชันแฮช จากนั้นเก็บข้อมูลในตำแหน่งนั้น
  2. การค้นหาข้อมูล (Search): คำนวณตำแหน่งของข้อมูลจากคีย์ แล้วค้นหาข้อมูลใน bucket นั้น
  3. การลบข้อมูล (Delete): คำนวณตำแหน่งของข้อมูลจากคีย์ แล้วลบข้อมูลใน bucket นั้น

ปัญหาที่อาจเกิดขึ้น:​

  • Collisions (การชนกัน): เมื่อมีการแฮชคีย์สองตัวที่ได้ค่า hash เดียวกัน (มีตำแหน่งเดียวกันใน hash table)
    • Chaining: ใช้รายการเชื่อมโยง (Linked List) เก็บข้อมูลที่ชนกันใน bucket เดียวกัน
    • Open Addressing: ค้นหาตำแหน่งที่ว่างใน hash table เมื่อเกิดการชนกัน เช่น Linear Probing, Quadratic Probing หรือ Double Hashing

ตัวอย่างโครงสร้าง Hash Table:​

สมมุติว่าเรามีข้อมูล:

  • คีย์: apple, banana, cherry
  • ค่าที่ต้องการเก็บ: 10, 20, 30

ฟังก์ชันแฮชอาจคำนวณเป็นดังนี้:

  • apple -> คีย์แฮช 3
  • banana -> คีย์แฮช 1
  • cherry -> คีย์แฮช 0

ดังนั้น Hash Table อาจมีลักษณะดังนี้:

Index 0 -> cherry -> 30
Index 1 -> banana -> 20
Index 3 -> apple -> 10

3. วิธีการจัดการกับการชนกัน (Collision Handling)​

1. Chaining​

ในวิธีนี้ การชนกันของคีย์จะถูกจัดเก็บในลิสต์ที่เชื่อมโยงในแต่ละ bucket:

  • หากมีการชนกันในตำแหน่งเดียวกัน (เช่น มีคีย์ที่แฮชออกมาเหมือนกัน), ข้อมูลจะถูกเก็บในลิสต์ที่เชื่อมโยง (Linked List) ใน bucket นั้น
  • ข้อดี: สามารถจัดเก็บข้อมูลได้มากขึ้นในแต่ละ bucket
  • ข้อเสีย: ต้องการพื้นที่หน่วยความจำเพิ่มเติมสำหรับลิสต์ที่เชื่อมโยง

2. Open Addressing​

ในวิธีนี้ เมื่อเกิดการชนกัน ข้อมูลจะถูกเก็บในตำแหน่งที่ว่างใกล้ๆ:

  • Linear Probing: หากเกิดการชนกันในตำแหน่งที่คำนวณได้, จะลองไปที่ตำแหน่งถัดไปที่ว่าง
  • Quadratic Probing: การค้นหาตำแหน่งว่างจะทำโดยใช้ฟังก์ชันกำลังสอง
  • Double Hashing: การใช้ฟังก์ชันแฮชสองครั้งในการคำนวณตำแหน่งถัดไป

4. ตัวอย่างการใช้งาน Hash Table (Python)​

โค้ดตัวอย่างการใช้งาน Hash Table ด้วยการใช้ Dictionary ใน Python:​

# สร้าง Hash Table (Dictionary)
hash_table = {}

# การแทรกข้อมูล
hash_table["apple"] = 10
hash_table["banana"] = 20
hash_table["cherry"] = 30

# การค้นหาข้อมูล
print(hash_table["apple"])  # ผลลัพธ์: 10

# การลบข้อมูล
del hash_table["banana"]

# การตรวจสอบข้อมูล
print("banana" in hash_table)  # ผลลัพธ์: False

ผลลัพธ์:

10
False

การจัดการการชนกันใน Hash Table:​

หากมีการชนกัน เช่น มีคีย์ที่แฮชออกมาเหมือนกัน (collision) ในการแทรกข้อมูล สามารถเลือกใช้ Chaining หรือ Open Addressing เพื่อจัดการการชนกันได้

5. ข้อดีและข้อเสียของ Hash Tables​

ข้อดี:​

  • การเข้าถึงข้อมูลเร็ว: การเข้าถึงข้อมูลใน Hash Table โดยใช้คีย์สามารถทำได้ในเวลา O(1) (เฉลี่ย)
  • การค้นหาที่มีประสิทธิภาพ: การค้นหาค่าใน Hash Table มีประสิทธิภาพสูง
  • การจัดการข้อมูลที่ไม่ต้องเรียงลำดับ: ไม่จำเป็นต้องใช้ฟังก์ชันการเรียงลำดับในการจัดเก็บข้อมูล

ข้อเสีย:​

  • การจัดการการชนกัน: การชนกัน (collision) อาจทำให้การเข้าถึงข้อมูลช้าลง
  • การใช้หน่วยความจำ: อาจต้องการพื้นที่หน่วยความจำเพิ่มเติมในการจัดเก็บข้อมูลและการจัดการการชนกัน
  • ไม่เหมาะสำหรับข้อมูลที่มีลำดับ (Order): หากข้อมูลมีความสำคัญในการเรียงลำดับ Hash Table อาจไม่เหมาะสม

สรุป:​

  • Hashing เป็นกระบวนการแปลงข้อมูลให้เป็นค่าตัวเลขที่สามารถใช้ในการเข้าถึงข้อมูลใน Hash Table ได้อย่างรวดเร็ว
  • Hash Table เป็นโครงสร้างข้อมูลที่ใช้ Hashing เพื่อจัดเก็บและค้นหาข้อมูลโดยใช้คีย์
  • การจัดการการชนกันใน Hash Table สามารถทำได้โดยใช้ Chaining หรือ Open Addressing
  • Hash Table เป็นโครงสร้างข้อมูลที่มีประสิทธิภาพสูงในการค้นหาและจัดเก็บข้อมูลที่ไม่จำเป็นต้องเรียงลำดับ