كيفية ضمان hashCode() يتسق مع تساوي()?

Question

عندما تجاوز يساوي() وظيفة جافا.لانغ.كائن ، javadocs تشير إلى ذلك ،

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

على hashCode() الأسلوب لا بد من العودة فريدة من نوعها صحيح لكل كائن (هذا من السهل القيام به عند المقارنة بين الأشياء على أساس موقع الذاكرة ، ببساطة العودة فريدة من نوعها صحيح عنوان الكائن)

كيف ينبغي أن hashCode (طريقة) أن تنقضها حتى ترجع فريدة من نوعها صحيح لكل كائن تستند فقط على هذا الكائن الخصائص?

public class People{
   public String name;
   public int age;

   public int hashCode(){
      // How to get a unique integer based on name and age?
   }
}
/*******************************/
public class App{
   public static void main( String args[] ){
       People mike = new People();
       People melissa = new People();
       mike.name = "mike";
       mike.age = 23;
       melissa.name = "melissa";
       melissa.age = 24;
       System.out.println( mike.hasCode() );  // output?
       System.out.println( melissa.hashCode(); // output?
   }
}

Answer 1

لا أقول hashcode لكائن يجب أن تكون فريدة من نوعها تماما ، إلا أن hashcode لمدة تساوي الأشياء ترجع نفس hashcode.إنه قانوني تماما أن يكون اثنين من غير متساوية الكائنات عودة نفس hashcode.ومع ذلك ، فإن أكثر فريدة من نوعها hashcode التوزيع على مجموعة من الكائنات ، أفضل أداء عليك الخروج من HashMaps وغيرها من العمليات التي تستخدم hashCode.

ايديس مثل IntelliJ Idea قد بنيت في المولدات يساوي hashCode عموما القيام بعمل جيد جدا في الخروج مع "جيدة بما فيه الكفاية" رمز لمعظم الكائنات (و ربما أفضل من بعض من ناحية الصياغة بشكل مفرط الذكاء وظائف التجزئة).

على سبيل المثال, وهنا hashCode وظيفة هذه الفكرة يولد الناس على الدرجة:

public int hashCode() {
    int result = name != null ? name.hashCode() : 0;
    result = 31 * result + age;
    return result;
}

Answer 2

لن أخوض في تفاصيل hashCode تفرد مارك بالفعل موجهة.الخاص بك People الدرجة, عليك أولا أن تقرر ما المساواة من شخص يعني.ربما المساواة لا يقوم إلا على الاسم ، ربما مبنية على الاسم والعمر.سيكون المجال تحديدا.دعونا نقول المساواة على أساس الاسم والعمر.الخاص بك تجاوزها equals قد تبدو

public boolean equals(Object obj) {
    if (this==obj) return true;
    if (obj==null) return false;
    if (!(getClass().equals(obj.getClass())) return false;
    Person other = (Person)obj;
    return (name==null ? other.name==null : name.equals(other.name)) &&
        age==other.age;
}

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

public int hashCode() {
    return (name==null ? 17 : name.hashCode()) ^ age;
}

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

public int hashCode() {
    return (name==null ? 17 : name.hashCode()) ^ age ^ height;
}

كما انها صالحة تماما لمدة غير يساوي الكائنات لها نفس رمز التجزئة:

public int hashCode() {    
    return age;    
}

في هذه الحالة جين سن 30 لا يساوي بوب سن 30 ، بعد كل تجزئة رموز 30.في حين صالح هذا أمر غير مرغوب فيه بالنسبة الأداء في تجزئة على أساس مجموعات.

Answer 3

سؤال آخر يسأل إذا كان هناك بعض الأساسية على مستوى منخفض الأمور أن جميع المبرمجين يجب أن تعرف, و أعتقد تجزئة عمليات البحث هي واحدة من تلك.حتى هنا يذهب.

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

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

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

مصطلح "الكمال التجزئة" هو مصطلح الحقيقي, و في بعض الحالات يمكنك إنشاء دالة البعثرة التي توفر رقم فريد لكل كائن.هذا ممكن فقط عندما كنت تعرف مجموعة من القيم الممكنة.في الحالة العامة, لا يمكنك تحقيق ذلك, وسوف يكون هناك بعض القيم التي ترجع نفس hashcode.هذا هو بسيط الرياضيات:إذا كان لديك سلسلة أكثر من 4 بايت, لا يمكنك إنشاء فريدة من نوعها 4 بايت hashcode.

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

تحرير استنادا إلى التعليقات:

1) قائمة مرتبطة ليست الطريقة الوحيدة لتمثيل الكائنات التي لها نفس hashcode ، على الرغم من أن الطريقة المستخدمة من قبل JDK 1.5 HashMap.على الرغم من أن ذاكرة أقل كفاءة من مجموعة من أنه لا يمكن القول خلق أقل بعنف عندما باسترجاع (لأن يمكن ربطها من دلو واحد و relinked إلى آخر).

2) اعتبارا من JDK 1.4 ، HashMap الدرجة يستخدم صفيف الحجم كقوة 2;قبل أن تستخدم 2^N+1 التي أعتقد هو رئيس ن <= 32.هذا لا تسرع مجموعة الفهرسة في حد ذاته ، ولكن لا تسمح مؤشر مجموعة احتساب مع المعامل و بدلا من شعبة ، كما أشار نيل كوفى.شخصيا أود السؤال هذا سابق لأوانه الأمثل ، ولكن بالنظر إلى قائمة المؤلفين على HashMap سوف نفترض أن هناك بعض الفائدة الحقيقية.

Answer 4

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

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

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

Answer 5

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

مباشرة سمات بعض بيئات التطوير hashcode وظيفة بناه.

إذا كنت لا تستخدم ايديس, النظر في استخدام Apahce العموم وفئة HashCodeBuilder

Answer 6

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

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

Answer 7

هذا هو ما هي الوثائق التي تحكي لنا عن تجزئة رمز الأسلوب

@ جافادوك

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

Answer 8

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