Algorithms/double hashing

التقطيع المضاعف Double hashing هو تقنية تستخدم في التخلص من التضاربات الحاصلة في جداول التقطيع ذات العنونة المفتوحة. وتتلخص فكرة هذه التقنية في تطبيق دالة تقطيع ثانية على المفتاح في حال حدوث التضارب.

يمكن إجراء التقطيع المضاعف باستخدام:

(hash1(key) + i \* hash2(key)) % TABLE_SIZE

إذ تمثّل الدالتان hash1()‎ و hash2()‎ دالتي تقطيع وTABLE_SIZE هو حجم الجدول.

ويتكرّر التعبير أعلاه بزيادة قيمة i في كل مرة يحدث فيها التضارب.

هناك دالة تقطيع ثانية أخرى مشهورة هي:

hash2(key) = PRIME - (key % PRIME)‎

PRIME هو عدد أوّلي أصغر من TABLE_SIZE.

مزايا دالة التقطيع الثانية الجيدة

تكون دالة التقطيع الثانية جيدة إن امتازت بما يلي:

• يجب أن لا تكون نتيجة تطبيقها هي الصفر.
• التأكد من أنّ جميع الخلايا قابلة للسبر.

أمثلة

تعرض الشيفرة التالية طريقة استخدام دالة التقطيع الثانية في لغة C++‎:

#include <bits/stdc++.h> 
using namespace std; 

// حجم جدول التقطيع
#define TABLE_SIZE 13 

// يستخدم هذا الرقم في دالة التقطيع الثانية.
#define PRIME 7 

class DoubleHash 
{ 
	// مؤشر إلى المصفوفة التي تحتوي على جدول التقطيع 
	int *hashTable; 
	int curr_size; 

public: 

	// دالة تتحقّق من امتلاء جدول التقطيع
	bool isFull() 
	{ 

		// إن وصل حجم الجدول إلى الحد الأقصى
		return (curr_size == TABLE_SIZE); 
	} 

	// دالة لحساب قيمة التقطيع الأولى 
	int hash1(int key) 
	{ 
		return (key % TABLE_SIZE); 
	} 

	// دالة لحساب قيمة التقطيع الثانية 
	int hash2(int key) 
	{ 
		return (PRIME - (key % PRIME)); 
	} 

	DoubleHash() 
	{ 
		hashTable = new int[TABLE_SIZE]; 
		curr_size = 0; 
		for (int i=0; i<TABLE_SIZE; i++) 
			hashTable[i] = -1; 
	} 

	// دالة لإدراج مفتاح في جدول التقطيع
	void insertHash(int key) 
	{ 
		// إن كان جدول التقطيع ممتلئًا
		if (isFull()) 
			return; 

		// الحصول على الموقع من قيمة التقطيع الأولى
		int index = hash1(key); 

		// في حال حدوث تضارب
		if (hashTable[index] != -1) 
		{ 
			// الحصول على الموقع الثاني من قيمة التقطيع الثانية 
			int index2 = hash2(key); 
			int i = 1; 
			while (1) 
			{ 
				// الحصول على الموقع الجديد
				int newIndex = (index + i * index2) % 
										TABLE_SIZE; 

				// تخزين المفتاح إن لم يحدث تضارب 
				if (hashTable[newIndex] == -1) 
				{ 
					hashTable[newIndex] = key; 
					break; 
				} 
				i++; 
			} 
		} 

		// إن لم يحدث تضارب
		else
			hashTable[index] = key; 
		curr_size++; 
	} 

	// دالة لعرض جدول التقطيع
	void displayHash() 
	{ 
		for (int i = 0; i < TABLE_SIZE; i++) 
		{ 
			if (hashTable[i] != -1) 
				cout << i << " --> "
					<< hashTable[i] << endl; 
			else
				cout << i << endl; 
		} 
	} 
}; 

// اختبار الدوال السابقة
int main() 
{ 
	int a[] = {19, 27, 36, 10, 64}; 
	int n = sizeof(a)/sizeof(a[0]); 

	// إدراج مفاتيح في جدول التقطيع
	DoubleHash h; 
	for (int i = 0; i < n; i++) 
		h.insertHash(a[i]); 

	// عرض جدول التقطيع
	h.displayHash(); 
	return 0; 
}

تعطي الشيفرة السابقة المخرجات التالية:

0
1 --> 27
2
3
4
5 --> 10
6 --> 19
7
8
9
10 --> 36
11
12 --> 64

مصادر

• صفحة Double Hashing في توثيق بنى المعطيات في موقع GeeksforGeeks.