جمع دالة البعثرة

Question

في المحلية الكائن هناك جمع الجوانب.

وقد جمع سطيح وقد تجزئة طريقة إرجاع طويلة.
http://www.cplusplus.com/reference/std/locale/collate/hash/

سؤالين:

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

ملاحظة:لا أستطيع استخدام C++0x الميزات
زيادة قد تكون على ما يرام.

Answer 1

لا أحد يعرف حقا-أنها يمكن أن تختلف من تطبيق واحد إلى آخر.المتطلبات الأساسية هي (N3092, §20.8.15):

لجميع أنواع الكائنات الرئيسية التي يوجد تخصص التجزئة ، مثيل التجزئة بما يلي:

1. تلبية تجزئة متطلبات (20.2.4) مع مفتاح استدعاء دالة الحجة نوع ، DefaultConstructible متطلبات (33) ، CopyAssignable متطلبات (37),
2. تكون قابلة للتبديل (20.2.2) عن lvalues,
3. توفير اثنين متداخلة أنواع result_type و argument_type التي يجب أن تكون مرادفات size_t الرئيسية ، على التوالي ،
4. تستوفي الشرط أنه إذا k1 == k2 هو صحيح ، ح(k1) == ح(k2) غير صحيح أيضا ، حيث h هو كائن من نوع تجزئة k1 و k2 هي كائنات من نوع الرئيسية.

و (N3092, §20.2.4):

نوع H يلتقي تجزئة الشروط إذا:

1. بل هو وظيفة نوع الكائن (20.8),
2. فإنه satisifes متطلبات CopyConstructible و التدمير (20.2.1),
3. التعبيرات في الجدول التالي صالحة و قد أشار دلالات ،
4. استوفى جميع المتطلبات الأخرى في هذا subclause.

§20.8.15 يغطي متطلبات على نتيجة تجزئة §20.2.4 على تجزئة نفسها.كما يمكنك أن ترى, ومع ذلك ، سواء حد العامة.الجدول الذي ذكر في الأساس يغطي أكثر من ثلاثة متطلبات:

1. وظيفة تجزئة يجب أن يكون "خالصة" (أي النتيجة تعتمد فقط على المدخلات ، وليس أي سياق التاريخ ، إلخ.)
2. وظيفة يجب أن لا تعديل الحجة التي مرت عليه ،
3. يجب أن لا رمي أي استثناءات.

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

Answer 2

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

لذا فإن أبسط طريقة معقولة تمامًا للحصول على قيمة تجزئة 32 بت هي:

int32_t value = hash(...);

(بالطبع هذا ينهار مجموعات من 4 مليارات قيم وصولاً إلى واحدة ، والتي تبدو كثيرًا ، ولكن لا يمكن تجنبها إذا كان هناك أربعة مليارات أضعاف عدد قيم المصدر.)