Implementasi terbaik untuk metode hashCode untuk koleksi

Bagaimana kita memutuskan penerapan hashCode()metode terbaik untuk koleksi (dengan asumsi bahwa metode yang sama telah diganti dengan benar)?

Implementasi terbaik? Itu adalah pertanyaan yang sulit karena itu tergantung pada pola penggunaan.

A untuk hampir semua kasus, implementasi yang baik dan wajar diusulkan dalam Josh Bloch 's Java yang Efektif pada Butir 8 (edisi kedua). Yang terbaik adalah mencarinya di sana karena penulis menjelaskan di sana mengapa pendekatannya bagus.

Versi singkat

1. Buat int resultdan tetapkan nilai yang bukan nol .

2. Untuk setiap bidang yang f diuji dalam equals()metode ini, hitung kode hash cdengan:

   • Jika bidang f adalah boolean: hitung (f ? 0 : 1);
   • Jika bidang f adalah byte, char, shortatau int: menghitung (int)f;
   • Jika bidang f adalah long: hitung (int)(f ^ (f >>> 32));
   • Jika bidang f adalah float: hitung Float.floatToIntBits(f);
   • Jika bidang f adalah double: menghitung Double.doubleToLongBits(f)dan menangani nilai pengembalian seperti setiap nilai panjang;
   • Jika bidang f adalah objek : Gunakan hasil dari hashCode()metode atau 0 jika f == null;
   • Jika bidang f adalah array : lihat setiap bidang sebagai elemen terpisah dan hitung nilai hash secara rekursif dan gabungkan nilai-nilai seperti yang dijelaskan berikutnya.

3. Gabungkan nilai hash cdengan result:

   result = 37 * result + c

4. Kembali result

Ini harus menghasilkan distribusi nilai hash yang tepat untuk sebagian besar situasi penggunaan.

Jika Anda senang dengan implementasi Java Efektif yang direkomendasikan oleh dmeister, Anda dapat menggunakan panggilan perpustakaan alih-alih memutar sendiri:

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

Ini membutuhkan Guava ( com.google.common.base.Objects.hashCode) atau pustaka standar di Java 7 ( java.util.Objects.hash) tetapi bekerja dengan cara yang sama.

Lebih baik menggunakan fungsi yang disediakan oleh Eclipse yang melakukan pekerjaan yang cukup bagus dan Anda dapat menempatkan upaya dan energi Anda dalam mengembangkan logika bisnis.

Meskipun ini terkait dengan Androiddokumentasi (Mesin Wayback) dan kode saya sendiri di Github , ini akan berfungsi untuk Java secara umum. Jawaban saya adalah perpanjangan dari Jawaban dmeister dengan hanya kode yang lebih mudah dibaca dan dimengerti.

@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;

}

EDIT

Biasanya, saat Anda menimpa hashcode(...), Anda juga ingin menimpa equals(...). Jadi bagi yang mau atau sudah menerapkan equals, berikut ini adalah referensi yang bagus dari Github saya ...

@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));
}

Pertama-tama pastikan bahwa persamaan diterapkan dengan benar. Dari artikel IBM DeveloperWorks :

• Simetri: Untuk dua referensi, a dan b, a.equals (b) jika dan hanya jika b.equals (a)
• Refleksivitas: Untuk semua referensi yang bukan nol, a.equals (a)
• Transitivitas: Jika a.equals (b) dan b.equals (c), maka a.equals (c)

Kemudian pastikan bahwa hubungannya dengan hashCode menghormati kontak (dari artikel yang sama):

• Konsistensi dengan kode hash (): Dua objek yang sama harus memiliki nilai kode hash () yang sama

Akhirnya fungsi hash yang baik harus berusaha untuk mendekati fungsi hash yang ideal .

about8.blogspot.com, katamu

jika equals () mengembalikan true untuk dua objek, maka hashCode () harus mengembalikan nilai yang sama. Jika equals () mengembalikan false, maka hashCode () harus mengembalikan nilai yang berbeda

Saya tidak bisa setuju dengan Anda. Jika dua objek memiliki kode hash yang sama, itu tidak harus berarti bahwa mereka sama.

Jika A sama dengan B maka A.hashcode harus sama dengan B.hascode

tapi

jika A.hashcode sama dengan B.hascode, itu tidak berarti bahwa A harus sama dengan B

Jika Anda menggunakan gerhana, Anda dapat membuat equals()dan hashCode()menggunakan:

Sumber -> Hasilkan kode hash () dan equals ().

Dengan menggunakan fungsi ini, Anda dapat memutuskan bidang mana yang ingin Anda gunakan untuk perhitungan kode persamaan dan hash, dan Eclipse menghasilkan metode yang sesuai.

Ada implementasi yang baik dari Jawa Efektif 's hashcode()dan equals()logika dalam Apache Commons Lang . Lihat HashCodeBuilder dan EqualsBuilder .

Hanya catatan singkat untuk melengkapi jawaban lain yang lebih terperinci (dalam hal kode):

Jika saya mempertimbangkan pertanyaan bagaimana-membuat-saya-membuat-tabel- has -di-java dan terutama entri FAQ jGuru , saya percaya beberapa kriteria lain yang dapat dinilai oleh kode hash adalah:

• sinkronisasi (apakah algo mendukung akses bersamaan atau tidak)?
• gagal iterasi aman (apakah algo mendeteksi koleksi yang berubah selama iterasi)
• nilai nol (apakah kode hash mendukung nilai nol dalam koleksi)

Jika saya memahami pertanyaan Anda dengan benar, Anda memiliki kelas koleksi khusus (yaitu kelas baru yang meluas dari antarmuka Koleksi) dan Anda ingin menerapkan metode hashCode ().

Jika kelas koleksi Anda memperluas AbstractList, maka Anda tidak perlu khawatir tentang hal itu, sudah ada implementasi equals () dan hashCode () yang berfungsi dengan mengiterasi semua objek dan menambahkan kode hash mereka () bersama-sama.

   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;
   }

Sekarang jika yang Anda inginkan adalah cara terbaik untuk menghitung kode hash untuk kelas tertentu, saya biasanya menggunakan operator ^ (bitwise eksklusif atau) untuk memproses semua bidang yang saya gunakan dalam metode equals:

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

@ about8: ada bug yang cukup serius di sana.

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

kode hash yang sama

Anda mungkin menginginkan sesuatu seperti

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

(Bisakah Anda mendapatkan kode hash langsung dari int di Jawa hari ini? Saya pikir ini melakukan autocasting .. jika itu masalahnya, lewati toString, itu jelek.)

Saat Anda secara spesifik meminta koleksi, saya ingin menambahkan aspek yang belum dijawab oleh jawaban lain: HashMap tidak mengharapkan kunci mereka untuk mengubah kode hash mereka begitu ditambahkan ke koleksi. Akan mengalahkan seluruh tujuan ...

Gunakan metode refleksi pada Apache Commons EqualsBuilder dan HashCodeBuilder .

Saya menggunakan pembungkus kecil di sekitar Arrays.deepHashCode(...)karena menangani array yang disediakan sebagai parameter dengan benar

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

metode hashing apa pun yang mendistribusikan nilai hash secara merata pada rentang yang mungkin adalah implementasi yang baik. Lihat java efektif ( http://books.google.com.au/books?id=ZZOiqZQIbRMC&dq=effective+java&pg=PP1&ots=UZMZ2siN25&sig=kR0n73DHJOn-D77qGj0wOxAxiZw&hl=en&sa=X&oi=book_result&resnum=1&ct=result ), ada tip yang baik di sana untuk implementasi kode hash (item 9 saya pikir ...).

Saya lebih suka menggunakan metode utilitas dari Google Koleksi Google lib dari Objek kelas yang membantu saya menjaga kode saya bersih. Sangat sering equalsdan hashcodemetode dibuat dari template IDE, sehingga tidak bersih untuk dibaca.

Berikut ini adalah demonstrasi pendekatan JDK 1.7+ lainnya dengan logika superclass. Saya melihatnya cukup meyakinkan dengan kelas Object hashCode () dicatat, ketergantungan JDK murni dan tidak ada pekerjaan manual tambahan. Harap dicatat Objects.hash()tidak ada toleransi.

Saya belum memasukkan equals()implementasi tetapi pada kenyataannya Anda tentu saja akan membutuhkannya.

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());
    }

}

Implementasi standar lemah dan menggunakannya menyebabkan tabrakan yang tidak perlu. Bayangkan a

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);
    }

    ...
}

Sekarang,

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

dan

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

memiliki yang sama hashCode, yaitu 31*(a+b) + csebagai pengganda yang digunakan untukList.hashCode kembali di sini. Jelas, tabrakan tidak dapat dihindari, tetapi menghasilkan tabrakan yang tidak perlu hanya ... tidak perlu.

Tidak ada yang secara substansial pintar dalam menggunakan 31. Pengganda harus ganjil untuk menghindari kehilangan informasi (pengganda genap mana pun kehilangan setidaknya bit yang paling signifikan, kelipatan empat kehilangan dua, dll.). Pengganda ganjil dapat digunakan. Pengganda kecil dapat menyebabkan komputasi lebih cepat (JIT dapat menggunakan shift dan penambahan), tetapi mengingat bahwa perkalian memiliki latensi hanya tiga siklus pada Intel / AMD modern, ini hampir tidak masalah. Pengganda kecil juga menyebabkan lebih banyak tabrakan untuk input kecil, yang terkadang menjadi masalah.

Menggunakan prime tidak ada gunanya karena bilangan prima tidak memiliki makna di cincin Z / (2 ** 32).

Jadi, saya akan merekomendasikan menggunakan nomor ganjil besar yang dipilih secara acak (jangan ragu untuk mengambil prime) Karena CPU i86 / amd64 dapat menggunakan instruksi yang lebih pendek untuk pemasangan operan dalam byte bertanda tunggal, ada keunggulan kecepatan kecil untuk pengganda seperti 109. Untuk meminimalkan benturan, ambil sesuatu seperti 0x58a54cf5.

Menggunakan pengganda yang berbeda di tempat yang berbeda itu membantu, tetapi mungkin tidak cukup untuk membenarkan pekerjaan tambahan.

Saat menggabungkan nilai hash, saya biasanya menggunakan metode menggabungkan yang digunakan di pustaka boost c ++, yaitu:

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

Ini melakukan pekerjaan yang cukup baik untuk memastikan distribusi yang merata. Untuk beberapa diskusi tentang cara kerja rumus ini, lihat posting StackOverflow: Nomor ajaib di boost :: hash_combine

Ada diskusi bagus tentang berbagai fungsi hash di: http://burtleburtle.net/bob/hash/doobs.html

Untuk kelas sederhana, seringkali paling mudah untuk mengimplementasikan kode hash () berdasarkan bidang kelas yang diperiksa oleh implementasi equals ().

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;
    }
}

Yang paling penting adalah menjaga agar kode hash () dan equals () konsisten: jika equals () mengembalikan nilai true untuk dua objek, maka kode hash () harus mengembalikan nilai yang sama. Jika equals () mengembalikan false, maka hashCode () harus mengembalikan nilai yang berbeda.