تحليل شامل للهاشتابل في جافا

توفر Hashtables طريقة مفيدة لتحسين أداء التطبيق.

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

تخيل أن لديك ملف بيانات يحتوي على حوالي ألف سجل - على سبيل المثال سجلات العملاء لشركة صغيرة - وبرنامج يقرأ السجلات في الذاكرة لمعالجتها. يحتوي كل سجل على رقم تعريف العميل الفريد المكون من خمسة أرقام، واسم العميل، والعنوان، ورصيد الحساب، وما إلى ذلك. افترض أنه لم يتم فرز السجلات حسب رقم معرف العميل، لذلك، إذا أراد البرنامج استخدام رقم العميل باعتباره "المفتاح" للعثور على سجل عميل معين، فإن الطريقة الوحيدة للعثور عليه هي البحث في كل سجل على التوالي. في بعض الأحيان، سيعثر على السجل الذي تحتاجه بسرعة، لكن في بعض الأحيان، قبل أن يعثر البرنامج على السجل الذي تحتاجه، يكون قد بحث تقريبًا عن السجل الأخير. إذا كنت تريد البحث بين 1000 سجل، فإن العثور على أي سجل واحد يتطلب من البرنامج التحقق من متوسط ​​500.5 ((1000 + 1)/2) من السجلات. إذا كنت تحتاج بشكل متكرر إلى البحث عن البيانات، فقد تحتاج إلى طريقة أسرع للعثور على السجل.

إحدى طرق تسريع عملية البحث هي تقسيم السجلات إلى أجزاء بحيث يمكنك البحث في عدة قوائم قصيرة بدلاً من البحث في قائمة واحدة كبيرة. بالنسبة للأرقام التعريفية للعملاء، يمكنك إنشاء 10 قوائم - قائمة واحدة لأرقام المعرفات التي تبدأ بالرقم 0، وقائمة واحدة لأرقام المعرفات التي تبدأ بالرقم 1، وهكذا. لذا، للعثور على الرقم التعريفي للعميل 38016، ما عليك سوى البحث في القائمة التي تبدأ بالرقم 3. إذا كان هناك 1000 سجل وكان متوسط ​​طول كل قائمة 100 (1000 سجل مقسمة إلى 10 قوائم)، فإن متوسط ​​عدد المقارنات للبحث عن سجل ينخفض ​​إلى حوالي 50 (انظر الشكل 1).

وبطبيعة الحال، إذا كان واحد من كل عشرة أرقام عملاء يبدأ بالرقم 0، وعشر آخر يبدأ بالرقم 1، وهكذا، فإن هذا النهج سيكون ناجحًا. إذا بدأ 90% من أرقام العملاء بالرقم 0، فستحتوي هذه القائمة على 900 سجل، مما يتطلب متوسط ​​450 مقارنة لكل عملية بحث. بالإضافة إلى ذلك، فإن 90% من عمليات البحث التي يحتاج البرنامج إلى إجرائها تكون عن أرقام تبدأ بالرقم 0. ولذلك، فإن متوسط ​​رقم المقارنة يتجاوز نطاق العمليات الحسابية البسيطة.

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

جداول التجزئة في جافا

تحتوي Java على فئتين، java.util.Hashtable و java.util.HashMap ، والتي توفر آلية تجزئة متعددة الأغراض. الفئتان متشابهتان جدًا وتوفران بشكل عام نفس الواجهة العامة. لكن لديهم بعض الاختلافات المهمة، والتي سأتحدث عنها لاحقًا.

تسمح لك كائنات Hashtable وHashMap بدمج مفتاح وقيمة وإدخال زوج المفتاح/القيمة في الجدول باستخدام طريقة put (). يمكنك بعد ذلك الحصول على القيمة عن طريق استدعاء الأسلوب get()، وتمرير المفتاح كمعلمة. يمكن أن يكون المفتاح والقيمة أي كائنات طالما أنها تستوفي متطلبين أساسيين. لاحظ أنه نظرًا لأن المفاتيح والقيم يجب أن تكون كائنات، فيجب تحويل الأنواع البدائية إلى كائنات باستخدام طرق مثل Integer(int).

من أجل استخدام كائن من فئة معينة كمفتاح، يجب أن توفر الفئة طريقتين، يساوي () و hashCode (). هاتان الطريقتان موجودتان في java.lang.Object ، لذلك يمكن لجميع الفئات أن ترث هاتين الطريقتين؛ ومع ذلك، فإن تنفيذ هاتين الطريقتين في فئة Object غير مجدي بشكل عام، لذلك تحتاج عادةً إلى تحميل هاتين الطريقتين بنفسك.

تقوم طريقة Equals () بمقارنة كائنها بكائن آخر وترجع صحيحًا إذا كان الكائنان يمثلان نفس المعلومات. تهدف هذه الطريقة أيضًا إلى التأكد من أن كلا الكائنين ينتميان إلى نفس الفئة. تُرجع الدالة Object.equals()‎ القيمة true إذا كان الكائنان المرجعيان كائنين متطابقين، وهو ما يفسر سبب كون هذه الطريقة غير مناسبة بشكل عام. في معظم الحالات، تحتاج إلى طريقة للمقارنة بين حقل وآخر، لذلك فإننا نعتبر الكائنات المختلفة التي تمثل نفس البيانات متساوية.

تقوم طريقة HashCode () بإنشاء قيمة int عن طريق إجراء دالة تجزئة باستخدام محتويات الكائن. يستخدم Hashtable وHashMap هذه القيمة لمعرفة المجموعة (أو القائمة) التي يوجد بها زوج المفتاح/القيمة.

على سبيل المثال، يمكننا أن ننظر إلى فئة السلسلة، حيث أن لديها أساليبها الخاصة التي تنفذ هاتين الطريقتين. تقارن String.equals() بين كائنين من كائنات السلسلة حرفًا بحرف وترجع صحيحًا إذا كانت السلاسل متماثلة:

انسخ رمز الكود كما يلي:

String myName = "Einstein";

// الاختبار التالي هو

// صحيح دائما

إذا (myName.equals("أينشتاين"))

{ ...

تقوم String.hashCode() بتشغيل دالة تجزئة على سلسلة. يتم ضرب الرمز الرقمي لكل حرف في السلسلة بـ 31، وتعتمد النتيجة على موضع الحرف في السلسلة. ثم يتم إضافة نتائج هذه الحسابات للحصول على المجموع. قد تبدو هذه العملية معقدة، لكنها تضمن توزيعًا أفضل للقيم. كما يوضح أيضًا إلى أي مدى يمكنك الذهاب عند تطوير طريقة hashCode() الخاصة بك، واثقًا من أن النتيجة فريدة من نوعها.

على سبيل المثال، لنفترض أنني أريد استخدام جدول تجزئة لتنفيذ كتالوج الكتب واستخدام رقم ISBN الخاص بالكتاب كمفتاح بحث للبحث. يمكنني استخدام فئة String لحمل التفاصيل وتجهيز طرق يساوي () و hashCode () (انظر القائمة 1). يمكننا إضافة أزواج المفاتيح/القيمة إلى جدول التجزئة باستخدام طريقة put () (انظر القائمة 2).

تقبل طريقة Put () معلمتين، كلاهما من النوع Object. المعلمة الأولى هي المفتاح؛ المعلمة الثانية هي القيمة. تستدعي طريقة Put () طريقة hashCode () الخاصة بالمفتاح وتقسم النتيجة على عدد القوائم في الجدول. استخدم الباقي كقيمة فهرس لتحديد القائمة التي سيتم إضافة السجل إليها. لاحظ أن المفتاح فريد في الجدول، إذا قمت باستدعاء put () باستخدام مفتاح موجود، فسيتم تعديل الإدخال المطابق بحيث يشير إلى قيمة جديدة ويتم إرجاع القيمة القديمة (عندما لا يكون المفتاح موجودًا في الجدول ، put () يُرجع قيمة فارغة).

لقراءة قيمة من الجدول، نستخدم مفتاح البحث مع طريقة get(). تقوم بإرجاع مرجع كائن تم تحويله إلى النوع الصحيح:

انسخ رمز الكود كما يلي:

BookRecord ر =

(سجل الكتب)isbnTable.get(

"0-345-40946-9");

System.out.println(

"المؤلف: " + br.author

+ "العنوان:" + br.title);

طريقة أخرى مفيدة هي إزالة ()، والتي يتم استخدامها تقريبًا مثل طريقة get () حيث تقوم بإزالة الإدخال من الجدول وإعادته إلى برنامج الاستدعاء.

صفك الخاص

إذا كنت تريد استخدام نوع بدائي كمفتاح، فيجب عليك إنشاء كائن من نفس النوع. على سبيل المثال، إذا كنت تريد استخدام مفتاح عدد صحيح، فيجب عليك استخدام المنشئ Integer(int) لإنشاء كائن من عدد صحيح. جميع فئات الغلاف، مثل Integer وFloat وBoolean، تتعامل مع القيم الأولية ككائنات، وتفرط في تحميل أساليب يساوي () و hashCode () بحيث يمكن استخدامها كمفاتيح. العديد من الفئات الأخرى المتوفرة في JDK تشبه هذا (حتى فئتي Hashtable وHashMap تنفذان أساليب يساوي () وhashCode () الخاصة بهما)، ولكن يجب عليك التحقق من الوثائق قبل استخدام كائنات من أي فئة كمفاتيح قابلة للتجزئة. من الضروري أيضًا التحقق من مصدر الفئة لمعرفة كيفية تنفيذ يساوي () و hashCode (). على سبيل المثال، تقوم كل من Byte وCraft وShort وInteger جميعها بإرجاع قيمة العدد الصحيح الممثلة كرمز تجزئة. هذا قد يناسب أو لا يناسب احتياجاتك.

استخدام Hashtables في جافا

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

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

انسخ رمز الكود كما يلي:

خطأ: يساوي منطقي عام (الكائن س)

{

إذا ((س == فارغة)

||!(يا مثيل myClass))

{

عودة كاذبة.

}

// الآن قارن حقول البيانات...

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

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

أداء هاشتابل

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

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

تعالج فئتا Hashtable وHashMap هذه المشكلة عن طريق توسيع الجدول ديناميكيًا عند إضافة الإدخالات. تحتوي كلا الفئتين على مُنشئات تقبل العدد الأولي للقوائم في الجدول، وعامل تحميل كمعلمة:

جدول التجزئة العام(

القدرة الأولية int,

عامل التحميل العائم)

خريطة التجزئة العامة (

القدرة الأولية int,

عامل التحميل العائم)

اضرب هذين الرقمين لحساب القيمة الحرجة. في كل مرة تتم إضافة إدخال جديد إلى جدول التجزئة، يتم تحديث العدد، وعندما يتجاوز العدد قيمة حرجة، تتم إعادة تعيين الجدول (إعادة التجزئة). (يتم زيادة حجم القائمة إلى ضعف الحجم السابق بالإضافة إلى 1، ويتم نقل كافة الإدخالات إلى القائمة الصحيحة.) يقوم المنشئ الافتراضي بتعيين السعة الأولية على 11 وعامل التحميل على 0.75، وبالتالي فإن القيمة الحرجة هي 8. عند إضافة السجل التاسع إلى الجدول، تتم إعادة قياس جدول التجزئة بحيث يحتوي على 23 قائمة، وستكون القيمة الحرجة الجديدة 17 (الجزء الصحيح من 23*0.75). يمكنك أن ترى أن عامل التحميل هو الحد الأعلى لمتوسط ​​عدد القوائم في جدول التجزئة، مما يعني أنه نادرًا ما يحتوي جدول التجزئة على العديد من القوائم التي تحتوي على أكثر من سجل واحد. قارن مثالنا الأصلي، حيث كان لدينا 1000 سجل موزعة على 10 قوائم. إذا استخدمنا القيم الافتراضية، فسوف يتسع هذا الجدول ليحتوي على أكثر من 1500 قائمة. ولكن يمكنك التحكم في هذا. إذا كان عدد القوائم مضروبًا في عامل التحميل أكبر من عدد الإدخالات التي تقوم بمعالجتها، فلن يتم إعادة إنشاء الجدول أبدًا، لذا يمكننا اتباع المثال أدناه:

انسخ رمز الكود كما يلي:

// لن يتم إعادة صياغة الجدول حتى يتم ذلك

// يحتوي على 1100 إدخال (10*110):

هاشتابل myHashTable =

جدول تجزئة جديد (10، 110.0F)؛

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

لاحظ أنه على الرغم من أن استدعاء put () يمكن أن يؤدي إلى زيادة حجم الجدول (زيادة عدد القوائم)، إلا أن استدعاء Remove() لن يكون له تأثير معاكس. لذا، إذا كان لديك جدول كبير وقمت بحذف معظم الإدخالات منه، فسوف ينتهي بك الأمر بجدول كبير ولكن معظمه فارغ.

Hashtable وHashMap

هناك ثلاثة اختلافات مهمة بين فئتي Hashtable وHashMap. الفرق الأول يرجع بشكل رئيسي إلى أسباب تاريخية. يعتمد Hashtable على فئة القاموس القديمة، وHashMap هو تطبيق لواجهة الخريطة المقدمة في Java 1.2.

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

والفرق الثالث هو أن HashMap فقط هو الذي يسمح لك باستخدام القيم الخالية كمفتاح أو قيمة لإدخال الجدول. يمكن أن يكون سجل واحد فقط في HashMap مفتاحًا فارغًا، ولكن أي عدد من الإدخالات يمكن أن يكون قيمة فارغة. هذا يعني أنه إذا لم يتم العثور على مفتاح البحث في الجدول، أو إذا تم العثور على مفتاح البحث ولكنه قيمة فارغة، فإن get() سيعود خاليًا. إذا لزم الأمر، استخدم طريقة تحتوي على مفتاح () للتمييز بين الحالتين.

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

حول الخصائص

في بعض الأحيان، قد ترغب في استخدام جدول التجزئة لتعيين السلاسل الرئيسية لسلاسل القيمة. توجد بعض الأمثلة لسلاسل البيئة في DOS وWindows وUnix، على سبيل المثال، يتم تعيين سلسلة المفاتيح PATH إلى سلسلة القيمة C:/WINDOWS;C:/WINDOWS/SYSTEM. تُعد جداول التصنيف طريقة بسيطة لتمثيل هذه العناصر، لكن Java توفر طريقة أخرى.

فئة Java .util.Properties هي فئة فرعية من Hashtable مصممة للاستخدام مع مفاتيح وقيم السلسلة. يشبه استخدام كائن الخصائص استخدام Hashtable، لكن الفصل يضيف طريقتين لتوفير الوقت يجب أن تعرفهما.

يحفظ الأسلوب Store() محتويات كائن الخصائص في ملف في نموذج قابل للقراءة. طريقة Load() هي العكس تمامًا، فهي تُستخدم لقراءة الملف وتعيين كائن الخصائص ليحتوي على مفاتيح وقيم.

لاحظ أنه نظرًا لأن الخصائص تعمل على توسيع Hashtable، يمكنك استخدام طريقة put () الخاصة بالفئة الفائقة لإضافة مفاتيح وقيم ليست كائنات سلسلة. هذا غير مستحسن. بالإضافة إلى ذلك، إذا كنت تستخدم store() مع كائن Properties لا يحتوي على كائن String، فسوف يفشل store(). كبديل لوضع () وget ()، يجب عليك استخدام setProperty () وgetProperty ()، والتي تأخذ معلمات السلسلة.

حسنًا، أتمنى أن تعرف الآن كيفية استخدام جداول التجزئة لتسريع عملية المعالجة