مرجع دانلود پاورپوینت های درسی

حجم فایل : 119.9 KB
نوع فایل : پاور پوینت
تعداد اسلاید ها : 17
بنام خدا File Structure Hashing منظور از Hashing چِيست؟

روش Hashing چگونه است؟

منظور از تلاقي يا Collision چيست؟

روش هاي کم نمودن تلاقي کدامند؟

انتخاب يک Hash Function چگونه است؟

بهينه سازي يک Hash Function چگونه است؟

روش هاي randomization براي کليدهاي عددي چگونه است؟

پيش بيني احتمال تلاقي چگونه است؟

منظور از نسبت تراکم (Packing Density) چيست؟

روش Progressive Overflow چيست؟

File Structure Hashing منظور از Hashing چِيست؟

روشي براي ايجاد ايندکس ميباشد،

که براي يافتن هر کليد به بيش از يک دسترسي به ديسک (I/O) احتياج نخواهيم داشت.

روش Hashing در مقايسه با روش هاي ديگرچگونه است؟

براي يافتن يک کليد در بين N کليد:

روش جست و جوي سري ==> تابع خطي مستقيم در رابطه با N ==> O(N)

روش هاي B-Tree ==> تابع لگاريتمي در رابطه با N ==> O( logk(N) )

روش هاي Hashing ==> تابع ثابت ==> (1)O
File Structure Hashing روش Hashing چگونه است؟

در اين روش تابعي به نام Hash Function تعريف مي شود،

که براي هرمقدارکليد يک آدرس مشخص در فضاي تعيين شده به ما ميدهد. File Structure Hashing مثال :تابع h(k) را در نظر مي گيريم بطوريکه:

کليد k زيرمجموعه اي از مقادير بنام U و
فضاي موجود براي 1000 کليد رزرو شده باشد.

در اينصورت ميتوان نوشت :
h : U { 0,1..,999 }
فرض کنيم h(k) به صورت زير تعريف شده باشد:
h(k) = ( k[0] * k[1]) mod 1000
در اينصورت برای مقدار کليد k = LOWELL خواهيم داشت:
h(LOWELL) = (76 * 79) mod 1000 = 4 File Structure Hashing مثال (ادامه...) :
h : U { 0,1..,999 }
h(k) = ( k[0] * k[1]) mod 1000

به همين صورت برای مقادير کليد زير خواهيم داشت:
File Structure منظور از تلاقي يا Collision چيست؟

در روش Hashing معمولا دو خاصيت زير موجود ميباشد:

هيچ رابطه مستقيمي بين مقادير کليدها و محل آنها در فايل وجود ندارد. (randomizing)

دو کليد مختلف ممکن است در يک آدرس قرار بگيرند. (تلاقي يا collision)

مثال: مقادير کليد زير را در نظر ميگيريم:

h ( LOWELL ) = h ( LOCK ) = h ( OLIVER ) = 4

اين سه کليد که آدرس (home address) آنها يکي ميباشد synonyms خوانده مي شوند.

در واقع جلوگيري از ايجاد synonym ها يا تلاقي (collision) بسيار دشوار مي باشد.
Hashingتلاقي کليدها در روش File Structure روش هاي کم نمودن تلاقي کدامند؟

انتخاب يک hash f...