دانلود پاورپوینت Hashing
دسته بندي :
علوم پایه »
دانلود پاورپوینت های علمی
لینک دانلود و خرید پایین توضیحات
دسته بندی : پاورپوینت
نوع فایل : powerpoint (..ppt) ( قابل ويرايش و آماده پرينت )
تعداد اسلاید : 17 اسلاید
قسمتی از متن powerpoint (..ppt) :
بنام خدا
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( log k (N) )
روش هاي Hashing ==> تابع ثابت ==> (1) O
File Structure
Hashing
روش Hashing چگونه است؟
در اين روش تابعي به نام Hash Function تعريف مي شود ،
که ب راي هر مقدار کليد يک آدرس مشخص در فضاي تعيين شده به ما ميد هد.
A
B
C
D
E
F
G
1
2
3
4
5
6
7
8
9
10
Key
Address
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( LO WELL ) = (76 * 79) mod 1000 = 4
LOWELL ’s
home
address
K=LOWELL
h(K)
Address
Address
Record
key
1
2
3
4
0
5
6
...
...
LOWELL . . .
= 4