دالة التجزئة

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

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

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

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

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

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

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

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

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

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

$${\displaystyle {\frac {m}{n}}{\sum _{j=1}^{m}b_{j}^{2}}-n}$$

حيث n هو عدد المفاتيح، و m هو عدد الحاويات، و b _j هو عدد العناصر في الحاوية j .

تشير النسبة ضمن فاصل ثقة واحد (مثل 0.95 إلى 1.05) إلى أن دالة التجزئة التي تم تقييمها لها توزيع منتظم متوقع.

تتمتع دوال التجزئة ببعض الخصائص التقنية التي تزيد من احتمالية توزيعها المنتظم عند تطبيقها. إحدى هذه الخصائص هي معيار الانهيار الصارم : عند عكس بت إدخال واحد، يتغير كل بت من بتات الإخراج باحتمالية 50%. يعود سبب هذه الخاصية إلى أن مجموعات فرعية مختارة من فضاء المفاتيح قد تتميز بانخفاض التباين. لكي يكون توزيع الإخراج منتظمًا، يجب أن يُترجم انخفاض التباين، حتى بت واحد، إلى ارتفاع التباين (أي التوزيع على فضاء الجدول) في الإخراج. يجب أن يتغير كل بت باحتمالية 50%، لأنه إذا كانت بعض البتات مقاومة للتغيير، فإن المفاتيح تتجمع حول تلك القيم. أما إذا كانت البتات تتغير بسهولة بالغة، فإن عملية الربط تقترب من دالة XOR ثابتة لبت واحد. وُصفت الاختبارات القياسية لهذه الخاصية في المراجع ^{[ 7 ]} . يتم هنا تقييم مدى ملاءمة هذا المعيار لدالة التجزئة الضربية ^{[ 8 ] .}

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

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

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

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

يمكننا السماح بأن يكون حجم الجدول n ليس قوةً للعدد 2، ومع ذلك لن نحتاج إلى إجراء أي عملية باقٍ أو قسمة، لأن هذه العمليات الحسابية قد تكون مكلفة. على سبيل المثال، لنفترض ^أن n أقل بكثير من 2b . لنفترض دالة مولد أرقام شبه عشوائية P (key) موزعة بانتظام على الفترة [0, ^2b  -  1] . دالة التجزئة الموزعة بانتظام على الفترة [0, n - 1] هي nP ( key) / ^2b . يمكننا استبدال القسمة بإزاحة بتة إلى اليمين (ربما أسرع) : nP (key) >> b .

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

نظام التجزئة الشامل هو خوارزمية عشوائية تختار دالة تجزئة h من بين مجموعة من هذه الدوال، بحيث يكون احتمال تصادم أي مفتاحين مختلفين هو 1/ m ، حيث m هو عدد قيم التجزئة المختلفة المطلوبة، بغض النظر عن المفتاحين. يضمن التجزئة الشامل (من الناحية الاحتمالية) أن تطبيق دالة التجزئة سيتصرف بنفس كفاءة استخدام دالة عشوائية، لأي توزيع لبيانات الإدخال. مع ذلك، سيشهد تصادمات أكثر من التجزئة المثالية، وقد يتطلب عمليات أكثر من دالة تجزئة مُخصصة.

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

تُستخدم دالة التجزئة في العديد من المواقف. ومن أبرز تطبيقاتها في مجال التشفير: ^{[ 9 ]}

• التحقق من سلامة البيانات : تشير قيم التجزئة المتطابقة للملفات المختلفة إلى المساواة، مما يوفر وسيلة موثوقة للكشف عن تعديلات الملفات.
• اشتقاق المفتاح : تؤدي التغييرات الطفيفة في المدخلات إلى تغيير عشوائي المظهر في المخرجات، وهو ما يُعرف بخاصية الانتشار. لذا، تُعدّ دوال التجزئة ذات قيمة كبيرة لدوال اشتقاق المفاتيح.
• رموز مصادقة الرسائل (MACs): من خلال دمج مفتاح سري مع بيانات الإدخال، يمكن لوظائف التجزئة إنشاء رموز مصادقة الرسائل (MACs) التي تضمن صحة البيانات، كما هو الحال في HMACs .
• تخزين كلمات المرور: لا تكشف قيمة تجزئة كلمة المرور عن أي تفاصيل خاصة بها، مما يؤكد أهمية تخزين كلمات المرور المجزأة بشكل آمن على الخادم.
• التوقيعات : يتم توقيع تجزئات الرسائل بدلاً من الرسالة بأكملها.

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

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

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

في العديد من التطبيقات، قد يختلف نطاق قيم التجزئة في كل تشغيل للبرنامج، أو قد يتغير خلال نفس التشغيل (على سبيل المثال، عند الحاجة إلى توسيع جدول التجزئة). في هذه الحالات، نحتاج إلى دالة تجزئة تأخذ مُعاملين: بيانات الإدخال z ، وعدد قيم التجزئة المسموح بها n .

يتمثل أحد الحلول الشائعة في حساب دالة تجزئة ثابتة ذات نطاق واسع جدًا (مثلاً، من 0 إلى 2 ^{^32}  -  1 )، ثم قسمة الناتج على n ، واستخدام باقي القسمة . إذا كان n نفسه قوة للعدد 2 ، فيمكن تحقيق ذلك باستخدام تقنية إخفاء البتات وإزاحة البتات . عند استخدام هذه الطريقة، يجب اختيار دالة التجزئة بحيث يكون توزيع الناتج منتظمًا نسبيًا بين 0 و n  -  1 ، لأي قيمة لـ n قد تظهر في التطبيق. اعتمادًا على الدالة، قد يكون الباقي منتظمًا فقط لقيم معينة من n ، مثل الأعداد الفردية أو الأولية .

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

من المستحسن استخدام دالة تجزئة تُعيد ترتيب أقل عدد ممكن من السجلات عند تغيير حجم الجدول. المطلوب هو دالة تجزئة H ( z , n ) (حيث z هو المفتاح المراد تجزئته و n هو عدد قيم التجزئة المسموح بها) بحيث يكون H ( z , n  +  1) = H ( z , n ) باحتمالية قريبة من n /( n  +  1) .

يُعدّ التجزئة الخطية والتجزئة الحلزونية مثالين على دوال التجزئة الديناميكية التي تُنفّذ في زمن ثابت، ولكنها تُخفّف من خاصية التوحيد لتحقيق خاصية الحد الأدنى من الحركة. تستخدم التجزئة القابلة للتمديد دالة تجزئة ديناميكية تتطلب مساحة تتناسب مع n لحساب دالة التجزئة، وتصبح دالةً للمفاتيح السابقة المُدخلة. وقد تم ابتكار العديد من الخوارزميات التي تحافظ على خاصية التوحيد ولكنها تتطلب زمنًا يتناسب مع n لحساب قيمة H ( z , n ) .

تُعد دالة التجزئة ذات الحركة الدنيا مفيدة بشكل خاص في جداول التجزئة الموزعة .

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

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

يعتمد معنى "صغير بما يكفي" على حجم النوع المستخدم كقيمة مُجزأة. على سبيل المثال، في لغة جافا ، يكون رمز التجزئة عددًا صحيحًا من 32 بت. وبالتالي، يمكن لكائنات الأعداد الصحيحة Integerوالعشرية من 32 بت Floatاستخدام القيمة مباشرةً، بينما لا يمكن Longلكائنات الأعداد الصحيحة والعشرية من 64 بت فعل ذلك Double.

يمكن لأنواع أخرى من البيانات استخدام مخطط التجزئة هذا أيضًا. على سبيل المثال، عند تحويل سلاسل الأحرف بين الأحرف الكبيرة والصغيرة ، يمكن استخدام الترميز الثنائي لكل حرف، مُفسَّرًا كعدد صحيح، لفهرسة جدول يُعطي الشكل البديل لهذا الحرف ("A" لـ "a"، "8" لـ "8"، إلخ). إذا تم تخزين كل حرف في 8 بتات (كما هو الحال في ASCII الموسع ^{[ ملاحظات 2 ]} أو ISO Latin 1 )، فإن الجدول يحتوي على 2 ^{^8} = 256 مدخلًا فقط؛ في حالة أحرف Unicode ، سيحتوي الجدول على 17 × 2^ ¹⁶ =1 114 112 مدخلاً.

يمكن استخدام نفس الأسلوب لربط رموز الدول المكونة من حرفين مثل "us" أو "za" بأسماء الدول (26 ^{2 = 676 مدخلًا في الجدول)،} وربط الرموز البريدية المكونة من 5 أرقام مثل 13083 بأسماء المدن (100000 مدخل)، إلخ . قد تُترك قيم البيانات غير الصالحة (مثل رمز البلد "xx" أو الرمز البريدي 00000) غير محددة في الجدول أو يتم تعيينها إلى قيمة "فارغة" مناسبة.

إذا كانت المفاتيح موزعة بشكل منتظم أو شبه منتظم على فضاء المفاتيح، بحيث تكون قيم المفاتيح عشوائية بشكل أساسي، فيمكن اعتبارها "مُجزأة" بالفعل. في هذه الحالة، يمكن استخراج أي عدد من أي بتات في المفتاح وتجميعها كمؤشر في جدول التجزئة. على سبيل المثال، قد تقوم دالة تجزئة بسيطة بإخفاء أقل m بت أهمية واستخدام النتيجة كمؤشر في جدول تجزئة بحجم 2^ ^m .

يتم إنتاج رمز التجزئة للمربعات الوسطى عن طريق تربيع المدخلات واستخراج عدد مناسب من الأرقام أو البتات الوسطى. على سبيل المثال، إذا كانت المدخلات هي123 456 789 وحجم جدول التجزئة10000 ، ثم ينتج عن تربيع المفتاح15 241 578 750 190 521 ، لذا يُؤخذ رمز التجزئة على أنه الأرقام الأربعة الوسطى من العدد المكون من 17 رقمًا (مع تجاهل الرقم الأعلى) 8750. تُنتج طريقة المربعات الوسطى رمز تجزئة معقولًا إذا لم يكن هناك الكثير من الأصفار في بداية أو نهاية المفتاح. هذه طريقة مُعدّلة من التجزئة الضربية، ولكنها ليست بنفس الجودة لأن المفتاح العشوائي ليس مُضاعِفًا جيدًا.

تتمثل إحدى التقنيات الشائعة في استخدام دالة باقي القسمة على المفتاح، وذلك باختيار قاسم M يكون عددًا أوليًا قريبًا من حجم الجدول، بحيث يكون h ( K ) ≡ K (mod M ) . عادةً ما يكون حجم الجدول قوةً للعدد 2. ينتج عن ذلك توزيع من {0, M − 1} . تُعطي هذه الطريقة نتائج جيدة على عدد كبير من مجموعات المفاتيح. من أبرز عيوب التجزئة بالقسمة أن القسمة تتطلب دورات متعددة على معظم البنى الحديثة (بما في ذلك x86 )، وقد تكون أبطأ بعشر مرات من الضرب. عيب آخر هو أنها لا تُفكك المفاتيح المتجمعة. على سبيل المثال، المفاتيح 123000، 456000، 789000، إلخ، باقي قسمتها على 1000 تُشير جميعها إلى نفس العنوان. تُجدي هذه التقنية نفعًا عمليًا لأن العديد من مجموعات المفاتيح عشوائية بما فيه الكفاية، واحتمالية أن تكون مجموعة المفاتيح دورية بمقدار عدد أولي كبير ضئيلة.

الترميز الجبري هو شكل من أشكال طريقة التجزئة بالقسمة، حيث يستخدم القسمة على متعدد حدود بتردد 2 بدلاً من عدد صحيح لربط n بت بـ m بت. ^{[ 3 ] : 512-513.} في هذا النهج، M = 2 ^{^m} ، ونفترض متعدد حدود من الدرجة m ، Z ( x ) = x^ ^m + ζ ^ _{m - 1} x^ ^{m - 1} + ... + ζ ^ ₀ . يمكن اعتبار المفتاح K = ( k _{^n - 1} … k^ ₁ k^ ₀ ) _{^2 متعدد الحدود} K ( x ) = k _{^n - 1} x ^{^n - 1} + ... + k^ ₁ x + k ^ ₀ . الباقي باستخدام حساب كثيرات الحدود modulo 2 هو K ( x ) mod Z ( x ) = h _{(m - 1} ) x ^{(m - 1)} + ... + h _{(1 )} x + h ₍₀₎ . وبالتالي ، h ( K ) = ( h _{(m - 1)} ... + h ₍₁₎ h ₍₀ )) _² . إذا تم إنشاء Z ( x ) بحيث تحتوي على t أو أقل من المعاملات غير الصفرية، فإن المفاتيح التي تشترك في أقل من t بتات تضمن عدم حدوث تصادم.

Z دالة لـ k و t و n (الأخير قاسم لـ ^2k - 1 ) وتُنشأ من الحقل المنتهي GF(2k ⁾ . يُعطي كنوت مثالًا: بأخذ ( n , m , t ) = (15 , 10 , 7) نحصل على Z ( x ) = x¹⁰ ⁺ x⁸ + ^x⁵ + x⁴ + ^{x² +} x + 1. الاشتقاق كما يلي ^:

ليكن S أصغر مجموعة من الأعداد الصحيحة بحيث يكون {1,2, … , t } ⊆ S و (2 j mod n ) ∈ S ∀ j ∈ S . ^{[ ملاحظات 3 ]}

يُعرِّف${\displaystyle P(x)=\prod _{j\in S}(x-\alpha ^{j})}$حيث α ∈ ⁿ GF(2 ^k ) وحيث تُحسب معاملات P ( x ) في هذا الحقل. إذن، درجة P ( x ) = | S | . بما أن α ^{2 j} هو جذر لـ P ( x ) كلما كان α ^j جذرًا، فإنه يترتب على ذلك أن معاملات p ⁱ لـ P ( x ) تحقق p ² _i = p _i ، لذا فهي جميعًا 0 أو 1. إذا كانت R ( x ) = r _{n − 1} x ^{n − 1} + ⋯ + r ₁ x + r ₀ أي متعددة حدود غير صفرية بتردد 2 ولها على الأكثر t معاملات غير صفرية، فإن R ( x ) ليست من مضاعفات P ( x ) بتردد 2. ^{[ ملاحظات 4 ]} يترتب على ذلك أن دالة التجزئة المقابلة ستربط المفاتيح التي تحتوي على أقل من t بتات مشتركة بمؤشرات فريدة. ^{[ 3 ] : 542–543}

النتيجة المعتادة هي أن قيمة n ستزداد، أو قيمة t ستزداد، أو كليهما، حتى يصبح المخطط قابلاً للتطبيق حسابيًا. لذلك، فهو أنسب للتنفيذ على مستوى الأجهزة أو البرامج المصغرة. ^{[ 3 ] : 542-543}

تضمن خوارزمية التجزئة بالتباديل الفريدة أفضل وقت إدخال في أسوأ الحالات. ^{[ 12 ]}

تستخدم التجزئة الضربية القياسية الصيغة h _{_a} ( K ) = ⌊ ( aK mod W ) / ( W / M ) ⌋ ، والتي تُنتج قيمة تجزئة في المجموعة {0, … , M − 1} . القيمة a هي قيمة مختارة بعناية، ويجب أن تكون أولية نسبيًا مع W ؛ أي كبيرة، وتمثيلها الثنائي مزيج عشوائي من 1 و0. توجد حالة خاصة عملية مهمة عندما يكون W = 2^{^w} و M = 2^{^m} قوتين للعدد 2، و w هو حجم كلمة الآلة . في هذه الحالة، تصبح الصيغة h _{_a} ( K ) = ⌊ ( aK mod 2^{^w} ) / 2 ^{^{w − m}}⌋ . هذه الحالة خاصة لأن العمليات الحسابية بتردد 2^{^w} تُجرى افتراضيًا في لغات البرمجة منخفضة المستوى، والقسمة الصحيحة على قوة من قوى العدد 2 هي ببساطة إزاحة إلى اليمين، لذا، في لغة C ، على سبيل المثال، تصبح هذه الدالة

unsigned hash ( unsigned K ) { return ( a * K ) >> ( w - m ); }

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

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

دالة التجزئة غير الموقعة ( عدد صحيح غير موقع K ) { K ^= K >> ( w - m ); return ( a * K ) >> ( w - m ); }

تُعدّ تجزئة فيبوناتشي نوعًا من التجزئة الضربية ^، حيث يكون المضاعف 2w / ϕ ، حيث w هو طول كلمة الآلة و ϕ (فاي) هي النسبة الذهبية (حوالي 1.618). من خصائص هذا المضاعف أنه يوزع بانتظام على مساحة الجدول كتل المفاتيح المتتالية بالنسبة لأي كتلة بتات في المفتاح. وتُعدّ المفاتيح المتتالية ضمن البتات العليا أو السفلى للمفتاح (أو أي حقل آخر) شائعة نسبيًا. وفيما يلي المضاعفات لأطوال الكلمات المختلفة:

• 16: أ = 9E37 ₁₆ =40 503 ₁₀
• 32: أ = 9E37 79B9 ₁₆ =2 654 435 769 ₁₀
• 48: أ = 9E37 79B9 7F4B ₁₆ =173 961 102 589 771 ₁₀ ^{[ ملاحظات 5 ]}
• 64: أ = 9E37 79B9 7F4A 7C15 ₁₆ =11 400 714 819 323 198 485 ₁₀

يجب أن يكون المضاعف فرديًا، بحيث يكون البت الأقل أهمية في الناتج قابلاً للعكس بتردد 2w . ولتحقيق ذلك ^، يتم تقريب القيمتين الأخيرتين المذكورتين أعلاه (لأعلى ولأسفل على التوالي) بأكثر من نصف البت الأقل أهمية.

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

طُرحت خوارزمية التجزئة زوبريست في الأصل كوسيلة لتمثيل وضعيات الشطرنج بشكل مُختصر في برامج ألعاب الكمبيوتر. يُخصص رقم عشوائي فريد لكل نوع من القطع (ستة أرقام لكل من الأسود والأبيض) في كل مربع من مربعات رقعة الشطرنج. وبذلك، يتم تهيئة جدول من 64×12 رقمًا عشوائيًا عند بدء تشغيل البرنامج. يمكن أن تكون الأرقام العشوائية بأي طول، ولكن 64 بت كان الطول الأمثل نظرًا لوجود 64 مربعًا على رقعة الشطرنج. يتم نسخ الوضعية بالمرور على القطع الموجودة فيها، وفهرسة الأرقام العشوائية المقابلة (لا تُحتسب المربعات الفارغة)، ثم إجراء عملية XOR بينها (يمكن أن تكون القيمة الابتدائية 0 (قيمة الوحدة لعملية XOR) أو قيمة بذرة عشوائية ). تُختزل القيمة الناتجة باستخدام عملية باقي القسمة، أو الطي، أو أي عملية أخرى لإنتاج فهرس جدول التجزئة. يُخزن تجزئة زوبريست الأصلية في الجدول كتمثيل للوضعية.

لاحقًا، تم توسيع هذه الطريقة لتشمل تجزئة الأعداد الصحيحة، وذلك بتمثيل كل بايت في كل موضع من المواضع الأربعة الممكنة في الكلمة برقم عشوائي فريد مكون من 32 بت. وبذلك، يتم إنشاء جدول من 2 ^{^8} × 4 أرقام عشوائية. يُنسخ العدد الصحيح المُجزأ ذو 32 بت عن طريق فهرسة الجدول تباعًا بقيمة كل بايت من العدد الصحيح الأصلي، ثم إجراء عملية XOR بين القيم المُحمّلة (مرة أخرى، يمكن أن تكون القيمة الابتدائية هي قيمة الوحدة أو قيمة بذرة عشوائية). أما التوسع الطبيعي ليشمل الأعداد الصحيحة ذات 64 بت، فيتم باستخدام جدول من 2 ^{^8} × 8 أرقام عشوائية ذات 64 بت.

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

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

قد تجمع دوال التجزئة البسيطة أول وآخر n حرف من سلسلة نصية مع طولها، أو تُنشئ تجزئة بحجم كلمة من الأحرف الأربعة الوسطى من السلسلة. هذا يوفر عناء المرور على السلسلة (التي قد تكون طويلة)، لكن دوال التجزئة التي لا تُجزئ جميع أحرف السلسلة قد تصبح خطية بسهولة بسبب التكرار أو التجميع أو غيرها من المشاكل في مجموعة المفاتيح. قد تكون هذه الاستراتيجيات فعالة كدالة تجزئة مخصصة إذا كان هيكل المفاتيح بحيث تكون الحقول الوسطى أو الطرفية أو غيرها من الحقول صفرًا أو أي قيمة ثابتة أخرى لا تُميز بين المفاتيح؛ عندها يمكن تجاهل الأجزاء الثابتة من المفاتيح.

المثال النموذجي لتجزئة الأحرف هو جمع القيم العددية لجميع الأحرف في السلسلة. لكن الأفضل هو ضرب مجموع التجزئة بثابت، عادةً ما يكون عددًا أوليًا كبيرًا، قبل إضافة الحرف التالي، مع تجاهل تجاوز السعة. استخدام عملية XOR بدلًا من الجمع بديلٌ ممكن. العملية الأخيرة هي باقي القسمة، أو القناع، أو دالة أخرى لتقليل قيمة الكلمة إلى فهرس بحجم الجدول. تكمن نقطة ضعف هذه الطريقة في احتمال تجمّع المعلومات في البتات العليا أو السفلى للبايتات؛ سيبقى هذا التجمّع في نتيجة التجزئة، مما يُسبب تصادمات أكثر من التجزئة العشوائية الصحيحة. على سبيل المثال، تحتوي رموز بايت ASCII على بت علوي قيمته 0، ولا تستخدم السلاسل القابلة للطباعة رمز البايت الأخير أو معظم رموز البايت الـ 32 الأولى، لذا تتجمع المعلومات، التي تستخدم رموز البايت المتبقية، في البتات المتبقية بطريقة غير واضحة.

صُممت الطريقة الكلاسيكية، المسماة بتجزئة PJW والمستوحاة من عمل بيتر ج. واينبرغر في مختبرات بيل في سبعينيات القرن الماضي، في الأصل لتجزئة المعرفات في جداول رموز المترجم كما هو موضح في "كتاب التنين" . ^{[ 15 ]} تقوم دالة التجزئة هذه بإزاحة البايتات بمقدار 4 بتات قبل جمعها. عند اكتمال القيمة، تُزاح البتات الأربعة العليا، وإذا كانت غير صفرية، تُجرى عليها عملية XOR مع البايت الأدنى من القيمة التراكمية. والنتيجة هي رمز تجزئة بحجم كلمة، يمكن تطبيق عملية باقي القسمة أو أي عملية اختزال أخرى عليه لإنتاج فهرس التجزئة النهائي.

اليوم، وخاصة مع ظهور أحجام الكلمات 64 بت، أصبح تجزئة السلاسل ذات الطول المتغير بواسطة أجزاء الكلمات أكثر كفاءة.

ستتيح المعالجات الدقيقة الحديثة معالجة أسرع بكثير إذا لم يتم حساب سلاسل الأحرف ذات 8 بت عن طريق معالجة حرف واحد في كل مرة، بل عن طريق تفسير السلسلة كمصفوفة من الأعداد الصحيحة ذات 32 بت أو 64 بت، ثم حساب تجزئة/تجميع قيم هذه الأعداد الصحيحة "ذات الكلمات العريضة" باستخدام عمليات حسابية (مثل الضرب بثابت وإزاحة البتات). تُملأ الكلمة الأخيرة، التي قد تحتوي على مواقع بايت غير مشغولة، بأصفار أو بقيمة عشوائية محددة قبل دمجها في التجزئة. يُختزل رمز التجزئة المُجمّع بعملية باقي القسمة النهائية أو عملية أخرى للحصول على فهرس في الجدول.

على غرار تحويل سلسلة أحرف ASCII أو EBCDIC التي تمثل عددًا عشريًا إلى قيمة عددية لأغراض الحساب، يمكن تحويل سلسلة متغيرة الطول إلى الصيغة التالية: x  k - 1  a  k -1 + x  k - 2  a  k - 2 + ... + x 1 a + x 0 . هذه الصيغة ببساطة متعددة حدود في أساس a > 1   ، تأخذ المكونات ( x 0 , x 1 , ..., x  k -1 ) كأحرف سلسلة الإدخال ذات الطول k . يمكن استخدامها مباشرةً كرمز تجزئة، أو تطبيق دالة تجزئة عليها لربط القيمة الكبيرة المحتملة بحجم جدول التجزئة. عادةً ما تكون قيمة a عددًا أوليًا كبيرًا بما يكفي لاستيعاب عدد الأحرف المختلفة في مجموعة أحرف المفاتيح المحتملة. يقلل تجزئة السلاسل باستخدام تحويل الأساس من عدد التصادمات. [ 16 ] قد تحد أحجام البيانات المتاحة من الحد الأقصى لطول السلسلة التي يمكن تجزئتها بهذه الطريقة. على سبيل المثال، كلمةٌ طولها 128 بت تُجزئ سلسلةً أبجديةً من 26 حرفًا فقط (مع تجاهل حالة الأحرف) باستخدام أساس 29؛ بينما تقتصر سلسلة ASCII قابلة للطباعة على 9 أحرف باستخدام أساس 97 وكلمة طولها 64 بت. مع ذلك، عادةً ما تكون المفاتيح الأبجدية قصيرة نسبيًا، لأنها تُخزَّن في جدول التجزئة. أما السلاسل الرقمية فلا تُشكِّل عادةً مشكلة؛ إذ يمكن لـ 64 بت أن تحسب حتى 10 ^19 ، أي 19 رقمًا عشريًا باستخدام أساس 10.

في بعض التطبيقات، مثل البحث عن السلاسل الفرعية ، يمكن حساب دالة تجزئة h لكل سلسلة فرعية مكونة من k حرفًا من سلسلة نصية معينة مكونة من n حرفًا، وذلك بتحريك نافذة عرضها k حرفًا على طول السلسلة، حيث k عدد صحيح ثابت، و n > k . يتطلب الحل المباشر، وهو استخراج هذه السلسلة الفرعية عند كل موضع حرف في النص وحساب h بشكل منفصل، عددًا من العمليات يتناسب مع k × n . مع ذلك، باختيار h المناسب ، يمكن استخدام تقنية التجزئة المتغيرة لحساب جميع هذه التجزئات بجهد يتناسب مع mk + n، حيث m هو عدد مرات ظهور السلسلة الفرعية. ^{[ 17 ]}  

تُعدّ خوارزمية رابين-كارب أشهر خوارزميات هذا النوع، حيث يبلغ أداءها في أفضل الحالات ومتوسطها O ( n + mk ) ، وفي أسوأ الحالات O ( n · k ) (مع العلم أن أسوأ حالة هنا شاذة للغاية: إذ يتكون كل من النص الأصلي والسلسلة الفرعية من حرف واحد متكرر، مثل t "AAAAAAAAAAA" و s "AAA"). عادةً ما تُستخدم دالة التجزئة بصمة رابين في هذه الخوارزمية ، وهي مصممة لتجنب التصادمات في سلاسل الأحرف ذات 8 بت، ولكن تُستخدم أيضًا دوال تجزئة أخرى مناسبة.