جدول التجزئة

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

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

في جدول التجزئة ذي الأبعاد المناسبة، يكون متوسط التعقيد الزمني لكل عملية بحث مستقلاً عن عدد العناصر المخزنة في الجدول. كما تسمح العديد من تصميمات جداول التجزئة بإضافة وحذف أزواج المفاتيح والقيم بشكل عشوائي، بتكلفة متوسطة ثابتة لكل عملية . ^{[ 5 ]}^{[ 4 ]}^{: 513-558}^{[ 6 ]}

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

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

تاريخ

ظهرت فكرة التجزئة بشكل مستقل في أماكن مختلفة. في يناير 1953، كتب هانز بيتر لونه مذكرة داخلية لشركة IBM استخدم فيها التجزئة مع التسلسل. اقترح إيه دي لينه أول مثال على العنونة المفتوحة ، استنادًا إلى مذكرة لونه. ^{[ 4 ]}^{: 547} في نفس الوقت تقريبًا، قام كل من جين أمدال وإيلين إم. ماكجرو وناثانيال روتشستر وآرثر صموئيل من قسم أبحاث IBM بتطبيق التجزئة على مُجمِّع IBM 701. ^[¹⁰^]^:¹²⁴ يُنسب الفضل في العنونة المفتوحة مع الاستكشاف الخطي إلى أمدال، على الرغم من أن أندريه إرشوف كان لديه نفس الفكرة بشكل مستقل. ^[¹⁰^]^:^124-125 صاغ دبليو ويسلي بيترسون مصطلح "العنونة المفتوحة" في مقالته التي تناقش مشكلة البحث في الملفات الكبيرة. ^[¹¹^]^:¹⁵

يُنسب الفضل في أول عمل منشور حول التجزئة باستخدام التسلسل إلى أرنولد دومي ، الذي ناقش فكرة استخدام باقي قسمة عدد أولي كدالة تجزئة. ^{[ 11 ]}^{: 15} وقد نُشر مصطلح "التجزئة" لأول مرة في مقال لروبرت موريس. ^{[ 10 ]}^{: 126} وقدّم كونهايم ووايس تحليلًا نظريًا للاستكشاف الخطي . ^{[ 11 ]}^{: 15}

ملخص

تُخزّن المصفوفة الترابطية مجموعة من أزواج (مفتاح، قيمة) وتسمح بالإدراج والحذف والبحث، مع شرط أن تكون المفاتيح فريدة . في تطبيق جدول التجزئة للمصفوفات الترابطية، تكون المصفوفة $A$ من الطول $m$ ممتلئ جزئيا بـ $n$ العناصر، حيث $m\geq n$ مفتاح $x$ يتم تجزئتها باستخدام دالة التجزئة $h$ لحساب موقع الفهرس $A[h(x)]$ في جدول التجزئة، حيث $h(x)<m$ تعتمد كفاءة جدول التجزئة على عامل التحميل، الذي يُعرَّف بأنه نسبة عدد العناصر المخزنة إلى عدد الخانات المتاحة، حيث يؤدي انخفاض عامل التحميل عمومًا إلى عمليات أسرع. ^{[ 12 ]} عند هذا الفهرس، يُخزَّن كلٌّ من المفتاح وقيمته المرتبطة به. يضمن تخزين المفتاح جنبًا إلى جنب مع القيمة إمكانية التحقق من المفتاح عند الفهرس لاسترجاع القيمة الصحيحة، حتى في حالة وجود تصادمات. في ظل افتراضات معقولة، تتمتع جداول التجزئة بحدود تعقيد زمني أفضل لعمليات البحث والحذف والإدراج مقارنةً بأشجار البحث الثنائية ذاتية التوازن . ^{[ 11 ]}^{: 1}

تُستخدم جداول التجزئة أيضًا بشكل شائع لتنفيذ المجموعات، وذلك بحذف القيمة المخزنة لكل مفتاح والاكتفاء بتتبع ما إذا كان المفتاح موجودًا أم لا. ^{[ 11 ]}^{: 1}

عامل التحميل

عامل التحميل $\alpha$ هي إحصائية حرجة لجدول التجزئة، ويتم تعريفها على النحو التالي: ^{[ 2 ]} ${\text{عامل الحمل}}\ (\alpha )={\frac {n}{m}},$ أين

$n$ يمثل عدد الإدخالات المشغولة في جدول التجزئة.
$m$ هو عدد الدلاء.

يتدهور أداء جدول التجزئة تبعًا لعامل التحميل $\alpha$ [ ¹¹^{] :}² في حالة الحجم ^الكبير $m$ و $n$ لكل مجموعة توزيع بواسون إحصائياً بقيمة متوقعة. $\lambda =\alpha$ لدالة تجزئة عشوائية مثالية .

يضمن البرنامج عادةً أن يكون عامل التحميل $\alpha$ يبقى أقل من قيمة ثابتة معينة، $\alpha _{\max }$ يساعد هذا في الحفاظ على الأداء الجيد. لذلك، يتمثل أحد الأساليب الشائعة في تغيير حجم جدول التجزئة أو "إعادة تجزئته" كلما زاد عامل التحميل. $\alpha$ يصل $\alpha _{\max }$ وبالمثل، يمكن أيضًا تغيير حجم الجدول إذا انخفض عامل التحميل عن $\alpha _{\max }/4$ [ ¹³^]

عامل التحميل للتسلسل المنفصل

باستخدام جداول التجزئة المتسلسلة المنفصلة، يخزن كل خانة من مصفوفة الحاويات مؤشرًا إلى قائمة أو مصفوفة من البيانات. ^{[ 14 ]}

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

باستخدام التسلسل المنفصل، قيمة $\alpha _{\max }$ إن أفضل أداء عادة ما يكون بين 1 و 3. ^{[ 13 ]}

عامل التحميل للعنونة المفتوحة

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

يصبح أداء العنونة المفتوحة سيئًا للغاية عندما يقترب عامل التحميل من 1. ^{[ 13 ]}

لذلك، يجب تغيير حجم جدول التجزئة الذي يستخدم عناوين مفتوحة أو إعادة تجزئته إذا كان عامل التحميل $\alpha$ النهج 1. ^{[ 13 ]}

مع العنونة المفتوحة، تكون قيم معامل الحمل الأقصى مقبولة $\alpha _{\max }$ ينبغي أن تتراوح النسبة بين 0.6 و 0.75. ^{[ 15 ]}^{[ 16 ]}^{: 110}

دالة التجزئة

دالة التجزئة $h:U\rightarrow \{0,...,m-1\}$ يرسم خريطة الكون $U$ أي مفاتيح للفهارس أو الخانات داخل الجدول، $h(x)\in \{0,...,m-1\}$ ل $x\in U$ تعتمد التطبيقات التقليدية لدوال التجزئة على افتراض الكون الصحيح، أي أن جميع عناصر الجدول تنبع من الكون. $U=\{0,...,u-1\}$ ، حيث يمثل طول البت $u$ يقتصر على حجم الكلمة في بنية الحاسوب . ^{[ 11 ]}^{: 2}

دالة التجزئة $h$ يقال إنه مثالي لمجموعة معينة $S$ إذا كان حقنيًا $S$ أي إذا كان كل عنصر $x\in S$ يشير إلى قيمة مختلفة في ${0,...,m-1}$ [ ^{17 ]}^{[ 18 ] يمكن إنشاء دالة تجزئة مثالية إذا}^كانت جميع المفاتيح معروفة مسبقًا. ^{[ 17 ]}

افتراض الكون الصحيح

تشمل أساليب التجزئة المستخدمة في فرضية الكون الصحيح التجزئة بالقسمة، والتجزئة بالضرب، والتجزئة الشاملة ، والتجزئة المثالية الديناميكية ، والتجزئة المثالية الثابتة . ^{[ 11 ]}^{: 2} ومع ذلك، فإن التجزئة بالقسمة هي الأسلوب الأكثر شيوعًا. ^{[ 19 ]}^{: 264}^{[ 16 ]}^{: 110}

التجزئة بالتقسيم

تكون آلية التجزئة بالقسمة كما يلي: ^{[ 11 ]}^{: 2} $h(x)\ =\ x\,{\bmod {\,}}m,$ أين $h(x)$ هي قيمة التجزئة لـ $x\in S$ و $m$ حجم الطاولة.

التجزئة بالضرب

تتمثل آلية التجزئة بالضرب فيما يلي: ^{[ 11 ]}^{: 2-3} $h(x)=\lfloor m{\bigl (}(xA){\bmod {1}}{\bigr )}\rfloor$ أين $A$ هو ثابت حقيقي غير صحيح و $m$ حجم الجدول. من مزايا التجزئة بالضرب أن $m$ ليس أمرًا بالغ الأهمية. ^{[ 11 ]}^{: 2-3} على الرغم من أي قيمة $A$ ينتج دالة تجزئة، ويقترح دونالد كنوث استخدام النسبة الذهبية . ^{[ 11 ]}^{: 3}

تجزئة السلاسل

يُستخدم عادةً نصٌّ كمفتاحٍ لدالة التجزئة. يصف الإصدار الثالث من كتاب "لغة برمجة C++" دالة تجزئة بسيطة، حيث يُزاح عددٌ صحيحٌ غير مُوَقَّع، قيمته الابتدائية صفر، إلى اليسار بتًّا واحدًا بشكلٍ متكرر، ثم يُجرى عليه عملية XOR مع قيمة العدد الصحيح للحرف التالي. بعد ذلك، تُؤخذ قيمة التجزئة هذه بتردد حجم الجدول. ^{[ 20 ]} إذا لم تكن الإزاحة إلى اليسار دائرية، فيجب أن يكون طول النص أقل بثمانية بتات على الأقل من حجم العدد الصحيح غير المُوَقَّع بالبتات. هناك طريقة شائعة أخرى لتجزئة نصٍّ إلى عدد صحيح، وهي استخدام دالة تجزئة متعددة الحدود .

اختيار دالة التجزئة

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

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

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

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

حل التصادم

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

التسلسل المنفصل

في عملية الربط المنفصل، تتضمن العملية إنشاء قائمة مرتبطة تحتوي على أزواج مفتاح-قيمة لكل فهرس في مصفوفة البحث. يتم ربط العناصر المتضاربة معًا من خلال قائمة مرتبطة واحدة، والتي يمكن اجتيازها للوصول إلى العنصر ذي مفتاح البحث الفريد. ^{[ 7 ]}^{: 464} يُعد حل التضارب من خلال الربط باستخدام قائمة مرتبطة طريقة شائعة لتنفيذ جداول التجزئة. $T$ و $x$ إذا كان جدول التجزئة والعقدة على التوالي، فإن العملية تتضمن ما يلي: ^{[ 19 ]}^{: 258}

Chained-Hash-Insert( T , k ) إدراج x في رأس القائمة المرتبطة T [ h ( k )] Chained-Hash-Search( T , k ) البحث عن عنصر بمفتاح k في القائمة المرتبطة T [ h ( k )] Chained-Hash-Delete( T , k ) حذف x من القائمة المرتبطة T [ h ( k )]

إذا كان العنصر قابلاً للمقارنة عدديًا أو معجميًا ، وتم إدراجه في القائمة مع الحفاظ على الترتيب الكلي ، فإن ذلك يؤدي إلى إنهاء أسرع لعمليات البحث غير الناجحة. ^{[ 4 ]}^{: 520-521}

هياكل بيانات أخرى للتسلسل المنفصل

إذا كانت المفاتيح مرتبة ، فقد يكون من الفعال استخدام مفاهيم " التنظيم الذاتي " مثل استخدام شجرة بحث ثنائية متوازنة ذاتيًا ، والتي من خلالها يمكن تقليل أسوأ حالة نظرية إلى $O(\log {n})$ على الرغم من أنها تُضيف تعقيدات إضافية. ^{[ 4 ]}^{: 521}

في التجزئة المثالية الديناميكية ، تُستخدم جداول التجزئة ثنائية المستوى لتقليل تعقيد البحث لضمان الحصول على نتيجة مثالية. $O(1)$ في أسوأ الأحوال. في هذه التقنية، دلاء من $k$ يتم تنظيم المدخلات على شكل جداول تجزئة مثالية مع $k^{2}$ توفر الفتحات وقت بحث ثابتًا في أسوأ الحالات، ووقتًا منخفضًا للإدراج. ^{[ 25 ]} تُظهر دراسة أن التسلسل المنفصل القائم على المصفوفات أكثر كفاءة بنسبة 97% مقارنةً بطريقة القائمة المرتبطة القياسية تحت ضغط عالٍ. ^{[ 26 ]}^{: 99}

تؤدي تقنيات مثل استخدام شجرة الدمج لكل مجموعة إلى وقت ثابت لجميع العمليات باحتمالية عالية. ^{[ 27 ]}

التخزين المؤقت وموقع المرجع

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

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

العنونة المفتوحة

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

تتضمن تسلسلات المجسات المعروفة ما يلي:

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

قد يكون أداء العنونة المفتوحة أبطأ مقارنةً بالتسلسل المنفصل، حيث يزداد تسلسل الفحص مع زيادة عامل التحميل. $\alpha$ يقترب من 1. ^{[ 13 ]}^{[ 26 ]}^{: 93} ينتج عن عملية البحث حلقة لا نهائية إذا وصل عامل التحميل إلى 1، في حالة جدول ممتلئ تمامًا. ^{[ 7 ]}^{: 471} يعتمد متوسط تكلفة البحث الخطي على قدرة دالة التجزئة على توزيع العناصر بشكل متساوٍ في جميع أنحاء الجدول لتجنب التكرارات ، حيث أن تكوين التكرارات سيؤدي إلى زيادة وقت البحث. ^{[ 7 ]}^{: 472}

التخزين المؤقت وموقع المرجع

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

تقنيات أخرى لحل التصادم تعتمد على العنونة المفتوحة

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

التجزئة المدمجة هي مزيج من التجزئة المتسلسلة المنفصلة والعنونة المفتوحة، حيث ترتبط الحاويات أو العقد داخل الجدول. ^{[ 34 ]}^{: 6-8.} تُعد هذه الخوارزمية مثالية لتخصيص الذاكرة الثابت . ^{[ 34 ]}^{: 4.} يتم حل التصادم في التجزئة المدمجة بتحديد أكبر خانة فارغة مُفهرسة في جدول التجزئة، ثم يتم إدخال القيمة المتصادمة في تلك الخانة. كما ترتبط الحاوية بخانة العقدة المُدخلة التي تحتوي على عنوان التجزئة المتصادم الخاص بها. ^{[ 34 ]}^{: 8}

هرس الوقواق

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

لعبة الهاش في لعبة الحجلة

خوارزمية التجزئة بالقفز هي خوارزمية تعتمد على العنونة المفتوحة، وتجمع بين عناصر خوارزمية التجزئة بالوقواق ، والاستكشاف الخطي ، والتسلسل من خلال مفهوم جوار الحاويات - الحاويات المتتالية المحيطة بأي حاوية مشغولة، والتي تُسمى أيضًا حاوية "افتراضية". ^{[ 36 ]}^{: 351-352.} صُممت هذه الخوارزمية لتقديم أداء أفضل عندما يتجاوز عامل تحميل جدول التجزئة 90%؛ كما أنها توفر إنتاجية عالية في الإعدادات المتزامنة ، مما يجعلها مناسبة تمامًا لتنفيذ جداول التجزئة المتزامنة القابلة لتغيير الحجم . ^{[ 36 ]}^{: 350.} تضمن خاصية الجوار في خوارزمية التجزئة بالقفز أن تكلفة العثور على العنصر المطلوب من أي حاوية معينة داخل الجوار قريبة جدًا من تكلفة العثور عليه في الحاوية نفسها؛ إذ تحاول الخوارزمية وضع عنصر في جواره - مع احتمال وجود تكلفة ناتجة عن إزاحة عناصر أخرى. ^{[ 36 ]}^{: 352}

تتضمن كل خانة داخل جدول التجزئة "معلومات القفزة" الإضافية - وهي عبارة عن مصفوفة بتات مكونة من H بت للإشارة إلى المسافة النسبية للعنصر الذي تم تجزئته في الأصل إلى الخانة الافتراضية الحالية ضمن H − 1 مدخل. ^[³⁶^]^:³⁵² ليكن $k$ و $Bk$ ليكن المفتاح المراد إدخاله والحاوية التي يتم تجزئة المفتاح إليها على التوالي؛ تتضمن عملية الإدخال عدة حالات بحيث يتم التعهد بخاصية الجوار للخوارزمية: ^{[ 36 ]}^{: 352-353} إذا $Bk$ إذا كانت الخانة فارغة، يُدرج العنصر، وتُضبط البتة اليسرى من خريطة البتات على 1؛ أما إذا لم تكن فارغة، فيُستخدم البحث الخطي للعثور على خانة فارغة في الجدول، ثم تُحدَّث خريطة بتات الخانة، ويُدرج العنصر؛ وإذا لم تكن الخانة الفارغة ضمن نطاق الجوار ، أي H − 1، تُجرى عمليات تبديل ومعالجة لاحقة لمصفوفة بتات معلومات القفزة لكل خانة وفقًا لخصائصها الثابتة في الجوار . ^{[ 36 ]}^{: 353}

تجزئة روبن هود

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

على الرغم من أن تجزئة روبن هود لا تُغير تكلفة البحث النظرية ، إلا أنها تؤثر بشكل كبير على تباين توزيع العناصر في المجموعات، ^[³⁸^]^:² أي أنها تتعامل مع التكوين طويل المدى في جدول التجزئة. ^[³⁹^] يجب إضافة قيمة PSL إضافية إلى كل عقدة داخل جدول التجزئة التي تستخدم تجزئة روبن هود. ^[⁴⁰^] ليكن $x$ كن المفتاح المراد إدخاله، $x{.}{\text{psl}}$ ليكن طول PSL (التزايدي) لـ $x$ ، $T$ كن جدول التجزئة و $j$ إذا كان المؤشر هو ، فإن إجراء الإدخال يكون كما يلي: ^{[ 37 ]}^{: 12-13}^{[ 41 ]}^{: 5}

لو $x{.}{\text{psl}}\ \leq \ T[j]{.}{\text{psl}}$ : تنتقل عملية التكرار إلى المجموعة التالية دون محاولة إجراء فحص خارجي.
لو $x{.}{\text{psl}}\ >\ T[j]{.}{\text{psl}}$ أدخل العنصر $x$ في الدلو $j$ ؛ تبديل $x$ مع $T[j]$ فليكن $x'$ واصل التحقيق من $(j+1)$ الدلو المراد إدخاله $x'$ كرر الإجراء حتى يتم إدخال كل عنصر.

تغيير الحجم الديناميكي

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

تغيير الحجم عن طريق نقل جميع الإدخالات

بشكل عام، يتم تخصيص جدول تجزئة جديد بحجم ضعف حجم جدول التجزئة الأصلي، ويتم نقل كل عنصر من جدول التجزئة الأصلي إلى الجدول الجديد المُخصص عن طريق حساب قيم التجزئة للعناصر متبوعة بعملية الإضافة. إعادة التجزئة عملية بسيطة، ولكنها مكلفة حسابيًا. ^{[ 44 ]}^{: 478-479}

بدائل لإعادة التدوير دفعة واحدة

لا تستطيع بعض تطبيقات جداول التجزئة، وخاصةً في الأنظمة الآنية ، تحمل تكلفة توسيع جدول التجزئة دفعةً واحدة، لأن ذلك قد يُقاطع العمليات الحساسة للوقت. إذا تعذر تجنب تغيير الحجم الديناميكي، فإن الحل يكمن في إجراء تغيير الحجم تدريجيًا لتجنب تقلبات التخزين - عادةً عند 50% من حجم الجدول الجديد - أثناء إعادة التجزئة، وتجنب تجزئة الذاكرة التي تُؤدي إلى ضغط الكومة نتيجةً لإلغاء تخصيص كتل ذاكرة كبيرة بسبب جدول التجزئة القديم. ^{[ 45 ]}^{: 2-3} في هذه الحالة، تتم عملية إعادة التجزئة تدريجيًا من خلال توسيع كتلة الذاكرة المُخصصة مسبقًا لجدول التجزئة القديم بحيث تبقى خانات جدول التجزئة دون تغيير. يتضمن أحد الأساليب الشائعة لإعادة التجزئة المُستهلكة الاحتفاظ بدالتي تجزئة. $h_{\text{old}}$ و $h_{\text{new}}$ تُعرف عملية إعادة تجزئة عناصر الحاوية وفقًا لدالة التجزئة الجديدة باسم التنظيف ، ويتم تنفيذها من خلال نمط الأوامر عن طريق تغليف العمليات مثل $\mathrm {إضافة} (\mathrm {key} )$ ، $\mathrm {Get} (\mathrm {key} )$ و $\mathrm {حذف} (\mathrm {key} )$ من خلال $\mathrm {Lookup} (\mathrm {key} ,{\text{command}})$ غلاف بحيث يتم إعادة تجزئة كل عنصر في الحاوية، وتتضمن إجراءاته ما يلي: ^{[ 45 ]}^{: 3}

ينظف $\mathrm {Table} [h_{\text{old}}(\mathrm {key} )]$ دلو.
ينظف $\mathrm {Table} [h_{\text{new}}(\mathrm {key} )]$ دلو.
يتم تنفيذ الأمر .

التجزئة الخطية

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

أداء

يعتمد أداء جدول التجزئة على قدرة دالة التجزئة على توليد أرقام شبه عشوائية ( $\sigma$ ) للإدخالات في جدول التجزئة حيث $K$ ، $n$ و $h(x)$ يشير إلى المفتاح وعدد الحاويات ودالة التجزئة بحيث $\sigma \ =\ h(K)\ \%\ n$ إذا كانت دالة التجزئة تُنتج نفس $\sigma$ للمفاتيح المميزة ( $K_{1}\neq K_{2},\ h(K_{1})\ =\ h(K_{2})$ ينتج عن ذلك تصادم ، والذي يتم التعامل معه بطرق متنوعة. التعقيد الزمني الثابت ( $O(1)$ يُفترض في عملية جدول التجزئة أن دالة التجزئة لا تُولّد فهارس متضاربة؛ وبالتالي، فإن أداء جدول التجزئة يتناسب طرديًا مع قدرة دالة التجزئة المختارة على توزيع الفهارس. ^{[ 47 ]}^{: 1} ومع ذلك، فإن بناء دالة تجزئة كهذه غير عملي ، ولذلك، تعتمد التطبيقات على تقنيات حل التصادم الخاصة بكل حالة لتحقيق أداء أعلى. ^[⁴⁷^]^:²

يُحقق أفضل أداء في حالة توزيع دالة التجزئة لعناصر الكون بشكل منتظم، وسحب العناصر المخزنة في الجدول عشوائيًا من الكون. في هذه الحالة، في التجزئة المتسلسلة، يكون الوقت المتوقع للبحث الناجح هو ${\textstyle 1+{\frac {\alpha }{2}}+\Theta \left({\frac {1}{m}}\right)}$ والوقت المتوقع للبحث غير الناجح هو ${\textstyle e^{-\alpha }+\alpha +\Theta \left({\frac {1}{m}}\right)}$ [ ⁴⁸^]

التطبيقات

المصفوفات الترابطية

تُستخدم جداول التجزئة بشكل شائع لتنفيذ أنواع عديدة من الجداول الموجودة في الذاكرة. كما تُستخدم لتنفيذ المصفوفات الترابطية . ^{[ 33 ]}

فهرسة قواعد البيانات

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

مخابئ

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

مجموعات

يمكن استخدام جداول التجزئة في تنفيذ بنية بيانات المجموعة ، التي يمكنها تخزين قيم فريدة دون أي ترتيب معين؛ تُستخدم المجموعة عادةً في اختبار انتماء قيمة ما إلى المجموعة، بدلاً من استرجاع العناصر. ^{[ 52 ]}

جدول التبديل

جدول نقل إلى جدول تجزئة معقد يخزن معلومات حول كل قسم تم البحث فيه. ^{[ 53 ]}

التطبيقات

توفر العديد من لغات البرمجة وظائف جداول التجزئة، إما كمصفوفات ترابطية مدمجة أو كوحدات مكتبة قياسية .

في لغة جافا سكريبت ، يُعرَّف "الكائن" بأنه مجموعة قابلة للتغيير من أزواج المفاتيح والقيم (تُسمى "الخصائص")، حيث يكون كل مفتاح إما سلسلة نصية أو رمزًا فريدًا مضمونًا؛ وأي قيمة أخرى، عند استخدامها كمفتاح، تُحوَّل أولًا إلى سلسلة نصية. وباستثناء أنواع البيانات "الأولية" السبعة، فإن كل قيمة في جافا سكريبت هي كائن. ^{[ 54 ]} كما أضافت ECMAScript 2015 Mapبنية البيانات التي تقبل قيمًا عشوائية كمفاتيح. ^{[ 55 ]}
تتضمن مكتبة C++11unordered_map القياسية أدوات لتخزين المفاتيح والقيم من أنواع عشوائية . ^{[ 56 ]}
تُنفذ الدالة المدمجة في لغة Gomap نوع الخريطة على شكل نوع ، والذي غالبًا ما يكون (ولكن ليس مضمونًا) جدول تجزئة. ^{[ 57 ]}
تتضمن لغة برمجة جافاHashSet المجموعات العامة ، والمجموعات الفرعية HashMap، والمجموعات الفرعية LinkedHashSet، والمجموعات LinkedHashMapالفرعية . ^{[ 58 ]}
تُنفذ الدالة المدمجة في بايثونdict جدول التجزئة على شكل نوع . ^{[ 59 ]}
تستخدم لغة روبي المدمجة Hashنموذج العنونة المفتوحة بدءًا من الإصدار 2.4 من روبي. ^{[ 60 ]}
تتضمن لغة البرمجة RustHashMap ، HashSetكجزء من مكتبة Rust القياسية. ^{[ 61 ]}
تتضمن مكتبة .NET القياسية و ،HashSet [ Dictionary62 ^{] [ 63}^{] لذا يمكن} استخدامها من لغات مثل C# و VB.NET . ^{[ 64 ]}

انظر أيضاً

ملحوظات

↑ توجد طرق ذات تعقيد زمني متوقع في أسوأ الحالاتيبلغ O(log² (1 - α )⁻¹ ) حيث α هو عامل التحميل.^[¹^]

مراجع

↑ مارتن فاراش-كولتون؛ أندرو كرابيفين؛ ويليام كوزماول. الحدود المثلى للعنونة المفتوحة بدون إعادة ترتيب . المؤتمر السنوي الخامس والستون لمؤسسة مهندسي الكهرباء والإلكترونيات (IEEE) حول أسس علوم الحاسوب (FOCS) لعام 2024. arXiv : 2501.02305 . doi : 10.1109/FOCS61266.2024.00045 .
1 2 كورمن، توماس هـ .؛ ليسرسون، تشارلز إي .؛ ريفست، رونالد ل .؛ شتاين، كليفورد (2009). مقدمة في الخوارزميات ( الطبعة الثالثة). معهد ماساتشوستس للتكنولوجيا. الصفحات 253-280 . ISBN 978-0-262-03384-8.
↑ ميلهورن، كورت ؛ ساندرز، بيتر (2008). "جداول التجزئة والمصفوفات الترابطية" (ملف PDF) . الخوارزميات وهياكل البيانات . سبرينغر. ص 81-98 . doi : 10.1007/978-3-540-77978-0_4 . ISBN 978-3-540-77977-3.
1 2 3 4 5 6 7 كنوت، دونالد إي. (24 أبريل 1998). فن برمجة الحاسوب: المجلد 3: الفرز والبحث ( الطبعة الثانية). أديسون-ويسلي بروفيشنال . ISBN 978-0-201-89685-5.
↑ ليسرسون، تشارلز إي. (خريف 2005). "المحاضرة 13: الخوارزميات المُستهلكة، مضاعفة الجدول، طريقة الجهد" . مقرر MIT 6.046J/18.410J مقدمة في الخوارزميات . مؤرشف من الأصل في 7 أغسطس 2009.
↑ كورمن، توماس هـ .؛ ليسرسون، تشارلز إي .؛ ريفست، رونالد ل .؛ شتاين، كليفورد (2001). "الفصل 11: جداول التجزئة". مقدمة في الخوارزميات ( الطبعة الثانية). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. الصفحات 221-252 . ISBN 978-0-262-53196-2.
1 2 3 4 5 سيدجويك، روبرت ؛ واين، كيفن (2011). الخوارزميات . المجلد 1 ( الطبعة الرابعة). أديسون-ويسلي بروفيشنال - عبر جامعة برينستون ، قسم علوم الحاسوب.
↑ سيلبرشاتز، أ.؛ كورث، هـ.ف.؛ سودارشان، س. (2020). مفاهيم نظام قواعد البيانات ( الطبعة السابعة). ماكجرو هيل .
↑ جودريتش، إم تي؛ تاماسيا، آر؛ جولدواسير، إم إتش (2014). هياكل البيانات والخوارزميات في جافا ( الطبعة السادسة). وايلي .
1 2 3 كونهايم، آلان ج. (2010). التجزئة في علوم الحاسوب . doi : 10.1002/9780470630617 . ISBN 978-0-470-34473-6.
1 2 3 4 5 6 7 8 9 10 11 12 ميهتا، دينش ب.؛ ميهتا، دينش ب.؛ ساهني، سرتاج، محرران. (2004). دليل هياكل البيانات وتطبيقاتها . doi : 10.1201/9781420035179 . ISBN 978-0-429-14701-2.
↑ كورمين، ث؛ ليسرسون، CE؛ الأماكن القريبة : شتاين، سي. (2009). مقدمة للخوارزميات ( الطبعة الثالثة). مطبعة معهد ماساتشوستس للتكنولوجيا .
1 2 3 4 5 6 7 مايرز، أندرو (2008). "CS 312: جداول التجزئة والتحليل المُستهلك" . جامعة كورنيل ، قسم علوم الحاسوب. مؤرشف من الأصل في 26 أبريل 2021. تم الاسترجاع في 26 أكتوبر 2021 - عبر cs.cornell.edu.
1 2 جيمس إس. بلانك وبراد فاندر زاندن. "ملاحظات محاضرة CS140 - التجزئة" .
↑ ماورر، دبليو دي؛ لويس، تي جي (مارس 1975). "طرق جداول التجزئة". مجلة ACM Computing Surveys . 7 (1): 5–19 . doi : 10.1145/356643.356645 . S2CID 17874775 .
1 2 أوولابي، أولوميد (فبراير 2003). "دراسات تجريبية لبعض دوال التجزئة". تكنولوجيا المعلومات والبرمجيات . 45 (2): 109-112 . doi : 10.1016/S0950-5849(02)00174-X .
1 2 لو، يي؛ برابهاكار، بالاجي؛ بونومي، فلافيو (2006). التجزئة المثالية لتطبيقات الشبكات . ندوة IEEE الدولية لنظرية المعلومات لعام 2006. الصفحات 2774-2778 . doi : 10.1109/ISIT.2006.261567 . ISBN 1-4244-0505-X. S2CID 1494710 .
↑ بلازوقي، جمال؛ بوتيلو، فابيانو سي؛ ديتزفيلبينجر، مارتن (2009). "التجزئة، والإزاحة، والضغط" (ملف PDF) . وقائع الندوة الأوروبية السنوية السابعة عشرة للخوارزميات - ESA 2009، كوبنهاغن، الدنمارك، 7-9 سبتمبر 2009. سلسلة محاضرات في علوم الحاسوب . المجلد 5757. برلين: سبرينغر. الصفحات 682-693 . CiteSeerX 10.1.1.568.130 . doi : 10.1007/978-3-642-04128-0_61 . MR 2557794 .
1 2 كورمن، توماس هـ .؛ ليسرسون، تشارلز إي .؛ ريفست، رونالد ل .؛ شتاين، كليفورد (2001). "الفصل 11: جداول التجزئة". مقدمة في الخوارزميات ( الطبعة الثانية). معهد ماساتشوستس للتكنولوجيا . ISBN 978-0-262-53196-2.
↑ ستروستروب، بيارن (1997). لغة البرمجة سي++، الطبعة الثالثة . ريدينغ، ماساتشوستس: أديسون-ويسلي. ص 503. ISBN 0-201-88954-4.
↑ بيرسون، كارل (1900). "حول معيار أن نظامًا معينًا من الانحرافات عن الاحتمال في حالة نظام متغيرات مترابطة يكون من الممكن افتراض أنه نشأ بشكل معقول عن أخذ عينات عشوائية" . المجلة الفلسفية . السلسلة 5. 50 (302): 157-175 . doi : 10.1080/14786440009463897 .
↑ بلاكيت، روبن (1983). "كارل بيرسون واختبار مربع كاي". المجلة الإحصائية الدولية . 51 (1): 59-72 . doi : 10.2307/1402731 . JSTOR 1402731 .
1 2 وانغ، توماس (مارس 1997). "جدول التجزئة المزدوج الأولي" . مؤرشف من الأصل في 3 سبتمبر 1999. تم الاسترجاع في 10 مايو 2015 .
↑ ويغمان، مارك ن.؛ كارتر، ج. لورانس (يونيو 1981). "دوال التجزئة الجديدة واستخدامها في المصادقة ومساواة المجموعات" . مجلة علوم الحاسوب والأنظمة . 22 (3): 265-279 . Bibcode : 1981JCoSS..22..265W . doi : 10.1016/0022-0000(81)90033-7 .
↑ ديمين، إريك؛ ليند، جيف (ربيع 2003). "المحاضرة 2" (ملف PDF) . 6.897: هياكل البيانات المتقدمة. مختبر علوم الحاسوب والذكاء الاصطناعي بمعهد ماساتشوستس للتكنولوجيا . مؤرشف (ملف PDF) من الأصل في 15 يونيو 2010. تم الاطلاع عليه في 30 يونيو 2008 .
1 2 3 كولبيبر، ج. شين؛ موفات، أليستير (2005). "رموز البايت المحسّنة ذات خصائص البادئة المقيدة". معالجة السلاسل واسترجاع المعلومات . سلسلة محاضرات في علوم الحاسوب. المجلد 3772. الصفحات 1-12 . doi : 10.1007/11575832_1 . ISBN 978-3-540-29740-6.
↑ ويلارد، دان إي. (2000). "دراسة الهندسة الحسابية، وأشجار فان إمده بواس، والتجزئة من منظور شجرة الاندماج". مجلة SIAM للحوسبة . 29 (3): 1030-1049 . doi : 10.1137/S0097539797322425 . MR 1740562 . .
↑ أسكيتيس، نيكولاس؛ سينها، رانجان (أكتوبر 2010). "هندسة سلاسل نصية قابلة للتوسع، ذات ذاكرة تخزين مؤقتة فعالة، وذات مساحة تخزين مناسبة". مجلة VLDB . 19 (5): 633-660 . doi : 10.1007/s00778-010-0183-9 .
↑ أسكيتيس، نيكولاس؛ زوبيل، جاستن (أكتوبر 2005). "حل التصادمات مع مراعاة ذاكرة التخزين المؤقت في جداول تجزئة السلاسل النصية". وقائع المؤتمر الدولي الثاني عشر، معالجة السلاسل النصية واسترجاع المعلومات (SPIRE 2005) . المجلد 3772/2005. الصفحات 91-102 . doi : 10.1007/11575832_11 . ISBN 978-3-540-29740-6.
↑ أسكيتيس، نيكولاس (2009). "جداول تجزئة سريعة ومضغوطة لمفاتيح الأعداد الصحيحة" (ملف PDF) . وقائع المؤتمر الأسترالي الآسيوي الثاني والثلاثين لعلوم الحاسوب (ACSC 2009) . المجلد 91. الصفحات 113-122 . ISBN 978-1-920682-72-9تمت أرشفة هذا الملف من النسخة الأصلية (PDF) بتاريخ 16 فبراير 2011. تم الاطلاع عليه بتاريخ 13 يونيو 2010 .
^ تينينباوم، آرون م. لانجسام، اليديدية؛ أوجنشتاين، موشيه ج. (1990). هياكل البيانات باستخدام C . برنتيس هول. ص 456 – 461، ص. 472. ردمك 978-0-13-199746-2.
1 2 باغ, راسموس ; رودلر، فليمنج فريش (2001). "تجزئة الوقواق". الخوارزميات – وكالة الفضاء الأوروبية 2001 . ملاحظات محاضرة في علوم الكمبيوتر. المجلد. 2161. ص 121 – 133. CiteSeerX 10.1.1.25.4189 . دوى : 10.1007/3-540-44676-1_10 . رقم ISBN 978-3-540-42493-2.
1 2 3 كورمن، توماس هـ .؛ ليسرسون، تشارلز إي .؛ ريفست، رونالد ل .؛ شتاين، كليفورد (2001)، "11 جدول تجزئة"، مقدمة في الخوارزميات ( الطبعة الثانية)، مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل ، الصفحات 221-252 ، ISBN 0-262-03293-7.
1 2 3 فيتر، جيفري س.؛ تشين، وين-تشين (1987). تصميم وتحليل التجزئة المدمجة . نيويورك، الولايات المتحدة: مطبعة جامعة أكسفورد . ISBN 978-0-19-504182-8– عبر موقع Archive.org .
^ باغ، راسموس ؛ رودلر، فليمنج فريش (2001). "تجزئة الوقواق". الخوارزميات – وكالة الفضاء الأوروبية 2001 . ملاحظات محاضرة في علوم الكمبيوتر. المجلد. 2161. ص 121 – 133. CiteSeerX 10.1.1.25.4189 . دوى : 10.1007/3-540-44676-1_10 . رقم ISBN 978-3-540-42493-2.
1 2 3 4 5 6 هيرليهي، موريس؛ شافيت، نير؛ تزافرير، موران (2008). "تجزئة هوبسكوتش". الحوسبة الموزعة . سلسلة محاضرات في علوم الحاسوب. المجلد 5218. الصفحات 350-364 . doi : 10.1007/978-3-540-87779-0_24 . ISBN 978-3-540-87778-3.
1 2 سيليس، بيدرو (1986). روبن هود هاشينغ (PDF) . أونتاريو، كندا: جامعة واترلو ، قسم علوم الكمبيوتر. رقم ISBN 978-0-315-29700-5OCLC 14083698. مؤرشف (PDF) من الأصل في 1 نوفمبر 2021. تم الاطلاع عليه في 2 نوفمبر 2021 .
↑ بوبليت، ب. ف.؛ فيولا، أ. (يوليو 2019). "تحليل خوارزمية روبن هود وغيرها من خوارزميات التجزئة في ظل نموذج الاستكشاف العشوائي، مع الحذف وبدونه" . التوافقية، الاحتمالات والحوسبة . 28 (4): 600-617 . doi : 10.1017/S0963548318000408 . S2CID 125374363 .
↑ كلاركسون، مايكل (2014). "المحاضرة 13: جداول التجزئة" . جامعة كورنيل ، قسم علوم الحاسوب. مؤرشف من الأصل في 7 أكتوبر 2021. تم الاطلاع عليه في 1 نوفمبر 2021 – عبر cs.cornell.edu.
↑ غريس، ديفيد (2017). "جافا هايبر تيكس وبنية البيانات: تجزئة روبن هود" (ملف PDF) . جامعة كورنيل ، قسم علوم الحاسوب. مؤرشف (ملف PDF) من الأصل في 26 أبريل 2021. تم الاطلاع عليه في 2 نوفمبر 2021 – عبر cs.cornell.edu.
↑ سيليس، بيدرو (28 مارس 1988). تجزئة روبن هود الخارجية (ملف PDF) (تقرير فني). بلومنجتون، إنديانا: جامعة إنديانا ، قسم علوم الحاسوب. 246. مؤرشف (ملف PDF) من الأصل في 3 نوفمبر 2021. تم الاطلاع عليه في 2 نوفمبر 2021 .
↑ غودارد، واين (2021). "الفصل ج5: جداول التجزئة" (ملف PDF) . جامعة كليمسون . الصفحات 15-16 . تم الاطلاع عليه في 4 ديسمبر 2023 .
↑ ديفاداس، سريني؛ ديمين، إريك (25 فبراير 2011). "مقدمة في الخوارزميات: تغيير حجم جداول التجزئة" (ملف PDF) . معهد ماساتشوستس للتكنولوجيا ، قسم علوم الحاسوب. مؤرشف (ملف PDF) من الأصل في 7 مايو 2021. تم الاطلاع عليه في 9 نوفمبر 2021 - عبر MIT OpenCourseWare .
↑ ثاريجا، ريما (2014). "التجزئة والتصادم". هياكل البيانات باستخدام لغة C. مطبعة جامعة أكسفورد. ص 464-488 . ISBN 978-0-19-809930-7.
1 2 فريدمان، سكوت؛ كريشنان، أناند؛ ليدفروست، نيكولاس (18 مارس 2003). "جداول التجزئة للأنظمة المدمجة والأنظمة الآنية" (ملف PDF) . جميع أبحاث علوم وهندسة الحاسوب . جامعة واشنطن في سانت لويس . doi : 10.7936/K7WD3XXV . مؤرشف (ملف PDF) من الأصل في 9 يونيو 2021. تم الاسترجاع في 9 نوفمبر 2021 - عبر جامعة نورث وسترن ، قسم علوم الحاسوب.
↑ ليتوين، ويتولد (1980). "التجزئة الخطية: أداة جديدة لمعالجة الملفات والجداول" (ملف PDF) . وقائع المؤتمر السادس حول قواعد البيانات الضخمة جدًا . جامعة كارنيجي ميلون . الصفحات 212-223 . مؤرشف (ملف PDF) من الأصل في 6 مايو 2021. تم الاطلاع عليه في 10 نوفمبر 2021 - عبر cs.cmu.edu.
1 2 دايك، توم فان (2010). "تحليل وتحسين أداء جداول التجزئة" (ملف PDF) . هولندا : جامعة توينتي . مؤرشف (ملف PDF) من الأصل في 6 نوفمبر 2021. تم الاطلاع عليه في 31 ديسمبر 2021 .
↑ بايزا-ياتس، ريكاردو؛ بوبليت، باتريسيو ف. (1999). "الفصل 2: البحث". في عطا الله (محرر). دليل الخوارزميات ونظرية الحوسبة . مطبعة سي آر سي. ص 2-6 . ISBN 0849326494.
^ ليخ باناشوفسكي. "الفهارس والفرز الخارجي" . pl:Polsko-Japońska Akademia Technik Komputerowych . مؤرشفة من الأصلي في 26 مارس 2022 . تم الاسترجاع في 26 مارس 2022 .
↑ تشونغ، ليانغ؛ تشنغ، شيوكيان؛ ليو، يونغ؛ وانغ، مينغتينغ؛ كاو، يانغ (فبراير 2020). "تعظيم نسبة نجاح الوصول إلى الذاكرة المؤقتة في اتصالات الأجهزة عبر شبكات الهاتف المحمول". اتصالات الصين . 17 (2): 232-238 . Bibcode : 2020CComm..17b.232Z . doi : 10.23919/jcc.2020.02.018 . S2CID 212649328 .
↑ بوتوملي، جيمس (1 يناير 2004). "فهم التخزين المؤقت" . مجلة لينكس . مؤرشف من الأصل في 4 ديسمبر 2020. تم الاطلاع عليه في 16 أبريل 2022 .
↑ جيل سيمان (2014). "المجموعات وجداول التجزئة" (ملف PDF) . جامعة ولاية تكساس . مؤرشف من الأصل في 1 أبريل 2022. تم الاطلاع عليه في 26 مارس 2022 .{{cite web}}: CS1 maint: bot: حالة عنوان URL الأصلي غير معروفة ( رابط )
↑ "جدول النقل - ويكي برمجة الشطرنج" . chessprogramming.org . مؤرشف من الأصل في 14 فبراير 2021. تم الاطلاع عليه في 1 مايو 2020 .
↑ "أنواع البيانات وهياكل البيانات في جافا سكريبت - جافا سكريبت | MDN" . developer.mozilla.org . تم الاطلاع عليه بتاريخ 24 يوليو 2022 .
↑ "خريطة - جافا سكريبت | MDN" . developer.mozilla.org . 20 يونيو 2023. تم الاطلاع عليه في 15 يوليو 2023 .
↑ "لغة البرمجة C++ - المواصفات الفنية" (ملف PDF) . المنظمة الدولية للمعايير . الصفحات 812-813 . مؤرشف من الأصل (ملف PDF) بتاريخ 21 يناير 2022. تم الاطلاع عليه بتاريخ 8 فبراير 2022 .
↑ "مواصفات لغة البرمجة Go" . go.dev . تم الاطلاع عليه في 1 يناير 2023 .
↑ "الدرس: التطبيقات (دروس Java™ > المجموعات)" . docs.oracle.com . مؤرشف من الأصل في 18 يناير 2017. تم الاطلاع عليه في 27 أبريل 2018 .
↑ تشانغ، خوان؛ جيا، يونوي (2020). "تحسين إعادة التجزئة في Redis باستخدام التعلم الآلي" . مجلة الفيزياء: سلسلة المؤتمرات . 1453 (1): 3. Bibcode : 2020JPhCS1453a2048Z . doi : 10.1088/1742-6596/1453/1/012048 . S2CID 215943738 .
↑ جونان شيفلر (25 ديسمبر 2016). "إصدار روبي 2.4: تجزئات أسرع، وأعداد صحيحة موحدة، وتقريب أفضل" . heroku.com . مؤرشف من الأصل في 3 يوليو 2019. تم الاطلاع عليه في 3 يوليو 2019 .
↑ "doc.rust-lang.org" . مؤرشف من الأصل في 8 ديسمبر 2022. تم الاطلاع عليه في 14 ديسمبر 2022 .
↑ "فئة HashSet (System.Collections.Generic)" . learn.microsoft.com . تم الاطلاع عليه في 1 يوليو 2023 .
↑ dotnet-bot. "فئة القاموس (System.Collections.Generic)" . learn.microsoft.com . تم الاطلاع عليه في 16 يناير 2024 .
↑ "مثال على HashSet في VB.NET" . دوت نت بيرلز .

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

تاماسيا، روبرتو؛ جودريتش، مايكل ت. (2006). "الفصل التاسع: الخرائط والقواميس". هياكل البيانات والخوارزميات في جافا : [ مُحدَّث لجافا 5.0 ] ( الطبعة الرابعة). هوبوكين، نيوجيرسي: وايلي. الصفحات 369-418 . ISBN 978-0-471-73884-8.
ماكنزي، بي جيه؛ هاريس، آر؛ بيل، تي. (فبراير 1990). "اختيار خوارزمية التجزئة". البرمجيات: الممارسة والخبرة . 20 (2): 209-224 . doi : 10.1002/spe.4380200207 . hdl : 10092/9691 . S2CID 12854386 .

روابط خارجية

مدخل المعهد الوطني للمعايير والتكنولوجيا (NIST) حول جداول التجزئة
هياكل البيانات المفتوحة - الفصل 5 - جداول التجزئة ، بات مورين
مقدمة معهد ماساتشوستس للتكنولوجيا في الخوارزميات: التجزئة 1 - فيديو محاضرة MIT OCW
مقدمة معهد ماساتشوستس للتكنولوجيا في الخوارزميات: التجزئة 2 - فيديو محاضرة معهد ماساتشوستس للتكنولوجيا المفتوحة

[2] توجد طرق ذات تعقيد زمني متوقع في أسوأ الحالاتيبلغ O(log² (1 - α )⁻¹ ) حيث α هو عامل التحميل.^[¹^]

[Farach-Colton_2024-1] مارتن فاراش-كولتون؛ أندرو كرابيفين؛ ويليام كوزماول. الحدود المثلى للعنونة المفتوحة بدون إعادة ترتيب . المؤتمر السنوي الخامس والستون لمؤسسة مهندسي الكهرباء والإلكترونيات (IEEE) حول أسس علوم الحاسوب (FOCS) لعام 2024. arXiv : 2501.02305 . doi : 10.1109/FOCS61266.2024.00045 .

[Cormen_et_al-3] 1 2 كورمن، توماس هـ .؛ ليسرسون، تشارلز إي .؛ ريفست، رونالد ل .؛ شتاين، كليفورد (2009). مقدمة في الخوارزميات ( الطبعة الثالثة). معهد ماساتشوستس للتكنولوجيا. الصفحات 253-280 . ISBN 978-0-262-03384-8.

[ms-4] ميلهورن، كورت ؛ ساندرز، بيتر (2008). "جداول التجزئة والمصفوفات الترابطية" (ملف PDF) . الخوارزميات وهياكل البيانات . سبرينغر. ص 81-98 . doi : 10.1007/978-3-540-77978-0_4 . ISBN 978-3-540-77977-3.

[knuth-5] 1 2 3 4 5 6 7 كنوت، دونالد إي. (24 أبريل 1998). فن برمجة الحاسوب: المجلد 3: الفرز والبحث ( الطبعة الثانية). أديسون-ويسلي بروفيشنال . ISBN 978-0-201-89685-5.

[leiser-6] ليسرسون، تشارلز إي. (خريف 2005). "المحاضرة 13: الخوارزميات المُستهلكة، مضاعفة الجدول، طريقة الجهد" . مقرر MIT 6.046J/18.410J مقدمة في الخوارزميات . مؤرشف من الأصل في 7 أغسطس 2009.

[cormen-7] كورمن، توماس هـ .؛ ليسرسون، تشارلز إي .؛ ريفست، رونالد ل .؛ شتاين، كليفورد (2001). "الفصل 11: جداول التجزئة". مقدمة في الخوارزميات ( الطبعة الثانية). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. الصفحات 221-252 . ISBN 978-0-262-53196-2.

[algo1rob-8] 1 2 3 4 5 سيدجويك، روبرت ؛ واين، كيفن (2011). الخوارزميات . المجلد 1 ( الطبعة الرابعة). أديسون-ويسلي بروفيشنال - عبر جامعة برينستون ، قسم علوم الحاسوب.

[9] سيلبرشاتز، أ.؛ كورث، هـ.ف.؛ سودارشان، س. (2020). مفاهيم نظام قواعد البيانات ( الطبعة السابعة). ماكجرو هيل .

[10] جودريتش، إم تي؛ تاماسيا، آر؛ جولدواسير، إم إتش (2014). هياكل البيانات والخوارزميات في جافا ( الطبعة السادسة). وايلي .

[Konheim-11] 1 2 3 كونهايم، آلان ج. (2010). التجزئة في علوم الحاسوب . doi : 10.1002/9780470630617 . ISBN 978-0-470-34473-6.

[hashhist-12] 1 2 3 4 5 6 7 8 9 10 11 12 ميهتا، دينش ب.؛ ميهتا، دينش ب.؛ ساهني، سرتاج، محرران. (2004). دليل هياكل البيانات وتطبيقاتها . doi : 10.1201/9781420035179 . ISBN 978-0-429-14701-2.

[13] كورمين، ث؛ ليسرسون، CE؛ الأماكن القريبة : شتاين، سي. (2009). مقدمة للخوارزميات ( الطبعة الثالثة). مطبعة معهد ماساتشوستس للتكنولوجيا .

[cornell08-14] 1 2 3 4 5 6 7 مايرز، أندرو (2008). "CS 312: جداول التجزئة والتحليل المُستهلك" . جامعة كورنيل ، قسم علوم الحاسوب. مؤرشف من الأصل في 26 أبريل 2021. تم الاسترجاع في 26 أكتوبر 2021 - عبر cs.cornell.edu.

[plank-15] 1 2 جيمس إس. بلانك وبراد فاندر زاندن. "ملاحظات محاضرة CS140 - التجزئة" .

[16] ماورر، دبليو دي؛ لويس، تي جي (مارس 1975). "طرق جداول التجزئة". مجلة ACM Computing Surveys . 7 (1): 5–19 . doi : 10.1145/356643.356645 . S2CID 17874775 .

[owo03-17] 1 2 أوولابي، أولوميد (فبراير 2003). "دراسات تجريبية لبعض دوال التجزئة". تكنولوجيا المعلومات والبرمجيات . 45 (2): 109-112 . doi : 10.1016/S0950-5849(02)00174-X .

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

[CHD-19] بلازوقي، جمال؛ بوتيلو، فابيانو سي؛ ديتزفيلبينجر، مارتن (2009). "التجزئة، والإزاحة، والضغط" (ملف PDF) . وقائع الندوة الأوروبية السنوية السابعة عشرة للخوارزميات - ESA 2009، كوبنهاغن، الدنمارك، 7-9 سبتمبر 2009. سلسلة محاضرات في علوم الحاسوب . المجلد 5757. برلين: سبرينغر. الصفحات 682-693 . CiteSeerX 10.1.1.568.130 . doi : 10.1007/978-3-642-04128-0_61 . MR 2557794 .

[cormenalgo01-20] 1 2 كورمن، توماس هـ .؛ ليسرسون، تشارلز إي .؛ ريفست، رونالد ل .؛ شتاين، كليفورد (2001). "الفصل 11: جداول التجزئة". مقدمة في الخوارزميات ( الطبعة الثانية). معهد ماساتشوستس للتكنولوجيا . ISBN 978-0-262-53196-2.

[21] ستروستروب، بيارن (1997). لغة البرمجة سي++، الطبعة الثالثة . ريدينغ، ماساتشوستس: أديسون-ويسلي. ص 503. ISBN 0-201-88954-4.

[chernoff-22] بيرسون، كارل (1900). "حول معيار أن نظامًا معينًا من الانحرافات عن الاحتمال في حالة نظام متغيرات مترابطة يكون من الممكن افتراض أنه نشأ بشكل معقول عن أخذ عينات عشوائية" . المجلة الفلسفية . السلسلة 5. 50 (302): 157-175 . doi : 10.1080/14786440009463897 .

[plackett-23] بلاكيت، روبن (1983). "كارل بيرسون واختبار مربع كاي". المجلة الإحصائية الدولية . 51 (1): 59-72 . doi : 10.2307/1402731 . JSTOR 1402731 .

[:0-24] 1 2 وانغ، توماس (مارس 1997). "جدول التجزئة المزدوج الأولي" . مؤرشف من الأصل في 3 سبتمبر 1999. تم الاسترجاع في 10 مايو 2015 .

[25] ويغمان، مارك ن.؛ كارتر، ج. لورانس (يونيو 1981). "دوال التجزئة الجديدة واستخدامها في المصادقة ومساواة المجموعات" . مجلة علوم الحاسوب والأنظمة . 22 (3): 265-279 . Bibcode : 1981JCoSS..22..265W . doi : 10.1016/0022-0000(81)90033-7 .

[26] ديمين، إريك؛ ليند، جيف (ربيع 2003). "المحاضرة 2" (ملف PDF) . 6.897: هياكل البيانات المتقدمة. مختبر علوم الحاسوب والذكاء الاصطناعي بمعهد ماساتشوستس للتكنولوجيا . مؤرشف (ملف PDF) من الأصل في 15 يونيو 2010. تم الاطلاع عليه في 30 يونيو 2008 .

[nick05-27] 1 2 3 كولبيبر، ج. شين؛ موفات، أليستير (2005). "رموز البايت المحسّنة ذات خصائص البادئة المقيدة". معالجة السلاسل واسترجاع المعلومات . سلسلة محاضرات في علوم الحاسوب. المجلد 3772. الصفحات 1-12 . doi : 10.1007/11575832_1 . ISBN 978-3-540-29740-6.

[28] ويلارد، دان إي. (2000). "دراسة الهندسة الحسابية، وأشجار فان إمده بواس، والتجزئة من منظور شجرة الاندماج". مجلة SIAM للحوسبة . 29 (3): 1030-1049 . doi : 10.1137/S0097539797322425 . MR 1740562 . .

[29] أسكيتيس، نيكولاس؛ سينها، رانجان (أكتوبر 2010). "هندسة سلاسل نصية قابلة للتوسع، ذات ذاكرة تخزين مؤقتة فعالة، وذات مساحة تخزين مناسبة". مجلة VLDB . 19 (5): 633-660 . doi : 10.1007/s00778-010-0183-9 .

[30] أسكيتيس، نيكولاس؛ زوبيل، جاستن (أكتوبر 2005). "حل التصادمات مع مراعاة ذاكرة التخزين المؤقت في جداول تجزئة السلاسل النصية". وقائع المؤتمر الدولي الثاني عشر، معالجة السلاسل النصية واسترجاع المعلومات (SPIRE 2005) . المجلد 3772/2005. الصفحات 91-102 . doi : 10.1007/11575832_11 . ISBN 978-3-540-29740-6.

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

[tenenbaum90-32] تينينباوم، آرون م. لانجسام، اليديدية؛ أوجنشتاين، موشيه ج. (1990). هياكل البيانات باستخدام C . برنتيس هول. ص 456 – 461، ص. 472. ردمك 978-0-13-199746-2.

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

[clrs-34] 1 2 3 كورمن، توماس هـ .؛ ليسرسون، تشارلز إي .؛ ريفست، رونالد ل .؛ شتاين، كليفورد (2001)، "11 جدول تجزئة"، مقدمة في الخوارزميات ( الطبعة الثانية)، مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل ، الصفحات 221-252 ، ISBN 0-262-03293-7.

[chen87-35] 1 2 3 فيتر، جيفري س.؛ تشين، وين-تشين (1987). تصميم وتحليل التجزئة المدمجة . نيويورك، الولايات المتحدة: مطبعة جامعة أكسفورد . ISBN 978-0-19-504182-8– عبر موقع Archive.org .

[36] باغ، راسموس ؛ رودلر، فليمنج فريش (2001). "تجزئة الوقواق". الخوارزميات – وكالة الفضاء الأوروبية 2001 . ملاحظات محاضرة في علوم الكمبيوتر. المجلد. 2161. ص 121 – 133. CiteSeerX 10.1.1.25.4189 . دوى : 10.1007/3-540-44676-1_10 . رقم ISBN 978-3-540-42493-2.

[nir08-37] 1 2 3 4 5 6 هيرليهي، موريس؛ شافيت، نير؛ تزافرير، موران (2008). "تجزئة هوبسكوتش". الحوسبة الموزعة . سلسلة محاضرات في علوم الحاسوب. المجلد 5218. الصفحات 350-364 . doi : 10.1007/978-3-540-87779-0_24 . ISBN 978-3-540-87778-3.

[waterloo86-38] 1 2 سيليس، بيدرو (1986). روبن هود هاشينغ (PDF) . أونتاريو، كندا: جامعة واترلو ، قسم علوم الكمبيوتر. رقم ISBN 978-0-315-29700-5OCLC 14083698. مؤرشف (PDF) من الأصل في 1 نوفمبر 2021. تم الاطلاع عليه في 2 نوفمبر 2021 .

[39] بوبليت، ب. ف.؛ فيولا، أ. (يوليو 2019). "تحليل خوارزمية روبن هود وغيرها من خوارزميات التجزئة في ظل نموذج الاستكشاف العشوائي، مع الحذف وبدونه" . التوافقية، الاحتمالات والحوسبة . 28 (4): 600-617 . doi : 10.1017/S0963548318000408 . S2CID 125374363 .

[cornell14-40] كلاركسون، مايكل (2014). "المحاضرة 13: جداول التجزئة" . جامعة كورنيل ، قسم علوم الحاسوب. مؤرشف من الأصل في 7 أكتوبر 2021. تم الاطلاع عليه في 1 نوفمبر 2021 – عبر cs.cornell.edu.

[41] غريس، ديفيد (2017). "جافا هايبر تيكس وبنية البيانات: تجزئة روبن هود" (ملف PDF) . جامعة كورنيل ، قسم علوم الحاسوب. مؤرشف (ملف PDF) من الأصل في 26 أبريل 2021. تم الاطلاع عليه في 2 نوفمبر 2021 – عبر cs.cornell.edu.

[indiana88-42] سيليس، بيدرو (28 مارس 1988). تجزئة روبن هود الخارجية (ملف PDF) (تقرير فني). بلومنجتون، إنديانا: جامعة إنديانا ، قسم علوم الحاسوب. 246. مؤرشف (ملف PDF) من الأصل في 3 نوفمبر 2021. تم الاطلاع عليه في 2 نوفمبر 2021 .

[43] غودارد، واين (2021). "الفصل ج5: جداول التجزئة" (ملف PDF) . جامعة كليمسون . الصفحات 15-16 . تم الاطلاع عليه في 4 ديسمبر 2023 .

[44] ديفاداس، سريني؛ ديمين، إريك (25 فبراير 2011). "مقدمة في الخوارزميات: تغيير حجم جداول التجزئة" (ملف PDF) . معهد ماساتشوستس للتكنولوجيا ، قسم علوم الحاسوب. مؤرشف (ملف PDF) من الأصل في 7 مايو 2021. تم الاطلاع عليه في 9 نوفمبر 2021 - عبر MIT OpenCourseWare .

[45] ثاريجا، ريما (2014). "التجزئة والتصادم". هياكل البيانات باستخدام لغة C. مطبعة جامعة أكسفورد. ص 464-488 . ISBN 978-0-19-809930-7.

[scott03-46] 1 2 فريدمان، سكوت؛ كريشنان، أناند؛ ليدفروست، نيكولاس (18 مارس 2003). "جداول التجزئة للأنظمة المدمجة والأنظمة الآنية" (ملف PDF) . جميع أبحاث علوم وهندسة الحاسوب . جامعة واشنطن في سانت لويس . doi : 10.7936/K7WD3XXV . مؤرشف (ملف PDF) من الأصل في 9 يونيو 2021. تم الاسترجاع في 9 نوفمبر 2021 - عبر جامعة نورث وسترن ، قسم علوم الحاسوب.

[47] ليتوين، ويتولد (1980). "التجزئة الخطية: أداة جديدة لمعالجة الملفات والجداول" (ملف PDF) . وقائع المؤتمر السادس حول قواعد البيانات الضخمة جدًا . جامعة كارنيجي ميلون . الصفحات 212-223 . مؤرشف (ملف PDF) من الأصل في 6 مايو 2021. تم الاطلاع عليه في 10 نوفمبر 2021 - عبر cs.cmu.edu.

[dijk10-48] 1 2 دايك، توم فان (2010). "تحليل وتحسين أداء جداول التجزئة" (ملف PDF) . هولندا : جامعة توينتي . مؤرشف (ملف PDF) من الأصل في 6 نوفمبر 2021. تم الاطلاع عليه في 31 ديسمبر 2021 .

[49] بايزا-ياتس، ريكاردو؛ بوبليت، باتريسيو ف. (1999). "الفصل 2: البحث". في عطا الله (محرر). دليل الخوارزميات ونظرية الحوسبة . مطبعة سي آر سي. ص 2-6 . ISBN 0849326494.

[50] ليخ باناشوفسكي. "الفهارس والفرز الخارجي" . pl:Polsko-Japońska Akademia Technik Komputerowych . مؤرشفة من الأصلي في 26 مارس 2022 . تم الاسترجاع في 26 مارس 2022 .

[51] تشونغ، ليانغ؛ تشنغ، شيوكيان؛ ليو، يونغ؛ وانغ، مينغتينغ؛ كاو، يانغ (فبراير 2020). "تعظيم نسبة نجاح الوصول إلى الذاكرة المؤقتة في اتصالات الأجهزة عبر شبكات الهاتف المحمول". اتصالات الصين . 17 (2): 232-238 . Bibcode : 2020CComm..17b.232Z . doi : 10.23919/jcc.2020.02.018 . S2CID 212649328 .

[52] بوتوملي، جيمس (1 يناير 2004). "فهم التخزين المؤقت" . مجلة لينكس . مؤرشف من الأصل في 4 ديسمبر 2020. تم الاطلاع عليه في 16 أبريل 2022 .

[53] جيل سيمان (2014). "المجموعات وجداول التجزئة" (ملف PDF) . جامعة ولاية تكساس . مؤرشف من الأصل في 1 أبريل 2022. تم الاطلاع عليه في 26 مارس 2022 .{{cite web}}: CS1 maint: bot: حالة عنوان URL الأصلي غير معروفة ( رابط )

[54] "جدول النقل - ويكي برمجة الشطرنج" . chessprogramming.org . مؤرشف من الأصل في 14 فبراير 2021. تم الاطلاع عليه في 1 مايو 2020 .

[55] "أنواع البيانات وهياكل البيانات في جافا سكريبت - جافا سكريبت | MDN" . developer.mozilla.org . تم الاطلاع عليه بتاريخ 24 يوليو 2022 .

[56] "خريطة - جافا سكريبت | MDN" . developer.mozilla.org . 20 يونيو 2023. تم الاطلاع عليه في 15 يوليو 2023 .

[57] "لغة البرمجة C++ - المواصفات الفنية" (ملف PDF) . المنظمة الدولية للمعايير . الصفحات 812-813 . مؤرشف من الأصل (ملف PDF) بتاريخ 21 يناير 2022. تم الاطلاع عليه بتاريخ 8 فبراير 2022 .

[58] "مواصفات لغة البرمجة Go" . go.dev . تم الاطلاع عليه في 1 يناير 2023 .

[59] "الدرس: التطبيقات (دروس Java™ > المجموعات)" . docs.oracle.com . مؤرشف من الأصل في 18 يناير 2017. تم الاطلاع عليه في 27 أبريل 2018 .

[60] تشانغ، خوان؛ جيا، يونوي (2020). "تحسين إعادة التجزئة في Redis باستخدام التعلم الآلي" . مجلة الفيزياء: سلسلة المؤتمرات . 1453 (1): 3. Bibcode : 2020JPhCS1453a2048Z . doi : 10.1088/1742-6596/1453/1/012048 . S2CID 215943738 .

[61] جونان شيفلر (25 ديسمبر 2016). "إصدار روبي 2.4: تجزئات أسرع، وأعداد صحيحة موحدة، وتقريب أفضل" . heroku.com . مؤرشف من الأصل في 3 يوليو 2019. تم الاطلاع عليه في 3 يوليو 2019 .

[62] "doc.rust-lang.org" . مؤرشف من الأصل في 8 ديسمبر 2022. تم الاطلاع عليه في 14 ديسمبر 2022 .

[63] "فئة HashSet (System.Collections.Generic)" . learn.microsoft.com . تم الاطلاع عليه في 1 يوليو 2023 .

[64] tnet-bot. "فئة القاموس (System.Collections.Generic)" . learn.microsoft.com . تم الاطلاع عليه في 16 يناير 2024 .

[65] "مثال على HashSet في VB.NET" . دوت نت بيرلز .

[

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[

[

[ 12 ]

[ 2 ]

13

[ 14 ]

[ 15 ]

[ 16 ]

17 ]

[ 18 ] يمكن إنشاء دالة تجزئة مثالية إذا

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

[ 31 ]

[ 32 ]

[ 33 ]

[ 34 ]

[ 35 ]

[ 36 ]

[ 37 ]

[

[

[

[ 41 ]

[ 42 ]

[ 43 ]

[ 44 ]

[ 45 ]

[ 46 ]

[ 47 ]

48

[ 49 ]

[ 50 ]

[ 51 ]

[ 52 ]

[ 53 ]

[ 54 ]

[ 55 ]

[ 56 ]

[ 57 ]

[ 58 ]

[ 59 ]

[ 60 ]

[ 61 ]

] [ 63

] لذا يمكن

[ 64 ]

[

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