Hashingบทที่ 12Hash function

Hash Function แบบเข้าใจง่ายสำหรับผู้เริ่มต้น

บทนี้จะอธิบายแบบค่อยเป็นค่อยไปว่า ฟังก์ชันแฮช (Hash Function) ทำงานอย่างไร ทำไมจึงสำคัญมากกับตารางแฮช (Hash Table) และต้องออกแบบอย่างไรให้กระจายข้อมูลได้ดี

1. Hash Function คืออะไร

ฟังก์ชันแฮช (Hash Function) คือฟังก์ชันที่รับข้อมูลเข้า (input) เช่น key แบบสตริง (string) แล้วแปลงเป็นค่าตัวเลข (hash value) เพื่อใช้งานต่อในระบบ

ในบริบทของตารางแฮช (Hash Table) ค่าตัวเลขนี้มักถูกนำไปคำนวณเป็นตำแหน่งจัดเก็บข้อมูล (index)

2. หน้าที่ของ Hash Function ใน Hash Table

หน้าที่หลักคือเปลี่ยน key ให้กลายเป็นตัวเลขที่ใช้หา index ของ bucket เพื่อให้การเพิ่ม ค้นหา และลบข้อมูลทำได้เร็ว

ถ้าไม่มี Hash Function ตารางแฮช (Hash Table) จะไม่รู้ว่าควรเก็บหรือค้น key นั้นที่ตำแหน่งใด

3. หลักการคร่าว ๆ ของการแปลง key ให้กลายเป็นตำแหน่ง

รับ key เช่น "apple"
คำนวณ hash value จาก key
นำ hash value ไปทำ mod ด้วยขนาดตาราง
ได้ index สำหรับเข้าถึง bucket

4. ตัวอย่างง่าย ๆ เช่น ใช้ผลรวมรหัสตัวอักษรแล้ว mod ด้วยขนาดตาราง

สมมติ tableSize = 8 และ key = "apple" เราเอารหัสตัวอักษรมาบวกกันได้ 530 แล้วคำนวณ 530 % 8 = 2

ดังนั้น key นี้จะไปอยู่ที่ index 2

5. อธิบายทีละขั้นจาก input -> hash value -> index

input: key เช่น "banana"
hash value: ผลรวมรหัสตัวอักษร เช่น 609
index: 609 % 8 = 1
เก็บหรือค้นข้อมูลที่ bucket index 1

6. คุณสมบัติของ Hash Function ที่ดี

คำนวณได้เร็ว

ควรใช้เวลาน้อยในการแปลง key เป็นเลข เพราะจะถูกเรียกบ่อยมากใน insert/search/delete

กระจายข้อมูลได้ดี

key ที่แตกต่างกันควรถูกส่งไปหลาย index อย่างสมดุล เพื่อไม่ให้ bucket ใด bucket หนึ่งแน่นเกินไป

ลดโอกาสเกิดการชนกัน

ต้องออกแบบให้ key ต่างกันมีโอกาสได้ค่า hash ซ้ำกันน้อยลง แม้ไม่สามารถหลีกเลี่ยงได้ 100%

7. ตัวอย่าง hash function แบบง่ายสำหรับการเรียนรู้

Learning Hash FunctionJS

เวอร์ชันง่ายเพื่อเข้าใจแนวคิด ไม่ใช่เวอร์ชัน production

function learningHash(key, tableSize) {
  let sum = 0;

  for (let i = 0; i < key.length; i += 1) {
    sum += key.charCodeAt(i);
  }

  return sum % tableSize;
}

8. อธิบายว่าทำไม hash function แบบง่ายเกินไปอาจมีปัญหา

วิธีบวกรหัสตัวอักษรอย่างเดียวมีโอกาสให้ key ต่างกันได้ผลรวมเท่ากัน หรือกระจายไม่ดี เช่น key จำนวนมากไปกอง bucket เดียว

เมื่อกระจุกมาก ๆ ความเร็วของ Hash Table จะลดลงอย่างชัดเจน

9. ความสัมพันธ์ระหว่าง hash function กับ collision

การชนกัน (collision) คือ key คนละค่าได้ index เดียวกัน ซึ่งหลีกเลี่ยงไม่ได้ 100% เมื่อขนาดตารางมีจำกัด

Hash Function ที่ดีจะช่วย “ลดความถี่ collision” โดยกระจายข้อมูลให้สมดุลมากขึ้น

10. Pseudocode

Pseudocode: Simple Hashbash

แสดงขั้นตอน input -> hash value -> index

ฟังก์ชัน simpleHash(key, tableSize):
  sum = 0

  สำหรับอักขระแต่ละตัว c ใน key:
    sum = sum + รหัสตัวอักษรของ c

  hashValue = sum
  index = hashValue mod tableSize

  คืนค่า (hashValue, index)

11. ตัวอย่างโค้ด JavaScript พร้อมคำอธิบาย

JavaScript: simpleHashJS

ตัวอย่างที่ใช้ charCode + mod ตามแนวทางในบทเรียน

function simpleHash(key, tableSize) {
  let sum = 0;

  for (let i = 0; i < key.length; i += 1) {
    sum += key.charCodeAt(i);
  }

  const hashValue = sum;
  const index = hashValue % tableSize;

  return { hashValue, index };
}

const tableSize = 8;

console.log(simpleHash("apple", tableSize));
console.log(simpleHash("banana", tableSize));
console.log(simpleHash("papel", tableSize)); // อาจชนกับ key อื่นในบางกรณี

โค้ดนี้ทำ 3 ขั้นหลัก: (1) รวมรหัสตัวอักษรเป็น hash value (2) คำนวณ mod ด้วยขนาดตาราง (3) คืน index สำหรับเลือก bucket

12. ข้อดีของการใช้ hash function

ทำให้เข้าถึงข้อมูลแบบ key-based ได้เร็ว
ลดต้นทุนการค้นหาเมื่อเทียบกับการไล่ทีละตัว
เป็นแกนสำคัญของโครงสร้างอย่าง Map, Set และ dictionary

13. ข้อจำกัดหรือสิ่งที่ต้องระวัง

collision เกิดได้เสมอ ต้องมีวิธีจัดการ collision ควบคู่
ถ้า hash function กระจายไม่ดี ประสิทธิภาพลดลง
ต้องเลือกขนาดตารางและนโยบายขยายตารางให้เหมาะกับโหลดจริง

14. ย้ำว่า hash function ที่ใช้สอนกับที่ใช้จริงอาจซับซ้อนต่างกัน

ตัวอย่างในบทเรียนตั้งใจให้เข้าใจหลักการก่อน จึงใช้สูตรง่าย แต่ระบบจริงมักใช้ฟังก์ชันที่ออกแบบมาดีกว่าเพื่อกระจายข้อมูลให้สม่ำเสมอขึ้น

สรุป: เรียนรู้แนวคิดจากเวอร์ชันง่าย แล้วค่อยต่อยอดไปเวอร์ชัน production

15. สรุปท้ายบท

ฟังก์ชันแฮช (Hash Function) คือหัวใจของตารางแฮช (Hash Table) เพราะมันแปลง key เป็นตำแหน่งสำหรับเข้าถึงข้อมูลอย่างรวดเร็ว

สูตรจำง่าย: input key -> hash value -> index -> bucket

16. แบบฝึกหัด 3 ข้อ use playground

ข้อ 1: คำนวณ index ด้วยมือ

ให้ key = "cat" และ tableSize = 8 จงหา hash value และ index

แนวเฉลยย่อ: 99 + 97 + 116 = 312, ดังนั้น index = 312 % 8 = 0

ข้อ 2: เขียนฟังก์ชัน simpleHash

รับ key และ tableSize แล้วคืน index โดยใช้ charCode + mod

แนวเฉลยย่อ: วนลูปบวก charCode แล้ว return sum % tableSize

ข้อ 3: ลองสร้าง collision แบบง่าย

หา key อย่างน้อย 2 ค่า ที่เมื่อคำนวณกับ tableSize เดียวกันแล้วได้ index เท่ากัน

แนวเฉลยย่อ: ทดลองหลาย key แล้วพิมพ์ผล index เปรียบเทียบ เพื่อยืนยันว่าชนกันได้จริง

ไปลองใน Playground (Array Lab)

ภาพประกอบที่ควรรู้

ภาพ 1: input หลายค่าไหลเข้า hash function

ภาพแสดง input หลายค่าไหลเข้า hash function

ภาพ 2: ผลลัพธ์เป็นตัวเลขและ index

ภาพ 3: key ต่างกันควรถูกกระจายไปหลายตำแหน่ง

ภาพ 4: เปรียบเทียบกระจายดี กับกระจายไม่ดี

ภาพเปรียบเทียบ hash function ที่กระจายดีและไม่ดี

Hashingบทที่ 12Hash function

Hash Function แบบเข้าใจง่ายสำหรับผู้เริ่มต้น

1. Hash Function คืออะไร

2. หน้าที่ของ Hash Function ใน Hash Table

3. หลักการคร่าว ๆ ของการแปลง key ให้กลายเป็นตำแหน่ง

รับ key เช่น "apple"
คำนวณ hash value จาก key
นำ hash value ไปทำ mod ด้วยขนาดตาราง
ได้ index สำหรับเข้าถึง bucket

4. ตัวอย่างง่าย ๆ เช่น ใช้ผลรวมรหัสตัวอักษรแล้ว mod ด้วยขนาดตาราง

สมมติ tableSize = 8 และ key = "apple" เราเอารหัสตัวอักษรมาบวกกันได้ 530 แล้วคำนวณ 530 % 8 = 2

ดังนั้น key นี้จะไปอยู่ที่ index 2

5. อธิบายทีละขั้นจาก input -> hash value -> index

input: key เช่น "banana"
hash value: ผลรวมรหัสตัวอักษร เช่น 609
index: 609 % 8 = 1
เก็บหรือค้นข้อมูลที่ bucket index 1

6. คุณสมบัติของ Hash Function ที่ดี

คำนวณได้เร็ว

ควรใช้เวลาน้อยในการแปลง key เป็นเลข เพราะจะถูกเรียกบ่อยมากใน insert/search/delete

กระจายข้อมูลได้ดี

ลดโอกาสเกิดการชนกัน

7. ตัวอย่าง hash function แบบง่ายสำหรับการเรียนรู้

Learning Hash FunctionJS

เวอร์ชันง่ายเพื่อเข้าใจแนวคิด ไม่ใช่เวอร์ชัน production

function learningHash(key, tableSize) {
  let sum = 0;

  for (let i = 0; i < key.length; i += 1) {
    sum += key.charCodeAt(i);
  }

  return sum % tableSize;
}

8. อธิบายว่าทำไม hash function แบบง่ายเกินไปอาจมีปัญหา

เมื่อกระจุกมาก ๆ ความเร็วของ Hash Table จะลดลงอย่างชัดเจน

9. ความสัมพันธ์ระหว่าง hash function กับ collision

Hash Function ที่ดีจะช่วย “ลดความถี่ collision” โดยกระจายข้อมูลให้สมดุลมากขึ้น

10. Pseudocode

Pseudocode: Simple Hashbash

แสดงขั้นตอน input -> hash value -> index

ฟังก์ชัน simpleHash(key, tableSize):
  sum = 0

  สำหรับอักขระแต่ละตัว c ใน key:
    sum = sum + รหัสตัวอักษรของ c

  hashValue = sum
  index = hashValue mod tableSize

  คืนค่า (hashValue, index)

11. ตัวอย่างโค้ด JavaScript พร้อมคำอธิบาย

JavaScript: simpleHashJS

ตัวอย่างที่ใช้ charCode + mod ตามแนวทางในบทเรียน

function simpleHash(key, tableSize) {
  let sum = 0;

  for (let i = 0; i < key.length; i += 1) {
    sum += key.charCodeAt(i);
  }

  const hashValue = sum;
  const index = hashValue % tableSize;

  return { hashValue, index };
}

const tableSize = 8;

console.log(simpleHash("apple", tableSize));
console.log(simpleHash("banana", tableSize));
console.log(simpleHash("papel", tableSize)); // อาจชนกับ key อื่นในบางกรณี

12. ข้อดีของการใช้ hash function

ทำให้เข้าถึงข้อมูลแบบ key-based ได้เร็ว
ลดต้นทุนการค้นหาเมื่อเทียบกับการไล่ทีละตัว
เป็นแกนสำคัญของโครงสร้างอย่าง Map, Set และ dictionary

13. ข้อจำกัดหรือสิ่งที่ต้องระวัง

collision เกิดได้เสมอ ต้องมีวิธีจัดการ collision ควบคู่
ถ้า hash function กระจายไม่ดี ประสิทธิภาพลดลง
ต้องเลือกขนาดตารางและนโยบายขยายตารางให้เหมาะกับโหลดจริง

14. ย้ำว่า hash function ที่ใช้สอนกับที่ใช้จริงอาจซับซ้อนต่างกัน

สรุป: เรียนรู้แนวคิดจากเวอร์ชันง่าย แล้วค่อยต่อยอดไปเวอร์ชัน production

15. สรุปท้ายบท

สูตรจำง่าย: input key -> hash value -> index -> bucket

16. แบบฝึกหัด 3 ข้อ use playground

ข้อ 1: คำนวณ index ด้วยมือ

ให้ key = "cat" และ tableSize = 8 จงหา hash value และ index

แนวเฉลยย่อ: 99 + 97 + 116 = 312, ดังนั้น index = 312 % 8 = 0

ข้อ 2: เขียนฟังก์ชัน simpleHash

รับ key และ tableSize แล้วคืน index โดยใช้ charCode + mod

แนวเฉลยย่อ: วนลูปบวก charCode แล้ว return sum % tableSize

ข้อ 3: ลองสร้าง collision แบบง่าย

หา key อย่างน้อย 2 ค่า ที่เมื่อคำนวณกับ tableSize เดียวกันแล้วได้ index เท่ากัน

ไปลองใน Playground (Array Lab)

ภาพประกอบที่ควรรู้

ภาพ 1: input หลายค่าไหลเข้า hash function

ภาพ 2: ผลลัพธ์เป็นตัวเลขและ index

ภาพ 3: key ต่างกันควรถูกกระจายไปหลายตำแหน่ง

ภาพ 4: เปรียบเทียบกระจายดี กับกระจายไม่ดี

Data Structures & Algorithms

Hash Function แบบเข้าใจง่ายสำหรับผู้เริ่มต้น

1. Hash Function คืออะไร

2. หน้าที่ของ Hash Function ใน Hash Table

3. หลักการคร่าว ๆ ของการแปลง key ให้กลายเป็นตำแหน่ง

4. ตัวอย่างง่าย ๆ เช่น ใช้ผลรวมรหัสตัวอักษรแล้ว mod ด้วยขนาดตาราง

5. อธิบายทีละขั้นจาก input -> hash value -> index

6. คุณสมบัติของ Hash Function ที่ดี

7. ตัวอย่าง hash function แบบง่ายสำหรับการเรียนรู้

8. อธิบายว่าทำไม hash function แบบง่ายเกินไปอาจมีปัญหา

9. ความสัมพันธ์ระหว่าง hash function กับ collision

10. Pseudocode

11. ตัวอย่างโค้ด JavaScript พร้อมคำอธิบาย

12. ข้อดีของการใช้ hash function

13. ข้อจำกัดหรือสิ่งที่ต้องระวัง

14. ย้ำว่า hash function ที่ใช้สอนกับที่ใช้จริงอาจซับซ้อนต่างกัน

15. สรุปท้ายบท

16. แบบฝึกหัด 3 ข้อ use playground

ภาพประกอบที่ควรรู้

Loading

Data Structures & Algorithms

Hash Function แบบเข้าใจง่ายสำหรับผู้เริ่มต้น

1. Hash Function คืออะไร

2. หน้าที่ของ Hash Function ใน Hash Table

3. หลักการคร่าว ๆ ของการแปลง key ให้กลายเป็นตำแหน่ง

4. ตัวอย่างง่าย ๆ เช่น ใช้ผลรวมรหัสตัวอักษรแล้ว mod ด้วยขนาดตาราง

5. อธิบายทีละขั้นจาก input -> hash value -> index

6. คุณสมบัติของ Hash Function ที่ดี

7. ตัวอย่าง hash function แบบง่ายสำหรับการเรียนรู้

8. อธิบายว่าทำไม hash function แบบง่ายเกินไปอาจมีปัญหา

9. ความสัมพันธ์ระหว่าง hash function กับ collision

10. Pseudocode

11. ตัวอย่างโค้ด JavaScript พร้อมคำอธิบาย

12. ข้อดีของการใช้ hash function

13. ข้อจำกัดหรือสิ่งที่ต้องระวัง

14. ย้ำว่า hash function ที่ใช้สอนกับที่ใช้จริงอาจซับซ้อนต่างกัน

15. สรุปท้ายบท

16. แบบฝึกหัด 3 ข้อ use playground

ภาพประกอบที่ควรรู้