ما هو رسمي معقول لحساب hashcode؟

Question

يحتوي Eclipse 3.5 على ميزة لطيفة للغاية لتوليد وظائف Java Hashcode (). سوف تولد على سبيل المثال (تقصير قليلا :)

class HashTest {
    int i;
    int j;        
    public int hashCode() {
        final int prime = 31;
        int result = prime + i;
        result = prime * result + j;
        return result;
    }
}

(إذا كان لديك سمات أكثر في الفصل، result = prime * result + attribute.hashCode(); يتكرر لكل سمة إضافية. للمجلس الدولي للمشاركة. يمكن حذفها.)

هذا يبدو جيدا ولكن لاختيار 31 من أجل رئيس الوزراء. ربما أخذت من تنفيذ hashcode سلسلة جافا, ، والتي تم استخدامها لأسباب الأداء التي تذهب منذ فترة طويلة بعد إدخال مضاعفات الأجهزة. هنا لديك العديد من تصادمات Hashcode للقيم الصغيرة من I و J: على سبيل المثال (0،0) و (-1،31) لها نفس القيمة. أعتقد أن هذا شيء سيء (TM)، لأن القيم الصغيرة تحدث في كثير من الأحيان. بالنسبة إلى String.hashcode، ستجد أيضا العديد من السلاسل القصيرة مع نفس hashcode، على سبيل المثال "CA" و "DB". إذا كنت تأخذ رئيسا كبيرا، تختفي هذه المشكلة إذا اخترت اليمين الرئيسي.

لذا سؤالي: ما هو جيد للاختيار؟ ما المعايير التي تنطبق عليها العثور عليها؟

هذا هو سؤال عام - لذلك أنا لا أريد أن أعطي مجموعة من I و J. لكنني أفترض في معظم التطبيقات، تحدث القيم الصغيرة نسبيا أكثر من القيم الكبيرة. (إذا كان لديك قيم كبيرة، فإن اختيار PRIME غير مهم.) قد لا يجعل الكثير من الفرق، ولكن اختيار أفضل هو وسيلة سهلة وواضحة لتحسين هذا - فلماذا لا تفعل ذلك؟ المشاع Lang. hashcodebuilder. يقترح أيضا القيم الصغيرة الغريبة.

(توضيح: هذا هو ليس نسخة مكررة لماذا يستخدم جهاز Java Hashcode () في السلسلة 31 كمضاعف؟ نظرا لأن سؤالي لا يهتم بتاريخ 31 في JDK، ولكن فيما يتعلق بأفضل قيمة في التعليمات البرمجية الجديدة باستخدام نفس القالب الأساسي. لا شيء من الإجابات تحاول الإجابة على ذلك.)

Answer 1

أوصي باستخدام 92821. وبعد وهنا لماذا.

لإعطاء إجابة ذات معنى لهذا، عليك أن تعرف شيئا عن القيم المحتملة لل i و j. وبعد الشيء الوحيد الذي يمكنني التفكير فيه بشكل عام هو أنه في كثير من الحالات، ستكون القيم الصغيرة أكثر شيوعا من القيم الكبيرة. (كانت احتمالات 15 التي تظهر كقيمة في البرنامج أفضل بكثير من، على سبيل المثال، 438281923.) لذلك يبدو من الجيد أن تجعل أصغر اصطدام حاشسك كبير قدر الإمكان عن طريق اختيار رئيس الوزراء المناسب. ل 31 هذا سيء إلى حد ما بالفعل i=-1 و j=31 لديك نفس قيمة التجزئة كما i=0 و j=0.

نظرا لأن هذا مثير للاهتمام، فقد كتبت برنامجا صغيرا قام بتفتيش المجموعة الدولية بأكملها لأفضل رئيسا بهذا المعنى. وهذا هو، بالنسبة لكل برايم بحثت عن الحد الأدنى لقيمة Math.abs(i) + Math.abs(j) على جميع قيم i,j التي لها نفس hashcode كما 0,0, ثم استغرق الأمر الرئيسي حيث هذه القيمة الدنيا كبيرة قدر الإمكان.

دروولول: أفضل رئيسا بهذا المعنى هو 486187739 (مع أصغر الاصطدام i=-25486, j=67194). تقريبا جيدة وأسهل بكثير لتذكر أن 92821 مع أصغر الاصطدام i=-46272 and j=46016.

إذا أعطيت "صغير" معنى آخر وتريد أن يكون الحد الأدنى Math.sqrt(i*i+j*j) بالنسبة للتصادم أكبر قدر ممكن، فإن النتائج مختلفة قليلا: أفضل سيكون 1322837333 i=-6815 and j=70091, ، ولكن بلدي 92821 المفضلة (أصغر الاصطدام -46272,46016) مرة أخرى تقريبا جيدة مثل أفضل قيمة.

أقر بأنها قابلة للنقاش تماما ما إذا كان هذا الحساب معنى كبير في الممارسة. لكنني أعتقد أن تناول 92821 كأكثر أهمية أكثر من 31 عاما، إلا إذا كان لديك أسباب جيدة لا ل.

Answer 2

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

Answer 3

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

في النهاية، ما هي أفضل طريقة للتجزئة يعتمد على ما تقارنه. في حالة زوج INT (كما هو الحال في مثالك)، يمكن أن يكون استخدام مشغلي BIG هذا كافية (مثل استخدام & ^).

Answer 4

تحتاج إلى تحديد النطاق الخاص بك ل I و J. يمكنك استخدام رقم رئيسي لكليهما.

public int hashCode() {
   http://primes.utm.edu/curios/ ;)
   return 97654321 * i ^ 12356789 * j;
}

Answer 5

سأختار 7243. كبير بما يكفي لتجنب الاكتيامات بأعداد صغيرة. لا يفيض بأعداد صغيرة بسرعة.

Answer 6

أريد فقط أن أشير إلى أن أي شكود لا علاقة له برايم. في jdk تنفيذ

for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }

وجدت إذا كنت تحل محل 31 مع 27, والنتيجة مشابهة جدا.