دانلود پاورپوینت Hashingتلاقی کلیدها در روش

لینک دانلود و خرید پایین توضیحات

دسته بندی : پاورپوینت

نوع فایل :  .PPT ( قابل ویرایش و آماده پرینت )

 قسمتی از متن .PPT : 

تعداد اسلاید : 15 اسلاید

Lecture 18 Hashing: Buckets, Double H., Scatter tables, Chaining area (Sections 11.6 – 11.9) File Structure Hashingتلاقی کلیدها در روش چه راه حل هایی برای مدیریت تلاقی وجود دارد؟

روش سرریز تدریجی (Progressive Overflow)

روش استفاده از Bucket ها

روش Hashing مجدد (Double)

روش سرریز تدریجی زنجیره ای (Chained)

روش زنجیره ای با فضای سرریز مجزا (Separate area)

روش جداول پراکنده (Scatter Tables) File Structure مدیریت تلاقی کلیدها استفاده از Bucket ها چگونه است؟

یک راه حل مساله تلاقی کلیدها اینست که در هرآدرس امکان نگاهداری چند کلید را داشته باشیم.
دراینصورت، مساله جابجایی محل قرارگرفتن کلید کمتر پیش می آید.
مثال:
جدول زیر یک Hash Table نمونه با استفاده از Bucketها را نشان میدهد.
هر Bucket می تواند سه رکورد را در خود جای دهد.
برای آدرس 33 هنوز مشکل سرریزی وجود دارد. (Nutt… is an overflow record) (صفحه 490 و 491 کتاب شکل 11.8) <= File Structure استفاده از Bucket ها Bucket ها در بهبود کارائی (Performance) چه تاثیری دارند؟

استفاده از Bucket ها حتی با ثابت نگاه داشتن نسبت تراکم ( Packing Density )،

تاثیر خوبی بر راندمان hashing خواهد گذاشت،

چون درصد جابجایی کلیدها را پایین می آورد.

در این حالت نسبت تراکم بطریق زیر محاسبه میگردد: که در آن:
r تعداد رکوردها،
N تعداد آدرسها و
b تعداد رکوردهایی که دریک Bucket جا میگیرند،
میباشد. File Structure مثال: فایلی با تعداد 750 رکورد را با دو سازماندهی مختلف در نظر میگیریم:  (جدول 11.3 صفحه 493)
توزیع Poisson برای فایلی با دو سازماندهی متفاوت تاثیر Bucket ها در بهبود کارائی File Structure تاثیر Bucket ها در بهبود کارائی مثال (ادامه...):
دراین فایل تعداد رکوردهایی که در آدرس خود قرار ندارند، چگونه محاسبه میشود؟

حالت اول (b=1): بعبارت دیگر، در این حالت 29.6% جابجایی (Overflow) داریم. File Structure تاثیر Bucket ها در بهبود کارائی مثال (ادامه...):
دراین فایل تعداد رکوردهایی که در آدرس خود قرار ندارند، چگونه محاسبه میشود؟

حالت دوم (b=2): بعبارت دیگر، در این حالت 18.7% جابجایی (Overflow) داریم. File Structure جدول زیر، میزان تلاقی کلیدها را برمبنای درصد رکورد ، برای مقادیر مختلف نسبت تراکم واندازه های مختلف Bucket ها نشان میدهد: تاثیر Bucket ها در بهبود کارائی (جدول 11.4 صفحه 495) File Structure جدول زیر، متوسط تعداد دسترسی لازم در یک جستجوی موفق با روش سرریز تدریجی را نشان میدهد: تاثیر Bucket ها در بهبود کارائی (جدول 11.5 صفحه 496) (- 1973 – Donald Knuth The Art of Computer Programming) File Structure استفاده از Bucket ها بهترین اندازه برای Bucket ها چیست ؟

بستگی به پارامترهای سیستم دارد مثل: اندازه I/O buffer ها، sector ها، cluster ها، track ها و نیز زمان دسترسی به داده ها ( seek time، rotational delay، transfer time)

اندازه یک Track زیاد خوا

دانلود پاورپوینت Hashingتلاقی کلیدها در روش

لینک دانلود و خرید پایین توضیحات

دسته بندی : پاورپوینت

نوع فایل :  .PPT ( قابل ویرایش و آماده پرینت )

 قسمتی از متن .PPT : 

تعداد اسلاید : 15 اسلاید

Lecture 18 Hashing: Buckets, Double H., Scatter tables, Chaining area (Sections 11.6 – 11.9) File Structure Hashingتلاقی کلیدها در روش چه راه حل هایی برای مدیریت تلاقی وجود دارد؟

روش سرریز تدریجی (Progressive Overflow)

روش استفاده از Bucket ها

روش Hashing مجدد (Double)

روش سرریز تدریجی زنجیره ای (Chained)

روش زنجیره ای با فضای سرریز مجزا (Separate area)

روش جداول پراکنده (Scatter Tables) File Structure مدیریت تلاقی کلیدها استفاده از Bucket ها چگونه است؟

یک راه حل مساله تلاقی کلیدها اینست که در هرآدرس امکان نگاهداری چند کلید را داشته باشیم.
دراینصورت، مساله جابجایی محل قرارگرفتن کلید کمتر پیش می آید.
مثال:
جدول زیر یک Hash Table نمونه با استفاده از Bucketها را نشان میدهد.
هر Bucket می تواند سه رکورد را در خود جای دهد.
برای آدرس 33 هنوز مشکل سرریزی وجود دارد. (Nutt… is an overflow record) (صفحه 490 و 491 کتاب شکل 11.8) <= File Structure استفاده از Bucket ها Bucket ها در بهبود کارائی (Performance) چه تاثیری دارند؟

استفاده از Bucket ها حتی با ثابت نگاه داشتن نسبت تراکم ( Packing Density )،

تاثیر خوبی بر راندمان hashing خواهد گذاشت،

چون درصد جابجایی کلیدها را پایین می آورد.

در این حالت نسبت تراکم بطریق زیر محاسبه میگردد: که در آن:
r تعداد رکوردها،
N تعداد آدرسها و
b تعداد رکوردهایی که دریک Bucket جا میگیرند،
میباشد. File Structure مثال: فایلی با تعداد 750 رکورد را با دو سازماندهی مختلف در نظر میگیریم:  (جدول 11.3 صفحه 493)
توزیع Poisson برای فایلی با دو سازماندهی متفاوت تاثیر Bucket ها در بهبود کارائی File Structure تاثیر Bucket ها در بهبود کارائی مثال (ادامه...):
دراین فایل تعداد رکوردهایی که در آدرس خود قرار ندارند، چگونه محاسبه میشود؟

حالت اول (b=1): بعبارت دیگر، در این حالت 29.6% جابجایی (Overflow) داریم. File Structure تاثیر Bucket ها در بهبود کارائی مثال (ادامه...):
دراین فایل تعداد رکوردهایی که در آدرس خود قرار ندارند، چگونه محاسبه میشود؟

حالت دوم (b=2): بعبارت دیگر، در این حالت 18.7% جابجایی (Overflow) داریم. File Structure جدول زیر، میزان تلاقی کلیدها را برمبنای درصد رکورد ، برای مقادیر مختلف نسبت تراکم واندازه های مختلف Bucket ها نشان میدهد: تاثیر Bucket ها در بهبود کارائی (جدول 11.4 صفحه 495) File Structure جدول زیر، متوسط تعداد دسترسی لازم در یک جستجوی موفق با روش سرریز تدریجی را نشان میدهد: تاثیر Bucket ها در بهبود کارائی (جدول 11.5 صفحه 496) (- 1973 – Donald Knuth The Art of Computer Programming) File Structure استفاده از Bucket ها بهترین اندازه برای Bucket ها چیست ؟

بستگی به پارامترهای سیستم دارد مثل: اندازه I/O buffer ها، sector ها، cluster ها، track ها و نیز زمان دسترسی به داده ها ( seek time، rotational delay، transfer time)

اندازه یک Track زیاد خوا