بخشی از پاورپوینت
--- پاورپوینت شامل تصاویر میباشد ----
اسلاید 1 :
v انواع روشهاي ديگرHashing کدامند؟ (ادامه...)
vروش Hashing با فضاي پويا (Dynamic) چيست؟
v
vروش Hashing با توسعه خطي (Linear) چيست؟
vروشهايHashingدرمقايسه با يکديگر چگونه اند؟
v
vدر روشهاي Hashingامکان کنترل Splitting چگونه است؟
اسلاید 2 :
vروش Hashing با فضاي پويا (Dynamic) چيست؟
v
روش ديگري از Hashing با فضاي متغير ميباشد که شباهتهاي زيادي با روش قبلي دارد:
qهر دو روش از يک Directory براي نگهداري آدرس Bucketها استفاده ميکنند.
qهر دو روش از ساختار Trie براي بسط دادن فضاي Directory استفاده مينمايند.
q
تفاوت عمدهاين روش اينست که:
qبراي شروع کار مانند روشهاي کلاسيک Hashing از يک تابع Hash براي آدرس دهي در يک فضاي ثابت (Fixed Size) استفاده مينمايد.
q
qهنگاميکه دراثر افزايش تعداد کليدها نيازبه Splitting در Bucketها ميشود، درختواره هايي با ساختار Trie که ريشه آنها در همان فضاي ثابت اوليه قرار دارد شروع به رشد مينمايند.
اسلاید 3 :
مثال:
شکل زير نمونه اي از يک ساختاراوليه Hashing بافضاي پويا را نشان ميدهد.
در اين ساختار چهار Bucket به چهار آدرس موجود در فضاي Directory مرتبط شده اند.
اسلاید 4 :
مثال: (ادامه...)
شکل زير نمونه اي از يک مرحله رشد در يک ساختار Hashing با فضاي پويا را نشان ميدهد.
در اين مرحله، Bucket مرتبط با آدرس4 به دو Bucket جديد تقسيم شده است.
اين نود به دو نود جديد40 و 41 که فرزندان آن ميباشند مرتبط شده است.
نود 4 يک نود Internal محسوب شده ودارایآدرس يک Bucket نخواهد بود.
دو نود جديد 40 و 41 نودهای External محسوب شده ودارایآدرسدو Bucketخواهند بود.
اسلاید 5 :
مثال: (ادامه...)
شکل زير نمونه اي از يک مرحله ديگر رشد در يک ساختار Hashing با فضاي پويا را نشان ميدهد.
دراين مرحله اتفاقي مشابه با مرحله قبل در مورد آدرس 2 و نيز آدرس 41 رخ داده است.
نودهاي جديد 20 و 21 در رابطه با نود 2 ايجاد شده اند.
همچنين، نودهاي 410 و 411 در رابطه با نود 41 ايجاد شده اند.
اسلاید 6 :
اين روش در مقايسه با روش قبلي(ExtendibleHashing) چگونه است؟
با وجود اينکه هر دو روش از ساختار Trie براي بسط دادن فضايHash استفاده مينمايند،
يک تفاوت مهم بين آنها اينست که در روش قبل ساختار Trie به يک Binary Tree کامل و سپس به يک Array تبديل ميشود،
در صورتيکه دراين روش ساختار Trie بصورت درختواره يا Linked Structure استفاده ميگردد.
يک تفاوت اساسي نيز اينست که رشد فضاي Directory دراين روش آهسته تر و بتدريج صورت ميپذيرد.
اسلاید 7 :
اين روش در مقايسه با روش قبلي چگونه است؟ (ادامه...)
از نظر تعداد دسترسي به ديسک، روش قبل اين مزيت را دارد که بيش از حداکثر دودسترسي به ديسک نميتواند داشته باشد.
در اين روش تعداد دسترسي به ديسک ميتواند بيشتر نيز بشود، که به دليل استفاده از Linked Structure در اين روش ميباشد.
درروش قبلفضاي Directory در هرمرحله رشد دو برابر ميگردد.
البته در روش قبلاندازه هر نود Directory ميتواند نصف اندازه نودهاي Directory در اين روش باشد زيرا نياز به نگهداشتن Pointer در آنها نميباشد.
اسلاید 8 :
روش Hashing با توسعه خطي (Linear) چيست؟
روش ديگري از Hashing با فضاي متغير است که با دو روش قبلکاملا متفاوت ميباشد،
بجز در يک مورد که استفاده از بيتهايPrefix براي تعيين Bucketها ميباشد.
در اين روش از ساختار Trie و يا يک Directory جهت آدرس دهي به Bucketها استفادهنميشود.
فضاي رزرو شده بجايDirectory براي خود Bucketها استفاده ميگردد.
و بيتهايPrefix کليد Hash مستقيما برايانتخاب Bucket مورد نظر در اين فضا بکار ميرود.
اسلاید 9 :
الگوريتمHashingبا توسعهخطيچگونه است؟
در اين الگوريتم، يک مکانيسم رشد تدريجي فضاي Hash بصورت زير تامين ميگردد:
هر گاه يک event که معمولا سرريز شدن يکي از Bucketها ميباشد رخ دهد يک Bucket جديد به فضاي Hash اضافه ميگردد. (ولي ...؟)
اين Bucket جديد لزومي ندارد که برايتعديل کليدها در Bucket سرريزشده استفاده گردد.
بلکه بصورتنوبتي براي تعديل کليدها در يکي از Bucketها که بوسيله اشاره گری موسوم به “Next Bucket to Extend” مشخص ميشود استفاده ميگردد.
براي تعديل کليدها بين Bucket بسط يافته و Bucket جديد يک بيت به تعداد بيتهاي Prefix اضافه ميگردد و کليدها بين دو Bucket توزيع ميشوند.
درصورتيکه Bucket سرريز همان Bucket بسط يافته نباشد، بايستي يک Bucket جديد ديگر نيز به Bucket سرريز شده متصل گردد تا کليدهاي اضافي در آن قرار گيرند.
اسلاید 10 :
مثال:
شکل زير نمونه اي از يک ساختاراوليه Hashing با توسعه خطي را نشان ميدهد.
در اين شکل، چهار Bucket براي قرار دادن کليدها رزرو شده اند.
با استفاده از دو بيتاول کليد Hash يکي از چهار Bucket انتخاب ميشود.
