Samengestelde objecten hashen

EDIT: This question is not about bitwise operators and can't be answered with Why are XOR often used in java hashCode() but another bitwise operators are used rarely?

Ik heb verschillende benaderingen voor hash-berekening van object gezien:

class A {
  public B b;
  public C c;

  @Override
  public boolean equals();
  @Override
  public int hashCode() {
   return c.hashCode() ^ b.hashCode(); //XOR
   return c.hashCode() + prime * b.hashCode();//SUM
   return Objects.hash(b,c);//LIB
  }
}

Het lijkt erop dat de LIB-methode SUM gebruikt, maar waarom is het beter dan XOR?

Ook al is het voorbeeld in Java, deze vraag gaat meer over wiskunde en waarschijnlijkheden.

11
toegevoegd de auteur assylias, de bron
toegevoegd de auteur assylias, de bron
Josh Bloch bespreekt een goede implementatie van de hashcode in Effectieve Java .
toegevoegd de auteur Edward Thomson, de bron
Josh Bloch bespreekt een goede implementatie van de hashcode in Effectieve Java .
toegevoegd de auteur Edward Thomson, de bron
Normaal gesproken gebruikt u gewoon de lib-functies. Tenzij u een kansverdelingsanalyse uitvoert om te bepalen hoe uw datapunten het best worden verdeeld. Vindt u veel botsingen met uw dataset?
toegevoegd de auteur CodeMonkeyForHire, de bron
Normaal gesproken gebruikt u gewoon de lib-functies. Tenzij u een kansverdelingsanalyse uitvoert om te bepalen hoe uw datapunten het best worden verdeeld. Vindt u veel botsingen met uw dataset?
toegevoegd de auteur CodeMonkeyForHire, de bron

12 antwoord

De SUM zorgt ervoor dat je alle bits van de hashcode gebruikt om je hashing te verspreiden (hier de 32 bits van een int), en maakt daar geen aanname van over de implementatie van sub hashcode ().

De XOR heeft alleen dezelfde eigenschap als de hashcode van B en C het heeft, anders gebruikt het alleen het minimum van het aantal "nuttige" bits in B- en C-hashcode, wat zou kunnen leiden tot een slechtere verdeling en vaker botsing . Het is heel gemakkelijk om het probleem te zien als B en C hele getallen zijn die erg klein zijn, je zult alleen de eerste paar bits gebruiken (zoals int.hashcode() is de identiteitsfunctie).

5
toegevoegd

De SUM zorgt ervoor dat je alle bits van de hashcode gebruikt om je hashing te verspreiden (hier de 32 bits van een int), en maakt daar geen aanname van over de implementatie van sub hashcode ().

De XOR heeft alleen dezelfde eigenschap als de hashcode van B en C het heeft, anders gebruikt het alleen het minimum van het aantal "nuttige" bits in B- en C-hashcode, wat zou kunnen leiden tot een slechtere verdeling en vaker botsing . Het is heel gemakkelijk om het probleem te zien als B en C hele getallen zijn die erg klein zijn, je zult alleen de eerste paar bits gebruiken (zoals int.hashcode() is de identiteitsfunctie).

5
toegevoegd

De SUM zorgt ervoor dat je alle bits van de hashcode gebruikt om je hashing te verspreiden (hier de 32 bits van een int), en maakt daar geen aanname van over de implementatie van sub hashcode ().

De XOR heeft alleen dezelfde eigenschap als de hashcode van B en C het heeft, anders gebruikt het alleen het minimum van het aantal "nuttige" bits in B- en C-hashcode, wat zou kunnen leiden tot een slechtere verdeling en vaker botsing . Het is heel gemakkelijk om het probleem te zien als B en C hele getallen zijn die erg klein zijn, je zult alleen de eerste paar bits gebruiken (zoals int.hashcode() is de identiteitsfunctie).

5
toegevoegd

De SUM zorgt ervoor dat je alle bits van de hashcode gebruikt om je hashing te verspreiden (hier de 32 bits van een int), en maakt daar geen aanname van over de implementatie van sub hashcode ().

De XOR heeft alleen dezelfde eigenschap als de hashcode van B en C het heeft, anders gebruikt het alleen het minimum van het aantal "nuttige" bits in B- en C-hashcode, wat zou kunnen leiden tot een slechtere verdeling en vaker botsing . Het is heel gemakkelijk om het probleem te zien als B en C hele getallen zijn die erg klein zijn, je zult alleen de eerste paar bits gebruiken (zoals int.hashcode() is de identiteitsfunctie).

5
toegevoegd

Het antwoord is (zoals altijd): " Het hangt ervan af. " Het hangt van je klas af.

Bijvoorbeeld als u overweegt

class X {
    T a, b;
    X(T _a, _b) { a = _a; b = _b }
}

je zou geen symmetrische operator gebruiken zoals + , * , of ^ (stel je voor T is int en je hebt hashing X (1,2) en X (2,1) . Uiteraard moet de hash-code anders zijn. drie "oplossingen" (xor-hash-waarden) zouden slecht zijn).

Als T een complex type is, zou de derde oplossing ( Objects.hash() ) mogelijk ook slecht zijn, omdat alleen de referenties worden beschouwd (gelijke objecten kunnen verschillende hash retourneren codes).

1
toegevoegd
Meer in het algemeen zijn alleen objecten die standaard hashCode-implementatie gebruiken onderworpen aan identiteitsversleuteling. Dergelijke objecten vallen buiten het bereik van deze vraag.
toegevoegd de auteur Basilevs, de bron
1. misbruik van term "complex type" (dat geen formele definitie heeft in CS en kan verwijzen, bijvoorbeeld naar een complex getal) 2. impliciete overtreding van hashCode() + gelijk() contract Waar ontbreekt mijn begrip?
toegevoegd de auteur Basilevs, de bron
Wat is een complex type? Waarom zou een gelijk object verschillende hash-code produceren?
toegevoegd de auteur Basilevs, de bron
Zou "Composite-type" hier beter werken?
toegevoegd de auteur Basilevs, de bron
3. Objects.hash() heeft alleen hashesreferenties voor arrays, aangezien er geen arrays in uw voorbeeld zijn, is dit argument niet van toepassing.
toegevoegd de auteur Basilevs, de bron
Bovenal, " Als T een complex type is, zou de derde oplossing (Objects.hash ()) mogelijk ook slecht zijn, omdat alleen de referenties worden beschouwd (gelijke objecten kunnen verschillende retourneren hash-codes). "zegt het al: Gelijke objecten kunnen verschillende verwijzingen hebben, die Objects.hash (...) beschouwen. Dus bij het passeren van gelijke objecten met verschillende referenties, kunnen verschillende hashcodes het gevolg zijn. Dat is wat ik schreef en ik denk dat het correct is.
toegevoegd de auteur U. Windl, de bron
Voor mij, vooral als ik het over een inconsistente taal als Java heb, is dit net als het splitsen van haren: of het nu Atomic of intrinsic_ of primitive is, het is allemaal een onderdeel, terwijl complex , composiet is de andere. In Eiffel zijn er alleen uitgebreide typen en referentie typen. En er zijn zeer duidelijke contracten met betrekking tot gelijkheid en hash-code, die afwezig zijn op Java (en ik geloof dat dat de reden is voor de meeste rotzooi in Java).
toegevoegd de auteur U. Windl, de bron
@Basilevs: Een complex type is duidelijk een niet-primitief type, d.w.z. een echt referentietype . Ik weet niet waarom je dit tegenspreekt als je niet begrijpt wat ik heb geschreven.
toegevoegd de auteur U. Windl, de bron

Het antwoord is (zoals altijd): " Het hangt ervan af. " Het hangt van je klas af.

Bijvoorbeeld als u overweegt

class X {
    T a, b;
    X(T _a, _b) { a = _a; b = _b }
}

je zou geen symmetrische operator gebruiken zoals + , * , of ^ (stel je voor T is int en je hebt hashing X (1,2) en X (2,1) . Uiteraard moet de hash-code anders zijn. drie "oplossingen" (xor-hash-waarden) zouden slecht zijn).

Als T een complex type is, zou de derde oplossing ( Objects.hash() ) mogelijk ook slecht zijn, omdat alleen de referenties worden beschouwd (gelijke objecten kunnen verschillende hash retourneren codes).

1
toegevoegd
Wat is een complex type? Waarom zou een gelijk object verschillende hash-code produceren?
toegevoegd de auteur Basilevs, de bron
3. Objects.hash() heeft alleen hashesreferenties voor arrays, aangezien er geen arrays in uw voorbeeld zijn, is dit argument niet van toepassing.
toegevoegd de auteur Basilevs, de bron
1. misbruik van term "complex type" (dat geen formele definitie heeft in CS en kan verwijzen, bijvoorbeeld naar een complex getal) 2. impliciete overtreding van hashCode() + gelijk() contract Waar ontbreekt mijn begrip?
toegevoegd de auteur Basilevs, de bron
Zou "Composite-type" hier beter werken?
toegevoegd de auteur Basilevs, de bron
Meer in het algemeen zijn alleen objecten die standaard hashCode-implementatie gebruiken onderworpen aan identiteitsversleuteling. Dergelijke objecten vallen buiten het bereik van deze vraag.
toegevoegd de auteur Basilevs, de bron
Bovenal, " Als T een complex type is, zou de derde oplossing (Objects.hash ()) mogelijk ook slecht zijn, omdat alleen de referenties worden beschouwd (gelijke objecten kunnen verschillende retourneren hash-codes). "zegt het al: Gelijke objecten kunnen verschillende verwijzingen hebben, die Objects.hash (...) beschouwen. Dus bij het passeren van gelijke objecten met verschillende referenties, kunnen verschillende hashcodes het gevolg zijn. Dat is wat ik schreef en ik denk dat het correct is.
toegevoegd de auteur U. Windl, de bron
Voor mij, vooral als ik het over een inconsistente taal als Java heb, is dit net als het splitsen van haren: of het nu Atomic of intrinsic_ of primitive is, het is allemaal een onderdeel, terwijl complex , composiet is de andere. In Eiffel zijn er alleen uitgebreide typen en referentie typen. En er zijn zeer duidelijke contracten met betrekking tot gelijkheid en hash-code, die afwezig zijn op Java (en ik geloof dat dat de reden is voor de meeste rotzooi in Java).
toegevoegd de auteur U. Windl, de bron
@Basilevs: Een complex type is duidelijk een niet-primitief type, d.w.z. een echt referentietype . Ik weet niet waarom je dit tegenspreekt als je niet begrijpt wat ik heb geschreven.
toegevoegd de auteur U. Windl, de bron

Het antwoord is (zoals altijd): " Het hangt ervan af. " Het hangt van je klas af.

Bijvoorbeeld als u overweegt

class X {
    T a, b;
    X(T _a, _b) { a = _a; b = _b }
}

je zou geen symmetrische operator gebruiken zoals + , * , of ^ (stel je voor T is int en je hebt hashing X (1,2) en X (2,1) . Uiteraard moet de hash-code anders zijn. drie "oplossingen" (xor-hash-waarden) zouden slecht zijn).

Als T een complex type is, zou de derde oplossing ( Objects.hash() ) mogelijk ook slecht zijn, omdat alleen de referenties worden beschouwd (gelijke objecten kunnen verschillende hash retourneren codes).

1
toegevoegd
Wat is een complex type? Waarom zou een gelijk object verschillende hash-code produceren?
toegevoegd de auteur Basilevs, de bron
Meer in het algemeen zijn alleen objecten die standaard hashCode-implementatie gebruiken onderworpen aan identiteitsversleuteling. Dergelijke objecten vallen buiten het bereik van deze vraag.
toegevoegd de auteur Basilevs, de bron
1. misbruik van term "complex type" (dat geen formele definitie heeft in CS en kan verwijzen, bijvoorbeeld naar een complex getal) 2. impliciete overtreding van hashCode() + gelijk() contract Waar ontbreekt mijn begrip?
toegevoegd de auteur Basilevs, de bron
Zou "Composite-type" hier beter werken?
toegevoegd de auteur Basilevs, de bron
3. Objects.hash() heeft alleen hashesreferenties voor arrays, aangezien er geen arrays in uw voorbeeld zijn, is dit argument niet van toepassing.
toegevoegd de auteur Basilevs, de bron
Voor mij, vooral als ik het over een inconsistente taal als Java heb, is dit net als het splitsen van haren: of het nu Atomic of intrinsic_ of primitive is, het is allemaal een onderdeel, terwijl complex , composiet is de andere. In Eiffel zijn er alleen uitgebreide typen en referentie typen. En er zijn zeer duidelijke contracten met betrekking tot gelijkheid en hash-code, die afwezig zijn op Java (en ik geloof dat dat de reden is voor de meeste rotzooi in Java).
toegevoegd de auteur U. Windl, de bron
Bovenal, " Als T een complex type is, zou de derde oplossing (Objects.hash ()) mogelijk ook slecht zijn, omdat alleen de referenties worden beschouwd (gelijke objecten kunnen verschillende retourneren hash-codes). "zegt het al: Gelijke objecten kunnen verschillende verwijzingen hebben, die Objects.hash (...) beschouwen. Dus bij het passeren van gelijke objecten met verschillende referenties, kunnen verschillende hashcodes het gevolg zijn. Dat is wat ik schreef en ik denk dat het correct is.
toegevoegd de auteur U. Windl, de bron
@Basilevs: Een complex type is duidelijk een niet-primitief type, d.w.z. een echt referentietype . Ik weet niet waarom je dit tegenspreekt als je niet begrijpt wat ik heb geschreven.
toegevoegd de auteur U. Windl, de bron

Het antwoord is (zoals altijd): " Het hangt ervan af. " Het hangt van je klas af.

Bijvoorbeeld als u overweegt

class X {
    T a, b;
    X(T _a, _b) { a = _a; b = _b }
}

je zou geen symmetrische operator gebruiken zoals + , * , of ^ (stel je voor T is int en je hebt hashing X (1,2) en X (2,1) . Uiteraard moet de hash-code anders zijn. drie "oplossingen" (xor-hash-waarden) zouden slecht zijn).

Als T een complex type is, zou de derde oplossing ( Objects.hash() ) mogelijk ook slecht zijn, omdat alleen de referenties worden beschouwd (gelijke objecten kunnen verschillende hash retourneren codes).

1
toegevoegd
1. misbruik van term "complex type" (dat geen formele definitie heeft in CS en kan verwijzen, bijvoorbeeld naar een complex getal) 2. impliciete overtreding van hashCode() + gelijk() contract Waar ontbreekt mijn begrip?
toegevoegd de auteur Basilevs, de bron
Wat is een complex type? Waarom zou een gelijk object verschillende hash-code produceren?
toegevoegd de auteur Basilevs, de bron
Meer in het algemeen zijn alleen objecten die standaard hashCode-implementatie gebruiken onderworpen aan identiteitsversleuteling. Dergelijke objecten vallen buiten het bereik van deze vraag.
toegevoegd de auteur Basilevs, de bron
Zou "Composite-type" hier beter werken?
toegevoegd de auteur Basilevs, de bron
3. Objects.hash() heeft alleen hashesreferenties voor arrays, aangezien er geen arrays in uw voorbeeld zijn, is dit argument niet van toepassing.
toegevoegd de auteur Basilevs, de bron
Bovenal, " Als T een complex type is, zou de derde oplossing (Objects.hash ()) mogelijk ook slecht zijn, omdat alleen de referenties worden beschouwd (gelijke objecten kunnen verschillende retourneren hash-codes). "zegt het al: Gelijke objecten kunnen verschillende verwijzingen hebben, die Objects.hash (...) beschouwen. Dus bij het passeren van gelijke objecten met verschillende referenties, kunnen verschillende hashcodes het gevolg zijn. Dat is wat ik schreef en ik denk dat het correct is.
toegevoegd de auteur U. Windl, de bron
Voor mij, vooral als ik het over een inconsistente taal als Java heb, is dit net als het splitsen van haren: of het nu Atomic of intrinsic_ of primitive is, het is allemaal een onderdeel, terwijl complex , composiet is de andere. In Eiffel zijn er alleen uitgebreide typen en referentie typen. En er zijn zeer duidelijke contracten met betrekking tot gelijkheid en hash-code, die afwezig zijn op Java (en ik geloof dat dat de reden is voor de meeste rotzooi in Java).
toegevoegd de auteur U. Windl, de bron
@Basilevs: Een complex type is duidelijk een niet-primitief type, d.w.z. een echt referentietype . Ik weet niet waarom je dit tegenspreekt als je niet begrijpt wat ik heb geschreven.
toegevoegd de auteur U. Windl, de bron

Dit komt omdat sum zorgt voor een betere distributie dan xof .

Als bijvoorbeeld int a en b waarden hebben tussen 0 en 7 ( 000 en 111 binair), dan zal het resultaat van xof van deze twee argumenten altijd tussen 0 en 7 liggen (terwijl xof slechts 3 bits zal veranderen). Wanneer u nu een vermenigvuldiging en een som uitvoert, krijgt u een veel betere verdeling omdat de waarden niet binnen het 0 en 7 bereik vallen.

0
toegevoegd
Trouwens, is int hashCode zijn waarde? Het zou erg slecht zijn voor niet-uniforme distributies voor de meeste use-cases, wat slecht is voor HashMap en andere hash-gebaseerde algoritmen.
toegevoegd de auteur Basilevs, de bron
Afhankelijk van de uitvoering ^^ maar het antwoord is, helaas, vaak wel.
toegevoegd de auteur C4stor, de bron
@Basilevs Ja, ik bedoelde breder, beter, het antwoord opgelost, bedankt.
toegevoegd de auteur Adam Siemion, de bron

Dit komt omdat sum zorgt voor een betere distributie dan xof .

Als bijvoorbeeld int a en b waarden hebben tussen 0 en 7 ( 000 en 111 binair), dan zal het resultaat van xof van deze twee argumenten altijd tussen 0 en 7 liggen (terwijl xof slechts 3 bits zal veranderen). Wanneer u nu een vermenigvuldiging en een som uitvoert, krijgt u een veel betere verdeling omdat de waarden niet binnen het 0 en 7 bereik vallen.

0
toegevoegd
Trouwens, is int hashCode zijn waarde? Het zou erg slecht zijn voor niet-uniforme distributies voor de meeste use-cases, wat slecht is voor HashMap en andere hash-gebaseerde algoritmen.
toegevoegd de auteur Basilevs, de bron
Afhankelijk van de uitvoering ^^ maar het antwoord is, helaas, vaak wel.
toegevoegd de auteur C4stor, de bron
@Basilevs Ja, ik bedoelde breder, beter, het antwoord opgelost, bedankt.
toegevoegd de auteur Adam Siemion, de bron

Dit komt omdat sum zorgt voor een betere distributie dan xof .

Als bijvoorbeeld int a en b waarden hebben tussen 0 en 7 ( 000 en 111 binair), dan zal het resultaat van xof van deze twee argumenten altijd tussen 0 en 7 liggen (terwijl xof slechts 3 bits zal veranderen). Wanneer u nu een vermenigvuldiging en een som uitvoert, krijgt u een veel betere verdeling omdat de waarden niet binnen het 0 en 7 bereik vallen.

0
toegevoegd
Trouwens, is int hashCode zijn waarde? Het zou erg slecht zijn voor niet-uniforme distributies voor de meeste use-cases, wat slecht is voor HashMap en andere hash-gebaseerde algoritmen.
toegevoegd de auteur Basilevs, de bron
Afhankelijk van de uitvoering ^^ maar het antwoord is, helaas, vaak wel.
toegevoegd de auteur C4stor, de bron
@Basilevs Ja, ik bedoelde breder, beter, het antwoord opgelost, bedankt.
toegevoegd de auteur Adam Siemion, de bron

Dit komt omdat sum zorgt voor een betere distributie dan xof .

Als bijvoorbeeld int a en b waarden hebben tussen 0 en 7 ( 000 en 111 binair), dan zal het resultaat van xof van deze twee argumenten altijd tussen 0 en 7 liggen (terwijl xof slechts 3 bits zal veranderen). Wanneer u nu een vermenigvuldiging en een som uitvoert, krijgt u een veel betere verdeling omdat de waarden niet binnen het 0 en 7 bereik vallen.

0
toegevoegd
Trouwens, is int hashCode zijn waarde? Het zou erg slecht zijn voor niet-uniforme distributies voor de meeste use-cases, wat slecht is voor HashMap en andere hash-gebaseerde algoritmen.
toegevoegd de auteur Basilevs, de bron
Afhankelijk van de uitvoering ^^ maar het antwoord is, helaas, vaak wel.
toegevoegd de auteur C4stor, de bron
@Basilevs Ja, ik bedoelde breder, beter, het antwoord opgelost, bedankt.
toegevoegd de auteur Adam Siemion, de bron