أفضل تنفيذ لطريقة hashCode للمجموعة

Question

كيف نقرر التنفيذ الأفضل لـ hashCode() طريقة لمجموعة (بافتراض أنه تم تجاوز طريقة يساوي بشكل صحيح)؟

Answer 1

أفضل تنفيذ؟هذا سؤال صعب لأنه يعتمد على نمط الاستخدام.

تم اقتراح التنفيذ الجيد المعقول في جميع الحالات تقريبًا جوش بلوخ'س جافا فعالة في البند 8 (الطبعة الثانية).أفضل شيء هو البحث عنه هناك لأن المؤلف يشرح هناك سبب كون هذا النهج جيدًا.

نسخة قصيرة

1. إنشاء int result وتعيين أ غير صفرية قيمة.

2. ل كل مجال f تم اختباره في equals() طريقة حساب رمز التجزئة c بواسطة:

   • إذا كان الحقل f هو a boolean:احسب (f ? 0 : 1);
   • إذا كان الحقل f هو a byte, char, short أو int:احسب (int)f;
   • إذا كان الحقل f هو a long:احسب (int)(f ^ (f >>> 32));
   • إذا كان الحقل f هو a float:احسب Float.floatToIntBits(f);
   • إذا كان الحقل f هو a double:احسب Double.doubleToLongBits(f) والتعامل مع القيمة المرجعة مثل كل قيمة طويلة؛
   • إذا كان الحقل f هو هدف:استخدم نتيجة hashCode() الطريقة أو 0 إذا f == null;
   • إذا كان الحقل f هو مجموعة مصفوفة:انظر إلى كل حقل كعنصر منفصل واحسب قيمة التجزئة في ملف الأزياء العودية ودمج القيم كما هو موضح بعد ذلك.

3. الجمع بين قيمة التجزئة c مع result:

   result = 37 * result + c
   

4. يعود result

يجب أن يؤدي هذا إلى توزيع مناسب لقيم التجزئة لمعظم حالات الاستخدام.

Answer 2

إذا كنت راضيًا عن تطبيق Java الفعال الذي أوصى به dmeister، فيمكنك استخدام استدعاء المكتبة بدلاً من إجراء استدعاء خاص بك:

@Override
public int hashCode() {
    return Objects.hashCode(this.firstName, this.lastName);
}

وهذا يتطلب إما الجوافة (com.google.common.base.Objects.hashCode) أو المكتبة القياسية في Java 7 (java.util.Objects.hash) ولكنه يعمل بنفس الطريقة.

Answer 3

من الأفضل استخدام الوظائف التي يوفرها Eclipse والتي تقوم بعمل جيد جدًا ويمكنك وضع جهودك وطاقتك في تطوير منطق الأعمال.

Answer 4

على الرغم من أن هذا مرتبط Android الوثائق (آلة Wayback) و الكود الخاص بي على جيثب, ، سيعمل مع Java بشكل عام.جوابي هو امتداد ل إجابة دميستر باستخدام رمز فقط يسهل قراءته وفهمه.

@Override 
public int hashCode() {

    // Start with a non-zero constant. Prime is preferred
    int result = 17;

    // Include a hash for each field.

    // Primatives

    result = 31 * result + (booleanField ? 1 : 0);                   // 1 bit   » 32-bit

    result = 31 * result + byteField;                                // 8 bits  » 32-bit 
    result = 31 * result + charField;                                // 16 bits » 32-bit
    result = 31 * result + shortField;                               // 16 bits » 32-bit
    result = 31 * result + intField;                                 // 32 bits » 32-bit

    result = 31 * result + (int)(longField ^ (longField >>> 32));    // 64 bits » 32-bit

    result = 31 * result + Float.floatToIntBits(floatField);         // 32 bits » 32-bit

    long doubleFieldBits = Double.doubleToLongBits(doubleField);     // 64 bits (double) » 64-bit (long) » 32-bit (int)
    result = 31 * result + (int)(doubleFieldBits ^ (doubleFieldBits >>> 32));

    // Objects

    result = 31 * result + Arrays.hashCode(arrayField);              // var bits » 32-bit

    result = 31 * result + referenceField.hashCode();                // var bits » 32-bit (non-nullable)   
    result = 31 * result +                                           // var bits » 32-bit (nullable)   
        (nullableReferenceField == null
            ? 0
            : nullableReferenceField.hashCode());

    return result;

}

يحرر

عادةً، عند التجاوز hashcode(...), ، فأنت تريد أيضًا التجاوز equals(...).لذلك بالنسبة لأولئك الذين سينفذون أو قاموا بالفعل بتنفيذه equals, ، هنا مرجع جيد من جيثب الخاص بي...

@Override
public boolean equals(Object o) {

    // Optimization (not required).
    if (this == o) {
        return true;
    }

    // Return false if the other object has the wrong type, interface, or is null.
    if (!(o instanceof MyType)) {
        return false;
    }

    MyType lhs = (MyType) o; // lhs means "left hand side"

            // Primitive fields
    return     booleanField == lhs.booleanField
            && byteField    == lhs.byteField
            && charField    == lhs.charField
            && shortField   == lhs.shortField
            && intField     == lhs.intField
            && longField    == lhs.longField
            && floatField   == lhs.floatField
            && doubleField  == lhs.doubleField

            // Arrays

            && Arrays.equals(arrayField, lhs.arrayField)

            // Objects

            && referenceField.equals(lhs.referenceField)
            && (nullableReferenceField == null
                        ? lhs.nullableReferenceField == null
                        : nullableReferenceField.equals(lhs.nullableReferenceField));
}

Answer 5

تأكد أولاً من تنفيذ المساواة بشكل صحيح.من مقالة IBM DeveloperWorks:

• تناظر:بالنسبة لمرجعين، a وb، a.equals(b) إذا وفقط إذا كان b.equals(a)
• الانعكاسية:بالنسبة لجميع المراجع غير الخالية، a.equals(a)
• عبورية:إذا كان أ.يساوي(ب) وب.يساوي(ج)، فإن أ.يساوي(ج)

ثم تأكد من أن علاقتهم بـ hashCode تحترم جهة الاتصال (من نفس المقالة):

• الاتساق مع hashCode ():يجب أن يكون لكائنين متساويين نفس قيمة hashCode()

أخيرًا، يجب أن تسعى وظيفة التجزئة الجيدة إلى الاقتراب من وظيفة التجزئة المثالية.

Answer 6

قلت about8.blogspot.com

إذا أعاد التابع يساوي () القيمة الحقيقية لكائنين، فيجب أن يُرجع hashCode () نفس القيمة.إذا قامت الدالة يساوي () بإرجاع خطأ، فيجب أن يُرجع hashCode () قيمًا مختلفة

لا أستطيع أن أتفق معك.إذا كان هناك كائنان لهما نفس رمز التجزئة، فهذا لا يعني بالضرورة أنهما متساويان.

إذا كان A يساوي B، فيجب أن يكون A.hashcode مساويًا لـ B.hascode

لكن

إذا كان A.hashcode يساوي B.hascode، فهذا لا يعني أن A يجب أن يساوي B

Answer 7

إذا كنت تستخدم Eclipse، فيمكنك إنشاء equals() و hashCode() استخدام:

المصدر -> إنشاء hashCode() و يساوي().

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

Answer 8

هناك تنفيذ جيد لل جافا فعالة'س hashcode() و equals() المنطق في أباتشي كومنز لانج.الدفع HashCodeBuilder و EqualsBuilder.

Answer 9

مجرد ملاحظة سريعة لإكمال إجابة أخرى أكثر تفصيلاً (من حيث الكود):

إذا كنت أفكر في السؤال كيف أقوم بإنشاء جدول تجزئة في Java وخاصة إدخال الأسئلة الشائعة لـ jGuru, أعتقد أن بعض المعايير الأخرى التي يمكن الحكم على رمز التجزئة بناءً عليها هي:

• المزامنة (هل تدعم الخوارزمية الوصول المتزامن أم لا)؟
• فشل التكرار الآمن (هل تكتشف الخوارزمية مجموعة تتغير أثناء التكرار)
• قيمة فارغة (هل يدعم رمز التجزئة القيمة الخالية في المجموعة)

Answer 10

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

إذا قامت فئة المجموعة الخاصة بك بتوسيع AbstractList، فلا داعي للقلق بشأن ذلك، فهناك بالفعل تطبيق يساوي () و hashCode () يعمل عن طريق التكرار عبر جميع الكائنات وإضافة hashCodes () معًا.

   public int hashCode() {
      int hashCode = 1;
      Iterator i = iterator();
      while (i.hasNext()) {
        Object obj = i.next();
        hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
      }
  return hashCode;
   }

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

public int hashCode(){
   return intMember ^ (stringField != null ? stringField.hashCode() : 0);
}

Answer 11

@about8 :هناك خطأ خطير جدا هناك.

Zam obj1 = new Zam("foo", "bar", "baz");
Zam obj2 = new Zam("fo", "obar", "baz");

نفس رمز التجزئة

ربما تريد شيئا من هذا القبيل

public int hashCode() {
    return (getFoo().hashCode() + getBar().hashCode()).toString().hashCode();

(هل يمكنك الحصول على hashCode مباشرة من int في Java هذه الأيام؟أعتقد أنه يقوم ببعض البث التلقائي..إذا كان هذا هو الحال، تخطي toString، فهو قبيح.)

Answer 12

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

Answer 13

استخدم طرق الانعكاس في Apache Commons EqualsBuilder و HashCodeBuilder.

Answer 14

تعتبر أي طريقة تجزئة تقوم بتوزيع قيمة التجزئة بالتساوي على النطاق المحتمل بمثابة تطبيق جيد.شاهد جافا الفعالة ( http://books.google.com.au/books?id=ZZOiqZQIbRMC&dq=efficiency+java&pg=PP1&ots=UZMZ2siN25&sig=kR0n73DHJOn-D77qGj0wOxAxiZw&hl=en&sa=X&oi=book_result&resnum=1&ct=result ) ، هناك نصيحة جيدة لتنفيذ رمز التجزئة (البند 9 على ما أعتقد ...).

Answer 15

أفضّل استخدام أساليب المنفعة fromm مجموعات Google lib من كائنات الفئة يساعدني ذلك في الحفاظ على الكود الخاص بي نظيفًا.غالبا equals و hashcode الأساليب مصنوعة من قالب IDE، لذا فهي ليست سهلة القراءة.

Answer 16

أستخدم غلافًا صغيرًا حولها Arrays.deepHashCode(...) لأنه يتعامل مع المصفوفات المتوفرة كمعلمات بشكل صحيح

public static int hash(final Object... objects) {
    return Arrays.deepHashCode(objects);
}

Answer 17

فيما يلي عرض توضيحي آخر لنهج JDK 1.7+ مع مراعاة منطق الطبقة الفائقة.أرى أنه ملائم جدًا مع حساب hashCode() الخاص بفئة الكائن، وتبعية JDK النقية وعدم وجود عمل يدوي إضافي.يرجى الملاحظة Objects.hash() غير متسامح.

أنا لم تشمل أي equals() التنفيذ ولكن في الواقع سوف تحتاج إليه بالطبع.

import java.util.Objects;

public class Demo {

    public static class A {

        private final String param1;

        public A(final String param1) {
            this.param1 = param1;
        }

        @Override
        public int hashCode() {
            return Objects.hash(
                super.hashCode(),
                this.param1);
        }

    }

    public static class B extends A {

        private final String param2;
        private final String param3;

        public B(
            final String param1,
            final String param2,
            final String param3) {

            super(param1);
            this.param2 = param2;
            this.param3 = param3;
        }

        @Override
        public final int hashCode() {
            return Objects.hash(
                super.hashCode(),
                this.param2,
                this.param3);
        }
    }

    public static void main(String [] args) {

        A a = new A("A");
        B b = new B("A", "B", "C");

        System.out.println("A: " + a.hashCode());
        System.out.println("B: " + b.hashCode());
    }

}

Answer 18

التنفيذ القياسي ضعيف ويؤدي استخدامه إلى تصادمات غير ضرورية.تخيل أ

class ListPair {
    List<Integer> first;
    List<Integer> second;

    ListPair(List<Integer> first, List<Integer> second) {
        this.first = first;
        this.second = second;
    }

    public int hashCode() {
        return Objects.hashCode(first, second);
    }

    ...
}

الآن،

new ListPair(List.of(a), List.of(b, c))

و

new ListPair(List.of(b), List.of(a, c))

عندى مثلها hashCode, ، يسمى 31*(a+b) + c كما المضاعف المستخدم ل List.hashCode يتم إعادة استخدامها هنا.من الواضح أن الاصطدامات أمر لا مفر منه، ولكن إنتاج تصادمات لا داعي لها هو مجرد...لا داعي.

لا يوجد شيء ذكي إلى حد كبير في الاستخدام 31.يجب أن يكون المضاعف فرديًا لتجنب فقدان المعلومات (أي مضاعف يفقد على الأقل الجزء الأكثر أهمية، ومضاعفات الأربعة تفقد اثنين، وما إلى ذلك).أي مضاعف فردي قابل للاستخدام.قد تؤدي المضاعفات الصغيرة إلى عمليات حسابية أسرع (يمكن لـ JIT استخدام الإزاحات والإضافات)، ولكن نظرًا لأن الضرب له زمن انتقال يبلغ ثلاث دورات فقط على معالجات Intel/AMD الحديثة، فإن هذا لا يهم.تؤدي المضاعفات الصغيرة أيضًا إلى مزيد من التصادم للمدخلات الصغيرة، وهو ما قد يمثل مشكلة في بعض الأحيان.

استخدام الأعداد الأولية لا معنى له لأن الأعداد الأولية ليس لها معنى في الحلقة Z/(2**32).

لذا، أوصي باستخدام رقم فردي كبير تم اختياره عشوائيًا (لا تتردد في أخذ رقم أولي).نظرًا لأن وحدات المعالجة المركزية i86/amd64 يمكنها استخدام تعليمات أقصر للمعاملات التي تتناسب مع بايت واحد موقع، فهناك ميزة سرعة صغيرة للمضاعفات مثل 109.لتقليل الاصطدامات، استخدم شيئًا مثل 0x58a54cf5.

يعد استخدام مضاعفات مختلفة في أماكن مختلفة أمرًا مفيدًا، ولكنه ربما لا يكون كافيًا لتبرير العمل الإضافي.

Answer 19

عند دمج قيم التجزئة، عادةً ما أستخدم طريقة الدمج المستخدمة في مكتبة Boost C++، وهي:

seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);

وهذا يقوم بعمل جيد إلى حد ما لضمان التوزيع المتساوي.للحصول على بعض المناقشات حول كيفية عمل هذه الصيغة، راجع منشور StackOverflow: الرقم السحري في Boost::hash_combine

هناك مناقشة جيدة حول وظائف التجزئة المختلفة في: http://burtleburtle.net/bob/hash/doobs.html

Answer 20

بالنسبة لفئة بسيطة، غالبًا ما يكون من الأسهل تنفيذ hashCode() استنادًا إلى حقول الفئة التي يتم التحقق منها من خلال تطبيق يساوي().

public class Zam {
    private String foo;
    private String bar;
    private String somethingElse;

    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }

        if (obj == null) {
            return false;
        }

        if (getClass() != obj.getClass()) {
            return false;
        }

        Zam otherObj = (Zam)obj;

        if ((getFoo() == null && otherObj.getFoo() == null) || (getFoo() != null && getFoo().equals(otherObj.getFoo()))) {
            if ((getBar() == null && otherObj. getBar() == null) || (getBar() != null && getBar().equals(otherObj. getBar()))) {
                return true;
            }
        }

        return false;
    }

    public int hashCode() {
        return (getFoo() + getBar()).hashCode();
    }

    public String getFoo() {
        return foo;
    }

    public String getBar() {
        return bar;
    }
}

الشيء الأكثر أهمية هو الحفاظ على تناسق hashCode() وequals():إذا أعاد التابع يساوي () القيمة الحقيقية لكائنين، فيجب أن يُرجع hashCode () نفس القيمة.إذا قامت الدالة يساوي () بإرجاع خطأ، فيجب أن يُرجع hashCode () قيمًا مختلفة.