كتب hash function algorithms
اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.
خوارزميات دالة هاش (معلومة)
يعتمد اختيار دالة هاش على طبيعة البيانات المدخلة بشكل كبير، وتوزيعها المحتمل في التطبيق.
دالة هاش البسيطة
إذا كانت البيانات التي سيُطبَّق عليها دالة هاش صغيرة بما يكفي، يُمكن استخدام البيانات نفسها باعتبارها قيمة هاش. وتبلغ تكلفة حوسبة دالة هاش "البسيطة" صفر (دالة متطابقة).
يعتمد مدى "صغر" البيانات على مساحة الذاكرة المتوفر لجدول هاش. فقد يشمل جهاز كمبيوتر في عام 2008 مساحة متوفرة من الذاكرة بقيمة جيجا بايت، وهذا يعني أنه يمكنها استيعاب قيم هاش تصل إلى 30 بت. ومع ذلك، هناك العديد من التطبيقات التي يُمكن أن تعمل بأقل من ذلك. فعلى سبيل المثال، عند تحديد سلسلة أحرف بين الحالة العلوية والسفلية، يمكن استخدام الترميز الثنائي لكل حرف لفهرسة جدول يُوفِّر الشكل البديل لهذا الحرف ("A" لـ"a"، و"8" لـ"8"). وإذا تم تخزين كل حرف في 8 بت (كما هو الحال في آسكي)، يحتوى الجدول على 2 8 = 256 فقط من المُدخلات؛ أما في حالة حروف اليونيكود سيحتوى الجدول على 17 × 2 16 = 1114112 من المُدخلات.
ويمكن استخدام هذه التقنية نفسها لتحديد رموز البلاد التي تتكون من حرفين "us" أو "za" لأسماء البلاد (26 ² = 676 إدخال في الجدول). كما يمكن أن تظل قيم البيانات غير الصحيحة غير معروفة (مثل رمز البلد "x x" أو الرمز البريدي 00000) في الجدول، أو يمكن تحديدها بقيمة أخرى مناسبة.
دالة هاش المثالية
تُعتبر الدالة هاش المتباينة دالة مثالية. وهي التي تُوجه كل مُدخل صحيح إلى قيمة هاش مختلفة. ويمكن تحديد موقع الإدخال المطلوب مباشرةً في جدول هاش من خلال هذه الدالة دون اللجوء إلى أي بحث إضافي.
تُعد دالات هاش المثالية فعَّآلة فقط عندما تكون المُدخلات ثابتة ومعروفة سلفاً مثل: تحديد أسماء الشهور من خلال الأعداد الصحيحة من 0 إلى 11. ويُمكن تمثيل الدالة المثالية للمجموعة n في أقل من 3*n من خلال الدالة هاش المناسبة التي يمكن العثور عليها في الوقت الذي يتناسب مع n. كما يمكن تقييم تلك الدالة من خلال عدد ثابت من العمليات. وهناك مولدات تُنتج شفرة تنفيذية لتقييم دالة هاش المثالية لمجموعة معينة من المُدخلات.
الحد الأدنى من المثالية للدالة هاش
تُعتبر الدالة هاش المثالية n في حالتها الدنيا إذا كانت مجموعتها تتألف من أعداد صحيحة متتالية n، عادةً من 0 إلى n-1. وتُنتج الدالة هاش أيضاً في هذه الحالة جدول هاش مُعقَّد دون وجود أي بنود فارغة، بالإضافة إلى توفير البحث من خلال خطوة واحدة. ويصعب العثور على دالات هاش المثالية في حالتها الدنيا بشكل كبير.
البيانت المُوزعة بالتساوي من خلال الدالة هاش
عندما تكون المدخلات مستقلة في شكل سلاسل ذات أطوال مختلفة (مثل أرقام الهواتف، ولوحات تسجيل المركبات، وأرقام الفواتير إلخ)، تحتاج الدالة هاش إلى تحديد نفس عدد مُدخلات القيم هاش. فعلى سبيل المثال، إذا كانت المُدخلات عبارة عن عدد صحيح z في المجموعة من 0 إلى N-1، يجب أن يكون الناتج عدداً صحيحاً h في المجموعة من 0 إلى n-1، حيث تكون قيمة N أكبر بكثير من n. وبالتالي، يمكن أن تكون الدالة هاش: h = z mod n (ما تبقى من z مقسوماً على n)، أو h = (z × n) ÷ N (خفض القيمة z بـ n/N لتصبح عدد صحيح)، أو غيرها من الصيغ الأخرى.
تطبيق الدالة هاش على البيانات من خلال توزيعات أخرى
لن تعمل هذه الصيغ البسيطة إذا لم تتساو مُدخلات القيم. فعلى سبيل المثال، يعيش معظم رواد أي مركز تجاري في نفس المنطقة الجغرافية، وبالتالي يتشابه أول 3 أو 4 أرقام لهواتفهم. وفي هذه الحالة، إذا كانت قيمة n تساوي 10000، ستَنتج تصادمات عديدة من صيغة القسمة: z × n ÷ N التي تعتمد بشكل كبير على الأرقام الرائدة. بينما يَنتج عن الصيغة المتبقية z mod n قيم هاش مُوزعة بشكل متساوي.
تطبيق الدالة هاش على البيانات متغيرة الطول
عندما تتكون قيم البيانات من سلاسل ذات أحرف طويلة (أو متغيرة الطول) مثل: أسماء الأشخاص، وعناوين الإنترنت، ورسائل البريد، يتم توزيعهم بشكل غير مُتساوي وتبعيات معقدة. فعلى سبيل المثال، يتميز النص في أي لغة طبيعية بتوزيع غير مُتساوي للحروف. وبالتالي، من المهم استخدام الدالة هاش التي تعتمد على كل حروف السلسلة عند التعامل مع هذه البيانات. كما يجب أن تعتمد على كل حرف بطريقة مختلفة.
وعادةً ما يُستخدم نظام ميركيل-دامجراد في دالات هاش الرمزية. وبصفة عامة، يتم تطبيق الدالة هاش على البيانات من خلال تقسيم المُدخلات إلى سلسلة من الوحدات الصغيرة (البت، والبايت، والكلمات إلخ)، ثم تجميع كل الوحدات b1، وb2...، وbm بالتتابع على النحو التالي:
S ← S0; // Initialize the state. for k in 1, 2, …, m do // Scan the input data units: S ← F(S, b[k]); // Combine data unit k into the state. return G(S, n) // Extract the hash value from the state.
كما يُستخدم هذا الأسلوب في كثير من النصوص الاختبارية وخوارزميات البصمات. ويُمكن أن يكون المتغير S عدد صحيح 32 أو 64 بت. وفي هذه الحالة، يمكن لـS0 أن تساوي 0، ويُمكن لـG:S,n أن تكون مجرد S mod n. ويعتمد أفضل اختيار لـF على طبيعة البيانات، وهي مسألة معقدة جداً. وإذا كانت وحدات b:k تتكون من بت واحد، يُمكن أن تُساوي F:S,b على سبيل المثال:
if highbit(S) = 0 then return 2 * S + b else return (2 * S + b) ^ P
> حيث يُشير highbit:S إلى أكثر بت مهم؛ بينما يدل المشغل "*" على عملية ضرب العدد الصحيح؛ وتشير "^" إلى عملية البت التي طُبِّقَت على الكلمات، وP هي كلمة مناسبة ثابتة.
دالات هاش ذات أغراض خاصة
في كثير من الحالات، يُمكن تصميم دالة هاش لأغراض خاصة (خوارزمية الكشف عن مجريات الأمور). وذلك للحصول على عدد أقل من التصادمات. لنفترض أن مُدخلات البيانات عبارة عن أسماء ملفات مثل: FILE0000.CHK، وFILE0001.CHK، وFILE0002.CHK مع وجود أرقام متسلسلة. يجب استخدام دالة لاستخراج الجزء الرقمي k من اسم الملف، واسترجاع k mod n. وليس من الضروري أن يكون للدالة التي تم تطبيقها على نوع معين من البيانات نفس التأثير على توزيع البيانات بشكل مختلف.
وفي بعض التطبيقات مثل البحث الفرعي، يجب تصميم دالة هاش h لكل حرف فرعي k لسلsلة الأحرف n؛ حيث أن k هو عدد صحيح ثابت، وقيمة n أكبر بكثير من قيمة k. ويتطلب الحل المباشر تطبيق عدد من العمليات على k:n. ويكمن الحل في استخراج حرف فرعي s من t على حدة، وتصميم h:s. ومع ذلك، يمكن استخدام تقنية دالة هاش المتداولة لحوسبة جميع الدالات بجهد يتناسب مع k + n.
