تابع درهم ساز (Hash Function) چیست؟

مدرس: مسعود کاویانی

فرض کنید، شما سرپرست ۲۰۰منشی هستید. هر کدام از این منشی ها یک شماره (از ۱ تا ۲۰۰) دارید. فرض میکنیم، که ۲۰۰اتاق مختلف نیز داریم و میخواهیم این منشی ها را بین ۲۰۰اتاق موجود (که باز هم از ۱ تا ۲۰۰ شماره گذاری شده اند) تقسیم کنیم. بسیار ساده است که به هر فرد بگوییم به سراغ اتاق هم شماره خود برود. مثلا منشی شماره ۳، به اتاق شماره ۳ برود. هنگامی که یک مراجعه کننده، به دنبال منشی شماره ۳ میگردد، به او میگویم به که اتاق شماره ۳ برو و با منشی صحبت کن. حال فرض کنید که تعداد منشی ها از ۲۰۰ به ۵۰۰ افزایش یافت ولی تعداد اتاق ها همان ۲۰۰ عدد باقی ماند. اکنون برای تقسیم این منشی ها به اتاق ها، چه تبدیری می توان اندیشید؟

همان طور که در مثال بالا، مشاهده کردید، هنگامی که تعداد منشی ها از تعداد اتاق ها بیشتر باشد، مجبور هستیم، در تعدادی از اتاق ها، چندین منشی را جای دهیم. مشکل اینجاست که اگر مراجعه کننده ای، به دنبال منشی شماره ۴۵۰ میگشت، از کجا باید بداند که به کدام اتاق مراجعه کند؟

یکی از راه حل های این مشکل، توابع درهم ساز (Hash Functions) هستند. این توابع ریاضی، یک عدد را به عنوان ورودی دریافت می کنند و آن را به یک عدد دیگر (در یک بازه خاص) تبدیل می کنند. در همان مثال بالا، یک تابع درهم ساز، می تواند اعداد بین ۰ تا ۵۰۰ (تعداد منشی ها) را به اعداد بین ۰ تا ۲۰۰ (تعداد اتاق ها) تبدیل کند. برای این کار تابعی مانند زیر را در نظر بگیرید:

 (X mod 200)

این تابع ساده درهم ساز، یک عدد مانند X را میگیرد و باقی مانده آن عدد بر ۲۰۰ را بر میگرداند. برای مثال، در همان مثال بالا، اگر عدد ۱۵۰ (منشی شماره ۱۵۰) به این تابع اعمال شود، این تابع عدد ۱۵۰ (اتاق شماره ۱۵۰) را برمیگرداند (باقی مانده تقسیم ۲۰۰ بر ۱۵۰، همان ۱۵۰ است). این درحالی است که اگر عدد ۴۱۰ (منشی شماره ۴۱۰) به این تابع اعمال شود، این تابع عدد ۱۰ را برمی گرداند (باقی مانده تقسیم ۲۰۰ بر ۴۱۰)، به این معنی که این منشی با شماره ۴۱۰، باید به اتاق شماره ۱۰ برود. هر گاه یک مراجعه کننده نیز با منشی شماره ۴۱۰ کار داشت، تابع درهم ساز به او می گوید به اتاق شماره ۱۰ برود (زیرا منشی آن جاست).

توابع درهم ساز، کاربردهای بسیار زیادی در علوم کامپیوتر و مهندسی نرم افزار دارند. برای مثال، فرض کنید میخواهید دو فایل مختلف را در دو کامپیوتر مختلف (سرور و Client) با یکدیگر مقایسه کنید. اگر حجم فایل زیاد باشد، برای مقایسه دقیق، نیاز است که فایل از سرور دانلود شود، و کاراکتر به کاراکتر با فایل موجود در سیستم Client مقایسه شود. اما با توابع درهم ساز مشخص (مثلا تابع md5) کار ساده تر می شود. از فایل موجود درسرور یک md5 گرفته می شود که عددی مانند زیر است:

۶۷t9dgs9aufg9wdgf97wgf

این کد درهم سازی شده، برای کامپیوتر Client ارسال می شود (که حجم آن به مراتب کمتر است). سپس شما، فایل موجود در کامپیوتر خود را نیز md5 کرده و با کد دریافت شده از سرور مقایسه میکنید. اگر این دو کد یکی بودند، میتوانید بفهمید (که به احتمال بسیار بسیار بسیار! زیاد) این دو فایل یکی هستند. زیرا احتمال بسیار کمی وجود دارد که دو فایل بزرگ، یک md5 مشابه را تولید کنند (که این به قدرت تابع درهم ساز نیز بستگی دارد)

همان طور که حدس میزنید (و در مثال منشی ها نیز دیدیم) توابع در هم ساز یک طرفه هستند. نکته مهم، در توابع درهم ساز، برخورد (یا Collision) است. در مثال منشی ها، هنگامی که تعداد اتاق ها کمتر از منشی ها باشد، میتوانید ببنید که چند منشی به یک اتاق می رود. در مثال md5 هم چون تعداد کاراکترهای خروجی تابع md5 معمولا کمتر از تعداد کاراکترهای فایل ها است، ممکن است برخورد پیش بیاید، به این معنی که هر دو فایل با محتوای مختلف دارای یک کد خروجی md5 باشند. برای همین است که که میگویند توابع درهم ساز، یک طرف هستند، یعنی اگر شما مقدار اولیه را داشته باشید، میتوانید به مقدار نهایی دست پیدا کنید (مثلا اگر شماره منشی را داشته باشید میتوانید به اتاق منشی دست پیدا کنید)، ولی اگر مقدار نهایی (شماره اتاق منشی) را داشته باشید، نمیتوانید بگویید که با کدام منشی کار دارید (زیرا در یک اتاق احتمالاً بیش از یک منشی قرار دارد). توجه کنید که توابع درهم ساز کارایی خود را در تعداد و شماره های بالا نمایش می دهند. مثلا فرض کنید ۱۰هزار منشی داریم و فقط ۲۰۰اتاق.

تابع درهم ساز

در تصویر بالا نیز که تابع درهم ساز وجود دارد که اسامی مختلف را به اعداد نگاشت می کند. همان طور که می بینید ممکن است چند عدد خالی بماند در حالی که به چند عدد دیگر ۲ یا بیشتر اسم تعلق بگیرد.

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

این درس از مجموعه درس توابع درهم ساز (Hash Functions) است
ترتیب پیشنهادی خواندن درس‌های این مجموعه به صورت زیر است:
منابع این بحث و اطلاعات بیشتر

» وب سایت MathWorld » وب سایت TuturialPoints » وب سایت QlikFix

در صورت تمایل به یادگیری بیشتر، منابع بالا در نظر گرفته شده است. می توانید با خواندن این منابع، به یادگیری خود در این زمینه عمق ببخشید

7 دیدگاه دربارهٔ «تابع درهم ساز (Hash Function) چیست؟»

  1. با سلام و احترام خدمت مهندس کاویانی بزرگوار

    در قسمت Mod عدد ۴۱۰ بر ۲۰۰ احتمالا اشتباه تایپی اتفاق افتاده
    چون حاصل رو نوشته ۱۱۰
    در صورتی که حاصلش میشه ۱۰

    با تشکر از تمام زحمات حضرتعالی و شیوه شیوای آموزش شما
    بسیار بسیار بسیار سلیس و روان مطالب رو می نویسید

    خدا قوت

  2. با سلام.خسته نباشید مهندس.خیلی شفاف و عالی توضیح دادید.ممنون
    ولی یه سوال :
    اگر عدد ۱۵۰ (منشی شماره ۱۵۰) به این تابع اعمال شود، این تابع عدد ۱۵۰ (اتاق شماره ۱۵۰) را برمیگرداند (باقی مانده تقسیم ۲۰۰ بر ۱۵۰، همان ۱۵۰ است) ؟؟؟؟؟؟؟؟😲
    چطور خارج قسمت و باقیمانده یکی شدن؟و اصلا چطور ۲۰۰ بر ۱۵۰ باقیمانده ۱۵۰ دارد؟

  3. با سلام و احترام
    مطلب شما بسیار خوب بود، بخصوص ذکر مثال درک مناسبی رو بوجود آورد
    با تشکر

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *