خوارزمية التجزئة غير المتصادمة لسلاسل تصل إلى 255 حرفًا

Question

أنا أبحث عن خوارزمية تجزئة، لإنشاء أقرب ما يمكن إلى تجزئة فريدة لسلسلة (الحد الأقصى len = 255) قدر الإمكان، والتي تنتج عددًا صحيحًا طويلًا (DWORD).

أدرك أن 26^255 >> 2^32، ولكنني أعلم أيضًا أن عدد الكلمات في اللغة الإنجليزية أقل بكثير من 2^32.

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

---

الاجابة:

واحد من متغيرات FNV يجب أن تلبي متطلباتك.إنها سريعة، وتنتج مخرجات موزعة بالتساوي إلى حد ما.(تم الرد عليه عنكبوتي)

---

Answer 1

يرى هنا لتكرار سابق لهذا السؤال (والإجابة).

Answer 2

تتمثل إحدى التقنيات في استخدام خوارزمية تجزئة معروفة (على سبيل المثال، MD5 أو SHA-1) واستخدام أول 32 بت فقط من النتيجة.

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

Answer 3

أجرى Ronny Pfannschmidt اختبارًا للكلمات الإنجليزية الشائعة أمس ولم يواجه أي تصادمات للكلمات الـ 10000 التي اختبرها في وظيفة تجزئة سلسلة Python.لم أختبرها بنفسي، لكن هذه الخوارزمية بسيطة وسريعة جدًا، ويبدو أنها مُحسّنة للكلمات الشائعة.

هنا التنفيذ:

static long
string_hash(PyStringObject *a)
{
    register Py_ssize_t len;
    register unsigned char *p;
    register long x;

    if (a->ob_shash != -1)
        return a->ob_shash;
    len = Py_SIZE(a);
    p = (unsigned char *) a->ob_sval;
    x = *p << 7;
    while (--len >= 0)
        x = (1000003*x) ^ *p++;
    x ^= Py_SIZE(a);
    if (x == -1)
        x = -2;
    a->ob_shash = x;
    return x;
}

Answer 4

H(مفتاح) = [GetHash(مفتاح) + 1 + (((GetHash(مفتاح) >> 5) + 1) % (hashsize – 1))] % hashsize

مقالة MSDN عن HashCodes

Answer 5

يمكن عرض String.hash() الخاص بـ Java بسهولة هنا, ، الخوارزمية الخاصة بها هي

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]