แฮชชิงคู่

แฮชชิ่งคู่ (อังกฤษ: 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 ความกว้างของตาราง ($k{\bmod {l}}ength$) จะได้ $26\mod 3=0$ ซึ่งเป็นค่าในตำแหน่งของตารางแฮช แล้วทำต่อให้ครบทุกค่า

26	54	94	17	31	77	44	51
0	2	3	4	5	12	5	12

4. หาค่าการแฮชสองชั้นโดยใช้ ค่าที่ใช้เพื่อเลื่อนค่าจากตำแหน่งเดิม ลบกับ ข้อมูล ณ ตำแหน่งที่ Mod ค่าที่ใช้เพื่อเลื่อนค่าจากตำแหน่งเดิม  ( $N-k\mod N$ ) จะได้ $5-k\mod 5$

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($n^{2}$) Best Case คือ ขนาดของข้อมูลเป็น 0 มีค่าเดียว หรือข้อมูลมีค่ามากกว่าตาราง O(1) Worst Case คือ ขนาดของข้อมูลที่ให้ฟังก์ชั่นทำงานครบทั้งหมด O($n^{2}$)

ตัวอย่างการเขียนโปรแกรม

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.