บทนำ
Hashing (การแฮช) คือกระบวนการสร้างค่าจากข้อความหรือรายการตัวเลขโดยใช้ฟังก์ชันทางคณิตศาสตร์ที่เรียกว่า Hash Function มี Hash Functions หลายตัวที่ใช้คีย์ (Keys) แบบตัวเลขหรือตัวอักษรผสมตัวเลข (Alphanumeric) Hash Functions ที่แตกต่างกันมีดังนี้:
Hash Functions (ฟังก์ชันแฮช)
ต่อไปนี้คือ Hash Functions บางตัว:
Division Method (วิธีการหาร)
นี่คือวิธีที่ง่ายที่สุดในการสร้าง Hash Function ฟังก์ชันแฮชสามารถอธิบายได้ดังนี้:
h(k) = k mod n
ที่นี่ h(k) คือค่าแฮชที่ได้จากการหารค่าคีย์ k ด้วยขนาดของ Hash Table n โดยใช้เศษเหลือ (Remainder) เหมาะสมที่ n เป็นจำนวนเฉพาะ (Prime Number) เพราะทำให้คีย์กระจายตัวอย่างสม่ำเสมอ (Uniform) มากขึ้น
ตัวอย่าง Division Method:
k=1276 n=10 h(1276) = 1276 mod 10 = 6
ค่าแฮชที่ได้คือ 6
ข้อเสียของ Division Method คือ คีย์ที่เรียงติดกัน (Consecutive Keys) จะ map ไปยังค่าแฮชที่ติดกันใน Hash Table ทำให้ประสิทธิภาพต่ำ
Multiplication Method (วิธีการคูณ)
Hash Function ที่ใช้สำหรับ Multiplication Method คือ:
h(k) = floor( n( kA mod 1 ) )
ที่นี่ k คือคีย์ และ A สามารถเป็นค่าคงที่ (Constant) ใดๆ ระหว่าง 0 ถึง 1 ทั้ง k และ A ถูกคูณกัน และส่วนนำทศนิยม (Fractional Part) ถูกแยกออกมา จากนั้นคูณกับ n เพื่อให้ได้ค่าแฮช
ตัวอย่าง Multiplication Method:
k=123 n=100 A=0.618033 h(123) = 100 (123 * 0.618033 mod 1) = 100 (76.018059 mod 1) = 100 (0.018059) = 1
ค่าแฮชที่ได้คือ 1
ข้อดีของ Multiplication Method คือ ทำงานกับค่า A ใดๆ ได้ แม้ว่าบางค่าจะเชื่อว่าดีกว่าอื่นๆ
Mid Square Method (วิธีกำลังสองกลาง)
Mid Square Method เป็น Hash Function ที่ดีมาก 関与ถึงการยกกำลังสองของค่าคีย์ (Square the Key) แล้วดึงหลักกลาง (Middle Digits) ออกมาเป็นค่าแฮช จำนวนหลัก r สามารถตัดสินใจได้ตามขนาดของ Hash Table
ตัวอย่าง Mid Square Method:
สมมติ Hash Table มี 100 ช่องจดจำ (Memory Locations) ดังนั้น r=2 เพราะต้องการสองหลักเพื่อ map คีย์ไปยังช่องจดจำ
k = 50 k*k = 2500 h(50) = 50 ค่าแฮชที่ได้คือ 50
Hash Tables (ตารางแฮช)
Hash Table เป็นโครงสร้างข้อมูล (Data Structure) ที่ map คีย์ไปยังค่า (Values) ใช้ Hash Function คำนวณ Index สำหรับคีย์ข้อมูล และเก็บคีย์ไว้ที่ Index นั้น
ตัวอย่าง Hash Table:
ลำดับคีย์ที่ต้องเก็บใน Hash Table คือ:
35 50 11 79 76 85
Hash Function h(k) ที่ใช้คือ:
h(k) = k mod 10
ด้วย Linear Probing ค่าจะถูกเก็บใน Hash Table ดังนี้:
