در توسینسو تدریس کنید

و

با دانش خود درآمد کسب کنید

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

سلام به دوستان عزیز 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 ای باشید.

پایان

نویسنده: احسان امجدی

منبع: انجمن تخصصی فناوری اطلاعات ایران

هرگونه نشر و کپی برداری بدون ذکر منبع و نام نویسنده دارای اشکال اخلاقی می باشد.

#تابع_هش_چیست؟ #هش_کد_چگونه_تعریف_میشود؟ #hash_function_چیست؟ #آرایه_هش_به_چه_صورت_است؟ #جدول_هش_چیست؟ #تابع_درهم_سازی_چیست؟ #hash_table_چیست؟
عنوان
1 معرفی راهکار هشینگ (Hashing) - بخش اول رایگان
2 معرفی راهکار هشینگ (Hashing) – بخش دوم رایگان
زمان و قیمت کل 0″ 0
2 نظر
فرهاد خانلری

"itpro سایت خیلی خوبی است"

مرسی مهندس

setareh

سلام

وقت بخیر

ببخشید برای حل این سوال چه کار باید کرد؟

یک رشته حاوی نام و شماره دانشجویی خودتان بیابید که چکیده آن در SHA256 در مبنای 16 با چهار

رقم یک تمام شود. به عنوان نمونه رشته زیر را در نظر بگیرید:

I am amir my student no is 123456789. haha hgqwdk qwj2388

چکیده این رشته برابر زیر است که پاسخ صحیح برای این مسئله محسوب میشود.

9ad29873880c032b832de70c773b39bf930f25d338339d31f4f8b2a4ab081111

ممنون میشم راهنمایی بفرمایید.

نظر شما
برای ارسال نظر باید وارد شوید.
از سرتاسر توسینسو
تنظیمات حریم خصوصی
تائید صرفنظر
×

تو می تونی بهترین نتیجه رو تضمینی با بهترین های ایران بدست بیاری ، پس مقایسه کن و بعد خرید کن : فقط توی جشنواره تابستانه می تونی امروز ارزونتر از فردا خرید کنی ....