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

في علم الحاسوب ، تُعرَّف دالة التجزئة المثالية $h$ لمجموعة $S بأنها$ دالة تجزئة تربط العناصر المختلفة في $S$ بمجموعة من $m$ عدد صحيح، دون حدوث أي تصادمات . رياضياً، هي دالة أحادية .

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

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

تتمثل معايير الأداء المهمة لوظائف التجزئة المثالية في وقت التقييم، والذي يجب أن يكون ثابتًا، ووقت الإنشاء، وحجم التمثيل.

طلب

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

أداء دوال التجزئة المثالية

تتمثل معايير الأداء المهمة للتجزئة المثالية في حجم التمثيل، ووقت التقييم، ووقت الإنشاء، بالإضافة إلى متطلبات النطاق. ${\frac {m}{n}}$ (متوسط عدد الخانات لكل مفتاح في جدول التجزئة). ^{[ 4 ]} يمكن أن يكون وقت التقييم سريعًا مثل $O (1)$ ، وهو الأمثل. ^{[ 2 ]}^{[ 4 ]} يجب أن يكون وقت الإنشاء على الأقل $O (n)$ ، لأنه يجب مراعاة كل عنصر في $S ، و$ $S$ تحتوي على $n$ عنصرًا. يمكن تحقيق هذا الحد الأدنى عمليًا. ^{[ 4 ]}

يعتمد الحد الأدنى لحجم التمثيل على $m$ و $n$ . لنفترض أن $m = (1 + ε) n$ و $h$ دالة تجزئة مثالية. يُعد التقريب الجيد للحد الأدنى هو $\log e-\varepsilon \log {\frac {1+\varepsilon }{\varepsilon }}$ عدد البتات لكل عنصر. بالنسبة للتجزئة المثالية الدنيا، $ε = 0$ ، يكون الحد الأدنى هو $log e \approx 1.44$ بت لكل عنصر. ^{[ 4 ]}

بناء

يمكن إيجاد دالة تجزئة مثالية لمجموعة محددة $S،$ قابلة للتقييم في وقت ثابت وبقيم ضمن نطاق صغير، باستخدام خوارزمية عشوائية في عدد من العمليات يتناسب مع حجم S. يستخدم التصميم الأصلي لفريدمان، كوملوس، وسزيميريدي (1984) مخططًا ثنائي المستوى لربط مجموعة $S$ مكونة من $n$ عنصرًا بنطاق من $O (n)$ من المؤشرات، ثم ربط كل مؤشر بنطاق من قيم التجزئة. يختار المستوى الأول من تصميمهم عددًا أوليًا كبيرًا $p$ (أكبر من حجم المجموعة الكاملة التي تم اختيار $S$ منها )، ومعاملًا $k$ ، ويربط كل عنصر $x$ من $S$ بالمؤشر.

g(x)=(kx{\bmod {p}}){\bmod {n}}.

إذا تم اختيار $k$ عشوائيًا، فمن المرجح أن تحدث تصادمات في هذه الخطوة، ولكن من المرجح أن يكون عدد العناصر $nᵢ التي يتم تعيينها$ $في$ $الوقت$ نفسه إلى نفس الفهرس $i صغيرًا. يُخصص المستوى الثاني من بنائها نطاقات منفصلة من$ $O (ni²)$ $من$ الأعداد الصحيحة لكل فهرس $i$ . ويستخدم مجموعة ثانية من الدوال الخطية المعيارية، واحدة لكل فهرس $i$ ، لتعيين كل عنصر $x$ من $S$ في النطاق المرتبط بـ $g (x)$ . ^{[ 2 ]}

كما بيّن فريدمان وكوملوس وسزيميريدي (1984) ، يوجد خيار للمعامل $k$ بحيث يكون مجموع أطوال النطاقات للقيم $n$ المختلفة للدالة $g (x)$ هو $O (n)$ . بالإضافة إلى ذلك، لكل قيمة من قيم $g (x)$ ، توجد دالة نمطية خطية تربط المجموعة الجزئية المناظرة من $S$ بالنطاق المرتبط بتلك القيمة. يمكن إيجاد كل من $k$ ، ودوال المستوى الثاني لكل قيمة من قيم $g (x) ، في$ وقت متعدد الحدود عن طريق اختيار القيم عشوائيًا حتى العثور على قيمة مناسبة. ^{[ 2 ]}

تتطلب دالة التجزئة نفسها مساحة تخزين $O (n)$ لتخزين $k$ و $p$ وجميع الدوال الخطية المعيارية من المستوى الثاني. يمكن حساب قيمة التجزئة لمفتاح معين $x في وقت ثابت عن طريق حساب$ $g (x)$ ، والبحث عن دالة المستوى الثاني المرتبطة بـ $g (x)$ ، وتطبيق هذه الدالة على $x$ . يمكن استخدام نسخة معدلة من هذا المخطط ثنائي المستوى مع عدد أكبر من القيم في المستوى الأعلى لإنشاء دالة تجزئة مثالية تُسقط $S$ على نطاق أصغر بطول $n + o (n)$ . ^{[ 2 ]}

وصف بيلازوغي، بوتيلو، وديتزفيلبينغر (2009) طريقةً أحدث لإنشاء دالة تجزئة مثالية ، وهي "التجزئة، والإزاحة، والضغط". في هذه الطريقة، تُستخدم دالة تجزئة من المستوى الأول $g لربط العناصر بنطاق من$ $r$ عدد صحيح. يُخزَّن العنصر $x \in S$ في الحاوية $B g(x)$ . ^{[ 4 ]}

بعد ذلك، وبترتيب تنازلي حسب الحجم، تُجزأ عناصر كل مجموعة باستخدام دالة تجزئة من سلسلة دوال تجزئة مستقلة وعشوائية تمامًا $(Φ1، Φ2،$ $Φ3 ، ...) ، بدءًا من Φ1$ . $إذا لم$ $تُنتج دالة التجزئة أي تصادمات للمجموعة، ولم تكن القيم الناتجة مشغولة بعد بعناصر من مجموعات أخرى، تُختار الدالة لتلك المجموعة. وإلا ،$ تُختبر دالة التجزئة التالية في السلسلة. ^{[ 4 ]}

لتقييم دالة التجزئة المثالية $h (x)،$ يكفي حفظ التعيين σ لفهرس الدلو $g (x)$ على دالة التجزئة الصحيحة في التسلسل، مما ينتج عنه $h(x) = Φ σ(g(x))$ . ^{[ 4 ]}

وأخيرًا، لتقليل حجم التمثيل، يتم ضغط ( $σ(i)) 0 \leq i < r$ إلى شكل يسمح بالتقييم في $O (1)$ . ^{[ 4 ]}

يتطلب هذا الأسلوب وقتًا خطيًا في $n$ للإنشاء، ووقت تقييم ثابت. حجم التمثيل من رتبة $O (n)$ ، ويعتمد على النطاق المُحقق. على سبيل المثال، مع $m = 1.23n ،$ حقق بيلازوغي، وبوتيلو ، وديتزفيلبينغر (2009) حجم تمثيل يتراوح بين 3.03 بت/مفتاح و1.40 بت/مفتاح لمجموعة المثال التي قدموها والمكونة من 10 ملايين مدخل، حيث تتطلب القيم الأقل وقت حساب أطول. الحد الأدنى للمساحة في هذا السيناريو هو 0.88 بت/مفتاح. ^{[ 4 ]}

الشفرة الزائفة

خوارزمية التجزئة والإزاحة والضغط هي (1) تقسيم S إلى مجموعات  $B i := g -1 ({i}) \cap S، 0 \leq i < r$  (2) فرز المجموعات B _i بترتيب تنازلي وفقًا للحجم |B _i | (3) قم بتهيئة المصفوفة T[0...m-1] بالأصفار. (4) لكل i ∈[r]، بالترتيب الوارد في (2)، قم بتنفيذ (5) لـ l ← 1,2,... (6) كرر تشكيل Ki _←{ Φ  $l$ ₍ x )|x ∈ Bi _} (6) حتى |K _i |=|B _i | و K _i∩ {j|T[j]=1}= ∅ (7) ليكن σ(i):= l الناجح (8) لكل j ∈ K _i،ليكن T[j]:= 1 (9) تحويل (σ _i ) _{0 ≤ i<r} إلى شكل مضغوط، مع الاحتفاظ بإمكانية الوصول  $O (1)$  .

الحدود الدنيا للمساحة

إن استخدام $O (n)$ كلمة من المعلومات لتخزين دالة فريدمان، كوملوس وسزيميريدي (1984) هو شبه مثالي: أي دالة تجزئة مثالية يمكن حسابها في وقت ثابت تتطلب ^على الأقل عددًا من البتات يتناسب مع حجم $S.$ [ ^{5 ]}

بالنسبة لدوال التجزئة المثالية الدنيا، فإن الحد الأدنى لمساحة المعلومات النظرية هو

\log _{2}e\approx 1.44

بتات/مفتاح. ^{[ 4 ]}

بالنسبة لدوال التجزئة المثالية، يُفترض أولاً أن مدى $h$ محدود بـ $n$ حيث $m = (1 +$ ε $)$ $n$ $.$ باستخدام الصيغة التي قدمها بيلازوغي، بوتيلو، وديتزفيلبينجر (2009) ولكون $U\supseteq S$ عندما يؤول حجمها $| U | = u$ إلى اللانهاية، فإن حدودها الدنيا للفضاء هي

\log _{2}e-\varepsilon \log {\frac {1+\varepsilon }{\varepsilon }}

بتات/مفتاح، ناقص $لوغاريتم (ن)$ بتات إجمالاً. ^{[ 4 ]}

الإضافات

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

يُعدّ استخدام دالة تجزئة مثالية الخيار الأمثل في الحالات التي توجد فيها مجموعة بيانات كبيرة ( $S$ ) يتم الاستعلام عنها بشكل متكرر، ونادرًا ما يتم تحديثها. وذلك لأن أي تعديل على المجموعة $(S)$ قد يؤدي إلى فقدان دالة التجزئة لملاءمتها المثالية للمجموعة المُعدّلة. تُعرف الحلول التي تُحدّث دالة التجزئة كلما تم تعديل المجموعة باسم التجزئة المثالية الديناميكية ^{[ 1 ]،} إلا أن هذه الطرق معقدة نسبيًا من حيث التنفيذ.

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

دالة التجزئة المثالية الدنيا هي دالة تجزئة مثالية تربط $n$ مفتاحًا بـ $n$ عددًا صحيحًا متتاليًا - عادةً الأعداد من $0$ إلى $n - 1$ أو من $1$ إلى $n$ . ويمكن التعبير عن ذلك بشكل أكثر رسمية كما يلي: ليكن $j$ و $k$ عنصرين من مجموعة منتهية $S.$ عندئذٍ، $تكون$ $h$ دالة تجزئة مثالية دنيا إذا وفقط إذا كان $h (j) = h (k)$ يستلزم $j = k$ ( خاصية التباين )، ويوجد عدد صحيح $a$ بحيث يكون مدى $h$ هو $a..a + | S | - 1.$ وقد ثبت أن مخطط التجزئة المثالي الأدنى للأغراض العامة يتطلب على الأقل $\log _{2}e\approx 1.44$ بتات/مفتاح. ^{[ 4 ]} بافتراض أن $S$ هي مجموعة من الأحجام $n$ تحتوي على أعداد صحيحة في النطاق $[1,2^{o(n)}]$ من المعروف كيفية إنشاء دالة تجزئة مثالية دنيا صريحة بكفاءة من $S$ ل $\{1,2,\ldots ,n\}$ ذلك يستغل المساحة $n\log _{2}e+o(n)$ ^{[ 6 ]} عمليًا، توجد مخططات تجزئة مثالية دنيا تستخدم حوالي 1.56 بت/مفتاح إذا أُتيح لها وقت كافٍ . ^{[ 7 ]}^{[ 8 ]}

التجزئة المثالية k

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

(4) لكل i ∈[r]، بالترتيب الوارد في (2)، قم بتنفيذ (5) لـ l ← 1,2,... (6) كرر تشكيل Ki _←{ Φ  $l$ ₍ x )|x ∈ Bi _} (6) حتى |K _i |=|B _i | و K _i∩ {j| T[j]=k }= ∅ (7) ليكن σ(i):= l الناجح (8) لكل j ∈ K _iضع T[j] ← T[j]+1

حفظ النظام

تكون دالة التجزئة المثالية الدنيا $F$ حافظة للترتيب إذا تم إعطاء $المفاتيح$ بترتيب معين $a₁, a₂, ..., aₙ ،$ ولكل مفتاحين $aₜ و$ $aₖ ،$ $فإن$ $j < k$ يستلزم $F (aₜ) < F( aₖ) . [$ 9 ^{] في هذه} الحالة ، قيمة الدالة هي ببساطة موضع كل مفتاح في الترتيب المُرتب لجميع المفاتيح. يتمثل أحد التطبيقات البسيطة لدوال التجزئة المثالية الدنيا الحافظة للترتيب مع زمن وصول ثابت في استخدام دالة تجزئة مثالية (عادية) لتخزين جدول بحث لمواضع كل مفتاح. يستخدم هذا الحل $O(n\log n)$ البتات، وهو الأمثل في الحالة التي قد تكون فيها دالة المقارنة للمفاتيح عشوائية. ^{[ 10 ]} ومع ذلك، إذا كانت المفاتيح $a1 ، a2 ، ...، an أعدادًا صحيحة$ مختارة من مجموعة كاملة $\{1,2,\ldots ,U\}$ عندئذٍ، يصبح من الممكن إنشاء دالة تجزئة تحافظ على الترتيب باستخدام فقط $O(n\log \log \log U)$ وحدات من المساحة. ^{[ 11 ]} علاوة على ذلك، من المعروف أن هذا الحد هو الأمثل. ^{[ 12 ]}

الإنشاءات ذات الصلة

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

تدعم خوارزميات قليلة من جداول التجزئة زمن بحث ثابتًا O(1) في أسوأ الحالات (زمن بحث ثابت حتى في أسوأ الحالات). ومن بين هذه الخوارزميات: التجزئة المثالية؛ التجزئة المثالية الديناميكية ؛ تجزئة الوقواق ؛ تجزئة الحجلة ؛ والتجزئة القابلة للتمديد . ^{[ 13 ]}^{: 42-69}

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

مراجع

1 2 ديتزفيلبينجر، مارتن؛ الأماكن القريبة : الأماكن القريبة : ماير أوف دير هايد، فريدهيلم؛ روهنيرت، هانز. تارجان، روبرت إي (1994)، “التجزئة الديناميكية المثالية: الحدود العليا والسفلى”، مجلة SIAM للحوسبة ، 23 (4): 738–761 ، دوى : 10.1137 / S0097539791194094 ، MR 1283572 .
1 2 3 4 5 فريدمان، مايكل إل . كوملوس, يانوس ; Szemerédi، Endre (1984)، “تخزين جدول متفرق مع $O$ $(1)$ أسوأ وقت وصول للحالة”، مجلة ACM ، 31 (3): 538، دوى : 10.1145/828.1884 ، MR 0819156 ، S2CID 5399743
↑ لو، يي ؛ برابهاكار، بالاجي ؛ بونومي، فلافيو (2006)، "التجزئة المثالية لتطبيقات الشبكات"، ندوة IEEE الدولية لنظرية المعلومات لعام 2006 ، الصفحات 2774-2778 ، doi : 10.1109/ISIT.2006.261567 ، ISBN 1-4244-0505-X، S2CID 1494710
1 2 3 4 5 6 7 8 9 10 11 12 بيلازوقي، جمال؛ بوتيلو، فابيانو سي؛ ديتزفيلبينجر، مارتن (2009)، "التجزئة، والإزاحة، والضغط" (ملف PDF) ، الخوارزميات - ESA 2009 (ملف PDF) ، سلسلة محاضرات في علوم الحاسوب ، المجلد 5757، برلين: سبرينغر، الصفحات 682-693 ، CiteSeerX 10.1.1.568.130 ، doi : 10.1007/978-3-642-04128-0_61 ، ISBN 978-3-642-04127-3MR 2557794 .
↑ فريدمان، مايكل ل .؛ كوملوس، يانوس (1984)، "حول حجم أنظمة الفصل وعائلات دوال التجزئة المثالية"، مجلة SIAM للطرق الجبرية والمنفصلة ، 5 (1): 61-68 ، doi : 10.1137/0605009 ، MR 0731857 .
↑ هاجيروب، توربن؛ ثولي، تورستن (2001)، "التجزئة المثالية الدنيا الفعالة في مساحة شبه دنيا" ، STACS 2001 ، برلين، هايدلبرغ: سبرينغر برلين هايدلبرغ، ص 317-326 ، doi : 10.1007/3-540-44693-1_28 ، ISBN 978-3-540-41695-1تم الاطلاع عليه بتاريخ 12 نوفمبر 2023{{citation}}: CS1 maint: work parameter with ISBN ( link )
↑ إسبوزيتو، إيمانويل؛ مولر غراف، توماس؛ فيغنا، سيباستيانو (2020)، "RecSplit: التجزئة المثالية الدنيا عبر التقسيم المتكرر"، وقائع ندوة هندسة الخوارزميات والتجارب (ALENEX) لعام 2020 ، الصفحات 175-185 ، arXiv : 1910.06416 ، doi : 10.1137 / 1.9781611976007.14 .
↑ minimal-perfect-hash (GitHub)
↑ جينكينز، بوب (14 أبريل 2009)، "التجزئة المثالية الدنيا التي تحافظ على الترتيب"، في بلاك، بول إي. (محرر)، قاموس الخوارزميات وهياكل البيانات ، المعهد الوطني الأمريكي للمعايير والتكنولوجيا ، تم الاطلاع عليه بتاريخ 5 مارس 2013
↑ فوكس، إدوارد أ.؛ تشين، تشي فان؛ داود، أمجد م.؛ هيث، لينوود س. (يوليو 1991)، "دوال التجزئة المثالية الدنيا الحافظة للترتيب واسترجاع المعلومات" (ملف PDF) ، معاملات ACM لأنظمة المعلومات ، 9 (3)، نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM: 281-308 ، doi : 10.1145/125187.125200 ، S2CID 53239140 .
↑ بلازوقي، جمال؛ بولدي، باولو؛ باج، راسموس ؛ فيجنا، سيباستيانو (نوفمبر 2008)، "نظرية وتطبيق التجزئة المثالية الدنيا الرتيبة"، مجلة الخوارزميات التجريبية ، 16 ، المادة رقم 3.2، 26 صفحة، doi : 10.1145/1963190.2025378 ، S2CID 2367401 .
↑ أسدي، سيبهر؛ فاراش-كولتون، مارتن؛ كوزماول، ويليام (يناير 2023)، "حدود دقيقة للتجزئة المثالية الدنيا الرتيبة" ، وقائع ندوة ACM-SIAM السنوية لعام 2023 حول الخوارزميات المنفصلة (SODA) ، فيلادلفيا، بنسلفانيا: جمعية الرياضيات الصناعية والتطبيقية، الصفحات 456-476 ، arXiv : 2207.10556 ، doi : 10.1137/1.9781611977554.ch20 ، ISBN 978-1-61197-755-4تم الاطلاع عليه بتاريخ 27 أبريل 2023{{citation}}: CS1 maint: work parameter with ISBN ( link )
1 2 تيموثي أ. ديفيس. "الفصل 5 التجزئة" : القسم الفرعي "جداول التجزئة مع أسوأ حالة وصول O(1)"
^ باغ، راسموس ؛ Rodler، Flemming Friche (2004)، “Cuckoo hashing”، مجلة الخوارزميات ، 51 (2): 122-144 ، دوى : 10.1016/j.jalgor.2003.12.002 ، MR 2050140 .

للمزيد من القراءة

ريتشارد ج. سيتشيلي. تبسيط وظائف التجزئة المثالية الدنيا ، اتصالات ACM، المجلد 23، العدد 1، يناير 1980.
توماس هـ. كورمين ، وتشارلز إي. ليسرسون ، ورونالد إل. ريفست ، وكليفورد شتاين . مقدمة للخوارزميات ، الطبعة الثالثة. مطبعة معهد ماساتشوستس للتكنولوجيا، 2009. ISBN 978-0262033848القسم 11.5: التجزئة المثالية، الصفحات 267، 277 – 282.
فابيانو سي. بوتيلو، وراسموس باغ، ونيفيو زيفياني. "التجزئة المثالية لتطبيقات إدارة البيانات" .
فابيانو سي بوتيلهو ونيفيو زيفياني . "التجزئة المثالية الخارجية لمجموعات المفاتيح الكبيرة جدًا" . مؤتمر ACM السادس عشر لإدارة المعلومات والمعرفة (CIKM07)، لشبونة، البرتغال، نوفمبر 2007.
جمال بلعزوقي، باولو بولدي، راسموس باغ ، وسيباستيانو فيغنا. "التجزئة المثالية الدنيا الرتيبة: البحث في جدول مُرتب باستخدام O(1) من عمليات الوصول" . في وقائع الندوة السنوية العشرين لجمعية ACM-SIAM حول الرياضيات المتقطعة (SODA)، نيويورك، 2009. مطبعة ACM.
مارشال د. براين وآلان ل. ثارب. "التجزئة شبه المثالية لمجموعات الكلمات الكبيرة". البرمجيات - الممارسة والخبرة، المجلد 19 (10)، 967-078، أكتوبر 1989. جون وايلي وأولاده.
دوغلاس سي. شميدت، GPERF: مولد دالة التجزئة المثالية ، تقرير C++، SIGS، المجلد 10، العدد 10، نوفمبر/ديسمبر، 1998.
هانز بيتر ليمان، توماس مولر، راسموس باج، جوليو إرمانو بيبيري، بيتر ساندرز، سيباستيانو فيجنا، ستيفان والزر، "التجزئة المثالية الدنيا الحديثة: دراسة استقصائية"، arXiv : 2506.06536 ، يونيو 2025. يناقش التطورات التي حدثت في هذا المجال بعد عام 1997.

روابط خارجية

gperf هو مولد تجزئة مثالي مفتوح المصدر مكتوب بلغة C و C++ (سريع جدًا، ولكنه يعمل فقط مع مجموعات صغيرة).
التجزئة المثالية الدنيا (خوارزمية بوب) من تأليف بوب جينكينز
cmph : مكتبة C Minimal Perfect Hashing Library، تطبيقات مفتوحة المصدر للعديد من عمليات التجزئة المثالية (البسيطة) (تعمل مع المجموعات الكبيرة)
Sux4J : برنامج مفتوح المصدر للتجزئة المثالية البسيطة أحادية اللون في جافا
MPHSharp : طرق التجزئة المثالية في لغة C#
BBHash : دالة تجزئة مثالية مصغرة مكتوبة بلغة C++ باستخدام ملفات الرأس فقط
Perfect::Hash ، مولد تجزئة مثالي بلغة بيرل يُنتج كود C. يحتوي على قسم "التقنيات السابقة" الذي يستحق الاطلاع عليه.

[DynamicPerfectHashing-1] 1 2 ديتزفيلبينجر، مارتن؛ الأماكن القريبة : الأماكن القريبة : ماير أوف دير هايد، فريدهيلم؛ روهنيرت، هانز. تارجان، روبرت إي (1994)، “التجزئة الديناميكية المثالية: الحدود العليا والسفلى”، مجلة SIAM للحوسبة ، 23 (4): 738–761 ، دوى : 10.1137 / S0097539791194094 ، MR 1283572 .

[inventor-2] 1 2 3 4 5 فريدمان، مايكل إل . كوملوس, يانوس ; Szemerédi، Endre (1984)، “تخزين جدول متفرق مع $O$ $(1)$ أسوأ وقت وصول للحالة”، مجلة ACM ، 31 (3): 538، دوى : 10.1145/828.1884 ، MR 0819156 ، S2CID 5399743

[3] لو، يي ؛ برابهاكار، بالاجي ؛ بونومي، فلافيو (2006)، "التجزئة المثالية لتطبيقات الشبكات"، ندوة IEEE الدولية لنظرية المعلومات لعام 2006 ، الصفحات 2774-2778 ، doi : 10.1109/ISIT.2006.261567 ، ISBN 1-4244-0505-X، S2CID 1494710

[CHD-4] 1 2 3 4 5 6 7 8 9 10 11 12 بيلازوقي، جمال؛ بوتيلو، فابيانو سي؛ ديتزفيلبينجر، مارتن (2009)، "التجزئة، والإزاحة، والضغط" (ملف PDF) ، الخوارزميات - ESA 2009 (ملف PDF) ، سلسلة محاضرات في علوم الحاسوب ، المجلد 5757، برلين: سبرينغر، الصفحات 682-693 ، CiteSeerX 10.1.1.568.130 ، doi : 10.1007/978-3-642-04128-0_61 ، ISBN 978-3-642-04127-3MR 2557794 .

[5] فريدمان، مايكل ل .؛ كوملوس، يانوس (1984)، "حول حجم أنظمة الفصل وعائلات دوال التجزئة المثالية"، مجلة SIAM للطرق الجبرية والمنفصلة ، 5 (1): 61-68 ، doi : 10.1137/0605009 ، MR 0731857 .

[6] هاجيروب، توربن؛ ثولي، تورستن (2001)، "التجزئة المثالية الدنيا الفعالة في مساحة شبه دنيا" ، STACS 2001 ، برلين، هايدلبرغ: سبرينغر برلين هايدلبرغ، ص 317-326 ، doi : 10.1007/3-540-44693-1_28 ، ISBN 978-3-540-41695-1تم الاطلاع عليه بتاريخ 12 نوفمبر 2023{{citation}}: CS1 maint: work parameter with ISBN ( link )

[RecSplit-7] إسبوزيتو، إيمانويل؛ مولر غراف، توماس؛ فيغنا، سيباستيانو (2020)، "RecSplit: التجزئة المثالية الدنيا عبر التقسيم المتكرر"، وقائع ندوة هندسة الخوارزميات والتجارب (ALENEX) لعام 2020 ، الصفحات 175-185 ، arXiv : 1910.06416 ، doi : 10.1137 / 1.9781611976007.14 .

[8] -perfect-hash (GitHub)

[9] جينكينز، بوب (14 أبريل 2009)، "التجزئة المثالية الدنيا التي تحافظ على الترتيب"، في بلاك، بول إي. (محرر)، قاموس الخوارزميات وهياكل البيانات ، المعهد الوطني الأمريكي للمعايير والتكنولوجيا ، تم الاطلاع عليه بتاريخ 5 مارس 2013

[10] فوكس، إدوارد أ.؛ تشين، تشي فان؛ داود، أمجد م.؛ هيث، لينوود س. (يوليو 1991)، "دوال التجزئة المثالية الدنيا الحافظة للترتيب واسترجاع المعلومات" (ملف PDF) ، معاملات ACM لأنظمة المعلومات ، 9 (3)، نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM: 281-308 ، doi : 10.1145/125187.125200 ، S2CID 53239140 .

[11] بلازوقي، جمال؛ بولدي، باولو؛ باج، راسموس ؛ فيجنا، سيباستيانو (نوفمبر 2008)، "نظرية وتطبيق التجزئة المثالية الدنيا الرتيبة"، مجلة الخوارزميات التجريبية ، 16 ، المادة رقم 3.2، 26 صفحة، doi : 10.1145/1963190.2025378 ، S2CID 2367401 .

[12] أسدي، سيبهر؛ فاراش-كولتون، مارتن؛ كوزماول، ويليام (يناير 2023)، "حدود دقيقة للتجزئة المثالية الدنيا الرتيبة" ، وقائع ندوة ACM-SIAM السنوية لعام 2023 حول الخوارزميات المنفصلة (SODA) ، فيلادلفيا، بنسلفانيا: جمعية الرياضيات الصناعية والتطبيقية، الصفحات 456-476 ، arXiv : 2207.10556 ، doi : 10.1137/1.9781611977554.ch20 ، ISBN 978-1-61197-755-4تم الاطلاع عليه بتاريخ 27 أبريل 2023{{citation}}: CS1 maint: work parameter with ISBN ( link )

[davis-13] 1 2 تيموثي أ. ديفيس. "الفصل 5 التجزئة" : القسم الفرعي "جداول التجزئة مع أسوأ حالة وصول O(1)"

[14] باغ، راسموس ؛ Rodler، Flemming Friche (2004)، “Cuckoo hashing”، مجلة الخوارزميات ، 51 (2): 122-144 ، دوى : 10.1016/j.jalgor.2003.12.002 ، MR 2050140 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

على

[ 6 ]

[ 7 ]

[ 8 ]

] في هذه

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]