تابع درهم‌سازی

یک تابع درهم‌سازی نوعی اینگونه کار می‌کند.

به هر رویه خوش تعریف یا تابع ریاضی که حجم زیادی از داده (احتمالاً حجم نامشخصی از داده) را به یک عدد طبیعی تبدیل کند یک تابع هش(به انگلیسی: Hash function)‏ یا تابع درهم‌سازی می‌گویند. عدد طبیعی حاصل از تابع درهم‌سازی معمولاً به عنوان اندیس یک آرایه مورد استفاده‌است. مقادیری حاصل از این تابع را معمولاً مقدار هش یا فقط هش می‌خوانند.

مقدمه

توابع درهم‌سازی بیشتر برای سرعت بخشیدن در جستجوی جداول یا فشرده‌سازی داده‌ها استفاده می‌شوند مانند جستجوی چیزی در یک پایگاه داده، تشخیص رکوردهای تکراری در حجم زیاد داده یا کشیدگی‌های مشابه در دنباله دی‌ان‌ای (DNA) و بسیاری کاربردهای مشابه.

چیستی

فرض کنید کلیدهااعداد صحیحی از یک تا ۱۰۰ باشند و حدود ۱۰۰ رکورد وجود دارد. یک روش کارآمد برای مرتب‌سازی رکوردها، ایجاد آرایه S با ۱۰۰ عنصر و نگهداری رکوردی با کلید i در [S[i است. بازیابی، بدون درنگ صورت می‌پذیرد و مقایسه کلیدها صورت نمی‌پذیرد. اگر حدود ۱۰۰ رکورد وجود داشته باشد و کلیدها، شماره‌های شناسایی ۹ رقمی باشند، همین راهبرد را می‌توان به کار برد. ولی در این مورد، راهبرد فوق به لحاظ حافظه، کارآیی بسیار کمی دارد زیرا آرایه‌ای با یک میلیارد عنصر برای نگهداری تنها ۱۰۰ رکورد مورد نیاز است. به طریق دیگر، می‌توانیم آرایه‌ای با تنها ۱۰۰ عنصر که از ۰ تا ۹۹ اندیس‌گذاری می‌شود، ایجاد کنیم و هر کلید را به مقداری میان 0 تا ۹۹ درهم‌سازی (به انگلیسی: Hash)‏ کنیم. تابع درهم‌سازی تابعی است که هر کلید را به یک اندیس تبدیل می‌کند و استفاده از تابع درهم‌سازی در مورد یک کلید خاص را«کلید درهم‌سازی» (به انگلیسی: Hash key)‏ می‌گویند. در مورد شماره‌های شناسایی، یک تابع درهم‌سازی ممکن، عبارت‌است از:

h(key) = key ٪ ۱۰۰

(٪ به معنای باقیمانده تقسیم کلید بر ۱۰۰ است.) این تابع صرفا دو رقم آخر کلید را باز می‌گرداند. اگر یک کلید درهم‌سازی، به i درهم‌سازی شود، کلید و رکورد آن را در [S[i نگهداری می‌کنیم. این راهبرد کلیدها را به ترتیب نگهداری نمی‌کند، یعنی این تابع فقط در صورتی قابل استفاده‌است که هرگز نیاز به بازاریابی کارآمد داده‌ها به صورت ترتیبی نباشد. اگر نیاز به این کار باشد، یکی از روش‌های بحث شده در قبل را باید به کار برد. اگر هیچ دو کلیدی به یک اندیس یکسان درهم‌سازی نشوند، این روش به خوبی عمل می‌کند. ولی هنگامی که تعداد قابل ملاحظه‌ای کلید وجود داشته باشد، به ندرت چنین می‌شود. برای مثال، اگر ۱۰۰ کلید وجود داشته باشد واحتمال آن که هر کلید به هر یک از ۱۰۰ اندیس درهم‌سازی شود، با احتمال بقیه کلیدها یکسان باشد، احتمال آن‌که هیچ دو کلیدی به یک اندیس یکسان درهم‌سازی نشوند، عبارت‌است‌از:

$\frac{100!}{100^{100}}\approx9.3\times (10^{-43})$

نمایش اضافه شدن کلید جدید

تقریبا مطمئن هستیم که حداقل دو کلید به یک اندیس درهم‌سازی می‌شوند. چنین رویدادی را برخوردCollision یا تصادم می‌گویند. راه‌های گوناگونی برای برطرف‌کردن در برخوردها وجود دارد. یکی از بهترین راه‌ها، استفاده از درهم‌سازی باز(یاآدرس‌دهی باز(به انگلیسی: Open Addressing)‏) است. برای درهم‌سازی باز، باکتی (سطل) برای هر مقدار درهم‌سازی ممکن ایجاد می‌کنیم و همه کلیدهایی را که به مقدار موجود در یک باکت درهم‌سازی می‌شوند، در باکت مربوط به آن قرار می‌دهیم. درهم‌سازی باز را معمولاً با لیست‌های پیوندی پیاده‌سازی می‌کنند. برای مثال، اگر درهم‌سازی را به دو رقم آخر اعداد انجام دهیم، آرایه‌ای از اشاره‌گرهای Bucket را ایجاد می‌کنیم که از 0 تا 99 اندیس‌گذاری می‌شوند. همه آن کلیدهایی که به i درهم‌سازی می‌شوند در یک لیست پیوندی(به انگلیسی: Link List)‏ که از [Bucket[i شروع می‌شود، قرار داده می‌شوند این نکته در شکل نشان داده شده‌است.

نمایشی از درهم‌سازی باز

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

$100\times (\frac{1}{100})^{100}=10^{-198}$

بنابراین، تقریبا برای همه کلیدها غیرممکن است که به یک باکت ختم شوند. در باره احتمال آن‌که ۷۰، ۸۰، ۹۰ یا هر تعداد دیگری از کلیدها به یک باکت ختم شوند، چه می‌توان گفت؟ هدف اصلی ما این‌است‌که بدانیم احتمال آن‌که درهم‌سازی، در حالت میانگین به جست‌وجویی بهتر از جست‌وجوی دودویی بینجامد، چقدر است. نشان می‌دهیم که اگر به قدر کافی بزرگ باشد، این نیز تقریبا یک قطعیت به شمار می‌رود.ولی نخست نشان می‌دهیم که با درهم‌سازی، کارها چقدر بهتر می‌شود. بدیهی است بهترین حالتی که ممکن‌است رخ دهد این‌است‌که کلیدها به طور یکنواخت در باکت‌ها توزیع شود. یعنی، اگر n کلیدو m باکت وجود داشته باشد، هر باکت حاوی n/m کلید می‌شود. در واقع هر باکت دقیقا هنگامی حاوی n/m کلید می‌شود که n مضرب m باشد. اگر چنین نباشد، یک توزیع نسبتا یکنواخت خواهیم داشت. قضیه‌های زیر نشان می‌دهد که وقتی کلیدها به طور یکنواخت توزیع شده باشند، جه اتفاقی می‌افتد. برای سادگی، آن‌هارا برای توزیعی دقیقا یکنواخت بیان می‌کنیم(یعنی برای موردی که n مضربی از m باشد).

درهم‌سازی دوگانه

اگر دو رکورد در توابع درهم سازی به یک مکان در فایل انتقال یابند به آن برخورد میگویند. روش ایده آل برای مقابله با برخوردها این است که بتوان الگوریتم تبدیلی پیدا کرد که به طور کلی برخوردها جلوگیری کند.

یکی از راههای جلوگیری از برخورد استفاده از روش وارسی خطی است.

روش وارسی خطی با داشتن یک تابع در هم ساز کمکی به نام g: U -> { 0 , 1 , … , m-1} از تابع زیر برای درهم سازی استفاده میکند:

                                           $h(k , i) = (g(k) + i) mod m$ به ازای i = 0 , 1 , … m-1  

به ازای یک کلید k، ابتدا$T[g(k)]$ را وارسی میکنیم سپس به $T[g(k)+1]$ و بعد به $T[g(k)+2]$ میرویم و این کار را به صورت حلقوی ادامه میدهیم تا به T[g(k) - 1] برسیم. در این حالت فقط m دنبالهٔ وارسی مجزا تولید میشود. درهم سازی دوگانه یک روش وارسی است که در آن توابع در هم سازی به صورت زیر است: $h(k ,i)=(h(k) + ig(k))mode m$

که در آن توابع h و g تابه‌های درهم ساز کمکی هستند. اولین وارسی در $T(h(k))$ انجام می‌شود و وارسی‌های بعدی به درایه‌ای با فاصله $g(k)mode m$ میرود. مثالی از این درج در شکل زیر آمده‌است، در این مثال، m=13 و $h(k)= k mode 13$ و $g(k) = 1+(k mode 11$) است.

چون 14=1(mode 13) و 14 = 3(mode 13) است بنابراین کلید 14، پس از آنکه درایه‌های 1 و 5 وارسی شده و پر بودند در درایهٔ خالی 9 درج می شود.

در طراحی این درهم سازی باید مقدار $g(k)$ نسبت به m اول باشد تا ایتکه کلیهٔ درایه‌های جدول وارسی شوند. یک روش مناسب انتخاب m به صورت توان 2 و طراحی g به طوری است که همیشه یک عدد فرد تولید کند. یک روش دیگر آن است که m عدد اول باشد و g همیشه یک عدد صحیح و مثبت کوچکتر از m را تولید کند.

درهم سازی دوگانه نسبت به وارسی خطی و وارسی درجهٔ 2 بهتر عمل میکند، زیرا به تعداد (m²) Ѳ در مقایسه با (m) Ѳ دنبالهٔ وارسی تولید میکند. بنابراین به نظر میرسد کارایی این درهم سازی به کارایی درهم سازی یکنوا نزدیکتر باشد.

جستارهای وابسته

• تابع درهم‌سازی کریپتوگرافیک

منابع

• جعفرنژاد قمی، عین الله. طراحی الگوریتم ها. چاپ ششم، انتشارات علوم رایانه، ۱۳۸۳.
• مترجمین: گروه مهندسی-پژوهشی خوارزمی.مقدمه‌ای بر الگوریتم ها. انتشارات دقت، ۱۳۸۷.

قدسی، محمد، داده ساختارها و مبانی الگوریتم‌ها، چاپ اول، انتشارات فاطمی، ۱۳۸۸.

• مشارکت‌کنندگان ویکی‌پدیا، «Hash function»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۱۵ نوامبر ۲۰۰۸).
• مشارکت‌کنندگان ویکی‌پدیا، «Hash»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۳ می ۲۰۱۱).
• مشارکت‌کنندگان ویکی‌پدیا، «Hash key»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۳ می ۲۰۱۱).
• مشارکت‌کنندگان ویکی‌پدیا، «Hash table»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۳ می ۲۰۱۱).
• مشارکت‌کنندگان ویکی‌پدیا، «Link exchange»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۳ می ۲۰۱۱).