هرس الوقواق

تجزئة الوقواق هي خوارزمية في برمجة الحاسوب لحل تصادمات التجزئة لقيم دوال التجزئة في جدول ، مع زمن بحث ثابت في أسوأ الحالات . يُستمد الاسم من سلوك بعض أنواع الوقواق ، حيث يدفع فرخ الوقواق البيض أو الصغار الأخرى خارج العش عند فقسه، في شكل من أشكال سلوك التطفل على الحضنة ؛ وبالمثل، قد يؤدي إدخال مفتاح جديد في جدول تجزئة الوقواق إلى دفع مفتاح قديم إلى موقع مختلف في الجدول.

تاريخ

وُصفت خوارزمية التجزئة باستخدام خوارزمية الوقواق لأول مرة من قِبل راسموس باج وفليمنج فريش رودلر في ورقة بحثية نُشرت في مؤتمر عام 2001. ^{[ 1 ]} وقد حازت هذه الورقة على جائزة اختبار الزمن من الندوة الأوروبية للخوارزميات عام 2020. ^{[ 2 ]}^{: 122}

العمليات

تجزئة الوقواق هي شكل من أشكال العنونة المفتوحة ، حيث تحتوي كل خلية غير فارغة في جدول التجزئة على مفتاح أو زوج مفتاح-قيمة . تُستخدم دالة تجزئة لتحديد موقع كل مفتاح، ويمكن العثور على وجوده في الجدول (أو القيمة المرتبطة به) بفحص تلك الخلية. مع ذلك، تعاني العنونة المفتوحة من التصادمات ، التي تحدث عند ربط أكثر من مفتاح بالخلية نفسها. تكمن الفكرة الأساسية لتجزئة الوقواق في حل التصادمات باستخدام دالتي تجزئة بدلاً من واحدة فقط. يوفر هذا موقعين محتملين في جدول التجزئة لكل مفتاح. في أحد المتغيرات الشائعة للخوارزمية، يُقسّم جدول التجزئة إلى جدولين أصغر متساويين في الحجم، وتوفر كل دالة تجزئة فهرسًا لأحد هذين الجدولين. من الممكن أيضًا أن توفر كلتا الدالتين فهارسًا لجدول واحد. ^{[ 1 ]}^{: 121-122}

ابحث عن

تستخدم خوارزمية التجزئة Cuckoo جدولين للتجزئة، $T_{1}$ و $T_{2}$ بافتراض $r$ يمثل طول كل جدول، وتُعرَّف دوال التجزئة للجدولين على النحو التالي: ${\displaystyle h_{1},\ h_{2}\$ و $\forall x\in S$ أين $x$ هو المفتاح و $S$ هي المجموعة التي تُخزَّن مفاتيحها في $h_{1}(x)$ ل $T_{1}$ أو $h_{2}(x)$ ل $T_{2}$ تتم عملية البحث كما يلي: ^{[ 1 ]}^{: 124}

دالة lookup ( x) تُرجع $T_{1}[h_{1}(x)]\ =\ x\vee T_{2}[h_{2}(x)]=x$ نهاية الدالة

أو المنطقي ( $\vee$ يشير ) إلى أن قيمة المفتاح $x$ يوجد في إما $T_{1}$ أو $T_{2}$ ، وهو $O(1)$ في أسوأ الأحوال. ^{[ 1 ]}^{: 123}

الحذف

يتم الحذف في $O(1)$ لا يُؤخذ الوقت منذ إجراء الفحص في الاعتبار. ويتجاهل هذا تكلفة عملية التقليص إذا كان الجدول متفرقًا للغاية. ^{[ 1 ]}^{: 124-125}

الإدخال

عند إدراج عنصر جديد باستخدام المفتاح $x$ ، تتضمن الخطوة الأولى فحص ما إذا كانت الفتحة $h_{1}(x)$ من الجدول $T_{1}$ إذا كان المكان مشغولاً، يتم إدخال العنصر فيه. أما إذا كان المكان مشغولاً، فسيتم إدخال العنصر الموجود فيه. $x'$ تمت إزالته و $x$ يتم إدراجه في $T_{1}[h_{1}(x)]$ . ثم، $x'$ يتم إدراجه في الجدول $T_{2}$ باتباع الإجراء نفسه. تستمر العملية حتى يتم العثور على موضع فارغ لإدخال المفتاح. ^{[ 1 ]}^{: 124-125.} لتجنب حلقة لا نهائية ، يتم تحديد عتبة. ${\text{Max-Loop}}$ يتم تحديد ذلك. إذا تجاوز عدد التكرارات هذا الحد الثابت، فسيتم تنفيذ كلا الإجراءين. $T_{1}$ و $T_{2}$ تُعاد معالجة البيانات باستخدام دوال تجزئة جديدة، وتتكرر عملية الإدخال. فيما يلي رمز زائف للإدخال: ^{[ 1 ]}^{: 125}

1 دالة insert(x) هي 2 إذا كان lookup(x) صحيحًا، فإن 3 تُرجع 4 نهاية الشرط 5 حلقة Max-Loop مرات 6 إذا $T_{1}[h_{1}(x)]$ = $\bot$ ثم 7  $T_{1}[h_{1}(x)]$ := x 8 إرجاع 9 نهاية إذا 10 × $\leftrightarrow T_{1}[h_{1}(x)]$  11 إذا $T_{2}[h_{2}(x)]$ = $\bot$ ثم 12  $T_{2}[h_{2}(x)]$ := x 13 إرجاع 14 نهاية الشرط 15 x $\leftrightarrow T_{2}[h_{2}(x)]$ حلقة طرفية 16  17 إعادة التجزئة() 18 إدراج(x) 19 نهاية الدالة

في السطرين 10 و15، "نهج الوقواق" المتمثل في ركل المفاتيح الأخرى التي تشغل $T_{1,2}[h_{1,2}(x)]$ يتكرر ذلك حتى يصبح لكل مفتاح "عشه" الخاص، أي عنصر $x$ يتم إدخالها في خانة فارغة في أي من الجدولين. $x\leftrightarrow y$ تبادل الرسائل $x$ و $y$ [ ¹^]^:^124-125

نظرية

تنجح عمليات الإدخال في وقت ثابت متوقع، ^{[ 1 ]} حتى مع الأخذ في الاعتبار إمكانية إعادة بناء الجدول، طالما أن عدد المفاتيح يبقى أقل من نصف سعة جدول التجزئة، أي أن عامل التحميل أقل من 50٪.

إحدى طرق إثبات ذلك تعتمد على نظرية الرسوم البيانية العشوائية : يمكن تكوين رسم بياني غير موجه يُسمى "رسم بياني الوقواق"، يحتوي على رأس لكل موقع في جدول التجزئة، وحافة لكل قيمة مُجزأة، حيث تمثل نهايتا الحافة الموقعين المحتملين للقيمة. عندئذٍ، تنجح خوارزمية الإدراج الجشعة لإضافة مجموعة من القيم إلى جدول تجزئة الوقواق إذا وفقط إذا كان رسم بياني الوقواق لهذه المجموعة من القيم عبارة عن غابة زائفة ، أي رسم بياني يحتوي على دورة واحدة على الأكثر في كل مكون من مكوناته المتصلة . أي رسم بياني فرعي ناتج عن الرؤوس ويحتوي على حواف أكثر من الرؤوس يُقابل مجموعة من المفاتيح التي لا يوجد لها عدد كافٍ من الخانات في جدول التجزئة. عند اختيار دالة التجزئة عشوائيًا، يكون رسم بياني الوقواق رسمًا بيانيًا عشوائيًا في نموذج إردوش-ريني . باحتمالية عالية، عندما يكون عامل التحميل أقل من 1/2 (أي ما يُقابل رسمًا بيانيًا عشوائيًا تكون فيه نسبة عدد الحواف إلى عدد الرؤوس أقل من 1/2)، يكون الرسم البياني غابة زائفة، وتنجح خوارزمية تجزئة الوقواق في وضع جميع المفاتيح. وتُثبت النظرية نفسها أيضًا أن الحجم المتوقع للمكون المتصل في رسم الوقواق البياني صغير، مما يضمن أن كل عملية إدخال تستغرق وقتًا متوقعًا ثابتًا. مع ذلك، وباحتمالية عالية أيضًا، سيؤدي عامل التحميل الأكبر من 1/2 إلى مكون ضخم يحتوي على دورتين أو أكثر، مما يتسبب في فشل بنية البيانات والحاجة إلى تغيير حجمها. ^{[ 3 ]}

بما أن دالة التجزئة العشوائية النظرية تتطلب مساحة تخزين كبيرة جدًا للاستخدام العملي، فإن السؤال النظري المهم هو: ما هي دوال التجزئة العملية الكافية لتجزئة الوقواق؟ أحد الأساليب هو استخدام التجزئة المستقلة عن k . في عام 2009، تم إثبات ^{[ 4 ]} أن $O(\log n)$ يكفي الاستقلال من الدرجة α، ويلزم على الأقل استقلال من الدرجة 6. ثمة نهج آخر يتمثل في استخدام تجزئة الجدولة ، وهي ليست مستقلة من الدرجة 6، ولكن تبين في عام 2012 ^{[ 5 ]} أنها تمتلك خصائص أخرى كافية لتجزئة الوقواق. أما النهج الثالث، الذي طُرح في عام 2014 ^{[ 6 ]} ، فيتمثل في تعديل جدول تجزئة الوقواق تعديلًا طفيفًا باستخدام ما يُسمى بالمخبأ، مما يُتيح استخدام دوال تجزئة مستقلة من الدرجة 2 فقط.

يمارس

عمليًا، يُعدّ تجزئة الوقواق أبطأ بنسبة تتراوح بين 20 و30% من الاستكشاف الخطي ، وهو الأسرع بين الطرق الشائعة. ^{[ 1 ]} والسبب هو أن تجزئة الوقواق غالبًا ما تتسبب في خطأين في ذاكرة التخزين المؤقت لكل عملية بحث، وذلك للتحقق من الموقعين اللذين يُحتمل تخزين المفتاح فيهما، بينما يتسبب الاستكشاف الخطي عادةً في خطأ واحد فقط في ذاكرة التخزين المؤقت لكل عملية بحث. مع ذلك، ونظرًا لضماناتها في أسوأ الحالات فيما يتعلق بوقت البحث، تظل تجزئة الوقواق مفيدة عند الحاجة إلى معدلات استجابة فورية .

مثال

تم إعطاء دوال التجزئة التالية (أقل رقمين أهمية من k في النظام ذي الأساس 11):

$h\left(k\right)=k{\bmod {1}}1$ $h'\left(k\right)=\left\lfloor {\frac {k}{11}}\right\rfloor {\bmod {1}}1$

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

الجدول 1: يستخدم h(k)
		خطوات
رقم الخطوة		1	2	3	4	5	6	7	8	9	10
تم إدخال المفتاح		53	50	20	75	100	67	105	3	36	45
h(k)		9	6	9	9	1	1	6	3	3	1
إدخالات جدول التجزئة	0
	1					100	67	67	67	67	45
	2
	3								3	36	36
	4
	5
	6		50	50	50	50	50	105	105	105	105
	7
	8
	9	53	53	20	75	75	75	53	53	53	53
	10

الجدول 2: يستخدم h′(k)
		خطوات
رقم الخطوة		1	2	3	4	5	6	7	8	9	10
تم إدخال المفتاح		53	50	20	75	100	67	105	3	36	45
h′(k)		4	4	1	6	9	6	9	0	3	4
إدخالات جدول التجزئة	0									3	3
	1				20	20	20	20	20	20	20
	2
	3
	4			53	53	53	53	50	50	50	50
	5
	6							75	75	75	75
	7
	8
	9						100	100	100	100	100
	10

دورة

إذا حاولتَ إدخال العنصر 45، فستدخل في حلقة مفرغة، وستفشل العملية. في الصف الأخير من الجدول، نجد نفس الوضع الأولي كما في البداية.

$h\left(45\right)=45{\bmod {1}}1=1$ $h'\left(45\right)=\left\lfloor {\frac {45}{11}}\right\rfloor {\bmod {1}}1=4$

الجدول 1	الجدول 2
يستبدل الرقم 45 الرقم 67 في الخلية 1	يستبدل الرقم 67 الرقم 75 في الخلية 6
يتم استبدال الرقم 53 بالرقم 75 في الخلية 9	يستبدل الرقم 53 الرقم 50 في الخلية 4
يتم استبدال الرقم 105 بالرقم 50 في الخلية 6	يتم استبدال الرقم 100 بالرقم 105 في الخلية 9
يتم استبدال الرقم 45 بالرقم 100 في الخلية 1	يستبدل الرقم 45 الرقم 53 في الخلية 4
يستبدل الرقم 53 الرقم 75 في الخلية 9	يستبدل الرقم 75 الرقم 67 في الخلية 6
يستبدل الرقم 67 الرقم 100 في الخلية 1	يتم استبدال الرقم 100 بالرقم 105 في الخلية 9
يتم استبدال الرقم 50 بالرقم 105 في الخلية 6	يتم استبدال الرقم 45 بالرقم 50 في الخلية 4
يستبدل الرقم 45 الرقم 67 في الخلية 1	يستبدل الرقم 67 الرقم 75 في الخلية 6

الاختلافات

تمت دراسة العديد من صيغ خوارزمية التجزئة باستخدام خوارزمية الوقواق، بهدف رئيسي هو تحسين استخدامها للمساحة عن طريق زيادة عامل التحميل الذي يمكنها تحمله إلى رقم يتجاوز عتبة 50% للخوارزمية الأساسية. كما يمكن استخدام بعض هذه الطرق لتقليل معدل فشل خوارزمية التجزئة باستخدام خوارزمية الوقواق، مما يقلل بشكل كبير من الحاجة إلى إعادة بناء بنية البيانات.

من المتوقع أن تستغل تعميمات خوارزمية التجزئة باستخدام أكثر من دالتين بديلتين جزءًا أكبر من سعة جدول التجزئة بكفاءة، مع التضحية ببعض سرعة البحث والإدخال. ويؤدي استخدام ثلاث دوال تجزئة فقط إلى زيادة الحمل بنسبة 91%. ^{[ 7 ]}

يستخدم تعميم آخر لخوارزمية تجزئة الوقواق، يُسمى تجزئة الوقواق المحظورة، أكثر من مفتاح واحد لكل مجموعة، بالإضافة إلى آلية تخصيص متوازنة. ويتيح استخدام مفتاحين فقط لكل مجموعة عامل تحميل يزيد عن 80%. ^{[ 8 ]}

من بين أنواع تجزئة الوقواق التي دُرست، تجزئة الوقواق مع التخزين المؤقت . في هذا النوع من تجزئة البيانات، يكون التخزين المؤقت عبارة عن مصفوفة تحتوي على عدد ثابت من المفاتيح، تُستخدم لتخزين المفاتيح التي لا يمكن إدخالها بنجاح في جدول التجزئة الرئيسي. يُقلل هذا التعديل معدل فشل تجزئة الوقواق إلى دالة متعددة الحدود عكسية ذات أس يمكن زيادته بشكل كبير عن طريق زيادة حجم التخزين المؤقت. مع ذلك، فإن زيادة حجم التخزين المؤقت تعني أيضًا إبطاء عمليات البحث عن المفاتيح غير الموجودة أو الموجودة فيه. يمكن استخدام التخزين المؤقت مع أكثر من دالتين للتجزئة أو مع تجزئة الوقواق المحجوبة لتحقيق كل من عوامل التحميل العالية ومعدلات الفشل المنخفضة. ^{[ 9 ]} يمتد تحليل تجزئة الوقواق مع التخزين المؤقت ليشمل دوال التجزئة العملية، وليس فقط نموذج دالة التجزئة العشوائية الشائع استخدامه في التحليل النظري للتجزئة. ^{[ 10 ]}

يوصي بعض الأشخاص بتعميم مبسط لتجزئة الوقواق يسمى ذاكرة التخزين المؤقت الترابطية المنحرفة في بعض ذاكرات التخزين المؤقت لوحدة المعالجة المركزية . ^{[ 11 ]}

يُعدّ مُرشِّح الوقواق نوعًا آخر من جداول التجزئة الوقواقية ، حيث يستبدل المفاتيح المخزنة في جدول التجزئة الوقواقية ببصمات أصابع أقصر بكثير، تُحسب بتطبيق دالة تجزئة أخرى على المفاتيح. وللسماح بنقل هذه البصمات داخل مُرشِّح الوقواق دون معرفة المفاتيح الأصلية، يُمكن حساب موقعي كل بصمة من بعضهما البعض باستخدام عملية "أو" الحصرية الثنائية مع البصمة، أو باستخدام تجزئة البصمة. تُشكِّل بنية البيانات هذه بنية بيانات تقريبية لعضوية المجموعة، ولها خصائص مشابهة لمُرشِّح بلوم : إذ يُمكنها تخزين أعضاء مجموعة من المفاتيح، واختبار ما إذا كان مفتاح الاستعلام عضوًا فيها، مع احتمال ضئيل لظهور نتائج إيجابية خاطئة (استعلامات تُبلَّغ بشكل خاطئ على أنها جزء من المجموعة) ولكن دون أي نتائج سلبية خاطئة . ومع ذلك، فهو يتفوّق على مُرشِّح بلوم في جوانب عديدة: فهو يستخدم ذاكرة أقل بمعامل ثابت، ويتمتّع بموقع مرجعي أفضل ، وعلى عكس مُرشِّحات بلوم، يسمح بحذف عناصر المجموعة بسرعة دون أي تكلفة إضافية على التخزين. ^{[ 12 ]}

مقارنة مع الهياكل ذات الصلة

أظهرت دراسة أجراها زوكوفسكي وآخرون ^{[ 13 ]} أن تجزئة الوقواق أسرع بكثير من التجزئة المتسلسلة لجداول التجزئة الصغيرة الموجودة في ذاكرة التخزين المؤقت على المعالجات الحديثة. كما أظهر كينيث روس ^{[ 14 ] أن نسخ تجزئة الوقواق المُجزأة (التي تستخدم مجموعات تحتوي على أكثر من مفتاح) أسرع من الطرق التقليدية حتى مع جداول التجزئة الكبيرة، عندما يكون استخدام المساحة مرتفعًا. وقد بحث أسكيتيس}^{[ 15 ]} أداء جدول تجزئة الوقواق المُجزأ بشكل أعمق، وقارنه بمخططات تجزئة بديلة.

يقدم استطلاع أجراه ميتزنماخر ^{[ 7 ]} مشاكل مفتوحة تتعلق بتجزئة الوقواق اعتبارًا من عام 2009.

المستخدمون المعروفون

تُستخدم خوارزمية التجزئة Cuckoo في نظام التوصيات الخاص بتطبيق TikTok لحل مشكلة "تداخل جداول التضمين"، والتي قد تؤدي إلى انخفاض جودة النموذج. يستفيد نظام التوصيات "Monolith" الخاص بتطبيق TikTok من خاصية حل التداخل في خوارزمية التجزئة Cuckoo لمنع ربط مفاهيم مختلفة بنفس المتجهات. ^{[ 16 ]}

انظر أيضاً

مراجع

1 2 3 4 5 6 7 8 9 10 باغ, راسموس ; رودلر، فليمنج فريش (2001). "تجزئة الوقواق". الخوارزميات – وكالة الفضاء الأوروبية 2001 . ملاحظات محاضرة في علوم الكمبيوتر. المجلد. 2161.سيتيسيركس 10.1.1.25.4189 . دوى : 10.1007/3-540-44676-1_10 . رقم ISBN 978-3-540-42493-2.
^ "ESA - الندوة الأوروبية حول الخوارزميات: جائزة ESA لاختبار الزمن لعام 2020" . esa-symposium.org . لجنة الجائزة: أوري زويك ، سمير خولر ، إديث كوهين . مؤرشف من الأصل بتاريخ 2021-05-22 . تم الاسترجاع بتاريخ 2021-05-22 .{{cite web}}صيانة CS1: أخرى ( رابط )
↑ كوتزلنيج، راينهارد (2006). الرسوم البيانية العشوائية ثنائية الأجزاء وتجزئة الوقواق (ملف PDF) . الندوة الرابعة حول الرياضيات وعلوم الحاسوب. الرياضيات المتقطعة وعلوم الحاسوب النظرية. المجلد AG. الصفحات 403-406 .
↑ كوهين، جيفري إس، ودانيال إم كين. "حدود الاستقلال المطلوب لتجزئة الوقواق." معاملات ACM في الخوارزميات (2009).
↑ باتراشكو، ميهاي، وميكيل ثورب. "قوة التجزئة الجدولية البسيطة." مجلة ACM (JACM) 59.3 (2012): 1-50.
↑ أومولر، مارتن، مارتن ديتزفيلبينجر، وفيليب وولفيل. "عائلات التجزئة الصريحة والفعالة تكفي لتجزئة الوقواق مع التخزين المؤقت." Algorithmica 70.3 (2014): 428-456.
1 2 ميتزنماخر، مايكل (9 سبتمبر 2009). "بعض الأسئلة المفتوحة المتعلقة بتجزئة الوقواق" (ملف PDF) . وقائع مؤتمر ESA 2009. تاريخ الاسترجاع: 10 نوفمبر 2010 .
↑ ديتزفيلبينجر، مارتن؛ وايدلينج، كريستوف (2007). "التخصيص المتوازن والقواميس ذات الحاويات المتراصة ذات الحجم الثابت" . علوم الحاسوب النظرية . 380 ( 1-2 ): 47-68 . doi : 10.1016/j.tcs.2007.02.054 . MR 2330641 .
↑ كيرش، آدم؛ ميتزنماخر، مايكل د.؛ ويدر، أودي (2010). "تجزئة أكثر قوة: تجزئة الوقواق مع مخزن مؤقت". مجلة SIAM للحوسبة . 39 (4): 1543-1561 . doi : 10.1137/080728743 . MR 2580539 .
↑ أومولر، مارتن؛ ديتزفيلبينجر، مارتن؛ وولفيل، فيليب (2014). "عائلات التجزئة الصريحة والفعالة تكفي لتجزئة الوقواق مع التخزين المؤقت". Algorithmica . 70 ( 3): 428–456 . arXiv : 1204.4431 . doi : 10.1007/s00453-013-9840-x . MR 3247374. S2CID 1888828 .
↑ "الهندسة المعمارية الدقيقة" .
↑ فان، بن؛ أندرسن، ديف جي؛ كامينسكي، مايكل؛ ميتزنماخر، مايكل دي (2014)، "مرشح الوقواق: أفضل عمليًا من بلوم"، وقائع المؤتمر الدولي العاشر لجمعية آلات الحوسبة حول تجارب وتقنيات الشبكات الناشئة (CoNEXT '14) ، الصفحات 75-88 ، doi : 10.1145/2674005.2674994
↑ زوكوفسكي، مارسين؛ هيمان، ساندور؛ بونكز، بيتر (يونيو 2006). "التجزئة الواعية بالبنية" (ملف PDF) . وقائع ورشة العمل الدولية الثانية حول إدارة البيانات على الأجهزة الجديدة - DaMoN '06 . ص 6. doi : 10.1145/1140402.1140410 . ISBN 1-59593-466-9تم الاطلاع عليه بتاريخ 16-10-2008 .
↑ روس، كينيث (2006-11-08). عمليات فحص التجزئة الفعالة على المعالجات الحديثة (ملف PDF) (تقرير بحثي). آي بي إم. RC24100 . تاريخ الاسترجاع: 2008-10-16 .
↑ أسكيتيس، نيكولاس (2009). "جداول تجزئة سريعة ومضغوطة لمفاتيح الأعداد الصحيحة". وقائع المؤتمر الأسترالي الآسيوي الثاني والثلاثين لعلوم الحاسوب (ACSC 2009) (ملف PDF) . المجلد 91. الجمعية الأسترالية للحاسبات. الصفحات 113-122 . ISBN 978-1-920682-72-9أُرشف من النسخة الأصلية (PDF) بتاريخ 16 فبراير 2011. تم الاطلاع عليه بتاريخ 13 يونيو 2010 .
^ ليو Z، Zou L، Zou X، Wang C، Zhang B، Tang D، Zhu B، Zhu Y، Wu P، Wang K، Cheng Y (27 سبتمبر 2022). “مونوليث: نظام التوصية في الوقت الحقيقي مع جدول التضمين بدون تصادم”. أرخايف : 2209.07663 [ cs.IR ].

روابط خارجية

بديل رائع وعملي لجداول التجزئة التقليدية. مؤرشف في 2019-04-07 في Wayback Machine ، يو. إرلينجسون، إم. ماناس، إف. مكشيري، 2006.
Cuckoo Hashing for Undergraduates, 2006 , R. Pagh, 2006.
التجزئة الوقواق، النظرية والتطبيق (الجزء 1، الجزء 2 والجزء 3 )، مايكل ميتزنماخر، 2007.
ناور، موني؛ سيجيف، جيل؛ ويدر، أودي (2008). "تجزئة الوقواق المستقلة عن التاريخ" . الندوة الدولية حول الأتمتة واللغات والبرمجة (ICALP) . ريكيافيك، أيسلندا . تاريخ الاسترجاع: 21 يوليو 2008 .
تحسينات خوارزمية لتجزئة الوقواق المتزامنة السريعة ، إكس. لي، دي. أندرسن، إم. كامينسكي، إم. فريدمان. يوروسيس 2014.

أمثلة

[Cuckoo-1] 1 2 3 4 5 6 7 8 9 10 باغ, راسموس ; رودلر، فليمنج فريش (2001). "تجزئة الوقواق". الخوارزميات – وكالة الفضاء الأوروبية 2001 . ملاحظات محاضرة في علوم الكمبيوتر. المجلد. 2161.سيتيسيركس 10.1.1.25.4189 . دوى : 10.1007/3-540-44676-1_10 . رقم ISBN 978-3-540-42493-2.

[2] "ESA - الندوة الأوروبية حول الخوارزميات: جائزة ESA لاختبار الزمن لعام 2020" . esa-symposium.org . لجنة الجائزة: أوري زويك ، سمير خولر ، إديث كوهين . مؤرشف من الأصل بتاريخ 2021-05-22 . تم الاسترجاع بتاريخ 2021-05-22 .{{cite web}}صيانة CS1: أخرى ( رابط )

[3] كوتزلنيج، راينهارد (2006). الرسوم البيانية العشوائية ثنائية الأجزاء وتجزئة الوقواق (ملف PDF) . الندوة الرابعة حول الرياضيات وعلوم الحاسوب. الرياضيات المتقطعة وعلوم الحاسوب النظرية. المجلد AG. الصفحات 403-406 .

[4] كوهين، جيفري إس، ودانيال إم كين. "حدود الاستقلال المطلوب لتجزئة الوقواق." معاملات ACM في الخوارزميات (2009).

[5] باتراشكو، ميهاي، وميكيل ثورب. "قوة التجزئة الجدولية البسيطة." مجلة ACM (JACM) 59.3 (2012): 1-50.

[6] أومولر، مارتن، مارتن ديتزفيلبينجر، وفيليب وولفيل. "عائلات التجزئة الصريحة والفعالة تكفي لتجزئة الوقواق مع التخزين المؤقت." Algorithmica 70.3 (2014): 428-456.

[mitzenmacher2009survey-7] 1 2 ميتزنماخر، مايكل (9 سبتمبر 2009). "بعض الأسئلة المفتوحة المتعلقة بتجزئة الوقواق" (ملف PDF) . وقائع مؤتمر ESA 2009. تاريخ الاسترجاع: 10 نوفمبر 2010 .

[8] ديتزفيلبينجر، مارتن؛ وايدلينج، كريستوف (2007). "التخصيص المتوازن والقواميس ذات الحاويات المتراصة ذات الحجم الثابت" . علوم الحاسوب النظرية . 380 ( 1-2 ): 47-68 . doi : 10.1016/j.tcs.2007.02.054 . MR 2330641 .

[9] كيرش، آدم؛ ميتزنماخر، مايكل د.؛ ويدر، أودي (2010). "تجزئة أكثر قوة: تجزئة الوقواق مع مخزن مؤقت". مجلة SIAM للحوسبة . 39 (4): 1543-1561 . doi : 10.1137/080728743 . MR 2580539 .

[10] أومولر، مارتن؛ ديتزفيلبينجر، مارتن؛ وولفيل، فيليب (2014). "عائلات التجزئة الصريحة والفعالة تكفي لتجزئة الوقواق مع التخزين المؤقت". Algorithmica . 70 ( 3): 428–456 . arXiv : 1204.4431 . doi : 10.1007/s00453-013-9840-x . MR 3247374. S2CID 1888828 .

[11] "الهندسة المعمارية الدقيقة" .

[12] فان، بن؛ أندرسن، ديف جي؛ كامينسكي، مايكل؛ ميتزنماخر، مايكل دي (2014)، "مرشح الوقواق: أفضل عمليًا من بلوم"، وقائع المؤتمر الدولي العاشر لجمعية آلات الحوسبة حول تجارب وتقنيات الشبكات الناشئة (CoNEXT '14) ، الصفحات 75-88 ، doi : 10.1145/2674005.2674994

[13] زوكوفسكي، مارسين؛ هيمان، ساندور؛ بونكز، بيتر (يونيو 2006). "التجزئة الواعية بالبنية" (ملف PDF) . وقائع ورشة العمل الدولية الثانية حول إدارة البيانات على الأجهزة الجديدة - DaMoN '06 . ص 6. doi : 10.1145/1140402.1140410 . ISBN 1-59593-466-9تم الاطلاع عليه بتاريخ 16-10-2008 .

[14] روس، كينيث (2006-11-08). عمليات فحص التجزئة الفعالة على المعالجات الحديثة (ملف PDF) (تقرير بحثي). آي بي إم. RC24100 . تاريخ الاسترجاع: 2008-10-16 .

[15] أسكيتيس، نيكولاس (2009). "جداول تجزئة سريعة ومضغوطة لمفاتيح الأعداد الصحيحة". وقائع المؤتمر الأسترالي الآسيوي الثاني والثلاثين لعلوم الحاسوب (ACSC 2009) (ملف PDF) . المجلد 91. الجمعية الأسترالية للحاسبات. الصفحات 113-122 . ISBN 978-1-920682-72-9أُرشف من النسخة الأصلية (PDF) بتاريخ 16 فبراير 2011. تم الاطلاع عليه بتاريخ 13 يونيو 2010 .

[16] ليو Z، Zou L، Zou X، Wang C، Zhang B، Tang D، Zhu B، Zhu Y، Wu P، Wang K، Cheng Y (27 سبتمبر 2022). “مونوليث: نظام التوصية في الوقت الحقيقي مع جدول التضمين بدون تصادم”. أرخايف : 2209.07663 [ cs.IR ].

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ] أن نسخ تجزئة الوقواق المُجزأة (التي تستخدم مجموعات تحتوي على أكثر من مفتاح) أسرع من الطرق التقليدية حتى مع جداول التجزئة الكبيرة، عندما يكون استخدام المساحة مرتفعًا. وقد بحث أسكيتيس

[ 15 ]

[ 16 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗