هياكل البيانات Hash tables بتتعامل ازاي مع الذاكرة ؟

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

إن هيكل البياناتHash Table بيستخدم طريقة فريدة لتنظيم البيانات في الذاكرة وحفظها بحيث يستطيع الوصول لأي عنصر بسرعة كبيرة في وقت ثابت  O(1).

حيث يبدأ ال Hash Table أولا بتخصيص مصفوفة (Array) في الذاكرة وكل حقل في المصفوفة يتم تخزين قيمة معينة فيه. وحجم المصفوفة يتحدد  بشكل مبدأى ويمكن تكبيره عند الحاجة.

بعد ذلك يتم إستخدام ما يسمى دالة التقطيع Hash Functions حيث تأخذ الدالة key الذي تريد حفظه وتقوم بتحويل المفتاح لرقم وهذا الرقم هو الindex الخاص بالمصفوفة الذي سيتم حفظ تلك القيمة فيه.

وتوجد العديد من الأمور التي تقوم بها تلك الخوارزمية لتنفيذ ذلك الأمر منها التعامل مع التصادمات (Collisions) والتي تحدث في دالة ال hash والتي تعيد عدة قيم نفس ال index للمصفوفة مما يسبب مشكلة .

ويمكنك قراءة التالي لمزيد من التفاصيل :

• https://wiki.hsoub.com/Algorithms/hashing#.D8.AC.D8.AF.D9.88.D9.84_.D8.A7.D9.84.D8.AA.D9.82.D8.B7.D9.8A.D8.B9

عن طريق تخصيص قطعة متجاورة من الذاكرة على الـ Heap لاستخدامها كمصفوفة، وتحتوي على دلاء buckets أو فتحات slots، وحجم المصفوفة هو أحد المحددات الرئيسية لكمية الذاكرة الأولية التي يستهلكها جدول الهاش، فيبدأ الجدول بحجم افتراضي 16 أو 32 فتحة ويتغير الحجم لاحقاً.

كل فتحة تخزن إما مؤشر pointer إلى بداية قائمة كقائمة مرتبطة لو كان الجدول يستخدم طريقة السلسلة المنفصلة Separate Chaining لحل التصادمات، أو البيانات نفسها وهي المفتاح والقيمة أو مؤشر للبيانات في حال الجدول يعتمد على العنونة المفتوحة Open Addressing.

ثم تخزين البيانات الفعلية على شكل أزواج مفتاح-قيمة Key-Value pairs وتحتاج أيضاً إلى ذاكرة والتي تضاف إلى الذاكرة التي تستهلكها المصفوفة الأساسية، وفي طريقة السلسلة المنفصلة، كل عنصر يتم إضافته يتم تغليفه wrap داخل عقدة قائمة list node تحتوي على البيانات الفعلية ومؤشر إلى العقدة التالية في السلسلة، وكل عقدة منها تستهلك ذاكرة إضافية للبيانات وللمؤشر.

وفي العنونة المفتوحة، توضع البيانات مباشرة أو مؤشر إليها داخل الفتحات الموجودة في المصفوفة الأساسية.

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

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

الف شكراا جدا لحضرتكم

جزاكم الله كل خير