نمایش مبدأ برای تابع هش

[[پرونده:Hash function.svg|بندانگشتی|300px|یک تابع درهمک‌سازی نوعی اینگونه کار می‌کند.]]
'''تابع هش''' {{به انگلیسی|Hash function}} یا '''تابع درهَمَک‌ساز''' یا '''تابع چکیده‌ساز'''<ref>{{یادکرد فرهنگستان|مصوب=تابع چکیده‌ساز|بیگانه=cryptographic hash function, hashing algorithm, hash function|بیگانه در فارسی=|حوزه=رمزشناسی|دفتر=نهم|بخش=فارسی|سرواژه=تابع چکیده‌ساز}}</ref> به هر [[الگوریتم|رویه خوش تعریف]]<ref>الگوریتم</ref> یا [[تابع (ریاضی)|تابع ریاضی]] می‌گویند که حجم زیادی از داده (احتمالاً حجم نامشخصی از داده) را به یک [[عدد طبیعی]] تبدیل کند. عدد طبیعی حاصل از تابع درهم‌سازی به عنوان [[اندیس]] یک [[آرایه]] مورد استفاده قرار می‌گیرد. مقادیر حاصل از این تابع را معمولاً '''مقدار هش''' یا فقط '''هش''' یا '''درهَمَک''' می‌خوانند. این توابع کاربردهای وسیعی در علوم کامپیوتر از جمله حفظ [[یکپارچگی داده‌ها|یکپارچگی داده]]‌ها دارند.<ref>{{cite web|url=https://csrc.nist.gov/glossary/term/hash_digest|title=NIST Glossary — hash digest|access-date=January 1, 2024}}</ref>

نرخ هش: تعداد هش بر ثانیه: واحد اندازه گیری قدرت محاسباتی در کامپیوتر ها. یعنی تعداد محاسباتی که یک کامپیوتر می‌تواند در هر ثانیه انجام دهد.<ref>{{یادکرد کتاب|عنوان=ملیاردر های بیت کوین‌. صفحه ۱۰۷. نوشته دو فارغ التحصیل هاروارد}}</ref>

== مقدمه ==
توابع درهم‌سازی بیشتر برای سرعت بخشیدن در [[الگوریتم جستجو|جستجوی]] جدول‌های، [[فشرده‌سازی داده‌ها]]، درج یا حذف برای مجموعه پویایی که تعداد عناصر آن در طول زمان تغییر می‌کند، استفاده می‌شوند مانند جستجوی چیزی در یک [[پایگاه داده]]، تشخیص رکوردهای تکراری در حجم زیاد داده یا کشیدگی‌های مشابه در دنباله [[دی.ان.ای|دی‌ان‌ای]] ([[:w:en:DNA|DNA]]) و بسیاری کاربردهای مشابه. در این مقاله دربارهٔ داده ساختاری به نام [[جدول درهمک‌سازی|جدول درهم‌سازی]] و روش درهم‌سازی صحبت می‌کنیم که با طراحی درست همه این اعمال را در بدترین حالت و نیز در حالت میانگین با هزینهٔ{{عبارت چپ‌چین|<math>O(1)</math>}} انجام می‌دهد.

== چیستی ==
فرض کنید کلیدها اعداد صحیحی از یک تا ۱۰۰ باشند و حدود ۱۰۰ رکورد وجود دارد. یک روش کارآمد برای [[مرتب‌سازی]] رکوردها، ایجاد آرایه S با ۱۰۰ عنصر و نگهداری رکوردی با کلید i در [S[i است. بازیابی، بدون درنگ صورت می‌پذیرد و مقایسه کلیدها صورت نمی‌پذیرد. اگر حدود ۱۰۰ رکورد وجود داشته باشد و کلیدها، شماره‌های شناسایی ۹ رقمی باشند، همین راهبرد را می‌توان به کار برد ولی به لحاظ حافظه، کارایی بسیار کمی دارد زیرا آرایه‌ای با یک میلیارد عنصر برای نگهداری تنها ۱۰۰ رکورد مورد نیاز است. به طریق دیگر، می‌توانیم آرایه‌ای با تنها ۱۰۰ عنصر که از ۰ تا ۹۹ اندیس‌گذاری می‌شود، ایجاد کنیم و هر کلید را به مقداری میان ۰ تا ۹۹ درهم‌سازی {{به انگلیسی|[[:w:en:Hash|Hash]]}} کنیم. تابع درهم‌سازی تابعی است که هر کلید را به یک اندیس تبدیل می‌کند و استفاده از تابع درهم‌سازی در مورد یک کلید خاص را «کلید درهم‌سازی» {{به انگلیسی|[[:w:en:Hash key|Hash key]]}} می‌گویند. در مورد شماره‌های شناسایی، یک تابع درهم‌سازی ممکن، عبارت‌است از:

{{وسط| <nowiki>h(key) = key %100</nowiki>}}

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

{{وسط‌چین}}<math>\frac{100!}{100^{100}}\approx9.3\times (10^{-43})</math>{{پایان}}

== جدول آدرس‌دهی مستقیم ==
در '''آدرس‌دهی مستقیم''' فرض می‌کنیم که مجموعه جهانی U نسبتاً کوچک است و {{عبارت چپ‌چین|<math>k\subseteq {0, 1, ... , m-1}</math>}} که m در آن خیلی بزرگ نیست، برای نمایش پویایی از این عناصر از آرایه {{عبارت چپ‌چین|<math>T[0 .... m-1]</math>}} به نام '''جدول آدرس‌دهی مستقیم''' استفاده می‌کنیم که در درایه iام تنها عنصری با کلید i می‌تواند قرار گیرد و درایه‌های دیگر خالی یا null هستند. اما هنوز این مشکل وجود دارد که این روش برای mهای بزرگ پاسخگو نیست و برای حل آن از '''جدول درهم‌سازی''' استفاده می‌شود.

== نمایش اضافه شدن کلید جدید ==
تقریباً مطمئن هستیم که حداقل دو کلید به یک اندیس درهم‌سازی می‌شوند. چنین رویدادی را برخورد [[:en:Collision (computer science)|Collision]] یا تصادف می‌گویند. راه‌های گوناگونی برای برطرف‌کردن در برخوردها وجود دارد. یکی از بهترین راه‌ها، استفاده از درهم‌سازی باز (یا آدرس‌دهی باز{{به انگلیسی|[[:en:Open addressing|Open Addressing]]}}) است. برای درهم‌سازی باز، باکتی ([[سطل]]) برای هر مقدار درهم‌سازی ممکن ایجاد می‌کنیم و همه کلیدهایی را که به مقدار موجود در یک باکت درهم‌سازی می‌شوند، در باکت مربوط به آن قرار می‌دهیم. درهم‌سازی باز را معمولاً با لیست‌های پیوندی پیاده‌سازی می‌کنند. برای مثال، اگر درهم‌سازی را به دو رقم آخر اعداد انجام دهیم، آرایه‌ای از اشاره‌گرهای باکت را ایجاد می‌کنیم که از ۰ تا ۹۹ اندیس‌گذاری می‌شوند. همه آن کلیدهایی که به i درهم‌سازی می‌شوند در یک لیست پیوندی{{به انگلیسی|[[:en:Link list|Link List]]}} که از [Bucket[i شروع می‌شود، قرار داده می‌شوند این نکته در شکل نشان داده شده‌است.

روش دیگری نیز برای برطرف کردن برخورد به نام '''روش زنجیره‌ای''' وجود دارد که در ادامه بیان خواهد شد.

== نمایشی از درهم‌سازی باز و جدول درهم‌سازی ==
[[پرونده:HASHTB12.svg|وسط|362px|راست|تصادم درهم‌سازی با کاوش خطی برطرف شده‌است.]]

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

<center><math>100\times (\frac{1}{100})^{100}=10^{-198}</math></center>

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

== روش زنجیره‌ای برای حل برخورد ==
در '''روش زنجیره‌ای''' عناصری را که به وسیله تابع درهم‌سازی به یک درایه از جدول درهم‌سازی- مثلاً iS- نگاشته می‌شوند به صورت یک لیست خطی یک‌سویه درمی‌آوریم و آدرس شروع آن را در همان درایه، یعنی {{عبارت چپ‌چین|<math>T[i]</math>}} قرار می‌دهیم. در حالت کلی عناصر با کلیدهای مختلف k که مقدار {{عبارت چپ‌چین|<math>h[k]</math>}} آن‌ها برابر است در لیست پیوندی {{عبارت چپ‌چین|<math>T[h(k)]</math>}} قرار می‌گیرند و درایه‌های خالی جدول هم لیست‌های تهی هستند، به چنین جدولی، '''جدول درهم‌سازی با روش زنجیره‌ای''' می‌گوییم. در این روش اعمال درج در زمان {{عبارت چپ‌چین|<math>O(1)</math>}} انجام می‌شود، اما عمل جستجو و حذف با یک عمل جستجوی عنصر همراه است که در بدترین حالت هزینه‌ای متناسب با طول لیست {{عبارت چپ‌چین|<math>(O(n))</math>}} دارد.

== توابع درهم‌سازی ==
یک تابع درهم‌سازی خوب تابعی است که ساده و یک‌نوا باشد، در ادامه یکی روشهای سادهٔ مختلف را برای طراحی تابع درهم‌سازی را بیان می‌کنیم.

=== روش ضرب ===
در این روش ابتدا کلید k را در یک عدد ثابت A که {{عبارت چپ‌چین|<math>0< A < 1</math>}} است ضرب کنیم و قسمت اعشاری آن را به‌دست آوریم. یعنی:{{سخ}}
{{عبارت چپ‌چین|<math>h(k) = \lfloor m((kA) mod (1)) \rfloor</math>}}{{سخ}}
{{عبارت چپ‌چین|<math>(kA) mod (1)\longleftrightarrow kA - \lfloor kA \rfloor</math>}}{{سخ}}
فرض کنید که کلمهٔ کامپیوتر w بیتی است و k در یک کلمه جای می‌گیرد. A را طوری انتخاب می‌کنیم که برابر {{عبارت چپ‌چین|<math>\frac{s}{2^w}</math>}} باشد، که در آن s یک عدد صحیح در محدودهٔ {{عبارت چپ‌چین|<math>0<s<2^w</math>}} باشد. ابتدا k را در عدد صحیح w بیتی {{عبارت چپ‌چین|<math>s=A.2^w</math>}} ضرب می‌کنیم و [[حاصل‌ضرب|حاصل ضرب]] یک عدد 2w بیتی به صورت {{عبارت چپ‌چین|<math>r_12^w+r_0</math>}} است که {{عبارت چپ‌چین|<math>r_1</math>}} کلمهٔ پر ارزش و {{عبارت چپ‌چین|<math>r_0</math>}} کلمهٔ کم‌ارزش حاصل ضرب است. عدد p بیتی تابع درهم‌سازی مورد نظر، p بیت پرارزش {{عبارت چپ‌چین|<math>r_0</math>}} است.

== درهم‌سازی دوگانه ==
[[پرونده:Pedagogical illustration of the principle of hashing functions.png|بندانگشتی|درهم سازی دوگانه]]
اگر دو رکورد در توابع [[درهم سازی]] به یک مکان در فایل انتقال یابند به آن برخورد می‌گویند. روش ایدئال برای مقابله با برخوردها این است که بتوان [[الگوریتم]] تبدیلی پیدا کرد که به‌طور کلی از وقوع برخوردها جلوگیری کند.

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

روش وارسی خطی با داشتن یک تابع در هم ساز کمکی به نام {{عبارت چپ‌چین|<math>g:U -> {0, 1, .... , m-1}</math>}} از تابع زیر برای درهم سازی استفاده می‌کند:

<math>h(k , i) = (g(k) + i) mod (m)</math> به ازای i = ۰ , ۱ , … m-1
به ازای یک کلید k، ابتدا<math> T[g(k)]</math> را وارسی می‌کنیم سپس به <math>T[g(k)+1]</math> و بعد به <math>T[g(k)+2]</math> می‌رویم و این کار را به صورت حلقوی ادامه می‌دهیم تا به <math> T[g(k)+m-1]</math> برسیم. در این حالت فقط m دنبالهٔ وارسی مجزا تولید می‌شود.
درهم سازی دوگانه یک روش وارسی است که در آن توابع در هم سازی به صورت زیر است:

<math>h(k ,i)=(h(k) + ig(k))mod (m)</math>

که در آن توابع h و g تابه‌های درهم ساز کمکی هستند. اولین وارسی در <math>T(h(k))</math> انجام می‌شود و وارسی‌های بعدی به درایه‌ای با فاصله <math>g(k)mod (m)</math> می‌رود. مثالی از این درج در شکل زیر آمده‌است، در این مثال، m=۱۳ و {{عبارت چپ‌چین|<math>h(k)= (k) mod (13)</math>}} و {{عبارت چپ‌چین|<math>g(k)= 1 + ((k) mod (11))</math>}} است.

چون h(14) = ۱ و g(14) = ۴ است بنابراین کلید ۱۴، پس از آنکه درایه‌های ۱ و ۵ وارسی شده و پر بودند در درایهٔ خالی ۹ درج می‌شود.

در طراحی این درهم سازی باید مقدار <math>g(k)</math> نسبت به m اول باشد تا اینکه کلیهٔ درایه‌های جدول وارسی شوند. یک روش مناسب انتخاب m به صورت توان ۲ و طراحی g به طوری است که همیشه یک عدد فرد تولید کند. یک روش دیگر آن است که m [[عدد اول]] باشد و g همیشه یک [[عدد صحیح]] و مثبت کوچکتر از m را تولید کند.

درهم سازی دوگانه نسبت به وارسی خطی و وارسی درجهٔ ۲ بهتر عمل می‌کند، زیرا به تعداد
{{عبارت چپ‌چین|<math>m^2(\theta)</math>}} در مقایسه با {{عبارت چپ‌چین|<math>m(\theta)</math>}} دنبالهٔ وارسی تولید می‌کند؛ بنابراین به نظر می‌رسد کارایی این درهم سازی به کارایی درهم سازی یکنوا نزدیکتر باشد.

== درهم‌سازی سراسری ==
در هنگام استفاده از توابع درهم سازی اگر تابعی که مورد استفادهٔ ماست توسط کاربر فهمیده شود، کاربر می‌تواند داده‌هایش را طوری وارد کند که تعداد برخوردها زیاد باشند. برای جلوگیری از این اتفاق، از درهم سازی سراسری استفاده می‌کنیم.

یک خانواده از توابع درهم ساز به اسم H را فرض کنید.

می‌گوییم H یک خانواده از توابع درهم ساز سراسری است اگر: در ازای هر دو کلید k1 و k2 که عضو مجموعهٔ کلیدهای مورد نظر ما هستند، تعداد توابع درهم ساز مانند h که عضو H هستند به طوری که <math>h(k1) = h(k2)</math> حداکثر برابر <math>\frac{|H|}{m}</math> باشد.

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

== درهم‌سازی کامل ==
گاهی ما در درهم‌سازی با کلیدهای ایستا- که از قبل معلوم هستند- سروکار داریم، در این حالت یک روش درهم‌سازی را '''کامل''' می‌نامیم اگر در بدترین حالت تعداد دسترسی‌ها به حافظه برای یک عمل جستجو {{عبارت چپ‌چین|<math>O(1)</math>}} باشد. ایدهٔ اصلی این نوع درهم‌سازی استفاده از دو سطح درهم‌سازی و یک تابع درهم‌سازی سراسری برای هر سطح است.

== درهم‌سازی پویا ==
در روش‌هایی که تا کنون برای درهم‌سازی بحث کرده‌ایم فرض بر می‌شود که تعداد عناصر حداکثر برابر اندازهٔ جدول- روش باز- یا تقریباً برابر آن- روش زنجیره‌ای- است در حالی که در بسیاری از مواقع تعداد عناصر از پیش مشخص نیست و نمی‌توان کران بالای خوبی برای اندازهٔ جدول درهم‌سازی پیش‌بینی کرد که باعث اتلاف حافظه نشود.{{سخ}}
برای حل این مشکل از روش '''درهم‌سازی پویا''' استفاده می‌شود که در آن اندازه جدول متناسب با نیاز متغیر است؛ که برای تغییر اندازه جدول نیز باید هزینه کنیم اما نشان داده شده است که حتی با هزینه لازم برای تغییر اندازه جداول همچنان کل هزینه برابر {{عبارت چپ‌چین|<math>O(1)</math>}}
می‌ماند.<ref name="knuth-1973">{{cite book|last=Knuth|first=Donald E.|author-link=Donald Knuth|date=1973|title=The Art of Computer Programming, Vol. 3, Sorting and Searching|url=https://archive.org/details/sortingsearching00knut|publisher=[[Addison-Wesley]]|location=Reading, MA., United States|isbn=978-0-201-03803-3|bibcode=1973acp..book.....K}}</ref>

== جستارهای وابسته ==
* [[تابع درهم‌سازی کریپتوگرافیک]]

== پانوشت‌ها ==
{{پانویس}}

== منابع ==
* [[جعفرنژاد قمی]]، عین‌الله. ''طراحی الگوریتم‌ها''. چاپ ششم، انتشارات [[علوم رایانه]]، ۱۳۸۳.
* مترجمان: گروه مهندسی-پژوهشی خوارزمی.''مقدمه‌ای بر الگوریتم‌ها''. انتشارات دقت، ۱۳۸۷.
* {{یادکرد-ویکی|عنوان=Hash function|بازیابی=۱۵ نوامبر ۲۰۰۸|پیوند=http://en.wikipedia.org/w/index.php?title=Hash_function&oldid=251957694}}
* {{یادکرد-ویکی|پیوند=http://en.wikipedia.org/wiki/Hash|عنوان = Hash|بازیابی =۳ می ۲۰۱۱}}
* {{یادکرد-ویکی|پیوند=http://en.wikipedia.org/wiki/Hash_key|عنوان = Hash key|بازیابی =۳ می ۲۰۱۱}}
* {{یادکرد-ویکی|پیوند=http://en.wikipedia.org/wiki/Hash_table|عنوان = Hash table|بازیابی =۳ می ۲۰۱۱}}
* {{یادکرد-ویکی|پیوند=http://en.wikipedia.org/wiki/Link_list|عنوان = Link exchange|بازیابی =۳ می ۲۰۱۱}}
* قدسی، محمد، [[داده ساختارها]] و مبانی الگوریتم‌ها، چاپ دوم، [[انتشارات فاطمی]]، ۱۳۸۹.

{{نرم‌افزارهای رمزنگاری}}
[[رده:تابع درهم‌سازی]]
[[رده:الگوریتم‌ها]]
[[رده:الگوریتم‌های جستجو]]
[[رده:ساختمان داده و الگوریتم]]