Java >> Java opplæring >  >> Tag >> boolean

hashkodeimplementering på boolske felt

boolean

Du har et par alternativer:

Alternativ 1:Bitflagging

Den beste måten å garanti på at det kan aldri være kollisjoner mellom boolske hashes er å bruke en teknikk som ligner på den som brukes i bitflagging, der du lar hver boolsk oppta sin egen bit. For eksempel:

// `byte` can be replaced with `short`, `int`, or `long` to fit all of your variables.
byte = 0;
if(bool1) booleans += 1;  // 0001
if(bool2) booleans += 2;  // 0010
if(bool3) booleans += 4;  // 0100
if(bool4) booleans += 8;  // 1000
...

Imidlertid blir denne tilnærmingen raskt ineffektiv med et stort antall booleaner og er svært avhengig av størrelsen på målmatrisen. For eksempel, hvis du har en målmatrise med størrelse 16, er det bare de 4 første som har en effekt på hash-verdien (siden den maksimale indeksen er 1111 ).

De to løsningene på dette er å enten øke størrelsen på målarrayen din (som kanskje ikke er under din kontroll), eller sørge for at rekkefølgen på booleanene dine går fra mest til minst variadisk. Ingen av disse er optimale, og derfor er denne metoden rask og enkel, men ikke særlig effektiv i praksis.

Alternativ 2:Baseendrende hash

Designet som Pham Trung viser i svaret sitt, utvider alternativ 1 som en enklere måte å imøtekomme flere felt. Som Adrian Shum kommenterte, gir dette svaret en oversikt over en "generell hashing-algoritme" som er designet for å være effektiv uavhengig av hva du prøver å hash.

Den grunnleggende ideen er å multiplisere en forenklet hash-verdi for hver type med et eller annet vilkårlig stort primtall for å sikre at hver hash er unik (selv om beviset for dette unngår meg). For eksempel:

int result = 0;
result = 31*result + bool1 ? 1 : 0;
result = 31*result + bool2 ? 1 : 0;
...

For en enda mer sparsom hashdistribusjon kan du kombinere dette med Boolean.hashCode , som de andre svarene viser:

int result = 0;
result += 31*result + bool1.hashCode();
result += 31*result + bool2.hashCode();
...

Det som er bra med denne løsningen er at den kan brukes på andre typer, som du allerede har i eksempelkoden:

...
result = 31*result + i;
result = 31*result + (a != null ? a.hashCode() : 0);
result = 31*result + my_complex_object.hashCode();

Merk :I disse eksemplene, 31 er bare en vilkårlig primtall. Du kunne enkelt ha brukt 37 , 113 eller 23456789 . Det er imidlertid avveininger for å bruke større multiplikander, nemlig at hasjen din raskere vil overstige Integer.MAX_VALUE og ugyldiggjøre hashen.


Når du har to eller enda flere booleaner, er hashkodealgoritmen allerede tatt hånd om det.

Se litt nærmere:

// Very simple example
public int hashCode() {
    int result = 31;

    for(boolean val : booleanList) {
        // This is the important part:
        result = 31 * result + Boolean.hashCode(val);
    }

    return result;
}

Merknad hoveddelen av for-løkken, i dette tilfellet, behandler vi hver boolsk forskjell, siden vi alltid multipliserer resultatet med 31 (eller et hvilket som helst godt primtall) før vi legger det til i resultatet.

Hvis vi visualiserer hele hashkoden som et tall på base 31 , slik at vi kan forstå at posisjonen og verdien av hver boolean blir tatt med i det endelige resultatet. Hver boolsk kan behandles som et siffer i hashkoden, så for store og små bokstaver (sann, usann) og store og små bokstaver (false, sann), vil de ha to forskjellige hashkoder.


Java Tag