موضوع مقاله: تابع درهم‌سازی کامل | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # تابع درهم‌سازی کامل | مقدمه: توابع هش کامل ممکن است برای پیاده‌سازی جدول جستجوی با بدترین زمان دسترسی استفاده شود. | ## بخش 1: تابع درهم‌سازی کامل | یک تابع هش کامل دارای بسیاری از کاربردهای مشابه توابع هش دیگر است، با این برتری که نیازی به بررسی مشکل برخورد ندارد. علاوه بر این، اگر کلیدها داده نباشند، لازم نیست کلیدها در جدول جستجو ذخیره شوند و موجب صرفه جویی در حافظه می‌شوند. کاربرد با قرار دادن کلیدهای (یا سایر مقادیر مرتبط) در یک جدول جستجوی فهرست شده (با اندیس) بوسیله خروجی این تابع، یک تابع درهم سازی کامل با مقادیر محدود می‌تواند برای یه عملیات جست و جوی کارآمد استفاده شود. سپس می‌توان با جستجوی سلول کلید مورد نظر در جدول، وجود کلید در را آزمایش کرد یا مقدار متناظر با آن را جستجو کرد. ساختن یک تابع درهم سازی کامل برای یک مجموعه خاص می‌تواند در زمان ثابت تعیین شود. یا با مقادیر موجود در یک محدوده کوچک، توسط یک الگوریتم تصادفی در تعدادی از عملیات‌ها که (که تعداد آن متناسب با اندازه S می‌باشد) می‌تواند جستجو شود. روش ساختن از یک طرح دو سطحی استفاده می‌کند تا یک مجموعه از عنصر به طیف وسیعی از شاخص مرتبط (نقشه) کند، و پس از آن هر شاخص به طیف وسیعی از مقادیر هش مرتبط می‌شود. سطح اول ساخت آنها، یک اول بسیار بزرگ (بزرگتر از اندازه مجموعه ای که از آن ترسیم شده‌است)، و یک پارامتر انتخاب می‌کند و هر عنصر از را به نمایه (اندیس) خودش مرتبط می‌کند. اگر به‌طور تصادفی انتخاب شود، این مرحله به احتمال زیاد دچار برخورد می‌شود، اما تعداد عناصر که همزمان به همان اندیس مرتبط (هش) می‌شوند، احتمالاً اندک است. | ## بخش 2: تابع درهم‌سازی کامل | سطح دوم از یک مجموعه دومی شامل توابع ماژولار خطی برای هر اندیس استفاده می‌کند تا هر عضو از را به محدوده مرتبط می‌کند. نشان می‌دهند ، انتخابی برای k وجود دارد طوری که مجموع طول دامنه‌ها برای مقدار متفاوت (g(x برابر (O(n باشد. همچنین، برای هر مقدار ، یک تابع ماژولار خطی وجود دارد که زیر مجموعهٔ مطابقت یافته را با محدوده مربوط به آن مقدار مرتبط می‌کند. چه توابع سطح دوم چه k به ازای هر مقدار با انتخاب مقادیر تصادفی تا زمانی که یکی از آنها را بیابد می‌تواند در زمان چند جمله ای کار کند. این تابع درهم سازی به خودی خود نیاز به فضای حافظه دارد تا و و همه توابع سطح دوم خطی ماژولار را ذخیره کند. محاسبه مقدار هش یک کلید داده شده احتمالاً در زمان ثابت با محاسبه ، جستجو با تابع سطح دوم مرتبط با و اجرای این تابع روی انجام می‌شود. یک نسخه اصلاح شده از این طرح دو سطحی با تعداد بیشتری از مقادیر در سطح بالا می‌تواند برای ساختن یک تابع درهم سازی کامل استفاده شود که را به محدوده کوچکتری با پیچیدگی مرتبط می‌کند (هش می‌کند). مرزهای پایین حافظه استفاده از کلمات حاوی اطلاعات برای ذخیره تابع تقریباً بهینه است: هر تابع درهم سازی کامل که در زمان ثابت قابل محاسبه باشد حداقل به تعدادی بیت نیاز دارد که متناسب با اندازه می‌باشد. برنامه‌های افزودنی در هم سازی کامل پویا استفاده از یک تابع درهم سازی کامل در شرایطی که یک مجموعه بزرگ که کاملاً پرس و جو شده وجود دارد، ، که به ندرت به روز می‌شود، بهترین گزینه است. | ## بخش 3: تابع درهم‌سازی کامل | این امر به این دلیل است که هرگونه اصلاح مجموعه ممکن است باعث شود تابع درهم سازی دیگر برای مجموعه تغییر یافته کامل نباشد. روش‌هایی که تابع درهم سازی را به روز می‌کند هر زمان که مجموعه تغییر یابد، به عنوان درهم سازی کامل پویا شناخته می‌شوند،. یک تابع درهم سازی کامل حداقلی یک نوع تابع درهم سازی کامل است که کلید را به عدد صحیح متوالی - معمولاً اعداد از تا یا از تا مرتبط می‌سازد (نقشه یا هش می‌کند). یک روش معمول برای اجرای این موارد: اجازه دهید و عناصر برخی از مجموعه محدود باشند. یک تابع هش کامل حداقلی است اگر و تنها اگر دلالت بر (تزریق) کند و یک عدد صحیح مانند وجود داشته باشد طوری که برد F برابر می‌باشد. ثابت شده‌است که برد هدف اصلی یک تابع درهم سازی کامل حداقل به ۱٫۴۴ بیت / کلید نیاز دارد.. در صورت اختصاص زمان کافی، بهترین توابع درهم سازی کامل حداقلی شناخته شده در حال حاضر با استفاده کمتر از ۲٫۱ بیت / کلید ارائه شده‌است.RecSplit. | ## جمع‌بندی | شانزدهمین کنفرانس ACM در مورد مدیریت اطلاعات و دانش (CIKM07)، لیسبون، پرتغال، نوامبر ۲۰۰۷.