Geriausias surinkimo metodas „hashCode“

Kaip išspręsti geriausią „ hashCode() metodo įgyvendinimą kolekcijai (su sąlyga, kad lygiavertis metodas yra teisingai apibrėžtas)?

270
22 сент. nustatė „ Omnipotent “ rugsėjo 22 d 2008-09-22 09:53 '08 at 9:53 2008-09-22 09:53
@ 20 atsakymų

Geriausias įgyvendinimas? Tai sudėtingas klausimas, nes jis priklauso nuo naudojimo modelio.

Beveik visais atvejais 8 punkte (antrasis leidimas) buvo pasiūlyta pagrįsta gera įgyvendinimas Josh Bloch Effective Java . Tai geriausia ieškoti ten, nes autorius paaiškina, kodėl požiūris yra geras.

Trumpas variantas

  1. Sukurkite int result tipo int result ir priskirkite nulinę vertę.

  2. Kiekvienam f equals() metodas patikrinamas maišos kodas c :

    • Jei f laukas yra boolean : apskaičiuoti (f? 0: 1) ;
    • Jei f laukas yra byte , char , short arba int : skaičiavimas (int)f ;
    • Jei f long laukas: apskaičiuoti (int)(f ^ (f >>> 32)) ;
    • Jei f laukas yra float apskaičiuokite Float.floatToIntBits(f) ;
    • Jei f laukas yra double : apskaičiuokite „ Double.doubleToLongBits(f) ir apdorokite grąžinimo vertę kaip bet kokią ilgą vertę;
    • Jei f laukas yra objektas: naudokite hashCode() metodo rezultatą arba 0, jei f == null ;
    • Jei f laukas yra masyvas: kiekvienas laukas laikomas atskiru elementu ir apskaičiuokite maišos reikšmę rekursyviu būdu ir sujunkite žemiau aprašytas vertes.
  3. Sujunkite maišos vertę c su result :

     result = 37 * result + c 
  4. Grąžinimo result

Tai turėtų padėti teisingai paskirstyti maišos vertes daugumai naudojimo situacijų.

407
22 сент. Atsakymas pateikiamas dmeister 22 Sep. 2008-09-22 10:22 '08, 10:22, 2008-09-22 10:22

Jei esate patenkintas dmeister rekomenduojamu „Efektyvaus Java“ diegimu, galite naudoti bibliotekos skambutį vietoj savo:

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

Tam reikia arba „Guava“ ( com.google.common.base.Objects.hashCode ), arba standartinės bibliotekos „Java 7“ ( java.util.Objects.hash ), tačiau ji veikia taip pat.

121
05 авг. atsakymas suteiktas bacar 05 rug . 2013-08-05 22:49 '13, 10:49 PM 2013-08-05 22:49

Geriau naudoti „Eclipse“ teikiamą funkciją, kuri atlieka gana gerą darbą, ir jūs galite įdėti savo pastangas ir energiją į verslo logiką.

59
29 нояб. Atsakymą Warrior pateikė lapkričio 29 d. 2008-11-29 09:30 '08, 9:30, 2008-11-29 09:30

Nors tai susiję su „ Android dokumentacija („Wayback Machine“) ir mano „Github“ kodu , apskritai jis veiks „Java“. Mano atsakymas yra „ dmeister Answer“ plėtinys , kuriame yra tik daug lengviau skaityti ir suprasti kodą.

 @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

Paprastai, kai ignoruojate hashcode(...) , taip pat norite panaikinti hashcode(...) equals(...) . Taigi tiems, kurie bus arba jau įgyvendino, equals , čia yra gera nuoroda iš mano „Github“ ...

 @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)); } 
53
04 июля '15 в 14:45 2015-07-04 14:45 Atsakymą pateikė Christopher Rucinski liepos 14 d. 15, 14:45 2015-07-04 14:45

Pirmiausia įsitikinkite, kad teisingai įdiegta lygi. Iš IBM developerWorks straipsnio :

  • Simetrija: dviem nuorodoms a ir b, a.equals (b), jei ir tik jei b.equals (a)
  • Refleksyvumas: visoms tuščioms nuorodoms a.equals (a)
  • Tikslumas: jei a.equals (b) ir b.equals (c), tada a.equals (c)

Tada įsitikinkite, kad jų ryšys su hashCode atitinka kontaktą (iš to paties straipsnio):

  • Suderinamumas su hashCode (): du lygūs objektai turi turėti tą pačią reikšmę hashCode ()

Galiausiai, gera maišos funkcija turėtų siekti tobulos maišos funkcijos.

17
22 сент. Atsakymą pateikė Grey Panther Sep 22 2008-09-22 10:08 '08, 10:08 2008-09-22 10:08

apie.blogspot.com, jūs sakėte

Jei dviejų objektų atveju lygūs () yra teisingi, tada hashCode () turėtų grąžinti tą pačią vertę. Jei lygūs () grąžina false, hashCode () turi grąžinti skirtingas reikšmes.

Aš negaliu su jumis sutikti. Jei du objektai turi tą patį maišos kodą, tai nereiškia, kad jie yra lygūs.

Jei A yra lygus B, tada A.hashcode turi būti lygus B.hascode

bet

jei A.hashcode yra B.hascode, tai nereiškia, kad A turi būti lygus B

11
22 сент. atsakymas pateikiamas panzupa 22 sep . 2008-09-22 11:47 '08 at 11:47 2008-09-22 11:47

Jei naudojate užtemimą, galite generuoti equals() ir hashCode() naudodami:

Šaltinis → Sukurti hashCode () ir lygus ().

Naudodami šią funkciją, galite nuspręsti, kuriuos laukus norite naudoti, kad apskaičiuotumėte lygybės ir maišos kodą, o „Eclipse“ generuoja atitinkamus metodus.

7
22 сент. Johannes K. Lehnert atsakymas rugsėjo 22 d 2008-09-22 15:50 '08, 15:50 pm 2008-09-22 15:50

Paprasta pastaba, skirta papildyti kitą išsamesnį atsakymą (pagal kodą):

Jei manau, kad klausimas, kaip-do-i-create-a-hash-table-in-java ir ypač įrašas jGuru DUK , manau, kad kai kurie kiti kriterijai, pagal kuriuos galite vertinti maišos kodą, yra tokie:

  • sinchronizavimas (ar algo palaiko lygiagrečią prieigą, ar ne)?
  • persiuntimo iteracija (ar algoritmas aptinka kolekciją, kuri keičiasi iteracijos metu).
  • null (ar maišos kodas palaiko nulį)
4
22 сент. Atsakymą pateikė VonC 22 sep. 2008-09-22 10:08 '08, 10:08 2008-09-22 10:08

Jei teisingai suprantu jūsų klausimą, turite savo kolekcijos klasę (ty naują klasę, kuri išeina iš kolekcijos sąsajos) ir norite įgyvendinti hashCode () metodą.

Jei jūsų kolekcijos klasė praplečia „AbstractList“, jūs neturite nerimauti, lygių () ir hashCode () įgyvendinimas jau egzistuoja, kuris veikia kartojant visus objektus ir kartu pridedant jų 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; } 

Dabar, jei norite geriausiai apskaičiuoti tam tikros klasės maišos kodą, paprastai naudoju ^ (bitų išskirtinį arba) operatorių, kad apdorotumėte visus laukus, kuriuos naudoju lygių metodu:

 public int hashCode(){ return intMember ^ (stringField != null ? stringField.hashCode() : 0); } 
4
22 сент. Mario Ortegón atsakymas, rugsėjo 22 d 2008-09-22 10:16 '08 10:16 am. 2008-09-22 10:16

Naudokite „Apache Commons EqualsBuilder“ ir „ HashCodeBuilder“ atspindžių metodus.

2
22 сент. Atsakymas, kurį pateikė Vihung Sep 22 2008-09-22 13:16 '08 13:16 pm 2008-09-22 13:16

Kadangi jūs specialiai paprašėte kolekcijų, norėčiau pridėti aspektą, kuris dar nebuvo paminėtas kituose atsakymuose: „HashMap“ nesitiki, kad jų raktai pakeis jų maišos kodą po to, kai jie bus įtraukti į kolekciją. Sunaikinkite visą tikslą ...

2
22 сент. Atsakymas pateikiamas Olaf Kock . 2008-09-22 10:15 '08 10:15 am. 2008-09-22 10:15

@ about8: Yra gana rimta klaida.

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

tas pats maišos kodas

tikriausiai norite kažką panašaus

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

(Ar jūs galite gauti hashCode tiesiogiai iš int į java šiomis dienomis? Manau, kad tai šiek tiek autoloading. Jei taip, praleiskite toString, tai negraži.)

2
22 сент. Atsakymas pateikiamas SquareCog 22 rugsėjis 2008-09-22 10:06 '08, 10:06 am. 2008-09-22 10:06

Norėčiau naudoti naudingumo metodus iš „Google“ kolekcijų „Lib“ rinkinių „Objektų“ klasėje, kuri padeda man išlaikyti savo kodą švariu. Labai dažnai equals ir hashcode metodai yra sukurti iš IDE šablono, todėl jų skaitymas nėra švarus.

1
22 сент. atsakymas pateikiamas panzupa 22 sep . 2008-09-22 11:51 '08 at 11:51 am 2008-09-22 11:51

Čia pateikiamas dar vienas JDK 1.7+ metodo demonstravimas su superklasės paskyra. Manau, kad tai gana patogu atsižvelgiant į hashCode () klasę, gryną JDK priklausomybę ir papildomą rankinį darbą. Atkreipkite dėmesį, kad Objects.hash() turi nulinę toleranciją.

Neįtraukiu equals() įgyvendinimo, bet iš tikrųjų jums tai reikės.

 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()); } } 
1
30 дек. Atsakymas pateikiamas Roman Nikitchenko 30 d. 2016-12-30 16:18 '17 at 16:18 2016-12-30 16:18

Aš naudoju mažą Arrays.deepHashCode(...) aplink Arrays.deepHashCode(...) , nes jis teisingai apdoroja masyvus, pateiktus kaip parametrai

 public static int hash(final Object... objects) { return Arrays.deepHashCode(objects); } 
1
21 дек. „ Starikoff“ atsakymas gruodžio 21 d 2015-12-21 15:08 '15, 15:08 2015-12-21 15:08

Standarto įgyvendinimas yra silpnas ir jo naudojimas sukelia nereikalingus konfliktus. Įsivaizduokite

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

Dabar

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

ir taip pat

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

turėti tą pačią hashCode , ty 31*(a+b) + c , nes daugiklis, naudojamas List.hashCode yra pakartotinai naudojamas čia. Akivaizdu, kad susidūrimai yra neišvengiami, tačiau nereikalingų susidūrimų kūrimas yra tiesiog ... nereikalingas.

Nėra nieko iš esmės protingo naudojant 31 . Daugiklis turi būti nelyginis, kad būtų išvengta informacijos praradimo (bet koks netgi daugiklis netenka bent reikšmingiausio bitų, keturių praradimų du kartus ir pan.). Galima naudoti bet kokį nelyginį daugiklį. Maži veiksniai gali paskatinti greitesnius skaičiavimus (JIT gali naudoti pamainas ir papildymus), tačiau, atsižvelgiant į tai, kad dauginimas turi vos trijų ciklų šiuolaikiniame „Intel“ / „AMD“, tai vargu ar svarbu. Maži veiksniai taip pat lemia didesnį susidūrimą su mažomis sąnaudomis, kurios kartais gali būti problema.

Pirminio skaičiaus naudojimas yra beprasmiškas, nes pagrindiniai numeriai žiede Z / (2 ** 32) neturi prasmės.

Todėl norėčiau rekomenduoti naudoti atsitiktinai pasirinktą didelį nelyginį skaičių (nedvejodami rinkitės pirminį numerį). Kadangi i86 / amd64 procesoriai gali naudoti trumpesnius nurodymus, kaip pakeisti operandus į vieną pasirašytą baitą, daugiklis, kaip 109, yra šiek tiek greitas. Jei norite sumažinti susidūrimus, atlikite kažką panašaus į 0x58a54cf5.

Skirtingų daugiklių naudojimas įvairiose vietose yra naudingas, bet tikriausiai nepakanka, kad pateisintų papildomą darbą.

1
10 дек. Atsakymas pateikiamas maaartinus 10 d. 2017-12-10 21:02 '17 21:02 2017-12-10 21:02

bet koks maišymo metodas, kuris tolygiai paskirsto maišos vertę galimame intervale, yra geras įgyvendinimas. Cm. Veiksmingas Java ( http://books.google.com.au/books?id=ZZOiqZQIbRMC> ), yra keletas gerų patarimų įgyvendinti hashcode (9 punktas, manau ...).

22 сент. atsakymas pateikiamas Chii 22 rugsėjis 2008-09-22 10:20 '08, 10:20, 2008-09-22 10:20

Sujungiant maišos reikšmes, paprastai naudojasi sujungimo metodu, kuris naudojamas C ++ C ++ bibliotekoje:

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

Tai gana geras darbas, užtikrinant tolygų paskirstymą. Jei norite aptarti, kaip ši formulė veikia, žr. „StackOverflow“ pranešimą: „ Magic number in boost“: „hash_combine“

Gera diskusija apie įvairias maišos funkcijas: http://burtleburtle.net/bob/hash/doobs.html

0
03 окт. atsakymas, kurį pateikė Edward Loper 03 spalis 2012-10-03 18:18 '12, 18:18, 2012-10-03 18:18

Paprasta klasė dažnai yra lengviau įdiegti hashCode (), remiantis klasių laukais, kuriuos tikrina lygių () įgyvendinimas.

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

Svarbiausia yra nuosekliai išlaikyti hashCode () ir lygiaverčius (): jei dviejų objektų atveju lygūs () yra teisingi, hashCode () turi grąžinti tą pačią vertę. Jei lygūs () grąžina false, hashCode () turi grąžinti skirtingas reikšmes.

-1
22 сент. Chris Carruthers atsakymas rugsėjo 22 d 2008-09-22 10:00 '08 10:00 val. 2008-09-22 10:00

Kiti klausimai apie žymenų arba Užduoti klausimą