التجزئة المثالية الديناميكية

يقدم ديتزفيلبينجر وآخرون خوارزمية قاموس ديناميكية، حيث عند إضافة مجموعة من n عنصرًا بشكل تدريجي إلى القاموس، يتم تشغيل استعلامات العضوية دائمًا في وقت ثابت، وبالتالي${\displaystyle O(1)}$في أسوأ الأحوال، يكون إجمالي مساحة التخزين المطلوبة هو${\displaystyle O(n)}$(خطي)، و${\displaystyle O(1)}$الوقت المتوقع للإدخال والحذف المستهلك ( الوقت الثابت المستهلك ).

في الحالة الديناميكية، عند إدخال مفتاح في جدول التجزئة، إذا كان مدخله في الجدول الفرعي المقابل مشغولاً، يُقال إن تصادمًا قد حدث، ويُعاد بناء الجدول الفرعي بناءً على إجمالي عدد المدخلات الجديد ودالة التجزئة المختارة عشوائيًا. وذلك لأن عامل التحميل لجدول المستوى الثاني يبقى منخفضًا.${\displaystyle 1/k}$إعادة البناء نادرة، والتكلفة المتوقعة المستهلكة لعمليات الإدخال هي${\displaystyle O(1)}$^{[ 2 ]} وبالمثل ، فإن التكلفة المتوقعة المستهلكة لعمليات الحذف هي${\displaystyle O(1)}$[ ^{2 ]​}

بالإضافة إلى ذلك، فإن الأحجام النهائية للجدول الرئيسي أو أي من الجداول الفرعية غير معروفة في الحالة الديناميكية. إحدى طرق الحفاظ على الأحجام المتوقعة${\displaystyle O(n)}$يُستخدم فراغ الجدول لحثّ المستخدم على إعادة بناء الجدول بالكامل عند حدوث عدد كافٍ من عمليات الإضافة والحذف. ووفقًا لنتائج ديتزفيلبينجر وآخرون ^{[ 2 ]} ، طالما أن العدد الإجمالي لعمليات الإضافة أو الحذف يتجاوز عدد العناصر وقت آخر عملية بناء، فإن التكلفة المتوقعة المُستهلكة للإضافة والحذف تظل ثابتة.${\displaystyle O(1)}$مع الأخذ في الاعتبار إعادة الصياغة الكاملة.

يستخدم تطبيق التجزئة المثالية الديناميكية بواسطة Dietzfelbinger et al. هذه المفاهيم، بالإضافة إلى الحذف الكسول ، ويتم عرضه في الشفرة الزائفة أدناه.

دالة Locate( x ) هي j := h( x ) إذا (الموضع hj ( x ) من الجدول الفرعي Tj يحتوي على x (غير محذوف)) أرجع ( x موجود في S ) نهاية إذا وإلا أرجع ( x غير موجود في S ) نهاية وإلا نهاية

أثناء إدخال مدخل جديد x في j ، يتم زيادة عداد العمليات العامة، count .

إذا كان x موجودًا في j ، ولكن تم وضع علامة عليه بأنه محذوف، فسيتم إزالة العلامة.

إذا كان x موجودًا في j أو في الجدول الفرعي T _j ، ولم يتم وضع علامة عليه بأنه محذوف، فإنه يقال إن تصادمًا قد حدث ويتم إعادة بناء الجدول T j من المستوى الثاني للخزان ^j _{باستخدام} دالة تجزئة مختلفة مختارة عشوائيًا h _j .

دالة Insert( x ) هي count = count + 1؛ إذا كان ( count > M ) FullRehash( x ); end if else j := h( x ); if (Position h j (x) of subtable T j contains x ) if ( x is marked deleted) قم بإزالة علامة الحذف؛ end if end if else b j = b j + 1; if ( b j <= m j ) if the position h j ( x ) of T j is empty قم بتخزين x في الموضع h j ( x ) من T j ؛ نهاية الشرط وإلا ضع جميع العناصر غير المميزة من T j في القائمة L j ؛ أضف x إلى القائمة Lj ؛ bj = طول Lj ؛ كرر hj = دالة مختارة عشوائيًا في H sj؛ حتى تصبح hj أحادية على عناصر Lj ؛ لكل y في القائمة Lj ، خزّن y في الموضع hj ( y ) من Tj ؛ نهاية الحلقة نهاية الشرط وإلا نهاية الشرط وإلا mj = 2 * max{1, mj } ؛ sj = 2 * mj * ( mj - 1 )؛ إذا كان المجموع الكلي لجميع sj ≤ 32 * M² / s ( M ) + 4 * M ، فخصص sj خلية لـ Tj ؛ ضع جميع العناصر غير المميزة من T j في القائمة L j ؛ أضف x إلى القائمة L j ؛ b j = طول L j ؛ كرر h j = دالة مختارة عشوائيًا في H sj ؛ حتى تصبح h j أحادية على عناصر L j ؛ لكل y في القائمة L j، خزّن y في الموضع h j ( y ) من T j ؛ نهاية الحلقة نهاية إذا وإلا FullRehash( x )؛ نهاية وإلا نهاية وإلا نهاية وإلا نهاية نهاية

يؤدي حذف العنصر x إلى وضع علامة عليه كمحذوف دون إزالته، ويزيد قيمة العداد . في حالة الإضافة والحذف، إذا وصل العداد إلى عتبة M، يُعاد بناء الجدول بالكامل، حيث M هو مضاعف ثابت لحجم S عند بدء مرحلة جديدة . تشير المرحلة هنا إلى الفترة الزمنية بين عمليات إعادة البناء الكاملة. لاحظ أن -1 في "Delete( x )" يُمثل عنصرًا غير موجود في مجموعة جميع العناصر الممكنة U.

دالة الحذف ( x ) هي: count = count + 1؛ j = h( x )؛ إذا كان الموضع hj ( x ) في الجدول الفرعي Tj يحتوي على x ، فضع علامة على x كمحذوف؛ وإلا فأرجع (x ليس عضوًا في S)؛ وإلا إذا كان ( count >= M ) إعادة التجزئة الكاملة(-1)؛ نهاية الشرط نهاية

تبدأ عملية إعادة بناء جدول S بالكامل بإزالة جميع العناصر التي تم وضع علامة عليها بأنها محذوفة، ثم يتم تعيين قيمة العتبة التالية M إلى مضاعف ثابت لحجم S. يتم اختيار دالة تجزئة، تقسم S إلى s ( M ) مجموعة فرعية، حيث يكون حجم المجموعة الفرعية j هو sj _، بشكل عشوائي متكرر حتى:

${\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 ]}

دالة FullRehash( x ) هي: ضع جميع العناصر غير المميزة من T في القائمة L ؛ إذا كان ( x موجودًا في U ) أضف x إلى L ؛ انتهى الشرط. عدد العناصر = طول القائمة L ؛ M = (1 + c ) * max{ عدد العناصر ، 4 }؛ كرر h = دالة مختارة عشوائيًا في H s(M) ؛ لكل j < s ( M ) كوّن قائمة L <sub>j</sub> لكل h( x ) = j ؛ b<sub> j </sub> = طول L<sub> j </sub>؛ m<sub> j</sub> = 2 * b <sub> j </sub> ؛ s <sub>j</sub> = 2 * m <sub>j </sub> * ( m <sub>j</sub> - 1)؛ انتهى التكرار حتى يصبح مجموع جميع s <sub>j </sub> ≤ 32 * M <sup>2</sup> / s ( M ) + 4 * M لكل j < s ( M ). خصص مساحة sj للجدول الفرعي Tj ؛ كرر hj = دالة مختارة عشوائيًا في H sj ؛ حتى تصبح hj أحادية على عناصر القائمة Lj ؛ نهاية الحلقة ؛ لكل x في القائمة Lj ، خزّن x في الموضع hj ( x ) من Tj ؛ نهاية الحلقة .