แฮชชิงคู่

แฮชชิ่งคู่ () เป็นเทคนิคการเขียนโปรแกรมคอมพิวเตอร์ โดยใช้ตารางแฮชเพื่อป้องกันการชนกันของแฮช ในกรณีที่สองค่าที่แตกกต่างกันค้นหาคีย์แฮชเดียวกัน ซึ่งการแฮชสองชั้นเป็นเทคนิค Open Address การแฮชแบบสองชั้นถูกนำไปใช้ในคลังโปรแกรมที่นิยมมาก

 หลักการทำงาน 
1. กำหนดความกว้างของตารางแฮช และ ค่าที่ใช้เพื่อเลื่อนค่าจากตำแหน่งเดิม

2. กำหนดข้อมูลที่เราต้องการ อย่างตัวอย่างจะกำหนดให้คือ 26, 54, 94, 17, 31, 77, 44 และ 51 ความกว้างของตาราง คือ 13 ค่าที่ใช้เพื่อเลื่อนค่าจากตำแหน่งเดิม คือ 5
0123456789101112NoneNoneNoneNoneNoneNoneNoneNoneNoneNoneNoneNoneNone
3. นำข้อมูลที่กำหนดให้มาคำนวณ โดย ข้อมูล ณ ตำแหน่งที่ Mod ความกว้างของตาราง () จะได้  ซึ่งเป็นค่าในตำแหน่งของตารางแฮช แล้วทำต่อให้ครบทุกค่า
26549417317744510234512512
4. หาค่าการแฮชสองชั้นโดยใช้ ค่าที่ใช้เพื่อเลื่อนค่าจากตำแหน่งเดิม ลบกับ ข้อมูล ณ ตำแหน่งที่ Mod ค่าที่ใช้เพื่อเลื่อนค่าจากตำแหน่งเดิม  (  ) จะได้ 
265494173177445141134314
5. นำค่าที่ได้ในข้อที่ 3 ไปใส่ยังตารางในข้อที่ 2

5.1 ค่า 26 ตำแหน่งที่ 0
012345678910111226NoneNoneNoneNoneNoneNoneNoneNoneNoneNoneNoneNone
5.2  ค่า 54 ตำแหน่งที่ 2
012345678910111226None54NoneNoneNoneNoneNoneNoneNoneNoneNoneNone
5.3 ค่า 94 ตำแหน่งที่ 3
012345678910111226None5494NoneNoneNoneNoneNoneNoneNoneNoneNone
5.4 ค่า 17 ตำแหน่งที่ 4
012345678910111226None549417NoneNoneNoneNoneNoneNoneNoneNone
5.5 ค่า 31 ตำแหน่งที่ 5
012345678910111226None54941731NoneNoneNoneNoneNoneNoneNone
5.6 ค่า 77 ตำแหน่งที่ 12
012345678910111226None54941731NoneNoneNoneNoneNoneNone77
5.7 ค่า 44 ตำแหน่งที่ 5 (กรณีค่าที่ตำแหน่งทับกัน จะนำค่าจากตารางในข้อที่ 4 มา บวกกับ ค่าตารางที่ 1 จะได้ 5 + 1 แล้ว Mod ด้วยความกว้างของตารางแฮช จะเท่ากับ 6)
012345678910111226None54941731

44NoneNoneNoneNoneNoneNone77
เมื่อได้ค่าเท่ากับ 6 แล้ว จะเป็นค่าตำแหน่งใหม่ที่ใส่ลงในตาราง
012345678910111226None54941731NoneNoneNoneNoneNoneNone77
ค่า 51 ตำแหน่งที่ 12 (กรณีค่าที่ตำแหน่งทับกัน จะนำค่าจากตารางในข้อที่ 4 มา บวกกับ ค่าตารางที่ 1 จะได้ 12 + 4 แล้ว Mod ด้วยความกว้างของตารางแฮช จะเท่ากับ 3)
012345678910111226None5494173144NoneNoneNoneNoneNone77

51
เมื่อได้ค่าเท่ากับ 3 แล้ว จะเป็นค่าตำแหน่งใหม่ที่ใส่ลงในตาราง แต่เมื่อกรณียังมีค่าในตารางให้นับเพิ่มอีก 3
012345678910111226None54

5194173144NoneNoneNoneNoneNone77
กรณียังมีค่าในตารางให้นับเพิ่มอีก 3
012345678910111226None54941731

5144NoneNoneNoneNoneNone77
กรณียังมีค่าในตารางให้นับเพิ่มอีก 3 แต่เมื่อเจอช่องที่ว่างเปล่า สามารถนำค่านั้นลงในตารางได้ทันที
012345678910111226None5494173144NoneNoneNoneNoneNone77

 ความซับซ้อนในการทำงาน 
จะสรุปได้ว่า 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.
หมวดหมู่:ขั้นตอนวิธีการค้นหา
หมวดหมู่:การแฮช