لماذا يجب استخدام تطبيق "Prime-onmed" Hashcode بدلا من "ساذج"؟

Question

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

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

Sub Main()
    Dim XorHashes(255) As Integer
    Dim PrimeHashes(255) As Integer

    For i = 0 To 255
        For j = 0 To 255
            For k = 0 To 255
                XorHashes(GetXorHash(i, j, k)) += 1
                PrimeHashes(GetPrimeHash(i, j, k)) += 1
            Next
        Next
    Next

    For i = 0 To 255
        Console.WriteLine("{0}: {1}, {2}", i, XorHashes(i), PrimeHashes(i))
    Next
    Console.ReadKey()
End Sub

Public Function GetXorHash(ByVal valueOne As Integer, ByVal valueTwo As Integer, ByVal valueThree As Integer) As Byte
    Return CByte((valueOne Xor valueTwo Xor valueThree) Mod 256)
End Function

Public Function GetPrimeHash(ByVal valueOne As Integer, ByVal valueTwo As Integer, ByVal valueThree As Integer) As Byte
    Dim TempHash = 17
    TempHash = 31 * TempHash + valueOne
    TempHash = 31 * TempHash + valueTwo
    TempHash = 31 * TempHash + valueThree

    Return CByte(TempHash Mod 256)
End Function

Answer 1

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

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

أيضا يجب عليك استخدام قيم 32 بت ل Gethashcode، وليس قيم 8 بت.

Answer 2

اقتطاع التجزئة هي مشكلتك هنا. يمكن أن تنتج طريقة XOR فقط 256 قيما مميزة. يمكن أن تولد الطريقة الرئيسية أكثر من 750،000 قيم مميزة، لكنك رمي 749،744 منها بعيدا عن طريق استخدام 8 بت منخفضة فقط. وبالتالي لا يمكن أبدا القيام بعمل أفضل من XOR.

في حالتك المحددة، يمكنك أن تفعل أفضل بكثير. هناك ما يكفي من البتات في عدد صحيح لتوليد تجزئة فريدة من نوعها مع 16 مليون قيم مميزة:

  Public Shared Function GetGoodHash(ByVal valueOne As Integer, ByVal valueTwo As Integer, ByVal valueThree As Integer) As Integer
    Return valueOne And 255 + (valueTwo And 255) << 8 + (valueThree And 255) << 16
  End Function

طريقة XOR على ما يرام عندما يتم توزيع قيم الإدخال بشكل جيد. مشكلة في الطريقة الرئيسية هي أنه من السهل أن تؤدي إلى استثناء تجاوز الفائض. من الصعب التعامل معها في رمز VB.NET، لا يحتوي على ما يعادل الكلمة الرئيسية التي لم يتم التحقق منها C #. يجب عليك تشغيل ذلك على مستوى العالم باستخدام Project + Properties، وعلامة التبويب ترجمة، خيارات الترجمة المتقدمة، حدد "إزالة الشيكات الفائضة الصحيحة". تجنب ذلك عن طريق حساب التجزئة باعتبارها INT64. مما يجعلها مكلفة بعض الشيء.