احسان امجدی
کارشناس امنیت اطلاعات و ارتباطات

Hash چیست و Hashing | هشینگ به چه معناست؟ راهنمای جامع

Hashing چیست؟ بی شک واژه هش و هشینگ را ممکن است روزانه بارها و بارها بشنوید و یا در صحبت های خود بکار برید. درباره ان نظر میدهید و نظر میشنوید اما خیلی کمتر از آن رغبت کرده اید خود را در دریای مفهوم آن غرق کنید. در اینجا میخواهیم به عنوان توفیقی اجباری شما را با مفهوم هش و هشینگ بطور ساده آشنا کنیم. برای این موضوع فقط کافیست کمی و فقط کمی از اطلاعات ریاضی خود را به ذهنتان فراخوانی کنید. با ما همراه باشید:

دوره های شبکه، برنامه نویسی، مجازی سازی، امنیت، نفوذ و ... با برترین های ایران
وب سایت توسینسو

چرا هشینگ؟

اینترنت تشکیل شده از میلیون ها انسان که روزانه چندین ترابایت محتوا تولید میکنند. بر طبق سرویس های جستجوی داده های اینترنت، مقدار محتوای تولید شده در اینترنت در هر شش ماه، دو برابر میشوند. با وجود این رشد سریع، جستجوی هرچیز در اینترنت غیر ممکن به نظر میرسد، مگر آن که ساختار و الگوریتم های جدیدی از داده را بر طبق مدل موجود، توسعه دهیم تا بتوانیم داده ها را در اینترنت ذخیره سازی و به آن ها دسترسی پیدا کنیم. اما چرا ساختارهای سنتی و مرسوم ذخیره سازی داده مانند استفاده از آرایه ها و لیست های در هم لینک شده نمیتوانند جوابگوی نیاز امروزه باشند؟

فرض کنید داده زیادی را در اختیار داریم که آن ها را بر روی یک آرایه ذخیره کردیم. زمان تخمینی برای آن که پارامتری را در آرایه جستجو و پیدا کنیم میتواند (O(log و یا (O(n باشد. این زمان بستگی به این دارد که ارایه ما مرتب شده است یا خیر.اگر آرایه مرتب شده باشد، استفاده از روش هایی چون جستجوی باینری میتواند در جستجوی آرایه مورد استفاده قرار گیرد. درغیر این صورت آرایه باید بصورت خطی مورد جستجو قرار گیرد. تازه این در حالی است که ممکن است نتیجه حاصله از جستجوی حجم زیادی از داده مورد نظر ما نباشد.

وب سایت توسینسو

بنابراین با توجه به موارد بالا، میخواهیم درباره تکنیک جدیدی به اسم هشینگ (Hashing) صحبت کنیم که این امکان را بما میدهد تا هر داده ورودی را زمان ثابت (O(1 بروزرسانی و بازیابی کنیم. زمان ثابت یا (O(1 به این مفهوم است که مقدار زمان لازم برای بازیابی داده بستگی به سایز داده (n) ندارد.

نقشه ساختار داده

در دنیای ریاضیات، یک نگاشت به ارتباط بین دو مجموعه اتلاق میشود. ما میتوانیم نگاشت M را به عنوان مجموعه ای از یک زوج در نظر بگیریم، جایی که هر جفت بشکلی از (Key, Value) است، در اینصورت برای کلید داده شده، میتوانیم مقداری را با استفاده از نوعی عملکرد که کلیدها را به مقادیر متناظر میکند، پیدا کنیم.

این کلید میتواند با استفاده از تابعی به نام تابع هش محاسبه شود. در ساده ترین حالت، میتوانیم تصور کنیم که آرایه ای بشکل نگاشت خواهد بود اگر کلید بصورت یک شاخص قرار گیرد و مقدار بصورت ارزشی برای آن شاخص. برای مثال آرایه A بما داده شده است.

اگر i کلید آن باشد، در اینصورت میتوانیم مقدار را با استفاده از جستجوی [A[i، پیدا کنیم. ایده استفاده از جدول هش میتواند تعمیم یافته موارد بالا باشد که در ادامه آن را توضیح خواهیم داد.مفهوم جدول هش (Hash Table) ایده ای کلی برای یک آرایه است، زمانی که کلید الزاما یک مقدار صحیح نیست. ما میتوانیم بجای کلید، یک نام و یا هر عنوانی در رابطه با شیء مورد نظر بگذاریم. هدف پیدا کردن تابع هش برای محاسبه یک شاخص است؛ در این صورت یک شی میتواند در جای خاصی از جدول ذخیره شود مثلا جایی که بتواند براحتی پیدا شود.

  • مثال : فرض کنید مجموعه از رشته های {"abc", "def", "ghi"} را در اختیار داریم که میخواهیم آن ها را در جدول ذخیره کنیم. هدف ما در اینجا پیدا کردن و یا بروزرسانی این رشته ها از جدول و با استفاده از (O(1 است. نگرانی از بابت ترتیب آن ها یا هرگونه وجود نظم در آن ها به هیچ وجه وجود ندارد.فرض میکنیم b"=2،"a"=1" و ... . همین ترتیب را برای تمام حروف الفبا در نظر میگیریم. سپس میتوانیم براحتی با این مکانیزم برای هرکدام از رشته ها بوسیله جمع مقدار عددی کاراکترها، یک عدد را محاسبه کنیم.
"abc"= 1+2+3=6,"def"=4+5+6=15,"ghi"=7+8+9=24

اگر ما فرض کنیم که جدولی با سایز 5 برای ذخیره این رشته ها داریم، میتوانیم مکان رشته را با استفاده از فرمول "sum mod 5" محاسبه کنیم. بنابراین میتوانیم

  • "abc" را در 6mod 5=1
  • "def" را در 15mod 5=0
  • و "ghi" را در 24mod 5=4

یعنی مکان های 1، 0 و 4 ذخیره کنیم.

وب سایت توسینسو

در نهایت میخواهیم اگر به ما رشته ای داده شد، بتوانیم بسرعت مکان آن را با استفاده از یک تابع هش ساده که باقی مانده تقسیم مجموع کاراکترها بر سایز جدول است را محاسبه کنیم. با استفاده از این مقدار هش میتوانیم رشته را جستجو کنیم. به نظر میرسد این روش راه خوبی برای ذخیره یک دیکشنری باشد. همچنین راه خوبی برای ذخیره زوج های (key,value) در جدول نیز هست.

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

وب سایت توسینسو

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

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

این بازآرایی عبارات بما این اجازه را میدهد تا بتوانیم مقدار هش را با سرعت بالاتری محاسبه کنیم.

وب سایت توسینسو

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

یک جدول هش بصورت آرایه ای که در ذخیره سازی داده با هر نوعی استفاده میشود، ذخیره میگردد. در این حالت توانستیم یک جدول عمومی را که میتواند انواع نود ها را ذخیره کند، تعریف کنیم. این ارایه، یک آرایه خالی است که بصورت زیر تعریف میشود:

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)

وب سایت توسینسو

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


احسان امجدی
احسان امجدی

کارشناس امنیت اطلاعات و ارتباطات

احسان امجدی ، مشاور امنیت اطلاعات و ارتباطات و تست نفوذ سنجی ، هکر کلاه سفید ، مدرس دوره های تخصصی امنیت اطلاعات و شبکه ، تخصص در حوزه های سرویس های مایکروسافت ، Routing و Switching ، مجازی سازی ، امنیت اطلاعات و تست نفوذ ، کشف جرائم رایانه ای و سیستم عامل لینوکس ، متخصص در حوزه SOC و ...

نظرات