دانلود فایل پاورپوینت Dynamic Hashing, Linear Hashing

— پاورپوینت شامل تصاویر میباشد —-

اسلاید ۱ :

v انواع روشهای دیگر Hashing کدامند؟     (ادامه…)

vروش Hashing با فضای پویا (Dynamic) چیست؟

v

vروش Hashing با توسعه خطی (Linear) چیست؟

vروشهای Hashing درمقایسه با یکدیگر چگونه اند؟

v

vدر روشهای Hashing امکان کنترل Splitting چگونه است؟

اسلاید ۲ :

vروش Hashing با فضای پویا (Dynamic) چیست؟

v

روش دیگری از Hashing با فضای متغیر میباشد که شباهتهای زیادی با روش قبلی دارد:

qهر دو روش از یک Directory برای نگهداری آدرس Bucketها استفاده میکنند.

qهر دو روش از ساختار Trie برای بسط دادن فضای Directory استفاده مینمایند.

q

تفاوت عمده این روش اینست که:

qبرای شروع کار مانند روشهای کلاسیک Hashing از یک تابع Hash  برای آدرس دهی در یک فضای ثابت (Fixed Size) استفاده مینماید.

q

qهنگامیکه دراثر افزایش تعداد کلیدها نیازبه Splitting در Bucketها میشود، درختواره هایی با ساختار Trie که ریشه آنها در همان فضای ثابت اولیه قرار دارد شروع به رشد مینمایند.

اسلاید ۳ :

  مثال:

  شکل زیر نمونه ای از یک ساختاراولیه Hashing با فضای  پویا را نشان میدهد.

 در این ساختار چهار Bucket به چهار آدرس موجود در فضای Directory مرتبط شده اند.

اسلاید ۴ :

      مثال: (ادامه…)

شکل زیر نمونه ای از یک مرحله رشد در یک ساختار Hashing با فضای  پویا را نشان میدهد.

در این مرحله، Bucket مرتبط با آدرس ۴ به دو Bucket جدید تقسیم شده است.

این نود به دو نود جدید ۴۰ و ۴۱ که فرزندان آن میباشند مرتبط شده است.

نود ۴ یک نود Internal محسوب شده ودارای آدرس یک Bucket نخواهد بود.

دو نود جدید ۴۰ و ۴۱ نودهای External محسوب شده ودارای آدرس دو Bucket خواهند بود.