به هر رویه خوش تعریف یا تابع ریاضی که حجم زیادی از داده (احتمالاً حجم نامشخصی از داده) را به یک عدد طبیعی تبدیل کند یک تابع هش (به انگلیسی: Hash function) یا تابع درهم سازی یا تابع چکیده ساز می گویند. عدد طبیعی حاصل از تابع درهم سازی معمولاً به عنوان اندیس یک آرایه مورد استفاده است. مقادیر حاصل از این تابع را معمولاً مقدار هش یا فقط هش می خوانند.
تابع درهم سازی کریپتوگرافیک
توابع درهم سازی بیشتر برای سرعت بخشیدن در جستجوی جدول های،فشرده سازی داده ها، درج یا حذف برای مجموعه پویایی که تعداد عناصر آن در طول زمان تغییر می کند، استفاده می شوند مانند جستجوی چیزی در یک پایگاه داده، تشخیص رکوردهای تکراری در حجم زیاد داده یا کشیدگی های مشابه در دنباله دی ان ای (DNA) و بسیاری کاربردهای مشابه. در این مقاله دربارهٔ داده ساختاری به نام جدول درهم سازی و روش درهم سازی صحبت می کنیم که با طراحی درست همه این اعمال را در بدترین حالت و نیز در حالت میانگین با هزینهٔ O ( 1 ) {\displaystyle O(1)} انجام می دهد.
فرض کنید کلیدها اعداد صحیحی از یک تا ۱۰۰ باشند و حدود ۱۰۰ رکورد وجود دارد. یک روش کارآمد برای مرتب سازی رکوردها، ایجاد آرایه S با ۱۰۰ عنصر و نگهداری رکوردی با کلید i در [S[i است. بازیابی، بدون درنگ صورت می پذیرد و مقایسه کلیدها صورت نمی پذیرد. اگر حدود ۱۰۰ رکورد وجود داشته باشد و کلیدها، شماره های شناسایی ۹ رقمی باشند، همین راهبرد را می توان به کار برد ولی به لحاظ حافظه، کارایی بسیار کمی دارد زیرا آرایه ای با یک میلیارد عنصر برای نگهداری تنها ۱۰۰ رکورد مورد نیاز است. به طریق دیگر، می توانیم آرایه ای با تنها ۱۰۰ عنصر که از ۰ تا ۹۹ اندیس گذاری می شود، ایجاد کنیم و هر کلید را به مقداری میان ۰ تا ۹۹ درهم سازی (به انگلیسی: Hash) کنیم. تابع درهم سازی تابعی است که هر کلید را به یک اندیس تبدیل می کند و استفاده از تابع درهم سازی در مورد یک کلید خاص را «کلید درهم سازی» (به انگلیسی: Hash key) می گویند. در مورد شماره های شناسایی، یک تابع درهم سازی ممکن، عبارت است از:
(٪ به معنای باقی مانده تقسیم کلید بر ۱۰۰ است) این تابع صرفاً دو رقم آخر کلید را بازمی گرداند. اگر یک کلید درهم سازی، به i درهم سازی شود، کلید و رکورد آن را در [S[i نگهداری می کنیم. این راهبرد کلیدها را به ترتیب نگهداری نمی کند، یعنی این تابع فقط در صورتی قابل استفاده است که هرگز نیاز به بازیابی کارآمد داده ها به صورت ترتیبی نباشد. اگر نیاز به این کار باشد، یکی از روش های بحث شده در قبل را باید به کار برد.اگر هیچ دو کلیدی به یک اندیس یکسان درهم سازی نشوند، این روش به خوبی عمل می کند. ولی هنگامی که تعداد قابل ملاحظه ای کلید وجود داشته باشد، به ندرت چنین می شود. برای مثال، اگر ۱۰۰ کلید وجود داشته باشد و احتمال آن که هر کلید به هر یک از ۱۰۰ اندیس درهم سازی شود، با احتمال بقیه کلیدها یکسان باشد، احتمال آن که هیچ دو کلیدی به یک اندیس یکسان درهم سازی نشوند، عبارت است از:
تابع درهم سازی کریپتوگرافیک
توابع درهم سازی بیشتر برای سرعت بخشیدن در جستجوی جدول های،فشرده سازی داده ها، درج یا حذف برای مجموعه پویایی که تعداد عناصر آن در طول زمان تغییر می کند، استفاده می شوند مانند جستجوی چیزی در یک پایگاه داده، تشخیص رکوردهای تکراری در حجم زیاد داده یا کشیدگی های مشابه در دنباله دی ان ای (DNA) و بسیاری کاربردهای مشابه. در این مقاله دربارهٔ داده ساختاری به نام جدول درهم سازی و روش درهم سازی صحبت می کنیم که با طراحی درست همه این اعمال را در بدترین حالت و نیز در حالت میانگین با هزینهٔ O ( 1 ) {\displaystyle O(1)} انجام می دهد.
فرض کنید کلیدها اعداد صحیحی از یک تا ۱۰۰ باشند و حدود ۱۰۰ رکورد وجود دارد. یک روش کارآمد برای مرتب سازی رکوردها، ایجاد آرایه S با ۱۰۰ عنصر و نگهداری رکوردی با کلید i در [S[i است. بازیابی، بدون درنگ صورت می پذیرد و مقایسه کلیدها صورت نمی پذیرد. اگر حدود ۱۰۰ رکورد وجود داشته باشد و کلیدها، شماره های شناسایی ۹ رقمی باشند، همین راهبرد را می توان به کار برد ولی به لحاظ حافظه، کارایی بسیار کمی دارد زیرا آرایه ای با یک میلیارد عنصر برای نگهداری تنها ۱۰۰ رکورد مورد نیاز است. به طریق دیگر، می توانیم آرایه ای با تنها ۱۰۰ عنصر که از ۰ تا ۹۹ اندیس گذاری می شود، ایجاد کنیم و هر کلید را به مقداری میان ۰ تا ۹۹ درهم سازی (به انگلیسی: Hash) کنیم. تابع درهم سازی تابعی است که هر کلید را به یک اندیس تبدیل می کند و استفاده از تابع درهم سازی در مورد یک کلید خاص را «کلید درهم سازی» (به انگلیسی: Hash key) می گویند. در مورد شماره های شناسایی، یک تابع درهم سازی ممکن، عبارت است از:
(٪ به معنای باقی مانده تقسیم کلید بر ۱۰۰ است) این تابع صرفاً دو رقم آخر کلید را بازمی گرداند. اگر یک کلید درهم سازی، به i درهم سازی شود، کلید و رکورد آن را در [S[i نگهداری می کنیم. این راهبرد کلیدها را به ترتیب نگهداری نمی کند، یعنی این تابع فقط در صورتی قابل استفاده است که هرگز نیاز به بازیابی کارآمد داده ها به صورت ترتیبی نباشد. اگر نیاز به این کار باشد، یکی از روش های بحث شده در قبل را باید به کار برد.اگر هیچ دو کلیدی به یک اندیس یکسان درهم سازی نشوند، این روش به خوبی عمل می کند. ولی هنگامی که تعداد قابل ملاحظه ای کلید وجود داشته باشد، به ندرت چنین می شود. برای مثال، اگر ۱۰۰ کلید وجود داشته باشد و احتمال آن که هر کلید به هر یک از ۱۰۰ اندیس درهم سازی شود، با احتمال بقیه کلیدها یکسان باشد، احتمال آن که هیچ دو کلیدی به یک اندیس یکسان درهم سازی نشوند، عبارت است از:
wiki: تابع درهم سازی