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

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

جزئیات

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

function Locate(x) is
       j = h(x);
       if (position hj(x) of subtable Tj 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_j وجود داشته باشد و به عنوان یک عضو حذف شده برجسب نخورده باشد، پس یک تصادم روی داده و خانه j اُم سطل جدول سطح دوم T_j دوباره با انتخاب تصادفی تابع درهم سازی h_j ساخته می‌شود. زیرا ضریب بارگذاری جدول سطح دوم، کم نگه داشته می‌شود. بازسازی کم صورت گرفته و هزینه سرشکن درج‌ها، از (1)O خواهد شد.[2]

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

حذف عنصر xبه سادگی بدون اینکه واقعاً آن را حذف کند یا count را زیاد کند، آن را به عنوان یک عضو حذف شده علامتگذاری می‌کند. در صورت انجام هردو عمل حذف و درج، اگر count به آستانه M برسد، کل جدول بازسازی می‌شود. M در ابتدای یک فاز جدید، یک مقدار مشخص و چند برابر سایز S است. در اینجا فاز به معنای زمان بین بازسازی‌های کامل است. هزینه سرشکن حذف برابر (O(1 است.[2] توجه کنید که در اینجا، مقدار -۱ در تابع "(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_j است) آنقدر به صورت تصادفی انتخاب می‌شود تا:

${\displaystyle \sum _{0\leq j\leq s(M)}s_{j}\leq {\frac {32M^{2}}{s(M)}}+4M.}$

در نهایت، برای هر زیرجدول T_j، یک تابع درهم سازی h_j به صورت تصادفی آنقدر از H_sj انتخاب می‌شود تا h_j روی T_jیک به یک باشد. زمان پیش‌بینی شده برای بازسازی کامل جدولS با سایزn برابر (O(n خواهد شد.[2]

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 Hs(M);
          for all j <s(M)
             form a list Lj for h(x) = j;
             bj = length of Lj;
             mj = ۲ * bj;
             sj = ۲ * mj * (mj - 1);
          end for
       until the sum total of all sj ≤ ۳۲ * M2 / s(M) + 4 * M
       for all j <s(M)
          Allocate space sj for subtable Tj;
          repeat
             hj = randomly chosen function in Hsj;
          until hj is injective on the elements of list Lj;
       end for
       for all x on list Lj
          store x in position hj(x) of Tj;
       end for
end

جستارهای وابسته

• Perfect hashing

منابع

1. Fredman, M. L. , Komlós, J. , and Szemerédi, E. 1984. Storing a Sparse Table with 0(1) Worst Case Access Time. J. ACM 31, 3 (Jun. 1984), 538-544 http://portal.acm.org/citation.cfm?id=1884#
2. Dietzfelbinger, M. , Karlin, A. , Mehlhorn, K. , Meyer auf der Heide, F. , Rohnert, H. , and Tarjan, R. E. 1994. Dynamic Perfect Hashing: Upper and Lower Bounds. SIAM J. Comput. 23, 4 (Aug. 1994), 738-761. http://portal.acm.org/citation.cfm?id=182370#
3. Erik Demaine, Jeff Lind. 6.897: Advanced Data Structures. MIT Computer Science and Artificial Intelligence Laboratory. Spring 2003. http://courses.csail.mit.edu/6.897/spring03/scribe_notes/L2/lecture2.pdf