Algorithms/hashing

لنفترض أنّنا نرغب في تصميم نظام لترتيب سجلات الموظفين باستخدام أرقام الهواتف، ونرغب في تنفيذ الاستعلامات التالية بكفاءة عالية:

1. إدراج رقم الهاتف والمعلومات المرتبطة به.
2. البحث عن رقم الهاتف وجلب المعلومات المرتبطة به.
3. حذف رقم الهاتف وجميع المعلومات المرتبطة به.

يمكن استخدام بنى المعطيات التالي للتعامل مع معلومات الموظفين:

1. مصفوفة من أرقام الهواتف والسجلّات.
2. قوائم مترابطة من أرقام الهواتف والسجلّات.
3. شجرة بحث ثنائية متوازنة تحتوي على أرقام الهواتف كمفاتيح.
4. جدول وصول مباشر Direct Access Table.

تفرض المصفوفات والقوائم المترابطة إجراء عملية البحث بطريقة خطّية تستهلك كثيرًا من الوقت. إن استخدمنا المصفوفات وحافظنا على ترتيب البيانات في المصفوفة، فإنّ بالإمكان البحث عن رقم الهاتف المطلوب بتعقيد زمني يبلغ O(Logn)‎ وباستخدام البحث الثنائي، ولكن عمليات الإضافة والحذف ستكون مكلفة وذلك لضرورة الاحتفاظ بترتيب العناصر بعد إجراء هاتين العمليتين.

يمكن الحصول على عمليات بحث وإدراج وحذف ذات سرعة مقبولة باستخدام شجرة البحث الثنائية المتوازنة وبتعقيد زمني يبلغ O(Logn)‎.

هناك حل آخر وهو استخدام جدول الوصول المباشر حيث ننشئ مصفوفة كبيرة ونستخدم أرقام الهواتف كفهارس في هذه المصفوفة. إن لم يكن هناك رقم للهاتف فلن يكون هناك سجل، وبخلاف ذلك يخزّن العنصر في المصفوفة مؤشرًا إلى السجلات المرتبطة برقم الهاتف. التعقيد الزمني لهذه الطريقة هو الأفضل بين جميع الطرق إذ يبلغ O(1)‎ لجميع العمليات. فعلى سبيل المثال لإدراج رقم الهاتف سننشئ سجلًا يتضمّن التفاصيل المرتبطة برقم الهاتف ونستخدم رقم الهاتف كفهرس لتخزين المؤشر إلى السجل الذي أنشأناه في الجدول.

ولكن لهذه الطريقة الكثير من المحددات والمشاكل العملية، ففي البداية تحتاج هذه الطريقة إلى مساحة كبيرة جدًّا، فإن كان رقم الهاتف مكوّنًا من n من الأعداد فإنّنا سنحتاج إلى O(m * 10n)‎ من المساحة للجدول وتمثّل m حجم المؤشر في السجلّ. المشكلة الأخرى هي أنّ العدد الصحيح قد لا يخزّن n من الأعداد في عدد من لغات البرمجة.

لا يمكن استخدام جدول الوصول المباشر دائمًا نظرًا لوجود هذه المشاكل؛ لذا يمكن استخدام التقطيع Hashing في مثل هذه الحالات وبأداء يفوق أداء المصفوفات والقوائم المترابطة وأشجار البحث الثنائية المتوازنة بكثير؛ إذ يبلغ التعقيد الزمني لعملية البحث O(1)‎ كمعدل ويبلغ O(n)‎ في أسوأ الأحوال.

يعدّ التقطيع تحسينًا لجدول الوصول المباشر، إذ تستخدم دالة تقطيع تحوّل رقم الهاتف المعطى أو أي مفتاح آخر إلى رقم أصغر وتستخدم هذ الرقم كفهرس في جدول يدعى جدول التقطيع hash table.

دالة التقطيع

تحوّل هذه الدالة رقم الهاتف الكبير المعطى إلى رقم صحيح أصغر، ويُستخدم الرقم الجديد في جدول التقطيع، ولتكون دالة التقطيع دالة جيّدة يجب أن تتصف بما يلي:

1. قادرة على إجراء عملية الحساب بفعالية.
2. قادرة على توزيع المفاتيح بانتظام، بمعنى أن يكون كل موقع في الجدول متاحًا لكل مفتاح وبصورة متساوية.

على سبيل المثال، تعدّ دالة التقطيع دالة سيئة إن أخذت أول ثلاثة أعداد في رقم الهاتف، ولكن يمكن تحسين هذه الدالة بجعلها تأخذ آخر ثلاثة أعداد من رقم الهاتف، وهذا لا يعني أنّ هذه الدالة هي أفضل دالة تقطيع في هذا الصدد، بل يمكن اتباع طرق أخرى لجعلها دالة أفضل.

جدول التقطيع

مصفوفة تخزّن مؤشرات إلى السجلات المرتبطة برقم هاتف معين. لا يحمل العنصر في جدول التقطيع أيّ قيمة إن لم يكن هناك قيمة مقطّعة باستخدام دالة التقطيع لرقم هاتف معين تساوي الفهرس الخاص بذلك العنصر.

تطبيقات عملية التقطيع

تتيح عملية التقطيع إجراء عمليات البحث والإدراج والحذف بمعدل زمني ثابت، ولهذا يعدّ التقطيع أحد أكثر بنى المعطيات استخدامًا، وهناك الكثير من الأمثلة مثل إيجاد العناصر المميزة distinct elements وإحصاء عدد المرات التي يتكرر فيها عنصر معيّن، وإيجاد العناصر المكرّرة وغيرها.

وهناك العديد من التطبيقات لعملية التقطيع، ومن بينها عمليات تعمية العملات الرقمية في وقتنا الحاضر، وفيما يلي بعض التطبيقات المعروفة:

• خلاصة الرسالة Message Digest
• التحقق من كلمة المرور
• بنى المعطيات (لغات البرمجة)
• عمليات التصريف Compiler Operation
• خوارزمية رابين-كارب.
• ربط اسم الملف بالمسار.

خلاصة الرسالة: خلاصة الرسالة هي إحدى تطبيقات دوال هاش التشفيرية Cryptographic hash Functions، وهي دوال تنتج مخرجات يكون من شبه المستحيل الوصول إلى المدخلات المفضية إليها. تسمّى هذه الخاصية اللاانعكاسية irreversibility.

لنفترض مثلًا أنّك ترغب في تخزين ملفاتك في إحدى خدمات التخزين السحابي المتاحة في الوقت الحاضر. يجب عليك أن تحرص على عدم قدرة أيّ طرفٍ ثالثٍ على التلاعب بملفاتك، ويمكنك القيام بذلك عن طريق حساب "الهاش hash" لكل ملف بواسطة خوارزمية هاش التشفيرية، ومن أكثر هذه الخوارزميات شيوعًا هي خوازمية SHA256. يصل أقصى طول للهاش الذي تنتجه هذه الخوارزمية إلى 32 بايتًا، وهذا يعني أنّه لا مشكلة في حساب قيمة الهاش لعدد كبير من الملفات، ويمكن تخزين هذه القيم في جهازك المحليّ.

بعد حساب قيم الهاش لجميع ملفاتك وللتأكد من عدم تلاعب أي طرف ثالث بها، يمكنك تحميل أيٍّ من الملفات وحساب قيمة الهاش مجدّدًا والتأكد من مطابقتها للقيمة السابقة، وبهذه الطريقة يمكنك اكتشاف أيّ تلاعبٍ في ملفّاتك؛ إذ إنّ من شبه المستحيل التعديل على الملف دون تغيير قيمة الهاش الخاصّة به.

التحقق من كلمات المرور

تستخدم دوال الهاش التشفيرية بصورة واسعة في التحقق من كلمات المرور، فعند استخدام موقع إلكتروني يتطلّب إنشاء حساب وتسجيل الدخول فيه يُدخل المستخدم عنوان بريده الإلكتروني وكلمة المرور لإثبات أنّ الحساب الذي يحاول الوصول إليه تابع له بالفعل. عند إدخال كلمة المرور تحسب قيمة الهاش لكلمة المرور وترسل إلى الخادوم لغرض مطابقتها مع كلمة المرور المخزّنة في الخادوم. تخزّن كلمات المرور في الخادوم كقيم هاش، وذلك لإرسال كلمة المرور من العميل إلى الخادوم دون تعرضها للسرقة.

بنى المعطيات (لغات البرمجة)

تمتلك العديد من لغات البرمجة جداول تقطيع كبنى معطيات، والفكرة الرئيسية هي في إنشاء زوج مفتاح-قيمة حيث يكون المفتاح قيمة فريدة، ويمكن للقيمة أن تكون متشابهة لمفاتيح مختلفة. يمكن الاستفادة من بنى المعطيات هذه في لغة C++‎ في المجموعات غير المرتبة unorderd_set و unordered_map، وفي HashSet و HashMap في لغة جافا، و dict في لغة بايثون.

عمليات التصريف:

يجري التعامل مع الكلمات المفتاحية في لغات البرمجة بطريقة مختلفة عن المعرّفات، وللتمييز بين الكلمات المفتاحية (مثل ifو elseو forو return وغيرها) والمعرّفات الأخرى بصورة صحيحة وتصريف البرنامج يخزّن المصرّف جميع الكلمات المفتاحية في مجموعة وينفّذ ذلك باستخدام جدول التقطيع.

خوارزمية رابن كارب Rabin-karp:

خوارزمية رابن كارب هي من أشهر التطبيقات لعملية التقطيع، وهي خوارزمية للبحث في النصوص تستخدم عملية التقطيع للعثور على مجموعة من الأنماط في سلسلة نصية معينة، ومن أهمّ التطبيقات العملية لهذه الخوارزمية هي كشف عمليات السرقة والانتحال plagiarism.

ربط اسم الملف بالمسار

يتكوّن الملف في نظام الملفات من جزئين أساسين هما اسم الملف file_name ومساره file_path، ولكي يحفظ نظام الملفات العلاقة التي تربط بين اسم الملف ومساره فإنّه يستخدم دالة ربط map(file_name, file_path)‎ تنفّذ بواسطة جداول التقطيع.

التضارب

تنتج دالة التقطيع عددًا صغيرًا من مفتاح يتضمّن عددًا صحيحًا كبيرًا أو سلسلة نصية؛ لهذا يظهر احتمال وجود مفتاحين يعطيان القيمة ذاتها. وتسمّى الحالة التي يرتبط فيها مفتاح مضاف حديثًا بموقع مشغول بعنصر آخر في جدول التطبيق بحالة التضارب ويجب التعامل معها والتخلص منها باستخدام بعض التقينات الخاصة.

واحتمال وقوع التضارب عالية في الواقع، وحتّى عند استخدام الجداول الكبيرة، ففي مفارقة عيد الميلاد Birthday Paradox ومع وجود 23 شخصًا فقط، فإنّ احتمالية وجود شخصين لهما عيد الميلاد نفسه هي 50%.

معالجة حالات التضارب

لما كان عمل دالة التقطيع هو إعطاء رقم صغير مقابل مفتاح كبير، فمن المحتمل أن يحمل مفتاحان القيمة ذاتها. تدعى الحالة التي يُدرج فيها مفتاح جديد في موقع مشغول بمفتاح آخر في جدول التقطيع بحالة التضارب، ويمكن التعامل مع هذه الحالة بعدد من التقنيات منها:

• الربط Chaining: تتلخص الفكرة في جعل كل خلية في جدول التقطيع تؤشر إلى قائمة مترابطة للسجلات التي تمتلك نفس قيمة دالة التقطيع. عملية الربط بسيطة ولكنّها تتطلب مساحة إضافية في الذاكرة خارج جدول التقطيع.
• العنونة المفتوحة Open Addressing: تخزّن جميع العناصر في هذه العملية في جدول التقطيع نفسه، وقد يمتلك العنصر في الجدول سجّلًا أو لا يمتلك واحدًا، وعند البحث عن عنصر معين نتفحّص الجدول خلية خلية بحثًا عن العنصر المطلوب، فإن لم نفلح في العثور عليه فهذا يعني أنّ العنصر غير موجود في جدول التقطيع.

الربط المتسلسل المنفصل

في هذه الطريقة تشير كل خلية في جدول التقطيع إلى قائمة مترابطة تحتوي على سجلات تمتلك نفس قيمة التقطيع.

لنفترض أنّ لدينا دالة تقطيع بسيطة مثل key mod 7 وتسلسل المفاتيح ‎50, 700, 76, 85, 92, 73, 101‎.

نقاط القوة ونقاط الضعف

نقاط القوة

1. سهلة التنفيذ.
2. لا يمتلئ جدول التقطيع إطلاقًا، ويمكن إضافة المزيد من العناصر إلى السلسلة.
3. أقل تحسّسًا لدالة التقطيع أو عوامل التحميل load factors.
4. تستخدم بكثرة عندما يكون عدد المفاتيح وتواتر إضافتها وحذفها مجهولًا.

نقاط الضعف

1. يكون أداء الذاكرة المخبئية في عملية الربط المتسلسل سيئًا وذلك لأنّ المفاتيح تخزّن باستخدام القوائم المترابطة. تقدّم طريقة العنونة المفتوحة أداءً أفضل في الذاكرة المخبئية إذ يُخزّن كل شيء في الجدول عينه.
2. يؤدي استخدام هذه الطريقة إلى إهدار بعض المساحة؛ وذلك لأنّ جزءًا من جدول التقطيع يبقى فارغًا.
3. إن أصبحت السلسلة طويلة فإنّ التعقيد الزمني لعملية البحث سيبلغ في أسوء حالاته O(n)‎.
4. تستهلك القوائم المترابطة مساحة إضافية.

أداء عملية الربط

يمكن تقييم أداء عملية التقطيع بافتراض أنّ احتمالية تقطيع أيّ مفتاح وإدراجه في جدول التقطيع متساوية لجميع المفاتيح (التقطيع البسيط المنتظم simple uniform hashing).

لو افترضنا أنّ:

m = عدد المواقع في جدول التقطيع.

n= عدد المفاتيح المراد إدراجها في جدول التقطيع.

فإنّ معامل التحميل ‎α = n/m‎.

والوقت المتوقّع لعملية البحث = ‎O(1+α)‎.

والوقت المتوقّع لعمليتي الإدراج والحذف = ‎O(1+α)‎.

وسيبلغ التعقيد الزمني لعمليات البحث والإدراج والحذف O(1)‎ إن كانت قيمة α تساوي O(1)‎.

أمثلة

يعرض المثال التالي كيفية معالجة حالة التضارب بواسطة طريقة السلسلة المنفصلة في لغة C++‎:

#include<iostream> 
#include <list> 
using namespace std; 

class Hash 
{ 
	int BUCKET; // No. of buckets 

	// مؤشر إلى مصفوفة 
    // Pointer to an array containing buckets 
	list<int> *table; 
public: 
	Hash(int V); // دالة بانية 

	// تدرج هذه الدالة مفتاحًا في جدول التقطيع 
	void insertItem(int x); 

	// تحذف هذه الدالة مفتاحًا من جدول التقطيع
	void deleteItem(int key); 

	// دالة تقطيع تربط القيم بالمفاتيح
	int hashFunction(int x) { 
		return (x % BUCKET); 
	} 

	void displayHash(); 
}; 

Hash::Hash(int b) 
{ 
	this->BUCKET = b; 
	table = new list<int>[BUCKET]; 
} 

void Hash::insertItem(int key) 
{ 
	int index = hashFunction(key); 
	table[index].push_back(key); 
} 

void Hash::deleteItem(int key) 
{ 
// الحصول على موقع المفتاح في جدول التقطيع 
int index = hashFunction(key); 

// الحصول على المفتاح في الموقع المعطى ضمن المصفوفة
list <int> :: iterator i; 
for (i = table[index].begin(); 
		i != table[index].end(); i++) { 
	if (*i == key) 
	break; 
} 

// إن كان المفتاح موجودًا في جدول التقطيع فسنحذفه
if (i != table[index].end()) 
	table[index].erase(i); 
} 

// دالة لعرض جدول التقطيع
void Hash::displayHash() { 
for (int i = 0; i < BUCKET; i++) { 
	cout << i; 
	for (auto x : table[i]) 
	cout << " --> " << x; 
	cout << endl; 
} 
} 

// اختبار الدوال السابقة
int main() 
{ 
// مصفوفة تتضمن المفاتيح التي ستضاف إلى الجدول
int a[] = {15, 11, 27, 8, 12}; 
int n = sizeof(a)/sizeof(a[0]); 

// تدرج الدالة المفاتيح في جدول التقطيع
Hash h(7); 
    // عدد العناصر في جدول التقطيع هو 7
for (int i = 0; i < n; i++) 
	h.insertItem(a[i]); 

// تحذف الدالة العنصر 12 من جدول التقطيع
h.deleteItem(12); 

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

return 0; 
}

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

0
1 --> 15 --> 8
2
3
4 --> 11
5
6 --> 27

العنونة المفتوحة

تخزّن جميع العناصر في هذه الطريقة في جدول التقطيع نفسه؛ لذا يلزم أن يكون حجم الجدول أكبر من العدد الكلي للمفاتيح أو يكون مساويًا له (لاحظ أنّ بالإمكان زيادة حجم الجدول عن طريق نسخ البيانات القديمة إن اقتضت الحاجة).

تتضمن طريقة العنونة المفتوحة العمليات التالية:

• Insert(k)‎: يجري سبر خلايا جدول التقطيع إلى حين الوصول إلى خلية فارغة، ويدرج العنصر k فيها.
• Search(k)‎: يجري سبر خلايا جدول التقطيع إلى أن لا يتساوى مفتاح الخلية مع قيمة k أو عند الوصول إلى خلية فارغة.
• Delete(k)‎: لا يُحذف المفتاح مباشرة لأنّ ذلك يؤدي إلى إيقاف عملية البحث؛ لذا تعلّم الخلايا المحذوفة بالعلامة deleted. يمكن للعملية Insert أن يدرج عنصرًا في الخلية المحذوفة، ولكن عملية البحث لن تتوقف عند الوصول إلى مثل هذه الخلايا.

طرق تنفيذ العنونة المفتوحة

يمكن تنفيذ العنونة المفتوحة باستخدام الطرق التالية:

1. السبر الخطي Linear Probing:

يُسبر جدول التقطيع في هذه الطريقة خطّيًا بحثًا عن الخلية التالية. وعادة ما يكون الفاصل بين سبرين 1 كما هو الحال في المثال أدناه.

لنفترض أنّ hash(x)‎ هي موقع الخلية الذي تم حسابه باستخدام دالة التقطيع وأنّ S هو حجم الجدول.

إن كانت الخلية hash(x) % S ممتلئة، سنحاول إجراء ‎(hash(x) + 1) % S‎.

إن كانت الخلية ‎(hash(x) + 1) % S‎ ممتلئة، سنحاول إجراء ‎(hash(x) + 2) % S‎.

إن كانت الخلية ‎(hash(x) + 2) % S‎ ممتلئة، سنحاول إجراء ‎(hash(x) + 3) % S‎.

لنأخذ دالة تقطيع بسيطة مثل key mod 7 والتسلسل التالي: ‎50, 700, 76 ,85, 92, 73, 101.

إن أكبر مشكلة تواجه عملية السبر الخطي هي حالة التجمّع clustering، حيث تشكّل العناصر المتتابعة مجموعات تؤدي إلى زيادة الوقت الذي يستغرقه إيجاد خلية فارغة أو البحث عن عنصر معيّن.

2. السبر التربيعي Quadratic Probing

نبحث في هذه الطريقة عن الخلية i² في الدورة ذات الرقم i.

لنفترض أنّ hash(x)‎ هي موقع الخلية الذي تم حسابه باستخدام دالة التقطيع وأنّ S هو حجم الجدول.

إن كانت الخلية hash(x) % S ممتلئة، سنحاول إجراء ‎(hash(x) + 1*1) % S‎.

إن كانت الخلية ‎(hash(x) + 1*1) % S‎ ممتلئة، سنحاول إجراء ‎(hash(x) + 2*2) % S‎.

إن كانت الخلية ‎(hash(x) + 2*2) % S‎ ممتلئة، سنحاول إجراء ‎(hash(x) + 3*3) % S‎.

3. التقطيع المضاعف Double Hashing

نستخدم في هذه الطريقة دالة تقطيع أخرى hash2(x)‎ ونبحث عن i*hash2(x)‎ في الدورة i.

لنفترض أنّ hash(x)‎ هي موقع الخلية الذي تم حسابه باستخدام دالة التقطيع وأنّ S هو حجم الجدول.

إن كانت الخلية hash(x) % S ممتلئة، سنحاول إجراء ‎(hash(x) + 1*hash2(x)) % S‎.

إن كانت الخلية ‎(hash(x) + 1*hash2(x)) % S‎ ممتلئة، سنحاول إجراء ‎(hash(x) + 2*hash2(x)) % S‎.

إن كانت الخلية ‎(hash(x) + 2*hash2(x)) % S‎ ممتلئة، سنحاول إجراء ‎(hash(x) + 3*hash2(x)) % S‎.

المقارنة بين الطرق الثلاثة

السبر الخطي هو الأفضل من ناحية أداء الذاكرة المخبئية، إلى جانب أنّ عملية الحساب فيه سهلة، ولكنّه يواجه مشكلة التجمّع.

أما السبر التربيعي فيقع بين السبر الخطي والتقطيع المضاعف من ناحية أداء الذاكرة المخبئية ومشكلة التجمّع.

التقطيع المضاعف هو الأسوء من ناحية أداء الذاكرة المخبئية، ولكنّه لا يواجه مشكلة التجمّع، إضافة إلى أنّ عمليات الحساب تستغرق وقتًا أطول نظرًا لاستخدام دالتي تقطيع.

المقارنة بين العنونة المفتوحة والسلاسل المنفصلة

يعقد الجدول التالي مقارنة بين طريقة العنونة المفتوحة والسلاسل المنفصلة:

ت	العنونة المفتوحة	السلاسل المنفصلة
1	تحتاج هذه الطريقة إلى إجراء حسابات مطولة.	هذه الطريقة أسهل في التنفيذ.
2	يمكن لجدول التقطيع أن يمتلئ.	لا يمتلئ جدول التقطيع في هذه الطريقة إطلاقًا، ويمكننا إدراج المزيد من العناصر في السلسلة.
3	تتطلب هذه الطريقة المزيد من العناية وذلك لتجنب الوقوع في مشكلة التجمّع ومعامل التحميل.	هذه الطريقة أقل تحسّسًا لدالة التقطيع أو معامل التحميل.
4	تستخدم هذه الطريقة عندما يكون عدد المفاتيح وتواترها معلومًا.	تستخدم هذه الطريقة غالبًا عندما لا يكون عدد وتواتر المفاتيح المراد إضافتها أو حذفها معلومًا.
5	تقدّم هذه الطريقة أداءً أفضل مع الذاكرة المخبئية وذلك لأنّ كل شيء يُخزّن في جدول التقطيع.	أداء هذه الطريقة مع الذاكرة المخبئية ليس جيّدًا وذلك لأنّ المفاتيح تخزّن في قوائم مترابطة.
6	يمكن استخدام الخلية في هذه الطريقة حتى إن يرتبط المدخل بتلك الخلية.	هدر في المساحة، إذ لا يُستخدم جدول التقطيع بأكمله.
7	لا توجد روابط في هذه الطريقة.	تستخدم هذه الطريقة مساحة إضافية لأجل الروابط.

أداء طريقة العنونة المفتوحة

كما هو الحال مع طريقة السلاسل، يمكن تقييم أداء عملية التقطيع بافتراض أنّ احتمالية تقطيع أيّ مفتاح وإدراجه في جدول التقطيع متساوية لجميع المفاتيح (التقطيع البسيط المنتظم simple uniform hashing).

لو افترضنا أنّ:

m = عدد المواقع في جدول التقطيع.

n= عدد المفاتيح المراد إدراجها في جدول التقطيع.

فإنّ معامل التحميل ‎α = n/m‎ سيكون أصغر من 1.

والوقت المتوقّع لعمليات البحث والإدراج والحذف سيكون أقل من ‎1/(1-α)‎.

وبهذا فإنّ التعقيد الزمني لعمليات البحث والإدراج والحذف سيبلغ ‎1/(1-α)‎.

انظر أيضًا

• التقطيع المزدوج

مصادر

• صفحة Hashing | Set 2 (Separate Chaining)‎ في توثيق بنى المعطيات في موقع GeeksforGeeks.
• صفحة Applications of Hashing في توثيق بنى المعطيات في موقع GeeksforGeeks.
• صفحة C++ program for hashing with chaining في توثيق بنى المعطيات في موقع GeeksforGeeks.
• صفحة Hashing | Set 3 (Open Addressing)‎ في توثيق بنى المعطيات في موقع GeeksforGeeks.