بخشی از پاورپوینت
--- پاورپوینت شامل تصاویر میباشد ----
اسلاید 1 :
Hashing
منظور از Hashing چِيست؟
روش Hashing چگونه است؟
منظور از تلاقي يا Collision چيست؟
روش هاي کم نمودن تلاقيکدامند؟
انتخاب يک Hash Function چگونه است؟
بهينه سازي يک Hash Function چگونه است؟
روشهايrandomizationبرايکليدهاي عدديچگونهاست؟
پيش بيني احتمال تلاقيچگونه است؟
منظور از نسبت تراکم (Packing Density) چيست؟
روش Progressi e O erflow چيست؟
اسلاید 2 :
منظور از Hashing چِيست؟
روشي براي ايجاد ايندکس ميباشد،
که براي يافتن هر کليد به بيش از يک دسترسي به ديسک (I/O) احتياج نخواهيم داشت.
روش Hashingدر مقايسه با روش هاي ديگرچگونه است؟
براي يافتن يک کليد در بين N کليد:
(1روش جست و جوي سري==> تابع خطي مستقيم در رابطه با N ==> O(N)
(2روش هاي B-Tree ==> تابع لگاريتمي در رابطه با N ==> O( logk(N) )
(3روش هاي Hashing ==> تابع ثابت ==> (1)O
اسلاید 3 :
روش Hashing چگونه است؟
در اين روش تابعي به نام Hash Function تعريف مي شود،
که براي هرمقدارکليد يک آدرس مشخص در فضاي تعيين شده به ما ميدهد.
اسلاید 4 :
مثال :تابع 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
اسلاید 5 :
مثال (ادامه...) :
h : U à{ 0,1..,999 }
h(k) = ( k[0] * k[1]) mod 1000
به همين صورت برای مقادير کليد زير خواهيم داشت:
اسلاید 6 :
Hashingتلاقي کليدها در روش
منظور از تلاقي يا Collision چيست؟
در روش Hashing معمولا دو خاصيت زير موجود ميباشد:
(1هيچ رابطه مستقيمي بين مقادير کليدها و محل آنها در فايل وجود ندارد. (randomizing)
(2دو کليد مختلف ممکن است در يک آدرس قرار بگيرند. (تلاقي يا collision)
مثال: مقادير کليد زير را در نظر ميگيريم:
h ( LOWELL ) = h ( LOCK ) = h ( OLI ER ) = 4
اين سه کليد که آدرس (home address) آنها يکي ميباشد synonyms خوانده مي شوند.
در واقع جلوگيري از ايجاد synonym ها يا تلاقي (collision) بسيار دشوار مي باشد.
اسلاید 7 :
کم نمودن تلاقي کليدها
روش هاي کم نمودن تلاقيکدامند؟
(1 انتخاب يک hash function خوب براي بسط دادن کامل کليدها در فضاي تعريف شده.
(2 انتخاب فضاي بزرگتر (براي پايين آوردن احتمال تلاقي).
(3 امکان حفظ چند کليد در يک آدرس (buckets) .
اسلاید 8 :
توليد کليد بکمکتابع Hash
انتخاب يک Hash Function چگونه است؟
يک Hash Function ساده که فقط تابع قسمتي از کليد نباشد:
(1 کل طول کليد را تبديل به يک سري اعداد مي کنيم.
مثلا کد اسکي (Ascii) کاراکترهاي آن.
(2 اعداد به دست آمده را به چند دسته تقسيم کرده و با يکديگر جمع مي کنيم.
مثلا هر دو کاراکتر يک دسته را تشکيل مي دهند.
(3 نتيجه به دست آمده را بر فضاي تعيين شده تقسيم مي کنيم
که بهتر است يک عدد اول يا prime number انتخاب شود و
باقيمانده آنرا به عنوان آدرس انتخاب کنيم.
اسلاید 9 :
توليد کليد بکمکتابع Hash
بهينه سازي يک Hash Function چگونه است؟
(1 با مطالعه ساختار کليد ميتوان:
يک الگوي مناسب براي مراحل 1و 2 در روش قبل پيدا نمود،
که نتيجه آن بهتر از بسط دادن اتفاقي کليدها مي باشد. (Better-than-random)
(2 در غير اين صورت مثلا براي کليدهاي عددي ميتوان از روش هاي randomization ديگري نيز استفاده کرد.
اسلاید 10 :
توليد کليد بکمکتابع Hash
روشهايrandomizationبرايکليدهاي عدديچگونهاست؟
(1 روش اول:
کليد را به توان 2 رسانده و
دو يا چند رقم از وسط نتيجه آن را استخراج مي کنيم.
مثال:
(2 روشدوم (Radix Transformation ):
کليد را در مبناي ديگري مثلا 11 محاسبه کرده
سپس بر بزرگترين آدرس موجود تقسيم مي کنيم و
باقيمانده آن را به عنوان آدرس انتخاب مي کنيم.
مثال:
