عرض مصدر Algorithms/double hashing

<noinclude>{{DISPLAYTITLE:التقطيع المضاعف}}</noinclude>
التقطيع المضاعف Double hashing هو تقنية تستخدم في التخلص من التضاربات الحاصلة في جداول التقطيع ذات العنونة المفتوحة. وتتلخص فكرة هذه التقنية في تطبيق دالة تقطيع ثانية على المفتاح في حال حدوث التضارب.

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

<code>(hash1(key) + i \* hash2(key)) % TABLE_SIZE</code>

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

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

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

<code>hash2(key) = PRIME - (key % PRIME)‎</code>

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

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

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

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

== أمثلة ==

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

<source lang="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; 
} 
</source>
تعطي الشيفرة السابقة المخرجات التالية:

<source lang="text">0
1 --> 27
2
3
4
5 --> 10
6 --> 19
7
8
9
10 --> 36
11
12 --> 64</source>

== انظر أيضًا ==
* [[Algorithms/hashing|التقطيع]]

== مصادر ==

* صفحة [https://www.geeksforgeeks.org/double-hashing/ Double Hashing] في توثيق بنى المعطيات في موقع GeeksforGeeks.

[[تصنيف: الخوارزميات]]
[[تصنيف: بنى المعطيات]]
[[تصنيف:التقطيع]]