Hashing algorithm واستخدامها داخل الـ java

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

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

 

Hashing

 

الكثير من الـ algorithms تستخدم في عملية البحث البسيطة عن Record معين أو Data معينة وسط الآلاف وأحيانا مئات الالاف من الملفات المخزنة في الذاكرة.

العامل المهم في عملية اختيار الطريقة الممتازة تعتمد على الوقت وفعالية الجهاز المستخدم في عملية البحث ومدى كفائته. وواحدة من أفضل الطرق المستخدمة حالياً هي الـ Hashing .

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

-          تعريف بسيط عن الـ Hashing.

-          بعض الطرق المستخدمة في التعامل مع الـ Data في حالة التكرار في طريقة الـ Hashing.

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

 

تعريف بسيط عن الـ Hashing:

هي طريقة تستخدم لحفظ الملفات وتخزينها ومن ثم البحث عنها بأسرع طريقة ممكنة. تتميز هذه الطريقة عن غيرها بأنها قادرة على جلب الـ Data بوقت سريع جدا وسط ملفات ومعلومات كبيرة نوعاً ما مقارنة بغيرها من الطرق.

هذه الطريقة تتميز بحفظ الـ Data في جدول بحيث يتم إعطاء كل معلومة رقم مميز يتم حفظه داخل جدول من البيانات ومن ثم يتم الوصول إليه مباشرة في حال الحاجة إلى البحث عنه. هذه الطريقة تتميز بقلة الوقت اللازم للقيام بهذه العملية بحيث يمكنك مباشرة معرفة ما إذا كان الملف الجاري البحث عنه موجود أو غير موجود دون الحاجة للبحث عنه داخل الذاكرة بأكملها.

مثال :

لنفرض بأن لدينا الأرقام التالية : 1-7-4-8-9-5 .

إذا قمنا بحفظ هذه الأرقام داخل Array بشكل عشوائي مباشر على سبيل المثال فعند البحث عن رقم 9 ستضطر إلى البحث داخل الـ Array بالكامل لمعرفة ما اذا كان الرقم 9 موجود أو لا. تخيل بأن لديك أكثر من الف رقم او أكثر!! يمكنك تخيل الوقت الطويل الذي ستحتاجه للقيام بعملية البحث هذه.

لكن باستخدام Hashing يمكننا مثلا تخزين هذه الأرقام داخل Array ولكن ليس بشكل عشوائي كما في السابق وإنما بالنسبة لباقي قسمة العدد على حجم الـ Array على سبيل المثال. لنتفرض بأننا انشأنا Array بحجم 9 خلايا، الصف الأول يوضح الـ index والصف الثاني يوضح العدد الموجود داخل هذا الـ index

8	7	6	5	4	3	2	1	0	index
									value

عند تعبئة هذه الـ Array سنستخدم العلاقة التالية : index = number % arrayLength. بمعنى آخر سيتم وضع الرقم داخل الخانة المعبرة عن باقي قسمة العدد على حجم الـ Array.

فيكون الجدول بعد التعبئة بهذا الشكل

8	7	6	5	4	3	2	1	0	index
8	7		5	4			1	9	value

لاحظ بأن الرقم 9 وضع بخانة رقم 0 لان باقي قسمة 9 على حجم الـ Array سيعطيك صفر.

الآن بامكانك مباشرة الذهاب حين البحث عن رقم 9 إلى الرقم المستخرج من الدالة index = number % arrayLength وهو صفر لتعرف ما اذا كان الرقم 9 موجود أو لا وبالتالي توفير الكثير من الوقت.

 

بعض الطرق المستخدمة في التعامل مع الـ Data في حالة التكرار في طريقة الـ Hashing:

في المثال السابق لم نصادف أي تكرار في قيمة باقي قسمة الارقام على حجم الـ array ولكن كيف من الممكن حل مشكلة تكرار القيم في حال وقوعها ؟

هناك الكثير من الحلول التي من الممكن استخدامها لحل هذه المشكلة ولكن سيتم ذكر حل واحد في هذا المقال وسيتم الحديث عن باقي الحلول في مقالات قادمة إن شاء الله.

1 - Separate Chaining : هذه الطريقة تعتمد على بناء ArrayList بشكل خاص أو أي Structure آخر بشكل عام داخل كل خلية في الـ Hash Table الموضح في الأمثلة السابقة.

لنأخذ هذه الأعداد على سبيل المثال : 12 – 17 – 29 – 6 – 30 – 31 – 4 – 8 ولنقم بتوزيعها علىHash Table  بحجم 4 خلايا.

 

في هذه الحالة يتم أولا معرفة الـ index المراد البحث داخله ومن ثم البحث داخل الـ ArrayList لمعرفة ما اذا كان الـ record المراد البحث عنه موجود أو غير موجود.

 

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

هناك الكثير من الطرق لتطبيق فكرة الـ Hashing بواسطة الجافا ولكن سنقوم باتباع الطريقة الأسهل والأقل تعقيداً. سنحتاج إلى إنشاء كلاس List :

List Class  : عبارة عن كلاس سيتم عمل objects منه  ويحتوي على الـ ArrayList المراد تخزين الـ Data فيها بالإضافة إلى Constructor.

import java.util.ArrayList;

public class List {
    
    private ArrayList<Integer> list = new ArrayList<Integer>();
    
    //Constructor
    public List(){
        
    }
    
    public ArrayList<Integer> getList(){
        return list ;
    }
    
}

 

نحتاج أيضاً لإنشاء test class للتأكد من صحة الـ HashTable 

Test Class : في التيست كلاس سنقوم بإنشاء Array من كلاس List. لاحظ بأنه يجب عليك تعريف كل عناصر هذه الـ Array وبدون هذا التعريف سيظهر لك NullPointerException.

//hash table
        List [] hashTable4 = new List [4] ;
        for (int i = 0 ; i<hashTable4.length ; i++)
            hashTable4[i] = new List();

 

ميثود print لطباعة الجدول 

public static void print(List [] array){
        for (int i = 0 ; i<array.length ; i++)
            System.out.println("index "+i+" : "+array[i].getList().toString());
    }

 

ميثود getHashCode لمعرفة الـ index المناسب 

public static int getHashCode(int num){
        return num%4 ; 
    }

 

نقوم بتخزين الأرقام في array لتسهيل عملية التصنيف والإدخال ومن ثم نقوم بإدخالها في object hashTable4

//numbers we want to add
int [] listOfNumbers = {12,17,29,30,6,31,4,8};
        
//add Numbers to the hash table
for (int i = 0 ; i<listOfNumbers.length ; i++){
   int index = getHashCode(listOfNumbers[i]);
   hashTable4[index].getList().add(listOfNumbers[i]);
}

 

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

 

كلمات دليلية: