แฮชชิงคู่

จากวิกิพีเดีย สารานุกรมเสรี
ไปยังการนำทาง ไปยังการค้นหา

แฮชชิ่งคู่ (อังกฤษ: 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.