جدول تجزئة: الفرق بين النسختين

[نسخة منشورة][نسخة منشورة]
تم حذف المحتوى تمت إضافة المحتوى
ط نقل Nehaoua صفحة جدول التقطيع إلى جدول تجزئة: المقالة أشمل
وسم: مُسترجَع
لا ملخص تعديل
وسمان: استرجاع يدوي تعديل مصدر 2017
سطر 1:
[[ملف:HASHTB12.svg|تصغير|200بك|يسار]]
{{مصدر|تاريخ=فبراير 2016}}
'''جدول التجزئة''' ويعرف أيضا بـ: ('''جدول هاش،''' '''جداول التقطيع، خريطة هاش، خريطة تقطيع، قاموس هاش، قاموس التقطيع)''' هو أحد بنى المعطيات في [[علم الحاسوب]] يملك خصائص المصفوفات الترابطية (associative array) ويمكن باستخدامه اسناد قيمة إلى مفتاح ما في ذاكرة الحاسب. والبحث عن قيم محددة بسرعة كبيرة مقارنة ببنى المعطيات الاخرى.
{{وصلات قليلة|تاريخ=يناير 2014}}
{{يتيمة|تاريخ=مارس 2009}}
'''جدول التقطيع''' في علوم الحاسب هو بنية معطيات تربط مفاتيح بقيم.
تدعم هذه البنية العمليات المعجميّة(البحث، الإضافة والحذف) بفعاليّة عالية، حيث يمكن القيام بكلِ من هذه العمليات باستخدام هذه البنية في زمن ثابت (O(1.
تعمل هذه البنية بتحويل المفتاح إلى قيمة عددية عادةً بوساطة تابع تقطيع.
 
يستعمل [[جدول التقطيع]]، تابع تقطيع يمكنه من حساب مكان القيمة في لائحة المفاتيح.
== العمليات الأساسية ==
يعمل جدول التقطيع بتحويل المفتاح إلى [[قيمة عددية]] باستخدام تابع تقطيع, هذه القيمة العددية تحدد مكان العنصر الحامل للمفتاح المقابل لها, تختلف جودة تابع التقطيع باختلاف التطبيق الذي يستخدم الجدول فيه وباختلاف تابع التقطيع.
 
في الحالة المثالية، يفترض بجدول التقطيع، ربط كل مفتاح بحجرة معينة، لكن في الواقع ذلك يجعل زمن البحث فيه عن القيم المتضاربة كبيراً جداً، لذلك تم إيجاد عدة حلول ونماذج لجداول التقطيع تم فيها افتراض وجود قيم متضاربة وتم تحسين زمن البحث فيها بشكل كبير.
بعض العمليات المعتادة على توابع التقطيع تتضمن الإدخال, الحذف و البحث, تنفذ كل هذه العملبات في وقت ثابت (بالكلفة)، مما يجعل استخدام هذه الجداول عملية فعالة جداً.
 
{{تهذيب|تاريخ=نوفمبر 2015}}
== معامل الحمل ==
أحد الخواص المهمة لجدول تقطيع ما هو نسبة امتلاء هذا الجدول, و هو نسبة عدد العناصر الموجودة في الجدول(n) إلى مساحة الجدول الكليّة (m).
و منه, يتضح تسمية النسبة (a=n/m) بمعامل الحمل.
معظم جداول التقطيع تربط الأداء الجيد ببقاء
عامل الحمل في مجال معين.
 
== جداول التقطيع ذات العنونة المباشرة (المفتوحة) ==
== حل التصادمات ==
العنونة المباشرة هي طريقة بسيطة التي تعمل كما يجب عندما المجموعة الكلية للمفاتيح U تكون صغيرة نسبيا لنفترض انه لتطبيق معين طلب مجموعة ديناميكية حيث ان لكل فرد في المجموعة اخذ مفتاح من {U={1,2,3,...,m-1 عندما m ليس عددا ضخما سنفترض ان المفاتيح الماخوذة مختلفة تماما.
بما أن الهدف من التقطيع هو إيجاد قيمة وحيدة لكل مفتاح, فعندما يوجد تابع التقطيع القيمة ذاتها لأكثر من مفتاح فيجب إيجاد مكان بديل للمفتاح الجديد, عملية إيجاد مكان جديد تعرف ب: '''حل التصادمات'''، إن حل التصادمات يجب أن يكون ب[[خوارزمية]] محددة، أي أن يضمن أن البحث المستقبلي عن القيمة سيرد النتيجة الصحيحة.
جدول العنونة سنطبقها بواسطة مصطفة اي جداول العنونة مباشرة (directed adress table) سيكون [T[0,...,m-1 وكل مكان في الجدول يسمى خلية أو slot الذي يلائم مفتاحا من المجموعة الكلية إذا الجدول لم يحوِ أيّ مفتاح قيمته k حينها [nil=T[k
<syntaxhighlight lang="freebasic">
direct-adress-search(T,k)
return T[k]
Direct-adress-insert(T,x)
T[key[x]]<-x
Direct-adress-delete(T,x)
T[key[x]]<-NIL
</syntaxhighlight>
كل الخوارزميات في الأعلى سريعة وفعالة حيث ان كل منها يقوم بعدد قليل من العمليات (O(1
== جداول هاش ==
الصعوبة في جداول العنونة المباشرة هي كبر المجموعة U حيث ان القيام بحفظ مصفوفة بحجم |U| غير واقعي وغير تطبيقي ومن ناحية أخرى قد تكون المجموعة K صغيرة كثيرا بالنسبة ل-U وعندها أغلب الأماكن في U ستكون حتما غير نافعة.
عندما تكون المجموعة K (القاموس) صغيرة جدا بالنسبة ل-U جدول هاش سيتطلب مكان اقل من جداول عنونة مباشرة اي سيتطلب جدول هاش (|O(|K بالرغم من أن بحث قيمة معينة في الجدول سيكون أيضا (O(1 المشكلة الوحيدة هو ان البحث في جدول الهاش هو متوقع بينما في العنونة المباشرة البحث هو (O(1 '''دائما'''
بالعنونة المباشرة حفظنا المفتاح k في الخلية k اما في الهاش فهذا المفتاح سوف يحفظ في (h(k اي اننا سوف نستخدم دالة هاش (hash function) لحساب الخلية التي سنحفظ فيها المفتاح k،
<syntaxhighlight lang="freebasic">
h:U->{0,1,...,m-1}
</syntaxhighlight>
نقول ان المفتاح k منقول(hashes)للخلية (h(k ; اي انه (h(k يسمى قيمة الهاش (hash value).
مشكلة من نوع اخر تظهر في الهاش وهي عندما يكون هناك مفتاحان k,t قيم الهاش خاصتهما متشابه اي : (h(t)=h(k
تسمى هذه الظاهرة بالتشابك في جدول الهاش أو collision ولهذه المشكلة يوجد حلول جيدة وفعالة.
قد يتبادر إلى الذهن حل عن طريق جعل h دالة عشوائية وساعتها سيكون هنالك اقل تشابك ولكن هذا الحل ليس طبيعي لاننا نريد الدالة h قطعية(deterministic)
الطريقة الأفضل لحل هذه المشكلة هي السلسلة (chaining) وهناك طريقة أخرى وهي العنونة المفتوحة (open addressing)
== حل مشكلة التشابك على طريق السلسلة ==
في طريقة السلسلة (chaining) كل التشابكات في نفس الخلية نسلسلها بواسطة سلسلة
عند حل التشابكات بواسطة السلسلة من السهل ان نطبق عمليات الجدول T
<syntaxhighlight lang="freebasic">
Chained-hash-Insert(T,x)
enter x in the haed of T[h(key(x))]
chained-hash-search(T,k)
search item with key value k in the list of T[h(k)]
chained-hash-delete(T,x)
delete x from T[h(key(x))]
</syntaxhighlight>
عملية الإدخال تتم ب-(O(1 وقت اما البحث ففي الحالة الأسوأ يكون البحث (|[[O(|T[h[key ولكن في حالات الوسط يكون (O(1 اما الحذف (O(1 عندما تكون السلسلة ذو اتجاهين اما إذا كانت ذو اتجاه واحد عندها سيتطلب منا البحث اولا من ثم الحذف اي انه سيتطلب وقتا كما في البحث
== تحليل الهاش مع سلسلة ==
عند إعطاءنا جدول T hg الذي يحوي على m خلايا و n قيم نعرف مقدم الكثافة(load factor) الخاص ب-T أو a=n/m اي معدل القيم المحفوظة في السلسلة الواحدة
في السيناريو الأسوأ فعالية الهاش مع سلسلة جدا سيئة : كل n المفاتيح موزعين لنفس الخلية ونكون سلسلة طويلة جدا والبحث عندها سيكون (O(n +الوقت المطلوب لحساب دالة الهاش وهو ليس بأفضل من البحث في سلاسل عادية
اما في السيناريو الوسط فعالية الهاش تقاس بمدى توزيع الدالة h للقيم بين المفاتيح سنفترض ان التوزيع سيكون بالتساوي اي ان الاحتمال بان قيمة معينة تذهب إلى مفتاح متساوية بين كل المفاتيح وكذلك سنفترض ان حساب دالة الهاش هو (O(1
قانون :
في جدول هاش مع سلسلة فيه التوزيع متساو لكل المفاتيح بحث فاشل يقوم ب-(O(1+a فعاليات (وقت الفعالية)
اثبات :
بما ان التوزيع متساو لكل المفاتيح الاحتمال بان مفتاح K يذهب لخلية معينة متساو لكل الخلايا (m خلايا) لذا الوقت المتوسط للبحث الفاشل عن k مساو تماما للوقت المتوسط لبحث أحد السلاسل والطول المتوقع لسلسلة كهذه هو مقدم الكثافة أو a اي ان وقت البحث المتوسط هو a ومع حساب دالة الهاش :
الوقت المتوقع هو : (O(1+a.
قانون :
في جدول هاش مع تشابك وفي الجدول التوزيع للمفاتيح متساو, بحث ناجح متوسط وقت البحث هو: (O(1+a.
ومن القانونين في الأعلى نستنتج ان كبر الجدول يجب أن يكون مشابها لعدد القيم المراد تخزينها اي بحالة وجود (O(n قيم عندها كبر الجدول هو (O(n وعندها تكون العلمليات كل واحد منها تنفذ ب-(O(1 وقت
== دوال هاش ==
{{مفصلة|دالة تجزئة}}
هنالك عدة حالات بناء على المعلومات التي لدينا عن التوزيع:<ref>{{مرجع كتاب|title=أساسيات أمن المعلومات والحاسوب|url=https://books.google.com.sa/books?id=dfhQDwAAQBAJ&pg=PA343&dq=%D8%AF%D8%A7%D9%84%D8%A9+%D9%87%D8%A7%D8%B4&hl=ar&sa=X&ved=2ahUKEwiG-OaphcXqAhUIxIUKHTnWDAYQ6AEwAHoECAYQAg#v=onepage&q=%D8%AF%D8%A7%D9%84%D8%A9%20%D9%87%D8%A7%D8%B4&f=false|publisher=Al Manhal|date=2010-01-01|ISBN=9796500012308|language=ar|author1=خضر مصباح إسماعيل| مسار الأرشيف = https://web.archive.org/web/20200712054223/https://books.google.com.sa/books?id=dfhQDwAAQBAJ&pg=PA343&dq=دالة+هاش&hl=ar&sa=X&ved=2ahUKEwiG-OaphcXqAhUIxIUKHTnWDAYQ6AEwAHoECAYQAg#v=onepage&q=دالة%20هاش&f=false | تاريخ الأرشيف = 12 يوليو 2020 }}</ref>
# إذا كان التوزيع معطى اي انه لكل مفتاح عندها:(h(k)=floor(km
في الحالات الأخرى وعند الافتراض ان المفاتيح ارقام طبيعية نستطيع استخدام الطرق التالية :
# * طريقة [[قسمة (رياضيات)|القسمة]] اي: h(k)=m mod k
# * طريقة [[ضرب|الضرب]] اي: ((h(k)=(floor(m(1 kA mod عندما: A بين 0 و 1
 
== مراجع ==
{{بذرة علم الحاسوب}}
{{مراجع}}
 
{{ضبط استنادي}}
{{شريط بوابات|علم الحاسوب|تقنية المعلومات|تعمية}}
 
[[{{تصنيف:علم الحاسوب]]كومنز|Hash tables}}
 
[[تصنيف:فهرسة دالاتية]]
[[تصنيف:بنى البيانات]]
[[تصنيف:خوارزميات بحث]]
{{بذرة[[تصنيف:1953 في علم الحاسوب}}]]