طريقة الـ Open Addressing في Hashing Algorithm مع التطبيق في Java

Abdulrahman Aghaمنذ 7 سنوات

بسم الله الرحمن الرحيم

السلام عليكم ورحمة الله وبركاته

ستحتاج إلى قراءة الموضوع السابق الخاص بـالـ Hashing Algorithm لكي تستطيع المتابعة من خلال الرابط التالي هنا

Hashing

سنتعرف معاً في هذا المقال على :

- طريقة الـ Open Addressing.

- طريقة التطبيق في لغة برمجة Java.

تكلمنا في المقالة السابقة عن الـ Hashing Algorthim وكيف يمكننا حل مشكلة تكرار الـ Data وتم مناقشة فكرة واحدة وهي الـ Separate Chaining .

وللتذكير فإن طريقة الـ Separate Chaining هي طريقة تعتمد على بناء ArrayList بشكل خاص أو أي Structure آخر بشكل عام داخل كل خلية في الـ Hash Table. ومن ثم يتم تخزين القيم اللي تمتلك نفس قيمة الـ Index في هذا الـ Structure. ولكن !!!

طريقة الـ Separate Chaining لها العديد من الميزات والعيوب مثل :

الميزات :

1 - مطلق الحرية في استخدام الـ Structure الذي يناسبك سواء كان Tree أو ArrayList على سبيل المثال.

2 - سهولة تطبيق فكرة الـ Separate Chaining داخل أي لغة برمجة.

العيوب :

1 - ماذا لو أدخل المستخدم 10 أرقام على سبيل المثال والتي تملك نفس الـ Index. فـ على سبيل المثال لنقل بأننا نريد ملئ HashTable بحجم خليتين بالأرقام التالية : 2-4-6-8-10-12. عند تطبيق الدالة Index = number % arrayLength سنجد بأن كل الأرقام ستوضع في خانة 0 في الجدول كما في الصورة التالية :

2هاش.png

ولكن لحظة !! الـ ArrayList الموجودة بالصورة هي عبارة عن Array عادية موضوعة داخل Index 0 والفكرة الاساسية من الـ Hashing لم يتم تطبيقها للأسف لأننا في حال أردنا البحث عن رقم 12 مثلاً سنضطر للبحث داخل كل الـ Array داخل Index 0. تخيل بأنك أضفت أكثر من الف Record وجميع هذه الـ Records تمتلك نفس الـ Index ستستغرق نفس الفترة الزمنية المستغرقة في حال إضافة هذه الـ Records في Array عادية بدون التطرق لفكرة الـ Hashing.

لذلك نستطيع القول بأن فكرة الـ Separate Chaining ليست ممتازة في جميع الأحوال. فما الحل ؟

الحل يتمثل في الطريقة الثانية وهي Open Addressing.

الطريقة الثانية : Open Addressing.

ميزة هذه الطريقة بأن كل الـ Records سيتم توزيعها على كل الخانات الفارغة داخل الـ Table. وفكرتها تعتمد على إضافة رقم معين يتم نقل الـ Record المتكرر إلى خلية ثانية بمقدار هذا الرقم. هذا الرقم يعتمد على عدة دوال وهي :

1 - Linear probing وهذه الطريقة التي سنناقشها في هذه المقالة.

2 - Quadratic probing وهي زيادة بمقدار مربع i كل مرة. بحيث i = 0 , 1 , 2 , etc بالشكل التالي i^2 +/- . بمعنى آخر سنقوم في البداية بالتحرك بمقدار i إلى اليمين ومن ثم بمقدار i إلى اليسار.

3 - Double hashing وهي زيادة بحسب دالة أخرى.

Linear probing أو زيادة خطية بمعنى زيادة عدد معين تختاره أنت من البداية يطلق عليه i على كل Record متكرر. لكي تتوضح الصورة لنأخذ المثال التالي:

نريد إضافة هذه الأرقام 5 - 10 - 21 - 31 إلى جدول مكون من 5 خانات. ونريد تحديد الـ i لكي تكون 1 في حالة التكرار. سيكون المخرج النهائي كالتالي :

1 - عند إضافة 5 .. لن يكون هناك أي مشاكل لأن الجدول يفتقر لوجود أي Data وسيتم وضعه في Index 0.
2 - عند إضافة 10 .. سنلاحظ وجود 5 في خانة Index 0 ولذلك لا يمكننا وضع 10 أيضاً فنقوم بزيادة الـ Index بـ قيمة i المختارة سابقاً وهي 1 فيصبح الـ Index هو Index 1.

3 - عند إضافة 21 .. يجب علينا إضافتها إلى Index 1 ولكنه ممتلئ بالقيمة 10 .. فنقوم بالزيادة بـ 1 ونقوم بوضعها بخانة Index 2.

4 - عند إضافة 31 .. يجب علينا إضافتها إلى Index 1 ولكنه ممتلئ بالقيمة 10 .. نقوم بزيادة 1 ونضيف 31 إلى Index 2 ولكنه ممتلئ أيضاً بالقيمة 21 فنقوم بزيادة 1 مرة أخرى ونضع 31 في Index 3.

المخرج النهائي :

2هاش (1).png

ولكن طريقة الـ Open Addressing فتحت لنا الباب لظهور مشكلة جديدة وهي مشكلة الحذف. ماذا لو أردنا في المثال السابق حذف الرقم 21. ومن ثم نريد إيجاد الرقم 31. سنقوم بالبحث بداية داخل Index 1 ولكننا سنجد 10 فـ سننتقل إلى Index 2 لنفاجئ بأن القيمة هي Null لأننا سبق وحذفنا الرقم 21. وهذا خطأ .. لأننا اتفقنا في البداية بأن الـ Index إذا كان Null "فارغ" يجب علينا ملء هذا الـ Index قبل الانتقال إلى Index جديد. ستخبرني بأنه من الممكن إكمال البحث حتى العودة للـ Index الذي بدأنا عنده للتأكد بأن 31 غير موجودة ولكن ماذا لو كان 31 غير موجود فعلاً و Index 2 فارغ بسبب إنه لم يتم إضافة 31 بعد .. في هذه الحالة ستقوم بتضييع الكثير من الوقت رغم علمك المسبق بأن 31 غير موجود. تبدو الفكرة محيرة فعلاً فما الحل؟ الحل يتمثل بإضافة " حالة " أو Status إلى الجدول الموجود في المثال السابق. سنقوم بتغيير حالة الـ 21 في حالة الحذف إلى D دلالة إلى Deleted بدون حذفها بشكل نهائي. في هذه الحالة لن يتعطل البحث أو يتوقف وستحل المشكلة.

في البداية ستكون الـ Status الخاصة بكل الخلايا E دلالة إلى Empty او فارغ. إذا تم وضع عنصر جديد داخلها سيتم تغيير حالتها إلى O دلالة إلى Occupied او ممتلئ.

الآن في حالة البحث عن 31 بعد حذف 21. سنقوم بالذهاب إلى Index 1 لنجد 10 فننتقل إلى Index 2 لنجد 21 فننتقل إلى Index 3 فنجد 31.

ماذا لو أردنا البحث عن 21 بعد حذفها ؟ لا يمكنك عمل return true في حالة البحث إلا في حالة واحدة فقط إذا كان القيمة الموجودة في الخلية = القيمة المبحوث عنها + الحالة أو الـ Status = O. لو كانت D كما في مثالنا يجب علينا عمل return false.

- التطبيق بلغة Java.

سنتحتاج إلى عمل 3 كلاسات. الكلاس الأول Cell والكلاس الثاني HashTable والثالث عبارة عن TestClass.

كلاس Cell : الخلية هنا تتكون من القيمة وحالتها كما أسلفنا سابقاً بالإضافة إلى بعض الـ Methods المهمة.


public class Cell {
	
	 Object dataObject ; // value 
	 String status ; // status E for empty, D for deleted, or O for occupied 
	
	public Cell(){
		status = "E"; // default value for a null cell
	}
	public Cell(Object obj){ 
		status = "O";
		dataObject = obj ;
	}
	
	public String toString(){
		return "Object : "+dataObject.toString()+"\t\t "+status+"\n" ;
	}
	
	public int getHash(){ // we are going to use hashCode() method that exists in Object class 
		return dataObject.hashCode();
	}
        
	public void setStatus(String s){
		status = s ;
	}

}

كلاس HashTable : يتكون من كل ماله علاقة بالجدول المراد إنشائه من Methods.

أولا: Instance Variables and Constructors


private int size ;
	private Cell [] list ;
	
	
	public HashTable(){ // default size for empty hash table
		size = 0 ;
	}
	public HashTable(int i){ // creating hash table with a desired value 
		list = new Cell[i];
		size = i ;
		for (int j = 0 ; j<i ; j++) // NullPointerException !!
			list[j] = new Cell();
	}

ثانياً : Insert method " إضافة "


public void insert(Object obj){
		Cell tmp = new Cell(obj);
		int index = obj.hashCode()%size ; 
		if (list[index].status.equals("E") || list[index].status.equals("D")){ // empty or deleted cell
			list[index] = tmp ;
		}else{ // status = occupied
			int counter = 0 ;
			index++;
			while(counter <list.length){
				if (list[index].status.equals("E")){ // empty cell
					list[index] = tmp ;
					list[index].setStatus("O");
					break ;
				}
				counter++;
				index = (index+1)%size;
			}
		}
	}

ثالثاً : retrieve method " بحث " هذه الميثود تعطيك قيمة الـ Index الموجود فيها العنصر المراد البحث عنه أو -1 إشارة إلى عدم وجوده


public int retrieve(Object obj){ // get index of obj 
		int index = obj.hashCode()%size ;
		if (list[index].status.equals("E"))
			return -1 ; // not found
		int counter = 0 ;
		while(counter < list.length){ // till the end of the table 
			if (list[index].status.equals("D") && list[index].dataObject.equals(obj))
				return -1 ;
			if (list[index].status.equals("O") && list[index].dataObject.equals(obj))
				return index;
			index = (index+1)%size;
			counter++ ;
		}
		return -1; // not found
	}

رابعاً : Delete Method " حذف "


public void delete(Object obj){
		int index = retrieve(obj);
		if (index != -1){ // if found
			list[index].setStatus("D");
		}
	}

خامساً وأخيراً : ميثود الطباعة.


public String toString(){
		String str = "";
                System.out.println("Value\tStatus");
		for (int i = 0 ; i<list.length ; i++){
			if (list[i].dataObject == null){
				str = str+" - ";
			}else 
				str = str+" "+list[i].dataObject.toString();
			str = str+"\t  "+list[i].status+"\n";
			
		}
		return str ;
	}

كلاس TestClass وسنقوم بعمل التالي :

سنقوم بعمل جدول مكون من 13 خانة ونقوم بعمل التالي:

1 - إضافة 18 - 26 - 35 - 9 من " اليمين إلى اليسار "

2 - البحث عن 15 - 48 " قيم غير موجودة "

3 - حذف 35

4 - البحث عن 9 " الخانة الصحيحة 10 "

5 - إضافة 64 - 47 " من اليمين إلى اليسار "

6 - طباعة الجدول


public class test {
	
	public static void main(String [] args){
                //create new hashTable
                HashTable hashTable = new HashTable (13);
		
                //insert 18 26 35 9 
                hashTable.insert(new Integer(18));
		hashTable.insert(new Integer(26));
		hashTable.insert(new Integer(35));
		hashTable.insert(new Integer(9));
		
                // get index of element 15 , 48
                System.out.println(hashTable.retrieve(new Integer(15))); // -1
		System.out.println(hashTable.retrieve(new Integer(48))); // -1
		
                //delete element 35 " change status to D " ;
                hashTable.delete(new Integer(35));
		
                // get index of element 9
                System.out.println(hashTable.retrieve(new Integer(9))); // 10
		
                //insert 64 47 
                hashTable.insert(new Integer(64));
		hashTable.insert(new Integer(47));
                
                //printing
		System.out.println(hashTable);
	}

}

المخرج النهائي :