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

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

1 نظرات
34 بازدیدها
سلام به دوستان عزیز ITPro ای و علاقه‌مندان به مباحث امنیت شبکه. در قسمت پیش بصورت مختصر مقدمه ای بر لزوم وجود هشینگ و مکانیزم ساده ای از چگونگی اجرای تابع هش خدمت شما ارائه شد. در این قسمت قصد داریم تا این بحث را ادامه دهیم. با ما همراه باشید:
Image

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


روشی که در قسمت قبل درباره آن صحبت شد، به تظر روشی خوب و کارا میاید و باعث میشود تا در رابطه با تابع هش بیشتر فکر کنیم. اول از همه، تابع هشی که ما استفاده کردیم (که مجموعی از حروف رشته بود) یک نمونه بد از تابع هش است؛ چرا که مشکلی که ایجاد خواهد شد در جایگشت های همان حروف خواهد بود. برای مثال فرض کنید که ما در مجموعه مان یک رشته "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 ))…)
این بازآرایی عبارات بما این اجازه را میدهد تا بتوانیم مقدار هش را با سرعت بالاتری محاسبه کنیم.
Image

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


یک جدول هش بصورت آرایه ای که در ذخیره سازی داده با هر نوعی استفاده میشود، ذخیره میگردد. در این حالت توانستیم یک جدول عمومی را که میتواند انواع نود ها را ذخیره کند، تعریف کنیم. این ارایه، یک آرایه خالی است که بصورت زیر تعریف میشود:
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)

--
Image

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


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

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

نظرات

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

arrow