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