در علوم کامپیوتر، هشینگ پویا و کامل یک تکنیک برنامهنویسی برای حل مشکل برخورد در ساختار دادههای جدول هش است. اگرچه این روش از نظر حافظه پرهزینهتر از روشهای دیگر است، اما برای شرایطی که نیاز به جستجو، درج و حذف سریع در مجموعههای بزرگ دادهها وجود دارد، بسیار مفید است.
مورد ثابت
مشکل هشینگ ثابت بهینه برای اولین بار توسط فردمن، کوملوس و سمردی حل شد. آنها در مقاله سال ۱۹۸۴ خود، یک طرح دو سطحی برای جدول هش ارائه دادند که در آن هر سطل در سطح اول به یک جدول هش جداگانه در سطح دوم مرتبط است. کلیدهای داده دو بار هش میشوند: مقدار هش اول به یک سطل در سطح اول اشاره میکند و مقدار هش دوم موقعیت ورودی در جدول سطح دوم را مشخص میکند. جدول سطح دوم تضمین میکند که بدون برخورد (هشینگ کامل) ساخته شود. در نتیجه، هزینه جستجو در بدترین حالت O(1) است.
مورد پویا
دیتزفلینگر و همکارانش یک الگوریتم دیکشنری پویا ارائه دادند که در آن جستجوی عضویت همیشه در زمان ثابت انجام میشود. این الگوریتم با بازسازی پویا و مدیریت بهینه حافظه، هزینه درج و حذف را به صورت امورتیزه ثابت نگه میدارد.
پیادهسازی
پیادهسازی هشینگ پویا و کامل شامل توابعی برای جستجو، درج، حذف و بازسازی کامل است. این توابع با استفاده از حذف تنبل و بازسازی پویا، کارایی سیستم را در شرایط پویا تضمین میکنند.