แฮชชิงคู่
แฮชชิ่งคู่ (อังกฤษ: Double Hashing) เป็นเทคนิคการเขียนโปรแกรมคอมพิวเตอร์ โดยใช้ตารางแฮชเพื่อป้องกันการชนกันของแฮช ในกรณีที่สองค่าที่แตกกต่างกันค้นหาคีย์แฮชเดียวกัน ซึ่งการแฮชสองชั้นเป็นเทคนิค Open Address การแฮชแบบสองชั้นถูกนำไปใช้ในคลังโปรแกรมที่นิยมมาก
หลักการทำงาน แก้
1. กำหนดความกว้างของตารางแฮช และ ค่าที่ใช้เพื่อเลื่อนค่าจากตำแหน่งเดิม
2. กำหนดข้อมูลที่เราต้องการ อย่างตัวอย่างจะกำหนดให้คือ 26, 54, 94, 17, 31, 77, 44 และ 51 ความกว้างของตาราง คือ 13 ค่าที่ใช้เพื่อเลื่อนค่าจากตำแหน่งเดิม คือ 5
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
None | None | None | None | None | None | None | None | None | None | None | None | None |
3. นำข้อมูลที่กำหนดให้มาคำนวณ โดย ข้อมูล ณ ตำแหน่งที่ Mod ความกว้างของตาราง ( ) จะได้ ซึ่งเป็นค่าในตำแหน่งของตารางแฮช แล้วทำต่อให้ครบทุกค่า
26 | 54 | 94 | 17 | 31 | 77 | 44 | 51 |
0 | 2 | 3 | 4 | 5 | 12 | 5 | 12 |
4. หาค่าการแฮชสองชั้นโดยใช้ ค่าที่ใช้เพื่อเลื่อนค่าจากตำแหน่งเดิม ลบกับ ข้อมูล ณ ตำแหน่งที่ Mod ค่าที่ใช้เพื่อเลื่อนค่าจากตำแหน่งเดิม ( ) จะได้
26 | 54 | 94 | 17 | 31 | 77 | 44 | 51 |
4 | 1 | 1 | 3 | 4 | 3 | 1 | 4 |
5. นำค่าที่ได้ในข้อที่ 3 ไปใส่ยังตารางในข้อที่ 2
5.1 ค่า 26 ตำแหน่งที่ 0
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
26 | None | None | None | None | None | None | None | None | None | None | None | None |
5.2 ค่า 54 ตำแหน่งที่ 2
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
26 | None | 54 | None | None | None | None | None | None | None | None | None | None |
5.3 ค่า 94 ตำแหน่งที่ 3
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
26 | None | 54 | 94 | None | None | None | None | None | None | None | None | None |
5.4 ค่า 17 ตำแหน่งที่ 4
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
26 | None | 54 | 94 | 17 | None | None | None | None | None | None | None | None |
5.5 ค่า 31 ตำแหน่งที่ 5
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
26 | None | 54 | 94 | 17 | 31 | None | None | None | None | None | None | None |
5.6 ค่า 77 ตำแหน่งที่ 12
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
26 | None | 54 | 94 | 17 | 31 | None | None | None | None | None | None | 77 |
5.7 ค่า 44 ตำแหน่งที่ 5 (กรณีค่าที่ตำแหน่งทับกัน จะนำค่าจากตารางในข้อที่ 4 มา บวกกับ ค่าตารางที่ 1 จะได้ 5 + 1 แล้ว Mod ด้วยความกว้างของตารางแฮช จะเท่ากับ 6)
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
26 | None | 54 | 94 | 17 | 31
44 |
None | None | None | None | None | None | 77 |
เมื่อได้ค่าเท่ากับ 6 แล้ว จะเป็นค่าตำแหน่งใหม่ที่ใส่ลงในตาราง
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
26 | None | 54 | 94 | 17 | 31 | None | None | None | None | None | None | 77 |
ค่า 51 ตำแหน่งที่ 12 (กรณีค่าที่ตำแหน่งทับกัน จะนำค่าจากตารางในข้อที่ 4 มา บวกกับ ค่าตารางที่ 1 จะได้ 12 + 4 แล้ว Mod ด้วยความกว้างของตารางแฮช จะเท่ากับ 3)
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
26 | None | 54 | 94 | 17 | 31 | 44 | None | None | None | None | None | 77
51 |
เมื่อได้ค่าเท่ากับ 3 แล้ว จะเป็นค่าตำแหน่งใหม่ที่ใส่ลงในตาราง แต่เมื่อกรณียังมีค่าในตารางให้นับเพิ่มอีก 3
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
26 | None | 54
51 |
94 | 17 | 31 | 44 | None | None | None | None | None | 77 |
กรณียังมีค่าในตารางให้นับเพิ่มอีก 3
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
26 | None | 54 | 94 | 17 | 31
51 |
44 | None | None | None | None | None | 77 |
กรณียังมีค่าในตารางให้นับเพิ่มอีก 3 แต่เมื่อเจอช่องที่ว่างเปล่า สามารถนำค่านั้นลงในตารางได้ทันที
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
26 | None | 54 | 94 | 17 | 31 | 44 | None | None | None | None | None | 77 |
ความซับซ้อนในการทำงาน แก้
จะสรุปได้ว่า Big(O) = O( ) Best Case คือ ขนาดของข้อมูลเป็น 0 มีค่าเดียว หรือข้อมูลมีค่ามากกว่าตาราง O(1) Worst Case คือ ขนาดของข้อมูลที่ให้ฟังก์ชั่นทำงานครบทั้งหมด O( )
ตัวอย่างการเขียนโปรแกรม แก้
def doubleHashing(data, hashTableSize, doubleHashSize):
if len(data) > hashTableSize:
return None
listOfHashTable = [None] * hashTableSize
for i in range(len(data)):
primaryHash = data[i] % hashTableSize
doubleHash = primaryHash
if listOfHashTable[primaryHash] is None:
listOfHashTable[primaryHash] = data[i]
else:
while listOfHashTable[doubleHash] is not None:
secondary = doubleHashSize - (data[i] % doubleHashSize)
doubleHash = (doubleHash + secondary) % hashTableSize
listOfHashTable[doubleHash] = data[i]
return listOfHashTable
อ้างอิง แก้
Mohit Makhija . Double Hashing Code2begin. Retrieved 1 May 2018.