hash table

للأسف اخي الكريم ليس لدي معلومه عن ماهية hash table

وماهو عملهـا

اتمنى لمن عنده معلومات ان يدلي بها

والسلاام

السلام عليكم

اخي العزيز ساحاول ان اشرح قدر المستطاع

hash table هو جدول يحتوي على indexes بحيث نستطيع الربط خلالها بين عضو لبين مكانه في الarray بهذه الطريقة نستطيع ان نقلل من زمن البحث عن عضو او زمن ادخال هذا العضو فكلنا يعلم مدى اهمية الcomplication في عملية البحث والادخال

والكل يعلم ان الcomplication في حالة الbinary tree (سواء كان بحث او ادخال) هو

(O(log2n وهو الافضل تقريبا في كل الحالات .

أما في حالة ال hash table فان الcomplication هي (O(1

ساطرح مثال لعمل الhash table و hash function

لو كان لدينا [array[700 وسنملاه باعداد عشوائية من 0 حتى 9999 فلو اردنا البحث في هذه المصفوفة عن الاعداد 3498 أو 9217 ....الخ

ففي كل مر سنحتاج لان نمر على كل العناصر حتى نصل الى المكان المطلوب بمعنى اصح سنستخدم في كل مرة loop حتى 700

هنا تاتي فكرة الhash function حيث ان هذه الدالة وظيفتها ان تحول العدد 3498 الى عدد يقع في المجال[0,699] مثال لهذه الدالة :

نفرض ان العدد هو xyzw فان الدالة ستفعل الاتي

index=[(x+y)*(z+w)]*2

على سبيل المثال العدد 3498 سيحول الى

index=[(3+4)*(9+8)]*2=238

وهكذا...فاكبر عدد لدينا هو 9999 سيحول الى

index=[(9+9)*(9+9)]*2=648

فلو اردنا ان ندخل العدد 3498 الى المصفوفة فسنستخدم الhash function لادخاله وكدلك في حال اي عدد اخر

واذا اردنا البحث في المصفوفة عن اى عدد ايضا سنستخدم ال hash function

من هنا نرى اننا قد استغنينا عن ال loop في حالة الادخال والبحث وهذا يقلل وقت البرنامج

بناءا على دلك فان ال complication هي( O(1 .

طبعا هنالك disadvantages لهذه الطريقة ان اردتم ان نتحدث عنها فلا مانع .

أرجو ان اكون قد أوصلت لكم الفكرة

مع تحياتي

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

الله يعطيك العافية اخ karimosh

بشرحك هذا تكون أنهيت مشكلة عدم فهمي لطريقة الـHash Table

أنا حراجع معك مافهمته من الموضوع :

1- هل index=[(x+y)*(z+w)]*2 هي طريقة عمل الـHash Table?

2- Index[238] = 3498 نتيجة لأن index=[(3+4)*(9+8)]*2=238

3- يتعامل الـHash Table مع المصفوفات فقط

3- لوكان لدينا مصفوفة حجمها [50] وأدخلنا الرقم 9999 ونعرف انه ليس له مكان في المصفوفة فهل الطريقة لتجنب ذلك هو مقارنة موقع الرقم المدخل مع حجم المصفوفة

السلام عليكم

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

نفترض اننا اردنا ان نجمع كلمات القاموس علي شكل data structure على شكل linked list مرتبه بحسب الحروف الابجديه ما المشاكل التى يمكن ان تواجهنا ؟

اولاً فى حالة البحث على اسواء الاحتمالات ستكون الكلمه فى اخر القاموس وبذالك لا بد ان نمور على القاموس باكمله للحصول على الكلمه, لو كان القاموس فيه 6 ملايين كلمه لا بد فى كل مره على اسواء التقديرات ان نمور على القاموس باكمله. وهذا يرمز له فى لغة الرياضيات ب O(N) ومعنى دالك ان البحث يستغرق فى اسواء الحالات بحث شامل.

هذا بالطبع يستغرق وقت إذا كانت عملية البحث هى جزء مهم فى عمل برنامج معين, لذالك لابد من حفظ القاموس بطريقه اذكى, نفترض الان اننا حفظنا القاموس على النحو التالى, كل لكمه تبداء بحرف معين فى لسته منفصله, مثلاً كلمة All فى لستة ال A وكلمة Ball فى لستة B وهكذا, هناك مشكله فى هذا الحل المشكله الاولى هى ان الكلمات التى تبداء بحرف A اكثر بكثير من الكلمات التى تبدا بحرف Z مثلاً لذالك او حرف T وهكذا وفى اسواء الاحوال كل كلمات القاموس تبداء بحرف معين مثل A او نقول ان البحث فى لسته A يشغل معظم عمل البرنامج وهذه اللسته تكون اضخم لسته فى القاموس بلغة الرياضيات مازال البحث ياخذ O(N); وكانت يابو زيد ما غزيت.

الان يجب ان نجد حل لتوزيع الكمات على 28 لسته بالتساوى او على الاقل بنسبه معقوله من الاختلاف بحيث يكون عدد الكلمات فى اللسته الاولى هو تقريباً نفس عدد الكلمات فى السته الثانيه والثالثه وهكذا....

هناك طرق عديده مثلاً نقوم بتحويل الكلمه إلى اعداد الاسكى, وكما تعلمون ان لكل حرف رقم معين مثلاً حرف A يرمز له برقم 65 على ما اذكر و B يرمز له ب 66 وهاكذا,

إذاً كلمه AB = 131, بعد ذالك نقوم بقسمة العدد على 28 وهو عدد اللستات التى نريد ان نحفظ فيها القاموس عندما نحصل على باقى القسمه وفى هذه الحاله هو 19 نضع الكلمه فى اللسته رقم 19, عند البحث عن الكلمه نقوم بنفس العمليه ونحصل على الرقم 19 وبذالك نعرف فى اى لسته توجد الكلمه ثم نقوم بالبحث عنها فى تلك اللسته فقط.

والان نسئل انفسنا ما هو الرمز الرياضي للوقت المستغرق فى البحث ؟؟

كما لاحظنا اللسته مقسمه إلى 28 لذالك البحث سيستغرق N/28 اليس كذالك, طيب وكيف يرمز له ب Big O او Ordo كما يسميها علماء الرياضيات؟, ستقول لى اكيد O(N/28) اليس كذالك؟ الاجابه هى لا, الوقت يرمز له ب O(N) لان اى رقم ثابت فى N يساوى N, لان N تعتبر عدد لا نهائي وكما نعلم العدد اللانهائى فى اى عدد هو عدد لا نهائى, مازال كاننا ما عملنا شئ.

طيب نعمل إيه حيرتنا يابوحميد :)

الحل بكل بساطه هو ان تقوم بعمل N لسته, كل عنصر فى القاموس يوضع فى لسته, ثم توجد معادله لحساب مكان الكلمه وبذالك يصبح البحث O(1).

ملاحظه بسيطه O(1) = O(2) = ... O(10000000) و هكذا, يعنى طالما العدد الذى نرمز له ب Big O هو عدد معروف constant يصبح الرمز الرياضى له عدد ثابت, يعنى على سبيل الثال لو قسمنا عدد اللسته على عدد ثابت وضمنا ان فى كل لسته يكون عدد العناصر محدود, فى هذه الحاله البحث ايضاً يكون محدود وهو O(1):

مسئلة حساب Ordo او Big O من المسائل المعقده فى علم الخوارزميات, ويستدعى الدراسه المتئنيه.

ملاحظه اخيره طريقة حساب مكان اللسته ايضاً يمكن حسابه ب Ordo وعليك عندما تختار طريقة حساب معينه, ان تختار طريقه لا تستغرق O(N); لانك فى هذه الحاله كانك لم تفعل شئ O(N) *O(1)=O(N) , ال O(N) لتحويل الكلمه بواصطة الرياضيات إلى رقم ثم O(1) للحصول على الكلمه.

خلاصة الكلام:

hash table معناها توزيع العناصر على عدد من القوائم بحيث نضع مجموعات فى كل قائمه.

نختار التوزيع بحيث تكون القوائم متساويه فى الطول, والعمليه الرياضيه لتحويل العنصر إلى عدد بحيث تعرف قائمته لا يكون معقداً ويستهلك وقت.

والسلام

السلام عليكم

أخي psk_cs بالنسبة لاسئلتك :

اقتباس

1- هل index=[(x+y)*(z+w)]*2 هي طريقة عمل الـHash Table?

هذه هي فكرة الhash function تحويل العدد الى اندكس اما بالنسبة للدالة نفسها فانت تستطيع ان تركب اى دالة اخرى لتقوم بالعمل لاحظ ان هذه الدالة مناسبة فقط للمثال الذي ذكرت .

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

index=x+y+z+w

فالعدد 9999 يمكن تحويله الى

index=9+9+9+9=36

وهكذا ...

أما لباقي اسئلتك فهي كما ذكرت صحيحة .

مع تحياتي

thank for the explain

but if I need to read for example "LDA 1000" using keyboard then store "LDA" in array, then I made hash table contains values as"LDA, LDB,..."and each value corresponding it new value. and I want to search about "LDA" in the hash table to return the new value, how I can make this hash table and what is the hash function for it,

and can I search using the array in the hash table???????

printf("Enter command please:\n");

gets(command);

for(i=0;command!=' ';i++)

{

nospace[j]=command;

j++;

}

how I can search using nospace in the hash table??

السلام عليكم

من الواضح من سؤالك إن الكلمات التى ستدرج فى ال hash table من نوع LDA,ADB.....LDZ فى هذه الحاله الحرف الاخير هو المختلف, لذالك يمكننا ان نختار رمز رياضى بسيط جداً على سبيل المثال :

كما نعلم الحرف A يرمز له فى لائحت ال ASCII بالعدد 65و الحرف B 66 وهاكذا, لذالك يمكننا ان نطرح الحرف الثالث من العدد 65 فنحصل على الاعداد المطلوبه,

65-65=0=A

66-65=1=B

.......

وهكذا نستطيع عمل hash table بسيط جداً, هذا إذا كان الامر كما ذكرتى ان الكلمات كلها على هذا النمط LDA,LDB الخ, اما إذا كان الوضع مختلف عن ذالك فلا بد من إيجاد حل اخر.

والسلام

there are words more than LDA, LDB ... how can I store them in a hash table???

السلام عليكم

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

لذالك انصحك بمحاوله فهم الموضوع بعمق بدلاً من البحث عن حل للمشكله, عند ذالك سيتاح لكى المجال فى إيجاد حلول كثيره, واظن هذا هو الهدف من الواجب وليس الهدف ايجاد حل لهذه المشكله بالذات.

ارجو ان تتقبلى منى هذه النصيحه بصدر رحب, ورمضان كريم.

والسلام

الهدف ان أعمل hash table مخزن فيو هاي الاشياء بس يعني ما بدي أدرسو , وكيف اقدر اعمل بحث من خلاله <<

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

اما بالنسبه لعملية البحث فتتم على النحو التالي:

بنفس ال function الذى تم بة تشفير الكلمه فى عملية ال Insert لمعرفة مكانها فى ال hash table يتم تشفير الكلمه التى نريد ان نبحث عنها فى ال hash table وبعد ان نتعرف على مكانها فى نقوم بعملية مقارنه عاديه مع الكلمه المدخله.

والسلام

اوكي شكرا على المعلومات

بس في مجال تساعدوني بعمل الكود الذي أريده ؟؟

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

ولكم جزيل شكري

السلام عليكم

مع الاسف اخت ايه انا خبرتى فى c++ محدوده, يمكنك وضع الكود الذى حاولتى فيه وإن شاء الله فى اخوه فى المنتدى يمكنهم ان يقومو بالمساعده. وانا إن شاء الله احاول ان اساعد على قدر المستطاع.

والسلام

اوكي شكرا لكم

ان شاء الله تكون مشكلتي انحلت لاني بدي أجرب اشي تاني غير hash table

تحياتي لكم