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

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

## جزئیات
در این روش، ورودی‌هایی که به یک خانه از جدول نظیر می‌شوند، مانند یک جدول درهم سازی سطح دوم جدا سازماندهی می‌شوند. اگر *k* ورودی در مجموعه *S* داشته باشیم، برای جدول درهم سازی ثانویه، *k*2 خانه اختصاص می‌دهیم و تابع درهم سازی آن، از توابع جهانی درهم سازی به صورت تصادفی به گونه‌ای انتخاب می‌شوند که عاری از تصادم باشد (برای مثال، تابع درهم سازی کامل). بنابراین هزینه جستجو مطمئناً در بدترین حالت از (1)O خواهد شد.

 **function** Locate(*x*) **is**
        *j* = h(**x**);
        **if** (position hj(*x*) of subtable *T<sub>j</sub>* contains *x* (not deleted))
           **return** (*x* is in *S*);
        **end if**
        **else**
           **return** (*x* is not in *S*);
        **end else**
 **end**

با اینکه هر جدول سطح دوم، به یک فضای درجه دوم نیاز دارد، اگر کلیدهای وارد شده به جدول سطح اول دارای توزیع یکنواخت باشند، کل ساختار از فضای (O(n خواهد بود؛ زیرا سایز سطل به احتمال زیاد، کم است.

در طول درج ورودی جدید *x* در مکان *j* اُم، شمارنده جهانی دستورها، *count*، یک واحد افزایش می‌یابد. اگر *x* در *j* وجود داشته باشد اما به عنوان یک عضو حذف شده برچسب خورده باشد، برچسب آن برداشته می‌شود. اگر *x* در *j* یا زیرجدول *T<sub>j</sub>* وجود داشته باشد و به عنوان یک عضو حذف شده برجسب نخورده باشد، پس یک تصادم روی داده و خانه j اُم سطل جدول سطح دوم *T<sub>j</sub>* دوباره با انتخاب تصادفی تابع درهم سازی *h<sub>j</sub>* ساخته می‌شود. زیرا ضریب بارگذاری جدول سطح دوم، کم نگه داشته می‌شود. بازسازی کم صورت گرفته و هزینه سرشکن درج‌ها، از (1)O خواهد شد.

 **function** Insert(*x*) **is**
        *count* = *count* + 1;
        **if** (*count*> *M*)
           FullRehash(*x*);
        **end if**
        **else**
           *j* = h(*x*);
           **if** (Position h*j*(x) of subtable *T<sub>j</sub>* contains *x*)
              **if** (*x* is marked deleted)
                 remove the delete marker;
              **end if**
           **end if**
           **else**
              *b<sub>j</sub>* = *b<sub>j</sub>* + 1;
              **if** (*b<sub>j</sub>* j*)
                 *'if** position h<sub>''j''</sub>(''x'') of ''T<sub>j</sub>'' is empty
                    store ''x'' in position h<sub>''j''</sub>(''x'') of ''T<sub>j</sub>'';
                 **end if**
                 **else**
                    Put all unmarked elements of ''T<sub>j</sub>'' in list ''L<sub>j</sub>'';
                    Append ''x'' to list ''L<sub>j</sub>'';
                    ''b<sub>j</sub>'' = length of ''L<sub>j</sub>'';
                    **repeat**
                       ''h<sub>j</sub>'' = randomly chosen function in ''H<sub>sj</sub>'';
                    **until** ''h<sub>j</sub>'' is injective on the elements of ''L<sub>j</sub>'';
                    **for** all ''y'' on list ''L<sub>j</sub>''
                       store ''y'' in position h<sub>''j''</sub>(''y'') of ''T<sub>j</sub>'';
                    **end for**
                 **end else**
              **end if**
              **else**
                 ''m<sub>j</sub>'' = ۲ * max{1, ''m<sub>j</sub>''};
                 ''s<sub>j</sub>'' = ۲ * ''m<sub>j</sub>'' * (''m<sub>j</sub>'' - 1);
                 **if** the sum total of all s<sub>j</sub> ≤ ۳۲ * ''M''<sup>2</sup> / ''s''(''M'') + 4 * ''M''
                    Allocate ''s<sub>j</sub>'' cells for ''T<sub>j</sub>'';
                    Put all unmarked elements of ''T<sub>j</sub>'' in list ''L<sub>j</sub>'';
                    Append ''x'' to list ''L<sub>j</sub>'';
                    ''b<sub>j</sub>'' = length of ''L<sub>j</sub>'';
                    **repeat**
                       ''h<sub>j</sub>'' = randomly chosen function in ''H<sub>sj</sub>'';
                    **until** ''h<sub>j</sub>'' is injective on the elements of ''L<sub>j</sub>'';
                    **for** all ''y'' on list ''L<sub>j</sub>''
                       store ''y'' in position h<sub>''j''</sub>(''y'') of ''T<sub>j</sub>'';
                    **end for**
                 **end if**
                 **else**
                    FullRehash(''x'');
                 **end else**
              **end else**
           **end else**
        **end else**
 **end**


حذف عنصر ''x''به سادگی بدون اینکه واقعاً آن را حذف کند یا ''count'' را زیاد کند، آن را به عنوان یک عضو حذف شده علامتگذاری می‌کند. در صورت انجام هردو عمل حذف و درج، اگر ''count'' به آستانه ''M'' برسد، کل جدول بازسازی می‌شود. ''M'' در ابتدای یک ''فاز'' جدید، یک مقدار مشخص و چند برابر سایز S است. در اینجا ''فاز'' به معنای زمان بین بازسازی‌های کامل است. هزینه سرشکن حذف برابر (O(1 است. توجه کنید که در اینجا، مقدار -۱ در تابع "(Delete(x" بیانگر یک مقداری است که در مقادیر ممکن ''U''نیست.


 **function** Delete(''x'') **is**
        ''count'' = ''count'' + 1;
        ''j'' = h(''x'');
        **if** position h(''x'') of subtable ''Tj'' contains ''x''
           mark ''x'' as deleted;
        **end if**
        **else**
           **return** (x is not a member of S);
        **end else**
        **if** (''count''>= ''M'')
           FullRehash(-1);
        **end if**
 **end**


یک بازسازی کامل از جدول''S''، با پاک کردن تمام اعضای برچسب خورده شروع شده و با مقدار دهی آستانه بعدی ''M'' در یک ثابت که چند برابر سایز S است ادامه پیدا می‌کند. یک تابع درهم سازی، که ''S'' را به چند زیرمجموعه(''s''(''M'' تقسیم می‌کند (که سایز زیرمجموعه ''j'' برابر ''s<sub>j</sub>'' است) آنقدر به صورت تصادفی انتخاب می‌شود تا:


<math>\sum_{0\le j\le s(M)} s_j \le \frac{32M^2}{s(M)} + 4M.</math>


در نهایت، برای هر زیرجدول ''T<sub>j</sub>''، یک تابع درهم سازی ''h<sub>j</sub>'' به صورت تصادفی آنقدر از ''H<sub>sj</sub>'' انتخاب می‌شود تا ''h<sub>j</sub>'' روی ''T<sub>j</sub>''یک به یک باشد. زمان پیش‌بینی شده برای بازسازی کامل جدول''S'' با سایز''n'' برابر (''O(''n خواهد شد.


 **function** FullRehash(''x'') **is**
        Put all unmarked elements of ''T'' in list ''L'';
        **if** (''x'' is in ''U'')
           append ''x'' to ''L'';
        **end if**
        ''count'' = length of list ''L'';
        ''M'' = (1 + ''c'') * max{''count'', 4};
        **repeat**
           h = randomly chosen function in ''H<sub>s(M)</sub>'';
           **for** all ''j'' <''s''(''M'')
              form a list ''L<sub>j</sub>'' for h(''x'') = ''j'';
              ''b<sub>j</sub>'' = length of ''L<sub>j</sub>'';
              ''m<sub>j</sub>'' = ۲ * ''b<sub>j</sub>'';
              ''s<sub>j</sub>'' = ۲ * ''m<sub>j</sub>'' * (''m<sub>j</sub>'' - 1);
           **end for**
        **until** the sum total of all s<sub>j</sub> ≤ ۳۲ * ''M''<sup>2</sup> / ''s''(''M'') + 4 * ''M''
        **for** all ''j'' <''s''(''M'')
           Allocate space ''s<sub>j</sub>'' for subtable ''T<sub>j</sub>'';
           **repeat**
              ''h<sub>j</sub>'' = randomly chosen function in ''H<sub>sj</sub>'';
           **until** ''h<sub>j</sub>'' is injective on the elements of list ''L<sub>j</sub>'';
        **end for**
        **for** all ''x'' on list ''L<sub>j</sub>''
           store ''x'' in position h<sub>''j''</sub>(''x'') of ''T<sub>j</sub>'';
        **end for**
 **end'''

## جستارهای وابسته
* Perfect hashing

## منابع

رده:الگوریتم‌های جستجو
رده:درهم‌سازی