بحث جست‌و‌جو نه تنها در ارتباط با ساختمان داده‌ (Data Structure)، بلکه در بدیهی‌ترین مسائل روزمرۀ دنیای برنامه‌نویسی هم از موارد پرتکرار و حائز اهمیت است و تاکنون الگوریتم‌های مختلفی برای آن ارائه شده است. وجه‌تمایز این الگوریتم‌ها به غیر از روش‌های پیاده‌سازی، هزینۀ اجرای آن‌ها می‌باشد (اساساً هزینۀ پیاده‌سازی هر الگوریتم به مقدار زمانی که اجرا می‌شود و همچنین میزان منابعی که مصرف می‌کند گفته می‌شود.) سؤالی که باید قبل از ورود به بحث Hash Table (یا همان جدول درهم‌سازی) مطرح کرد و به آن پاسخ داد این است که آیا امکان دارد هزینۀ جست‌و‌جو به قدری کم شود که با یک حرکت بتوان اِلمان مورد نظر را در یک لیست پیدا کرد که در جواب باید بگوییم آری. در واقع، چنین چیزی به کمک Hash Table امکان‌پذیر است اما احتمالاً در ادامه می‌پرسید که Hash Table چگونه این کار را انجام می‌دهد؟ که برای یافتن پاسخ به این سؤال، در ادامه با سکان آکادمی همراه باشید.

آشنایی با ساختار Hash Table

Hash Table بسیار شبیه به دیتاتایپ Dictionary در زبان پایتون می‌باشد بدین معنا که یکسری Key:Value را شامل می‌شود که که هر Value (مقدار) مربوط به یک Key (کلید) خاص می‌باشد و لازم به ذکر است که هیچ‌وقت نمی‌توانیم دو کلید یکسان داشته باشیم اما تفاوت بارز آن‌ها از اینجا ناشی می‌شود که در دیتاتایپ Hash Table بین Key و Value رابطۀ معناداری وجود دارد که توسط چیزی تحت عنوان Hash Function برقرار می‌شود. به عبارت دیگر، هر اِلمان یا دیتا در خانه‌ای قرار می‌گیرد که Hash Function طی یک عملیات ریاضیاتی مشخص، آن را تولید کرده باشد.

Hash Function چیست؟

هَش فانکشن تابعی یک‌طرفه است که ترجیحاً باید یک به یک باشد؛ بدان معنا که به ازای هر x فقط و فقط یک y وجود داشته باشد. به طور کلی، محدودیتی برای توابع هَش نداریم اما یکی از معروف‌ترین آن‌ها تابع زیر است اما دقت کنید که این تابع یک به یک نیست و به ازای ایکس‌های مختلف ممکن است خروجی یکسان داشته باشد:

f(x) = x mod m

در تابع فوق، m همان طول جدول هَش، mod تابع باقیمانده و x هم که اِلمان یا دیتای ورودی است.

چرا تابع هَش باید یک به یک باشد؟

تنها دلیل آن جلوگیری از ایجاد به اصطلاح Collision (تصادم یا برخورد) در Hash Table است. در واقع، اگر قرار باشد تابع هَش به ازای ورودی‌های مختلف خروجی‌های یکسان تولید کند، آن‌گاه در یک خانه از جدول باید چند دیتای مختلف قرار بگیرد که اساساً چنین چیزی امکان‌پذیر نیست. برای روشن‌تر شدن این مسئله، مثالی می‌زنیم. فرض کنید اعداد 30، 3، 66، 23، 10، 5 و 46 را داریم و می‌خواهیم آن‌ها را در یک آرایه به طول 10 با استفاده از تابع هَش f(x)=x mod 10 به همین ترتیبی که هستند ذخیره کنیم. هر عدد را با x در تابع بالا جایگزین می‌کنیم:

f(30) = 30 mod 10 = 0
f(3) = 3 mod 10 = 3
f(66) = 66 mod 10 = 6
f(23) = 23 mod 10 = 3
f(10) = 10 mod 10 = 0
f(5) = 5 mod 10 = 5
f(46) = 46 mod 10 = 6

همان‌طور که در بالا مشاهده می‌کنید، برای اعداد 3 و 23 خروجی‌های یکسانی داریم و همین‌طور برای اعداد 30 و 10 یا اعداد 46 و 66 و از آنجایی که خروجی تابع بیانگر محلی است که اِلِمان مورد نظر باید در آن قرار بگیرد، بنابراین هر دو اِلِمان باید در یک خانه قرار بگیرند که چنین چیزی امکان‌پذیر نیست و به همین دلیل به آن Collision (برخورد) می‌‌گویند.

نکته آخر

پیدا کردن یک Hash Function که یک به یک هم باشد کار چندان ساده‌ای نیست و این برای داده‌هایی که تایپ‌های متفاوت‌تری هم دارند مشکل را دو چندان می‌کند اما چنانچه بتوانیم تابع هَشی (ترجیحاً یک به یک) را پیدا کنیم، آن‌گاه کل معمای Hash Table حل شده و آسان می‌شود و می‌توانیم بعد از ذخیره‌سازی، هر دیتای دلخواهی را با یک حرکت پیدا کنیم به این صورت که داده را در تابع هَش قرار می‌دهیم و خروجی را آن را محاسبه می‌کنیم؛ سپس در جدول هَش Value مربوط به آن خروجی را نگاه می‌کنیم که چنانچه مساوی دادۀ ما بود، این بدان معنا است که دیتای مذکور در آن جدول وجود دارد و در غیر این صورت، یعنی چنین دیتایی وجود ندارد.

حال سؤال اینجا است که چنانچه تابع هَش یک طرفه نبود برای حل Collision در هَش تِیبل چه سولوشنی را می‌توان به کار گرفت؟ اگر پاسخ به این سؤال را می‌دانید، در بخش نظرات پاسخ به این سؤال را با دیگر کاربران سکان آکادمی مطرح نمایید.

Hash Table چیست و چه زمانی از آن استفاده می‌شود؟