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

یک عملکرد کمترین هش کامل برای چهار نام نشان داده شده

یک تابع هش کامل برای چهار نام نشان داده شده

در علوم رایانه، یک تابع درهم سازی کامل برای مجموعه الگو:Mvar تابع هشی است که عناصر مجزا از الگو:Mvar را بدون برخورد به مجموعه ای از اعداد صحیح مرتبط می‌کند. از نظر ریاضی، یک تایع یک به یک است.

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

کاربرد

با قرار دادن کلیدهای الگو:Mvar (یا سایر مقادیر مرتبط) در یک جدول جستجوی فهرست شده (با اندیس) بوسیله خروجی این تابع، یک تابع درهم سازی کامل با مقادیر محدود می‌تواند برای یه عملیات جست و جوی کارآمد استفاده شود. سپس می‌توان با جستجوی سلول کلید مورد نظر در جدول، وجود کلید در الگو:Mvar را آزمایش کرد یا مقدار متناظر با آن را جستجو کرد. هرگونه جستجو در بدترین حالت در زمان ثابت صورت می‌گیرد.

ساختن

یک تابع درهم سازی کامل برای یک مجموعه خاص الگو:Mvar می‌تواند در زمان ثابت تعیین شود. یا با مقادیر موجود در یک محدوده کوچک، توسط یک الگوریتم تصادفی در تعدادی از عملیات‌ها که (که تعداد آن متناسب با اندازه S می‌باشد) می‌تواند جستجو شود. روش ساختن الگو:Harvard citation text از یک طرح دو سطحی استفاده می‌کند تا یک مجموعه الگو:Mvar از الگو:Mvar عنصر به طیف وسیعی از الگو:ریاضی شاخص مرتبط (نقشه) کند، و پس از آن هر شاخص به طیف وسیعی از مقادیر هش مرتبط می‌شود. سطح اول ساخت آنها، یک الگو:Mvar اول بسیار بزرگ (بزرگتر از اندازه مجموعه ای که الگو:Mvar از آن ترسیم شده‌است)، و یک پارامتر الگو:Mvar انتخاب می‌کند و هر عنصر الگو:Mvar از الگو:Mvar را به نمایه (اندیس) خودش مرتبط می‌کند.

$g(x)=(kxmodp)modn.$

اگر الگو:Mvar به‌طور تصادفی انتخاب شود، این مرحله به احتمال زیاد دچار برخورد می‌شود، اما تعداد عناصر الگو:Mvar که همزمان به همان اندیس الگو:Mvar مرتبط (هش) می‌شوند، احتمالاً اندک است. در سطح دوم ساخت آن به هر اندیس یا شاخص i دامنه الگو:ریاضی از اعداد صحیح را مرتبط می‌کند. سطح دوم از یک مجموعه دومی شامل توابع ماژولار خطی برای هر اندیس الگو:Mvar استفاده می‌کند تا هر عضو الگو:Mvar از الگو:Mvar را به محدودهالگو:ریاضی مرتبط می‌کند.

الگو:Harvard citation text نشان می‌دهند ، انتخابی برای k وجود دارد طوری که مجموع طول دامنه‌ها برای الگو:Mvar مقدار متفاوت (g(x برابر (O(n باشد. همچنین، برای هر مقدار الگو:ریاضی، یک تابع ماژولار خطی وجود دارد که زیر مجموعهٔ مطابقت یافته الگو:Mvar را با محدوده مربوط به آن مقدار مرتبط می‌کند. چه توابع سطح دوم چه k به ازای هر مقدار الگو:ریاضی با انتخاب مقادیر تصادفی تا زمانی که یکی از آنها را بیابد می‌تواند در زمان چند جمله ای کار کند.

این تابع درهم سازی به خودی خود نیاز به فضای حافظهالگو:ریاضی دارد تا الگو:Mvar و الگو:Mvar و همه توابع سطح دوم خطی ماژولار را ذخیره کند. محاسبه مقدار هش یک کلید الگو:Mvar داده شده احتمالاً در زمان ثابت با محاسبه الگو:ریاضی، جستجو با تابع سطح دوم مرتبط با الگو:ریاضی و اجرای این تابع روی انجام می‌شود. یک نسخه اصلاح شده از این طرح دو سطحی با تعداد بیشتری از مقادیر در سطح بالا می‌تواند برای ساختن یک تابع درهم سازی کامل استفاده شود که الگو:Mvar را به محدوده کوچکتری با پیچیدگی الگو:ریاضی مرتبط می‌کند (هش می‌کند).

مرزهای پایین حافظه

استفاده از کلمات حاوی اطلاعات الگو:ریاضی برای ذخیره تابع الگو:Harvard citation text تقریباً بهینه است: هر تابع درهم سازی کامل که در زمان ثابت قابل محاسبه باشد حداقل به تعدادی بیت نیاز دارد که متناسب با اندازه الگو:Mvar می‌باشد

برنامه‌های افزودنی

در هم سازی کامل پویا

استفاده از یک تابع درهم سازی کامل در شرایطی که یک مجموعه بزرگ که کاملاً پرس و جو شده وجود دارد، الگو:Mvar، که به ندرت به روز می‌شود، بهترین گزینه است. این امر به این دلیل است که هرگونه اصلاح مجموعه الگو:Mvar ممکن است باعث شود تابع درهم سازی دیگر برای مجموعه تغییر یافته کامل نباشد. روش‌هایی که تابع درهم سازی را به روز می‌کند هر زمان که مجموعه تغییر یابد، به عنوان درهم سازی کامل پویا شناخته می‌شوند، اما این روش‌ها برای پیاده‌سازی نسبتاً پیچیده هستند.

یک تابع درهم سازی کامل حداقلی یک نوع تابع درهم سازی کامل است که الگو:Mvar کلید را به الگو:Mvar عدد صحیح متوالی - معمولاً اعداد از الگو:ریاضی تا الگو:ریاضی یا از الگو:ریاضی تا الگو:Mvar مرتبط می‌سازد (نقشه یا هش می‌کند). یک روش معمول برای اجرای این موارد: اجازه دهید الگو:Mvar و الگو:Mvar عناصر برخی از مجموعه الگو:Mvar محدود باشند. الگو:Mvar یک تابع هش کامل حداقلی است اگر و تنها اگر الگو:ریاضی دلالت بر الگو:ریاضی (تزریق) کند و یک عدد صحیح مانند الگو:Mvar وجود داشته باشد طوری که برد F برابر الگو:ریاضی می‌باشد. ثابت شده‌است که برد هدف اصلی یک تابع درهم سازی کامل حداقل به ۱٫۴۴ بیت / کلید نیاز دارد. در صورت اختصاص زمان کافی، بهترین توابع درهم سازی کامل حداقلی شناخته شده در حال حاضر با استفاده کمتر از ۲٫۱ بیت / کلید ارائه شده‌است.

پانویس

• ریچارد جی. سیچلی. توابع حداقل کمال کاملاً ساده ساخته شده، ارتباطات ACM، جلد. ۲۳، شماره ۱، ژانویه ۱۹۸۰.
• توماس اچ. کورمن، چارلز ا. لییسرسون، رونالد ال ریوست و کلیفورد اشتاین. مقدمه ای بر الگوریتم‌ها، چاپ سوم. MIT Press، ۲۰۰۹. الگو:شابک۲ شابک 978-0262033848. بخش ۱۱٫۵: حشیش کامل، صص ۲۶۷، 277 – ۲۸۲.
• فابیانو سی بوتلو، راسموس پاغ و نیویو زیویانی. "هشی کردن کامل برای برنامه‌های مدیریت داده".
• فابیانو سی بوتلو و نویو زیویانی . "هشیی کامل خارجی برای مجموعه‌های کلید بسیار بزرگ". شانزدهمین کنفرانس ACM در مورد مدیریت اطلاعات و دانش (CIKM07)، لیسبون، پرتغال، نوامبر ۲۰۰۷.
• Djamal Belazzougui، پائولو Boldi , Rasmus Pagh و Sebastiano Vigna. "حداقل یکنواخت کردن کامل یکنواخت: در جستجوی یک جدول مرتب شده با دسترسی O (1)". در مجموعه مقالات بیستمین همایش سالانه ACM-SIAM در ریاضیات گسسته (SODA)، نیویورک، ۲۰۰۹. مطبوعات ACM.
• داگلاس C. اشمیت ، GPERF: یک ژنراتور عملکرد عالی هش، گزارش C ++ , SIGS، جلد. ۱۰، شماره ۱۰، نوامبر / دسامبر ۱۹۹۸.
• Minimal Perfect Hashing توسط باب جنکینز
• gperf یک ژنراتور هش منبع کامل C و C ++ است
• cmph منبع باز است که بسیاری از روش‌های هشی کردن کامل را اجرا می‌کند
• Sux4J متن باز است که هشیی کامل را اجرا می‌کند، از جمله هشدار کامل یکنواخت در جاوا
• MPHSharp متن باز است و بسیاری از روشهای بی‌حس کننده را در C # اعمال می‌کند.
• BBHash یک تابع هش کامل متن باز با منبع ++ C فقط + است