دانلود پاورپوینت Hashing: Algorithm, Collision, Packing

\n

Hashing: Algorithm, Collision, Packing

\n

\n

عنوان های پاورپوینت  : 

\n

\n

\n

Hashing: Algorithm, Collision, Packing

\n

Lecture 17Hashing: Algorithm, Collision, Packing (Sections 11.1 – 11.5)

\n

Hashing

\n

Hashing

\n

Hashing

\n

Hashing

\n

Hashing

\n

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

\n

کم نمودن تلاقی کلیدها

\n

تولید کلید بکمک تابع Hash

\n

تولید کلید بکمک تابع Hash

\n

تولید کلید بکمک تابع Hash

\n

محاسبه احتمال تلاقی کلیدها

\n

محاسبه احتمال تلاقی کلیدها

\n

محاسبه احتمال تلاقی کلیدها

\n

راه حلی برای تلاقی کلیدها

\n

راه حلی برای تلاقی کلیدها

\n

\n \n\n \n\n

---

\n\nقسمت ها و تکه های اتفاقی از فایل\n\n \n\n \n\nHashing: Algorithm, Collision, Packing\n\n2pro.ir\n\nLecture 17Hashing: Algorithm, Collision, Packing (Sections 11.1 – 11.5)\n\nHashing\n\nمنظور از Hashing چِیست؟\n\n \n\nروش Hashing  چگونه است؟\n\n \n\nمنظور از تلاقی  یا Collision چیست؟\n\n \n\nروش های کم نمودن تلاقی کدامند؟\n\n \n\nانتخاب یک Hash Function چگونه است؟\n\n \n\nبهینه سازی یک Hash Function چگونه است؟\n\n \n\nروش های randomization برای کلیدهای عددی چگونه است؟\n\n \n\nپیش بینی احتمال تلاقی چگونه است؟\n\n \n\nمنظور از نسبت تراکم (Packing Density) چیست؟\n\n \n\nروش Progressive Overflow چیست؟\n\n \n\n \n\nHashing\n\nمنظور از Hashing چِیست؟\n\n \n\nروشی برای ایجاد ایندکس میباشد،\n\n \n\nکه برای یافتن هر کلید به بیش از یک دسترسی به دیسک (I/O) احتیاج نخواهیم داشت.\n\n \n\nروش Hashing در مقایسه با روش های دیگرچگونه است؟\n\n \n\nبرای یافتن یک کلید در بین N کلید:\n\n \n\nروش جست و جوی سری ==>   تابع خطی مستقیم در رابطه با N   ==>  O(N)\n\n \n\nروش های B-Tree      ==>   تابع لگاریتمی در رابطه با N       ==>  O( logk(N) )\n\n \n\nروش های Hashing     ==>   تابع ثابت                              ==>  (1)O\n\n \n\nHashing\n\nروش Hashing  چگونه است؟\n\n \n\nدر این روش تابعی به نام Hash Function تعریف می شود،\n\n \n\nکه برای هرمقدارکلید یک آدرس مشخص در فضای تعیین شده به ما میدهد.\n\nHashing\n\nمثال :تابع h(k) را در نظر می گیریم بطوریکه:\n\n \n\nکلید k    زیرمجموعه ای از مقادیر بنام U  و\n\nفضای موجود برای 1000 کلید رزرو شده باشد.\n\n \n\nدر اینصورت میتوان نوشت :\n\nh : U { 0,1..,999 }\n\nفرض کنیم h(k) به صورت زیر تعریف شده باشد:\n\nh(k) = ( k[0] * k[1]) mod 1000\n\nدر اینصورت برای مقدار کلید k = LOWELL خواهیم داشت:\n\nh(LOWELL) = (76 * 79) mod 1000 = 4\n\nHashing\n\nمثال (ادامه...) :\n\nh : U { 0,1..,999 }\n\nh(k) = ( k[0] * k[1]) mod 1000\n\n \n\nبه همین صورت برای مقادیر کلید زیر خواهیم داشت:\n\n \n\nHashingتلاقی کلیدها در روش\n\nمنظور از تلاقی  یا Collision چیست؟\n\nدر روش Hashing  معمولا دو خاصیت زیر موجود میباشد:\n\n \n\nهیچ رابطه مستقیمی بین مقادیر کلیدها و محل آنها در فایل وجود ندارد.  (randomizing)\n\n \n\nدو کلید مختلف ممکن است در یک آدرس قرار بگیرند.  (تلاقی یا collision)\n\n \n\nمثال:  مقادیر کلید زیر را در نظر میگیریم:\n\n \n\nh ( LOWELL ) = h ( LOCK ) = h ( OLIVER ) = 4\n\n \n\nاین سه کلید که آدرس (home address) آنها یکی میباشد synonyms  خوانده می شوند.\n\n \n\n....\n\nروش اول:\n\n \n\nکلید را به توان 2 رسانده و\n\nدو یا چند رقم از وسط نتیجه آن را استخراج می کنیم.\n\nمثال:\n\n \n\nمحاسبه احتمال تلاقی کلیدها\n\nپیش بینی احتمال تلاقی چگونه است؟\n\n \n\nدر صورتیکه توزیع کلیدها کاملا  random باشد،\n\nبکمک تابع Poisson  میتوان احتمال تلاقی آدرسها را پیش بینی کرد:\n\nمحاسبه احتمال تلاقی کلیدها\n\n \n\nپیش بینی احتمال تلاقی چگونه است؟\n\n \n\nمثال: اگر N= 1000  و  r= 1000 باشد، خواهیم داشت:\n\n \n\n368 آدرس بدون کلید\n\n \n\n368 آدرس با یک کلید\n\n \n\n184 آدرس با دو کلید\n\n \n\n61 آدرس با سه کلید\n\nمحاسبه احتمال تلاقی کلیدها\n\nمنظور از نسبت تراکم (Packing Density) چیست؟\n\n \n\nنسبت  r به N را (یعنی r/N) نسبت تراکم یا (Packing Density) می گویند.\n\nبا پایین آوردن نسبت تراکم، احتمال تلاقی نیز کمتر میشود.\n\n \n\nمثال: در مثال قبل اگر نسبت تراکم را کمتر کنیم مثلا  r= 500و N= 1000 باشند خواهیم داشت:\n\n \n\nنسبت تراکم:\n\n \n\n \n\n607آدرس بدون کلید\n\n \n\n303 آدرس با یک کلید\n\n \n\n90آدرس با دو کلید یا بیشتر\n\nراه حلی برای تلاقی کلیدها\n\nروش Progressive Overflow چیست؟\n\n \n\nراه حلی برای مساله تلاقی کلیدها میباشد،\n\n \n\nهرگاه آدرس مربوط به یک  کلید (Home address) بوسیله کلید دیگری اشغال شده باشد،\n\n \n\nاولین آدرس آزاد بعد  از آن را برای قرار دادن کلید انتخاب میکنیم.\n\n \n\nمثال (1) : شکل زیر نحوه قرار دادن کلید York را با استفاده از روش فوق نشان میدهد:\n\nراه حلی برای تلاقی کلیدها\n\nمثال (2) : شکل زیر نحوه قرار دادن کلید Blue را با استفاده از روش فوق نشان میدهد:\n\n \n\n \n\n \n\n30 تا 70 درصد پروژه | پاورپوینت | سمینار | طرح های کارآفرینی و  توجیهی |  پایان-نامه |  پی دی اف  مقاله ( کتاب ) | نقشه | پلان طراحی |  های آماده به صورت رایگان میباشد ( word | pdf | docx | doc )