درخواست های ارتباط
جستجو
    لیست دوستان من
    صندوق پیام
    همه را دیدم
    • در حال دریافت لیست پیام ها
    صندوق پیام
    رویدادها
    همه را دیدم
    • در حال دریافت لیست رویدادها
    همه رویدادهای من
    تخفیف های وب سایت
    همه تخفیف ها

    عضویت در

    کانال تلگرام

    توسینسو

    اطلاعات مطلب
      مدرس/نویسنده
      احسان امجدی
      امتیاز: 58440
      رتبه:14
      1
      199
      45
      620
      احسان امجدی ، مشاور امنیت اطلاعات و ارتباطات و تست نفوذ سنجی ، هکر کلاه سفید ، مدرس دوره های تخصصی امنیت اطلاعات و شبکه ، تخصص در حوزه های سرویس های مایکروسافت ، Routing و Switching ، مجازی سازی ، امنیت اطلاعات و تست نفوذ ، کشف جرائم رایانه ای و سیستم عامل لینوکس ، متخصص در حوزه SOC و ... پروفایل کاربر

      معرفی راهکار هشینگ (Hashing) – بخش دوم

      تاریخ 44 ماه قبل
      نظرات 1
      بازدیدها 326
      سلام به دوستان عزیز ITPro ای و علاقه‌مندان به مباحث امنیت شبکه. در قسمت پیش بصورت مختصر مقدمه ای بر لزوم وجود هشینگ و مکانیزم ساده ای از چگونگی اجرای تابع هش خدمت شما ارائه شد. در این قسمت قصد داریم تا این بحث را ادامه دهیم. با ما همراه باشید:
      معرفی راهکار هشینگ (Hashing) – بخش دوم

      مشکلی که در رابطه با هشینگ وجود دارد


      روشی که در قسمت قبل درباره آن صحبت شد، به تظر روشی خوب و کارا میاید و باعث میشود تا در رابطه با تابع هش بیشتر فکر کنیم. اول از همه، تابع هشی که ما استفاده کردیم (که مجموعی از حروف رشته بود) یک نمونه بد از تابع هش است؛ چرا که مشکلی که ایجاد خواهد شد در جایگشت های همان حروف خواهد بود. برای مثال فرض کنید که ما در مجموعه مان یک رشته "abc" و یک رشته "bac" داشته باشیم. در این صورت اگر طبق تابع هش قسمت قبل بخواهیم پیش برویم، در نهایت ارزشی را که از عمل مجموع بدست خواهیم آورد و متعاقب آن کلید حاصله نیز مشابه خواهند بود. در این حالت رشته ها باید هر دو در یک مکان هش شوند، که در این صورت چیزی که به آن تصادم (Collision) گوییم رخ خواهد داد . این اصلا موضوع خوبی نیست. ثانیا، باید یک سایز خوب برای جدول هش پیدا کنیم، ترجیحا باید یک عدد اول باشد؛ در این صورت هرگاه مجموع اعداد متناظر با کاراکترها با یکدیگر متفاوت باشد، در هنگام عمل باقیمانده گیری از تقسیم مجموع بر سایز جدول، تا حد زیادی از رخداد تصادم (collision) جلوگیری خواهد شد.

      سوال اول: چگونه میتوانیم یک تابع هش خوب انتخاب کنیم؟
      سوال دوم: چگونه میتوان از رخداد تصادم (Collision) پیشگیری نمود؟

      مساله ذخیره سازی و بازیابی داده در زمان(O(1، برای جواب دادن به سوال های فوق بکمک میآید. انتخاب یک تابع هش "خوب"، کلید موفقیت در پیاده سازی یک جدول هش است. وقتی میگوییم "خوب" منظورمان اینست که تابع باید براحتی محاسبه شود و تا حد امکان از وقوع تصادم جلوگیری کند. اگر تابع بسختی محاسبه شود، آنگاه مزیت جستجوی در زمان (O(1 را از دست خواهیم داد. هرگاه یک تابع هش خیلی خوب را انتخاب کردیم، توانسته ایم تا حد زیادی از وقوع تصادم ها بکاهیم.

      پیدا کردن یک تابع هش "خوب"


      پیدا کردن یک تابع هش تمام و کمال بسیار سخت است، در چنین تابعی هیچگونه تصادمی رخ نمیدهد. اما میتوانیم وضعیت تابع هش را با انجام کارهای زیر بهتر نماییم. فرض کنید نیاز داریم تا یک دیکشنری را در جدول هش ذخیره کنیم. یک دیکشنری مجموعه ای از رشته ها است و میتوانیم برای آن یک تابع هش بشکل زیر تعریف کنیم. فرض کنید که S رشتهای به طول n و p یک عدد اول است:
      S= S1S2….Sn
      H(S)=H(“S1S2….Sn”)=S1+ p S2 + p2 S3 + …. + pn-1 Sn
      
      بروشنی مشخص است هر رشته نهایتا به عدد منحصربفردی ختم خواهد شد، اما زمانی که میخواهیم باقیمانده تقسیم عدد حاصله بر سایز جدول هش را بدست آوریم، هنوز این امکان وجود دارد تصادم رخ دهد اما این مقدار تصادم بسیار کمتر از زمانی خواهد بود که از تابع هش اولیه که در قسمت پیش توضیح داده شد، استفاده کردیم.
      اگر چه تابع هشی که در بالا گفته شد توانست مقدار تصادم ها را کاهش دهد اما هنوز با این حقیقت که تابع هش باید راحت محاسبه شود، روبرو هستیم. با فرض این که تابع بالا را بطور مستقیم محاسبه کنیم، میتوانیم تعداد محاسبات را با مرتب سازی عبارات بصورت زیر تا حدی کاهش دهیم:
      H(S) = S1 + p ( S2 + p ( S3 + …. p ( Sn-1 + p Sn ))…)
      
      این بازآرایی عبارات بما این اجازه را میدهد تا بتوانیم مقدار هش را با سرعت بالاتری محاسبه کنیم.
      معرفی راهکار هشینگ (Hashing) – بخش دوم

      پیاده سازی یک جدول هش ساده


      یک جدول هش بصورت آرایه ای که در ذخیره سازی داده با هر نوعی استفاده میشود، ذخیره میگردد. در این حالت توانستیم یک جدول عمومی را که میتواند انواع نود ها را ذخیره کند، تعریف کنیم. این ارایه، یک آرایه خالی است که بصورت زیر تعریف میشود:
      Void* A[n];
      
      آرایه باید بصورت زیر آغاز شود:
      For ( i = 0 ; i< n ; i++ )
               A[i] = NULL ;
      
      فرض کنید میخواهیم رشته ها در این جدول ذخیره کنیم و میتوانیم آن ها را بسرعت پیدا کنیم. به منظور این که بدانیم که کجا باید رشته ها را ذخیره کنیم، باید یک مقدار را با استفاده از تابع هش برای آن ها محاسبه کنیم. یک تابع هش ممکن در این باره بصورت زیر است:
      S= S1S2….Sn
      H(S) = H(“S1S2….Sn”) = S1+ p S2 + p2 S3 + …. + pn-1 Sn
      
      نکته: پارامتر p یک عدد اول است.
      میتوان با استفاده از عمل فاکتورگیری، محاسبه در معادله بالا را کاراتر نمود. با استفاده از عمل فاکتورگیری در معادله بالا، میتوانیم یک تابع hashcode را تعریف کنیم که مقدار هش را برای یک رشته بصورت زیر محاسبه نماید:
      Inthashcode (char*s) {
      Int sum = s[strlen(s) – 1 ] , p = 101 ;
      Inti ;
            For ( i = 1 ; i<strlen(s) ; i++ )
                  Sum = s[strlen(s) - i – 1 ] + p * sum ;
           Return sum ;
      }
      
      این کد اجازه میدهد تا هر رشته ای در جدول بصورت زیر قرار گیرد. فرض میکنیم سایز جدول 101 است:
      A[hashcode(s) % 101 ] = s ;
      
      مشکلی که در روش بالا وجود دارد اینست که اگر هر تصادمی رخ دهد، به این معنی است که دو رشته با کد هش یکسان وجود دارند؛ در این صورت ناخودآگاه یکی از رشته ها را از دست خواهیم داد. بنابراین نیاز داریم تا راهی پیدا کنیم که بتوان بوسیله آن تصادم را در جدول مدیریت کرد.

      تصادم ها (collisions)

      --
      معرفی راهکار هشینگ (Hashing) – بخش دوم

      مساله ای که در رابطه با هشینگ وجود دارد اینست که ممکن است دو رشته در یک مکان جدول هش شوند. به این رویداد، تصادم گویند. میتوان این مساله را با راهکارهای زیادی مانند جستجوی خطی (جستجوی برای مکان موجود بعدی .... ,i+1, i+2 در مقدار هش شده i)، جستجوی درجه دوم (مانند جستجوی خطی، با این تفاوت که بدنبال موقعیت های موجود بعدی .... ,i+1, i+4, i+9 در مقدار هش شده i هستیم و در صورت هش شدن دو رشته در یک مکان از یک لیست لینک شده استفاده میکنیم) مدیریت نمود.
      مانا و ITPro ای باشید.
      پایان


      نویسنده: احسان امجدی
      منبع: انجمن تخصصی فناوری اطلاعات ایران
      هرگونه نشر و کپی برداری بدون ذکر منبع و نام نویسنده دارای اشکال اخلاقی می باشد.
      برچسب ها
      ردیفعنوان
      1معرفی راهکار هشینگ (Hashing) - بخش اول
      2معرفی راهکار هشینگ (Hashing) – بخش دوم
      دورهمجموعه کل دوره
      مطالب مرتبط

      در حال دریافت اطلاعات

      نظرات

      برای ارسال نظر ابتدا به سایت وارد شوید